Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Procedia Computer Science

New variant for Learning with Errors Problem

Xuyang Wang, Aiqun Hu, Hao Fang

Published Jan 1, 2018• 3 citations
Publisher

Abstract

The Learning with Errors (LWE) problem is a special average-case lattice problem, which has proved to be as hard as worst-case lattice problems. By this property, it has become the cornerstones for a series of cryptographic applications under the security assumption of worst-case lattice problems. However, the efficiency of these applications are not high. Therefore, how to improve the efficiency of cryptographic applications based on LWE is an urgent problem to be solved. In this paper, a new variant of LWE is proposed. By using trapdoor composed by lattice-based matrix and its dual orthogonal matrix, we construct a more efficient public key encryption (PKE) scheme based on the variant. Furthermore, by the hardness of the variant problem, we prove the new PKE scheme is chosen plaintext attack (CPA) secure. At last, we analyze the homomorphism property of the new PKE scheme.

DOI
10.1016/j.procs.2018.04.243

Related papers

Securely Instantiating Cryptographic Schemes Based on the Learning with Errors Assumption

Florian Göpfert

Since its proposal by Regev in 2005, the Learning With Errors (LWE) problem was used as the underlying problem for a great variety of schemes. Its applications are many-fold, reaching from basic and highly practical primitives like key exchange, public-key encryption, and signature schemes to very advanced solutions like fully homomorphic encryption, group signatures, and identity based encryption. One of the underlying reasons for this fertility is the flexibility with that LWE can be instantiated. Unfortunately, this comes at a cost: It makes selecting parameters for cryptographic applications complicated. When selecting parameters for a new LWE-based primitive, a researcher has to take the influence of several parameters on the efficiency of the scheme and the runtime of a variety of attacks into consideration. In fact, the missing trust in the concrete hardness of LWE is one of the main problems to overcome to bring LWE-based schemes to practice. This thesis aims at closing the gap between the theoretical knowledge of the hardness of LWE, and the concrete problem of selecting parameters for an LWE-based scheme. To this end, we analyze the existing methods to estimate the hardness of LWE, and introduce new estimation techniques where necessary. Afterwards, we show how to transfer this knowledge into instantiations that are at the same time secure and efficient. We show this process on three examples: - A highly optimized public-key encryption scheme for embedded devices that is based on a variant of Ring-LWE. - A practical signature scheme that served as the foundation of one of the best lattice-based signature schemes based on standard lattices. - An advanced public-key encryption scheme that enjoys the unique property of natural double hardness based on LWE instances similar to those used for fully homomorphic encryption.

•Jan 1, 2016•2 citations

Public Key Encryption from MP-LWE for the Middle-Product One

Weixian Lai, Hao Lei, Lichun Li +1 more

Middle-Product Learning with Errors (MP-LWE) is a variant of the LWE problem introduced by Rosca et al., which achieves a trade-off between security and efficiency for lattice-based public-key encryption. In a nutshell, the public-key encryption based on MP-LWE outperform LWE-based schemes in efficiency while mitigating risks inherent in constructions from Polynomial/Ring LWE. A challenging problem is how to construct a PKE scheme whose security is based on some difficult problem that is the same hard as LWE, but it is of higher efficiency than existing LWE-based PKE schemes. In this paper, we solve this problem. First, we show MP-LWE for the middle-product one is of the same hard as LWE. Second, we propose a PKE scheme from MP-LWE for the middle-product one with shorter public key length than PKE scheme based on LWE.

•Jul 1, 2026•0 citations

Efficient Chosen-Ciphtertext Secure Public Key Encryption Scheme From Lattice Assumption

Fenghe Wang, Chunxiao Wang, Yupu Hu

Abstract: Using the Bonsai trees primitive and Gentry’s CPA-secure (chosen-plaintext attack) public-key encryption (PKE) scheme, we propose an efficient chosen-ciphtertext secure PKE scheme over lattice. If the decision variant of the learning with errors (LWE) problem is hard and the one-time signature used in this scheme is strong unforgeable, the proposed PKE scheme is indistinguishable against the adaptive chosen-ciphtertext attack (IND-CCA2). One of the characters for this scheme is that, before any encryption operation, the encryption algorithm uses a new choice rule to fix the public parameter matrixes used in the encryption operation. With the help of this new choice rule, we can achieve the chosen-ciphtertext security with much shorter the public key size in contrast to the lattice-based encryption scheme proposed in STOC’09 by Peikert. Moreover, as a CCA-secure PKE scheme, the message-tociphtertext expanse factor of this scheme which is controlled efficiently is nearly closed to the message-to-ciphtertext expanse factor of Gentry’s scheme which is CPA secure. Due to the quantum intractability of the LWE problem on which the scheme is based, the proposed PKE scheme is secure even in quantum-era.

Applied Mathematics & Information Sciences•Oct 9, 2013•0 citations

Adaptive Secure Homomorphic Encryption Scheme

Ma Boyu, Chen Hong

Due to the threat of future quantum computers, it is necessary to develop cryptographic schemes that are resistant to quantum attacks. Lattice based cryptographic schemes have resistance to quantum attacks and security under worst-case assumptions that are difficult to solve. To solve the problems of large size of public and private keys, low encryption efficiency, and large noise growth in identity based encryption schemes, an adaptive secure identity based all homomorphic encryption scheme based on Learning with Errors (LWE) is constructed. This scheme uses {0,1} matrices to store plaintext, significantly improving encryption efficiency compared to single bit encryption schemes. It uses key conversion technology to achieve homomorphic operations and modulus conversion technology to reduce noise. It also converts IDs into bit sequences to construct an encryption scheme for adaptive security. Compared to selective security that only provides security guarantees for specific types of attacks, adaptive security is suitable for general scenarios, providing higher security guarantees and being able to cope with more challenging attack situations. It has been proven through the LWE problem that the security of our proposed scheme satisfies IND-ID-CPA. Finally, the experimental results indicate that this scheme introduces less noise, and has higher encryption efficiency and performance.

IEEE International Conference on Control, Electronics and Computer Technology (ICCECT)•Apr 26, 2024•0 citations

STP‐LWE: A Variant of Learning with Error for a Flexible Encryption

Bo Gao, Yanfeng Shi, Chunli Yang +3 more

We construct a flexible lattice based scheme based on semitensor product learning with errors (STP‐LWE), which is a variant of learning with errors problem. We have proved that STP‐LWE is hard when LWE is hard. Our scheme is proved to be secure against indistinguishable chosen message attacks, and it can achieve a balance between the security and efficiency in the hierarchical encryption systems. In addition, our scheme is almost as efficient as the dual encryption in GPV08.

Mathematical Problems in Engineering•Jan 1, 2014•11 citations

Efficient Instantiation of LWE-based Public-Key Encryption and Commitment Schemes

김진수

The Learning with Errors (LWE) problem has been used as a underlying problem of a variety of cryptographic schemes. It makes possible constructing advanced solutions like fully homomorphic encryption, multi linear map as well as basic primitives like key-exchange, public-key encryption, signature. Recently, developments in quantum computing have triggered interest in constructing practical cryptographic schemes. In this thesis, we propose efficient post-quantum public-key encryption and commitment schemes based on a variant LWE, named as spLWE. We also suggest related zero-knowledge proofs and LWE-based threshold cryptosystems as an application of the proposed schemes. In order to achieve these results, it is essential investigating the hardness about the variant LWE problem, spLWE. We describe its theoretical, and concrete hardness from a careful analysis.

•Jan 1, 2018•0 citations
The Learning with Errors (LWE) problem is a special average-case lattice problem, which has proved to be as hard as worst-case lattice problems. By this property, it has become the cornerstones for a series of cryptographic applications under the security assumption of worst-case lattice problems. However, the efficiency of these applications are not high. Therefore, how to improve the efficiency of cryptographic applications based on LWE is an urgent problem to be solved. In this paper, a new variant of LWE is proposed. By using trapdoor composed by lattice-based matrix and its dual orthogonal matrix, we construct a more efficient public key encryption (PKE) scheme based on the variant. Furthermore, by the hardness of the variant problem, we prove the new PKE scheme is chosen plaintext attack (CPA) secure. At last, we analyze the homomorphism property of the new PKE scheme.
Since its proposal by Regev in 2005, the Learning With Errors (LWE) problem was used as the underlying problem for a great variety of schemes. Its applications are many-fold, reaching from basic and highly practical primitives like key exchange, public-key encryption, and signature schemes to very advanced solutions like fully homomorphic encryption, group signatures, and identity based encryption. One of the underlying reasons for this fertility is the flexibility with that LWE can be instantiated. Unfortunately, this comes at a cost: It makes selecting parameters for cryptographic applications complicated. When selecting parameters for a new LWE-based primitive, a researcher has to take the influence of several parameters on the efficiency of the scheme and the runtime of a variety of attacks into consideration. In fact, the missing trust in the concrete hardness of LWE is one of the main problems to overcome to bring LWE-based schemes to practice. This thesis aims at closing the gap between the theoretical knowledge of the hardness of LWE, and the concrete problem of selecting parameters for an LWE-based scheme. To this end, we analyze the existing methods to estimate the hardness of LWE, and introduce new estimation techniques where necessary. Afterwards, we show how to transfer this knowledge into instantiations that are at the same time secure and efficient. We show this process on three examples: - A highly optimized public-key encryption scheme for embedded devices that is based on a variant of Ring-LWE. - A practical signature scheme that served as the foundation of one of the best lattice-based signature schemes based on standard lattices. - An advanced public-key encryption scheme that enjoys the unique property of natural double hardness based on LWE instances similar to those used for fully homomorphic encryption.
Middle-Product Learning with Errors (MP-LWE) is a variant of the LWE problem introduced by Rosca et al., which achieves a trade-off between security and efficiency for lattice-based public-key encryption. In a nutshell, the public-key encryption based on MP-LWE outperform LWE-based schemes in efficiency while mitigating risks inherent in constructions from Polynomial/Ring LWE. A challenging problem is how to construct a PKE scheme whose security is based on some difficult problem that is the same hard as LWE, but it is of higher efficiency than existing LWE-based PKE schemes. In this paper, we solve this problem. First, we show MP-LWE for the middle-product one is of the same hard as LWE. Second, we propose a PKE scheme from MP-LWE for the middle-product one with shorter public key length than PKE scheme based on LWE.
Abstract: Using the Bonsai trees primitive and Gentry’s CPA-secure (chosen-plaintext attack) public-key encryption (PKE) scheme, we propose an efficient chosen-ciphtertext secure PKE scheme over lattice. If the decision variant of the learning with errors (LWE) problem is hard and the one-time signature used in this scheme is strong unforgeable, the proposed PKE scheme is indistinguishable against the adaptive chosen-ciphtertext attack (IND-CCA2). One of the characters for this scheme is that, before any encryption operation, the encryption algorithm uses a new choice rule to fix the public parameter matrixes used in the encryption operation. With the help of this new choice rule, we can achieve the chosen-ciphtertext security with much shorter the public key size in contrast to the lattice-based encryption scheme proposed in STOC’09 by Peikert. Moreover, as a CCA-secure PKE scheme, the message-tociphtertext expanse factor of this scheme which is controlled efficiently is nearly closed to the message-to-ciphtertext expanse factor of Gentry’s scheme which is CPA secure. Due to the quantum intractability of the LWE problem on which the scheme is based, the proposed PKE scheme is secure even in quantum-era.
Due to the threat of future quantum computers, it is necessary to develop cryptographic schemes that are resistant to quantum attacks. Lattice based cryptographic schemes have resistance to quantum attacks and security under worst-case assumptions that are difficult to solve. To solve the problems of large size of public and private keys, low encryption efficiency, and large noise growth in identity based encryption schemes, an adaptive secure identity based all homomorphic encryption scheme based on Learning with Errors (LWE) is constructed. This scheme uses {0,1} matrices to store plaintext, significantly improving encryption efficiency compared to single bit encryption schemes. It uses key conversion technology to achieve homomorphic operations and modulus conversion technology to reduce noise. It also converts IDs into bit sequences to construct an encryption scheme for adaptive security. Compared to selective security that only provides security guarantees for specific types of attacks, adaptive security is suitable for general scenarios, providing higher security guarantees and being able to cope with more challenging attack situations. It has been proven through the LWE problem that the security of our proposed scheme satisfies IND-ID-CPA. Finally, the experimental results indicate that this scheme introduces less noise, and has higher encryption efficiency and performance.
The Learning with Errors (LWE) problem has been used as a underlying problem of a variety of cryptographic schemes. It makes possible constructing advanced solutions like fully homomorphic encryption, multi linear map as well as basic primitives like key-exchange, public-key encryption, signature. Recently, developments in quantum computing have triggered interest in constructing practical cryptographic schemes. In this thesis, we propose efficient post-quantum public-key encryption and commitment schemes based on a variant LWE, named as spLWE. We also suggest related zero-knowledge proofs and LWE-based threshold cryptosystems as an application of the proposed schemes. In order to achieve these results, it is essential investigating the hardness about the variant LWE problem, spLWE. We describe its theoretical, and concrete hardness from a careful analysis.