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

JOURNAL OF ELECTRONICS INFORMATION TECHNOLOGY

On the Hardness of the Asymmetric Learning With Errors Problem

Jiang Zhang, Shuqin Fan

Published Feb 19, 2020• 0 citations
Publisher

Abstract

Due to the advantages such as the worst-case hardness assumption, lattice-based cryptography is believed to the most promising research direction in post-quantum cryptography. As one of the two main hard problems commonly used in lattice-based cryptography, Learning With Errors (LWE) problem is widely used in constructing numerous cryptosystems. In order to improve the efficiency of lattice-based cryptosystems, Zhang et al. (2019) introduced the Asymmetric LWE (ALWE) problem. In this paper, the relation between the ALWE problem and the standard LWE problem is studied, and it shows that for certain error distributions the two problems are polynomially equivent, which paves the way for constructing secure lattice-based cryptosystems from the ALWE problem.

DOI
10.11999/jeit190685

Related papers

On Ideal Lattices and Learning with Errors over Rings

Vadim Lyubashevsky, Chris Peikert, Oded Regev

The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called ring-LWE , and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE.

Journal of the ACM•Nov 1, 2013•911 citations

Lattice-Based Cryptography

Seong Oun Hwang, Intae Kim, Wai‐Kong Lee

This chapter introduces post-quantum cryptography. It describes lattice-based cryptographic constructions of post-quantum cryptography. Lattice-based cryptographic constructions are one of candidates of post-quantum cryptography, which are believed to be secure against quantum computers. Learning with errors (LWE) is one of the most promising primitives in many usages due to its lightweight operation and rigorous security reduction against the worst-case of the lattice problems that are considered to be hard to solve even after the advance of quantum computers. After the research about the connection between the LWE problem and some lattice problems, some variants of LWE, of which the secret distributions are modified from the uniform distribution, were proposed. Due to the efficiency and compactness of ring-LWE, many lattice-based cryptosystems are constructed as ring-LWE based, rather than LWE-based. The chapter explains a ring variant of Lizard scheme, called RLizard, IND-CCA secure encryption scheme.

CRC Press eBooks•Feb 19, 2021•1 citation

On lattices, learning with errors, random linear codes, and cryptography

Oded Regev

Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the “learning from parity with error” problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., nonquantum). We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size Õ( n 2 ) and encrypting a message increases its size by a factor of Õ( n ) (in previous cryptosystems these values are Õ( n 4 ) and Õ( n 2 ), respectively). In fact, under the assumption that all parties share a random bit string of length Õ( n 2 ), the size of the public key can be reduced to Õ( n ).

arXiv:2401.03703•Journal of the ACM•Sep 1, 2009•2,538 citations

Hardness of decision (R)LWE for any modulus.

Adeline Roux-Langlois, Damien Stehlé

Abstract. The decision Learning With Errors problem has proven an extremely flexible foundation for devising provably secure cryptographic primitives. LWE can be expressed in terms of linear algebra over Z/qZ. This modulus q is the subject of study of the present work. When q is prime and small, or when it is exponential and composite with small factors, LWE is known to be at least as hard as standard worst-case problems over euclidean lattices (sometimes using quantum reductions). The Ring Learning With Errors problem is a structured variant of LWE allowing for more compact keys and more efficient primitives. It is known to be at least as hard as standard worst-case problems restricted to so-called ideal lattices, but under even more restrictive arithmetic conditions on q. In this work, we prove that the arithmetic form of the modulus q is irrelevant to the computational hardness of LWE and RLWE. More precisely, we show that these problems are at least as hard as standard worst-case problems on lattices, under the unique condition that q is of polynomial bit-size. This result is most useful for adapting LWE-based cryptographic constructions to the RLWE setting. Among others, this allows us to derive the first Identity-Based Encryption scheme of quasi-optimal performance proven secure under standard worst-case lattice assumptions, in the standard model. Other applications include authentication, functional encryption and traitor tracing.

•Jan 1, 2012•12 citations

On lattices, learning with errors, random linear codes, and cryptography

Oded Regev

Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the 'learning from parity with error' problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for SVP and SIVP. A main open question is whether this reduction can be made classical.Using the main result, we obtain a public-key cryptosystem whose hardness is based on the worst-case quantum hardness of SVP and SIVP. Previous lattice-based public-key cryptosystems such as the one by Ajtai and Dwork were only based on unique-SVP, a special case of SVP. The new cryptosystem is much more efficient than previous cryptosystems: the public key is of size Õ(n2) and encrypting a message increases its size by Õ(n)(in previous cryptosystems these values are Õ(n4) and Õ(n2), respectively). In fact, under the assumption that all parties share a random bit string of length Õ(n2), the size of the public key can be reduced to Õ(n).

ACM Symposium on Theory of Computing (STOC)•May 22, 2005•2,530 citations

Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography

Maria E. Sabani, Ilias Κ. Savvas, Georgia Garani

The swift advancement of quantum computing devices holds the potential to create robust machines that can tackle an extensive array of issues beyond the scope of conventional computers. Consequently, quantum computing machines create new risks at a velocity and scale never seen before, especially with regard to encryption. Lattice-based cryptography is regarded as post-quantum cryptography’s future and a competitor to a quantum computer attack. Thus, there are several advantages to lattice-based cryptographic protocols, including security, effectiveness, reduced energy usage and speed. In this work, we study the learning with errors (LWE) problem and the cryptosystems that are based on the LWE problem and, in addition, we present a new efficient variant of LWE cryptographic scheme.

Signals•Apr 13, 2024•34 citations
Due to the advantages such as the worst-case hardness assumption, lattice-based cryptography is believed to the most promising research direction in post-quantum cryptography. As one of the two main hard problems commonly used in lattice-based cryptography, Learning With Errors (LWE) problem is widely used in constructing numerous cryptosystems. In order to improve the efficiency of lattice-based cryptosystems, Zhang et al. (2019) introduced the Asymmetric LWE (ALWE) problem. In this paper, the relation between the ALWE problem and the standard LWE problem is studied, and it shows that for certain error distributions the two problems are polynomially equivent, which paves the way for constructing secure lattice-based cryptosystems from the ALWE problem.
The “learning with errors” (LWE) problem is to distinguish random linear equations, which have been perturbed by a small amount of noise, from truly uniform ones. The problem has been shown to be as hard as worst-case lattice problems, and in recent years it has served as the foundation for a plethora of cryptographic applications. Unfortunately, these applications are rather inefficient due to an inherent quadratic overhead in the use of LWE. A main open question was whether LWE and its applications could be made truly efficient by exploiting extra algebraic structure, as was done for lattice-based hash functions (and related primitives). We resolve this question in the affirmative by introducing an algebraic variant of LWE called ring-LWE , and proving that it too enjoys very strong hardness guarantees. Specifically, we show that the ring-LWE distribution is pseudorandom, assuming that worst-case problems on ideal lattices are hard for polynomial-time quantum algorithms. Applications include the first truly practical lattice-based public-key cryptosystem with an efficient security reduction; moreover, many of the other applications of LWE can be made much more efficient through the use of ring-LWE.
This chapter introduces post-quantum cryptography. It describes lattice-based cryptographic constructions of post-quantum cryptography. Lattice-based cryptographic constructions are one of candidates of post-quantum cryptography, which are believed to be secure against quantum computers. Learning with errors (LWE) is one of the most promising primitives in many usages due to its lightweight operation and rigorous security reduction against the worst-case of the lattice problems that are considered to be hard to solve even after the advance of quantum computers. After the research about the connection between the LWE problem and some lattice problems, some variants of LWE, of which the secret distributions are modified from the uniform distribution, were proposed. Due to the efficiency and compactness of ring-LWE, many lattice-based cryptosystems are constructed as ring-LWE based, rather than LWE-based. The chapter explains a ring variant of Lizard scheme, called RLizard, IND-CCA secure encryption scheme.
Our main result is a reduction from worst-case lattice problems such as GapSVP and SIVP to a certain learning problem. This learning problem is a natural extension of the “learning from parity with error” problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for GapSVP and SIVP. A main open question is whether this reduction can be made classical (i.e., nonquantum). We also present a (classical) public-key cryptosystem whose security is based on the hardness of the learning problem. By the main result, its security is also based on the worst-case quantum hardness of GapSVP and SIVP. The new cryptosystem is much more efficient than previous lattice-based cryptosystems: the public key is of size Õ( n 2 ) and encrypting a message increases its size by a factor of Õ( n ) (in previous cryptosystems these values are Õ( n 4 ) and Õ( n 2 ), respectively). In fact, under the assumption that all parties share a random bit string of length Õ( n 2 ), the size of the public key can be reduced to Õ( n ).
Abstract. The decision Learning With Errors problem has proven an extremely flexible foundation for devising provably secure cryptographic primitives. LWE can be expressed in terms of linear algebra over Z/qZ. This modulus q is the subject of study of the present work. When q is prime and small, or when it is exponential and composite with small factors, LWE is known to be at least as hard as standard worst-case problems over euclidean lattices (sometimes using quantum reductions). The Ring Learning With Errors problem is a structured variant of LWE allowing for more compact keys and more efficient primitives. It is known to be at least as hard as standard worst-case problems restricted to so-called ideal lattices, but under even more restrictive arithmetic conditions on q. In this work, we prove that the arithmetic form of the modulus q is irrelevant to the computational hardness of LWE and RLWE. More precisely, we show that these problems are at least as hard as standard worst-case problems on lattices, under the unique condition that q is of polynomial bit-size. This result is most useful for adapting LWE-based cryptographic constructions to the RLWE setting. Among others, this allows us to derive the first Identity-Based Encryption scheme of quasi-optimal performance proven secure under standard worst-case lattice assumptions, in the standard model. Other applications include authentication, functional encryption and traitor tracing.
Our main result is a reduction from worst-case lattice problems such as SVP and SIVP to a certain learning problem. This learning problem is a natural extension of the 'learning from parity with error' problem to higher moduli. It can also be viewed as the problem of decoding from a random linear code. This, we believe, gives a strong indication that these problems are hard. Our reduction, however, is quantum. Hence, an efficient solution to the learning problem implies a quantum algorithm for SVP and SIVP. A main open question is whether this reduction can be made classical.Using the main result, we obtain a public-key cryptosystem whose hardness is based on the worst-case quantum hardness of SVP and SIVP. Previous lattice-based public-key cryptosystems such as the one by Ajtai and Dwork were only based on unique-SVP, a special case of SVP. The new cryptosystem is much more efficient than previous cryptosystems: the public key is of size Õ(n2) and encrypting a message increases its size by Õ(n)(in previous cryptosystems these values are Õ(n4) and Õ(n2), respectively). In fact, under the assumption that all parties share a random bit string of length Õ(n2), the size of the public key can be reduced to Õ(n).
The swift advancement of quantum computing devices holds the potential to create robust machines that can tackle an extensive array of issues beyond the scope of conventional computers. Consequently, quantum computing machines create new risks at a velocity and scale never seen before, especially with regard to encryption. Lattice-based cryptography is regarded as post-quantum cryptography’s future and a competitor to a quantum computer attack. Thus, there are several advantages to lattice-based cryptographic protocols, including security, effectiveness, reduced energy usage and speed. In this work, we study the learning with errors (LWE) problem and the cryptosystems that are based on the LWE problem and, in addition, we present a new efficient variant of LWE cryptographic scheme.