In cryptography, learning with errors (LWE) is a mathematical problem that is widely used to create secure encryption algorithms. It is based on the idea of representing secret information as a set of equations with errors. In other words, LWE is a way to hide the value of a secret by introducing noise to it. In more technical terms, it refers to the computational problem of inferring a linear ${\displaystyle n}$-ary function ${\displaystyle f}$ over a finite ring from given samples ${\displaystyle y_{i}=f(\mathbf {x} _{i})}$ some of which may be erroneous. The LWE problem is conjectured to be hard to solve, and thus to be useful in cryptography.

More precisely, the LWE problem is defined as follows. Let ${\displaystyle \mathbb {Z} _{q}}$ denote the ring of integers modulo ${\displaystyle q}$ and let ${\displaystyle \mathbb {Z} _{q}^{n}}$ denote the set of ${\displaystyle n}$-vectors over ${\displaystyle \mathbb {Z} _{q}}$. There exists a certain unknown linear function ${\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}$, and the input to the LWE problem is a sample of pairs ${\displaystyle (\mathbf {x} ,y)}$, where ${\displaystyle \mathbf {x} \in \mathbb {Z} _{q}^{n}}$ and ${\displaystyle y\in \mathbb {Z} _{q}}$, so that with high probability ${\displaystyle y=f(\mathbf {x} )}$. Furthermore, the deviation from the equality is according to some known noise model. The problem calls for finding the function ${\displaystyle f}$, or some close approximation thereof, with high probability.

The LWE problem was introduced by Oded Regev in 2005 (who won the 2018 Gödel Prize for this work); it is a generalization of the parity learning problem. Regev showed that the LWE problem is as hard to solve as several worst-case lattice problems. Subsequently, the LWE problem has been used as a hardness assumption to create public-key cryptosystems, such as the ring learning with errors key exchange by Peikert.

Denote by ${\displaystyle \mathbb {T} =\mathbb {R} /\mathbb {Z} }$ the additive group on reals modulo one. Let ${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$ be a fixed vector. Let ${\displaystyle \phi }$ be a fixed probability distribution over ${\displaystyle \mathbb {T} }$. Denote by ${\displaystyle A_{\mathbf {s} ,\phi }}$ the distribution on ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$ obtained as follows.

The learning with errors problem ${\displaystyle \mathrm {LWE} _{q,\phi }}$ is to find ${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$, given access to polynomially many samples of choice from ${\displaystyle A_{\mathbf {s} ,\phi }}$.

For every ${\displaystyle \alpha >0}$, denote by ${\displaystyle D_{\alpha }}$ the one-dimensional Gaussian with zero mean and variance ${\displaystyle \alpha ^{2}/(2\pi )}$, that is, the density function is ${\displaystyle D_{\alpha }(x)=\rho _{\alpha }(x)/\alpha }$ where ${\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}$, and let ${\displaystyle \Psi _{\alpha }}$ be the distribution on ${\displaystyle \mathbb {T} }$ obtained by considering ${\displaystyle D_{\alpha }}$ modulo one. The version of LWE considered in most of the results would be ${\displaystyle \mathrm {LWE} _{q,\Psi _{\alpha }}}$

The LWE problem described above is the search version of the problem. In the decision version (DLWE), the goal is to distinguish between noisy inner products and uniformly random samples from ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$ (practically, some discretized version of it). Regev showed that the decision and search versions are equivalent when ${\displaystyle q}$ is a prime bounded by some polynomial in ${\displaystyle n}$.

Intuitively, if we have a procedure for the search problem, the decision version can be solved easily: just feed the input samples for the decision problem to the solver for the search problem. Denote the given samples by ${\displaystyle \{(\mathbf {a} _{i},\mathbf {b} _{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }$. If the solver returns a candidate ${\displaystyle \mathbf {s} }$, for all ${\displaystyle i}$, calculate ${\displaystyle \{\langle \mathbf {a} _{i},\mathbf {s} \rangle -\mathbf {b} _{i}\}}$. If the samples are from an LWE distribution, then the results of this calculation will be distributed according ${\displaystyle \chi }$, but if the samples are uniformly random, these quantities will be distributed uniformly as well.