Learning with Errors (LWE) standard

Updated: March 26, 2026

Learning with errors (LWE) is a computational, average-case problem introduced in 2005 by Oded Regev [1], which is a generalisation of the Learning Parity with Noise problem. Regev showed that solving LWE is hard to solve on average if a version of the shortest vector problem is hard in its worst-case. LWE serves as the foundational pillar for a vast majority of modern lattice-based cryptography, including constructions for any primitive in cryptomania [2] such as public-key encryption, identity-based encryption, and fully homomorphic encryption.

Definition

The LWE problem comes in two versions: Search and Decision. Both rely on a secret vector $\vec{s}$, a uniformly random matrix $\mat{A}$, and a short error vector $\vec{e}$ sampled from an error distribution $\chi$ (typically discrete Gaussian).

Search LWE$_{n,m,q,\chi}$

Let matrix $\mat{A} \in \ZZ_q^{m \times n}$ and secret vector $\vec{s} \in \ZZ_q^n$ be chosen uniformly at random. Let $\vec{e} \in \ZZ_q^m$ be sampled from the error distribution $\chi$. Given the matrix $\mat{A}$ and the vector $\vec{b} = \mat{A} \cdot \vec{s} + \vec{e} \bmod q$, an adversary is asked to find the secret vector $\vec{s}$.

Without the error vector $\vec{e}$, finding $\vec{s}$ would require solving a system of linear equations, efficiently solvable using Gaussian elimination. The error $\vec{e}$ is supposed to blur the structure of the underlying lattice.

Decision LWE$_{n,m,q,\chi}$

Let matrix $\mat{A} \in \ZZ_q^{m \times n}$ and secret vector $\vec{s} \in \ZZ_q^n$ be chosen uniformly at random. Let $\vec{e} \in \ZZ_q^m$ be sampled from the error distribution $\chi$. An adversary is asked to distinguish between the LWE distribution $(\mat{A}, \vec{b} = \mat{A} \cdot \vec{s} + \vec{e} \bmod q)$ and a uniformly random distribution over $\ZZ_q^{m \times n} \times \ZZ_q^m$.

For cryptographic constructions, Decision LWE is often more directly applicable (e.g., for achieving indistinguishability in encryption schemes). Search and Decision LWE are polynomially equivalent for typical parameter choices [1]. Thus, we only give the decision version of LWE below.

Ring-LWE$_{m,q,\chi,\mathcal{R}}$

Let $\mathcal{R}_q$ be the polynomial ring $\ZZ_q[X]/(f(X))$. Let $\vec{a} \in \mathcal{R}_q^m$ and $s \in \mathcal{R}_q$ be chosen uniformly at random, and let $\vec{e} \in \mathcal{R}_q^m$ be drawn from the error distribution $\chi$. The adversary is asked to distinguish the LWE distribution $(\vec{a}, \vec{b} = \vec{a} \cdot s + \vec{e})$ from a uniformly random distribution over $\mathcal{R}_q^m \times \mathcal{R}_q^m$ .

Ring-LWE (R-LWE) [3] adds more structure to LWE by replacing matrix-vector multiplications with polynomial multiplications. In applications, this results in reduced key sizes and accelerated execution times (using the NTT). The polynomial $f(X)$ is typically a cyclotomic polynomial, such as $X^d + 1$ where $d$ is a power of 2.

Module-LWE$_{n,m,q,\chi,\mathcal{R}}$

Let $\mat{A} \in \mathcal{R}_q^{m \times n}$ be a uniformly random matrix and $\vec{s} \in \mathcal{R}_q^n$ be a random secret vector. Let $\vec{e} \in \mathcal{R}_q^m$ be sampled from the error distribution $\chi$. The adversary is asked to distinguish the LWE distribution $(\mat{A}, \vec{b} = \mat{A} \cdot \vec{s} + \vec{e})$ from a uniformly random distribution over $\mathcal{R}_q^{m \times n} \times \mathcal{R}_q^m$.

By using vectors/matrices over the ring $\mathcal{R}_q$, Module-LWE (M-LWE) [4] can be seen as a generalisation of LWE and R-LWE whose definitions can be recovered by setting $\mathcal{R} = \ZZ$ and $n=1$ respectively.

Variants

Short Secret LWE$_{n,m,q,\chi}$

Let matrix $\mat{A} \in \ZZ_q^{m \times n}$ be chosen uniformly at random. Let the short secret vector $\vec{s} \in \ZZ_q^n$ and $\vec{e} \in \ZZ_q^m$ be sampled from the error distribution $\chi$. An adversary is asked to distinguish between the LWE distribution $(\mat{A}, \vec{b} = \mat{A} \cdot \vec{s} + \vec{e} \bmod q)$ and a uniformly random distribution over $\ZZ_q^{m \times n} \times \ZZ_q^m$.

Short secret LWE (ssLWE) is also known as normal-form LWE and often referred to as LWE itself due to its frequent usage.

Applebaum et al. [5] showed that ssLWE is at least as hard as standard LWE. The reduction utilises an invertible submatrix $\mat{A}_0$ from the LWE challenge matrix $\mat{A} = \begin{bmatrix} \mat{A}_0^T &\mat{A}_1^T \end{bmatrix}^T$. It defines the ssLWE challenge as $(-\mat{A}_1 \cdot \mat{A}_0^{-1}, \vec{b}_1 - \mat{A}_1 \cdot \mat{A}_0^{-1} \cdot \vec{b}_0)$ s.t. the resulting distribution

\[\begin{align}\vec{b}_1 - \mat{A}_1 \cdot \mat{A}_0^{-1} \cdot \vec{b}_0 &= \mat{A}_1 \cdot \vec{s} + \vec{e}_1 - \mat{A}_1 \cdot \mat{A}_0^{-1} \cdot \left( \mat{A}_0 \cdot \vec{s} + \vec{e}_0 \right) \\ &= - \mat{A}_1 \cdot \mat{A}_0^{-1} \cdot \vec{e}_0 + \vec{e}_1\end{align}\]

uses a short secret $\vec{e}_0$ sampled from the error distribution $\chi$ by splitting $\vec{b} = \begin{bmatrix} \vec{b}_0^T &\vec{b}_1^T \end{bmatrix}^T$ and $\vec{e} = \begin{bmatrix} \vec{e}_0^T &\vec{e}_1^T \end{bmatrix}^T$.

Hardness

Regev [1] proved a worst-case hardness theorem for LWE.

Theorem For any $m=\poly{n}$, any modulus $q \leq 2^{\poly{n}}$, and any (discretised) Gaussian error distribution $\chi$ of parameter $\alpha q \geq 2\sqrt{n}$ where $0 < \alpha < 1$, solving the decision-LWE$_{n,m,q,\chi}$ problem is at least as hard as quantumly solving GapSVP$_\gamma$ and SIVP$_\gamma$ on arbitrary $n$-dimensional lattices, for some $\gamma = \bigO{n/\alpha}$.

Later, a completely classical reduction to LWE was established [6] and a dimension-modulus trade-off in the classical reduction established [7].

Similar reductions exist for R-LWE and M-LWE for cyclotomic rings but their hardness relies on the worst-case hardness of GapSVP and SIVP over ideal and module lattices respectively [3][4]. Furthermore, R-LWE is at least as hard as NTRU as sketched in Section 4.4.4 of [8].

Cryptanalytically there are two families of strategies to solve LWE, which can be outlined in the following way:

Primal Attack: Transform an LWE challenge $(\mat{A}, \vec{b} = \mat{A} \cdot \vec{s} + \vec{e})$ into a (unique) shortest vector problem defined by $\mat{B} = \begin{bmatrix} \mat{A}^T &0 \\ \vec{b}^T &1 \end{bmatrix}$, which contains an unusually short vector since $\begin{bmatrix} -\vec{s}^T &1 \end{bmatrix} \cdot \mat{B} = \begin{bmatrix} \vec{e}^T &1 \end{bmatrix}$. Assuming an adversary recovers this short vector from the uSVP instance (using basis reduction algorithms), it recovered the error vector, which enables recovery of the secret vector $\vec{s}$ using Gaussian elimination with $\mat{A}$ and $\vec{b} - \vec{e}$.
Dual Attack: To build a distinguisher for decision LWE, an adversary tries to solve the (scaled) dual SIS challenge. Assuming it succeeds in finding a short non-zero SIS solution $\vec{u}^T$ s.t. $\vec{u}^T \cdot \mat{A} = \vec{0}$. If the challenger handed out the LWE challenge $(\mat{A}, \vec{b} = \mat{A} \cdot \vec{s} + \vec{e})$, then $\langle \vec{u}, \vec{b} \rangle = \langle \vec{u}, \vec{e} \rangle$ remains short. Otherwise, the result is uniformly distributed in $\ZZ_q$.

Constructions built from LWE

This is a non-exhaustive list of constructions, whose security is or can be based on LWE (or R-LWE and M-LWE).

Public-key encryption [1](missing reference)[9]
Key Encapsulation Mechanisms, including ML-KEM (Kyber)
Fully Homomorphic Encryption [10][11]
Oblivious Transfer [12]
Identity-Based Encryption [13][14]

Short Integer Solution can be seen as a dual of LWE.
Learning Parity with Noise yields a specialisation of LWE.
Learning with Rounding TODO

References

[1]Oded Regev. 2005. On lattices, learning with errors, random linear codes, and cryptography. In Proceedings of the 37th Annual ACM Symposium on Theory of Computing, Baltimore, MD, USA, May 22-24, 2005, 2005. ACM, 84–93. https://doi.org/10.1145/1060590.1060603
[2]Russell Impagliazzo. 1995. A Personal View of Average-Case Complexity. In Proceedings of the Tenth Annual Structure in Complexity Theory Conference, Minneapolis, Minnesota, USA, June 19-22, 1995, 1995. IEEE Computer Society, 134–147. https://doi.org/10.1109/SCT.1995.514853
[3]Vadim Lyubashevsky, Chris Peikert, and Oded Regev. 2010. On Ideal Lattices and Learning with Errors over Rings. In Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings (Lecture Notes in Computer Science), 2010. Springer, 1–23. Retrieved from https://ia.cr/2012/230
[4]Adeline Langlois and Damien Stehlé. 2015. Worst-case to average-case reductions for module lattices. Des. Codes Cryptogr. 75, 3 (2015), 565–599. Retrieved from https://ia.cr/2012/090
[5]Benny Applebaum, David Cash, Chris Peikert, and Amit Sahai. 2009. Fast Cryptographic Primitives and Circular-Secure Encryption Based on Hard Learning Problems. In Advances in Cryptology - CRYPTO 2009, 29th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 16-20, 2009. Proceedings (Lecture Notes in Computer Science), 2009. Springer, 595–618. https://doi.org/10.1007/978-3-642-03356-8_35
[6]Chris Peikert. 2009. Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. In Proceedings of the 41st Annual ACM Symposium on Theory of Computing, STOC 2009, Bethesda, MD, USA, May 31 - June 2, 2009, 2009. ACM, 333–342. Retrieved from https://ia.cr/2008/481
[7]Zvika Brakerski, Adeline Langlois, Chris Peikert, Oded Regev, and Damien Stehlé. 2013. Classical hardness of learning with errors. In Symposium on Theory of Computing Conference, STOC’13, Palo Alto, CA, USA, June 1-4, 2013, 2013. ACM, 575–584. https://doi.org/10.1145/2488608.2488680
[8]Chris Peikert. 2016. A Decade of Lattice Cryptography. Found. Trends Theor. Comput. Sci. 10, 4 (2016), 283–424. Retrieved from https://ia.cr/2015/939
[9]Richard Lindner and Chris Peikert. 2011. Better Key Sizes (and Attacks) for LWE-Based Encryption. In Topics in Cryptology - CT-RSA 2011 - The Cryptographers’ Track at the RSA Conference 2011, San Francisco, CA, USA, February 14-18, 2011. Proceedings (Lecture Notes in Computer Science), 2011. Springer, 319–339. Retrieved from https://ia.cr/2010/613
[10]Zvika Brakerski and Vinod Vaikuntanathan. 2011. Efficient Fully Homomorphic Encryption from (Standard) LWE. In IEEE 52nd Annual Symposium on Foundations of Computer Science, FOCS 2011, Palm Springs, CA, USA, October 22-25, 2011, 2011. IEEE Computer Society, 97–106. Retrieved from https://ia.cr/2011/344
[11]Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan. 2012. (Leveled) fully homomorphic encryption without bootstrapping. In Innovations in Theoretical Computer Science 2012, Cambridge, MA, USA, January 8-10, 2012, 2012. ACM, 309–325. https://doi.org/10.1145/2090236.2090262
[12]Chris Peikert, Vinod Vaikuntanathan, and Brent Waters. 2008. A Framework for Efficient and Composable Oblivious Transfer. In Advances in Cryptology - CRYPTO 2008, 28th Annual International Cryptology Conference, Santa Barbara, CA, USA, August 17-21, 2008. Proceedings (Lecture Notes in Computer Science), 2008. Springer, 554–571. Retrieved from https://ia.cr/2007/348
[13]Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan. 2008. Trapdoors for hard lattices and new cryptographic constructions. In Proceedings of the 40th Annual ACM Symposium on Theory of Computing, Victoria, British Columbia, Canada, May 17-20, 2008, 2008. ACM, 197–206. Retrieved from https://ia.cr/2007/432
[14]Shweta Agrawal, Dan Boneh, and Xavier Boyen. 2010. Efficient Lattice (H)IBE in the Standard Model. In Advances in Cryptology - EUROCRYPT 2010, 29th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Monaco / French Riviera, May 30 - June 3, 2010. Proceedings (Lecture Notes in Computer Science), 2010. Springer, 553–572. https://doi.org/10.1007/978-3-642-13190-5_28