Learning with errors (LWE) is a problem in machine learning. A generalization of the parity learning problem, it has recently[1][2] been used to create public-key cryptosystems based on worst-case hardness of some lattice problems. The problem was introduced[1] by Oded Regev in 2005.

Given access to samples ${\displaystyle (x,y)}$ where ${\displaystyle x\in \mathbb {Z} _{q}^{n}}$ and ${\displaystyle y\in \mathbb {Z} _{q}}$, with assurance that, for some fixed linear function ${\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}$ ${\displaystyle ,y=f(x)}$ with high probability and deviates from it according to some known noise model, the algorithm must be able to recreate ${\displaystyle f}$ or some close approximation of it.

## Definition

Denote by ${\displaystyle \mathbb {T} =\mathbb {R} /\mathbb {Z} }$ the additive group on reals modulo one. Denote by ${\displaystyle A_{s,\phi }}$ the distribution on ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$ obtained by choosing a vector ${\displaystyle \mathbf {a} \in \mathbb {Z} _{q}^{n}}$ uniformly at random, choosing ${\displaystyle e}$ according to a probability distribution ${\displaystyle \phi}$ on ${\displaystyle \mathbb{T}}$ and outputting ${\displaystyle (\mathbf {a} ,\langle \mathbf {a} ,s\rangle /q+e)}$ for some fixed vector ${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$ where the division is done in the field of reals, and the addition in ${\displaystyle \mathbb{T}}$.

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

For every ${\displaystyle \alpha>0}$, denote by ${\displaystyle D_\alpha}$ denote the one-dimensional Gaussian with density function ${\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 LWE_{q,\Psi _{\alpha }}}$

## Decision version

The LWE problem described above is the search version of the problem. In the decision version, 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[1] showed that the decision and search versions are equivalent when ${\displaystyle q}$ is a prime bounded by some polynomial in ${\displaystyle n}$.

### Solving decision assuming search

Intuitively, it is easy to see that if we have a procedure for the search problem, the decision version can be solved easily: just feed the input samples for the decision version to the procedure for the search problem, and check if the ${\displaystyle s}$ returned by the search procedure can generate the input pairs modulo some noise.

### Solving search assuming decision

For the other direction, suppose that we have a procedure for the decision problem, the search version can be solved as follows: Recover the ${\displaystyle s}$ one co-ordinate at a time. Suppose we are guessing the first co-ordinate, and we are trying to test if ${\displaystyle s_{i}=k}$ for a fixed ${\displaystyle k\in Z_{q}}$. Choose a number ${\displaystyle l\in \mathbb {Z} _{q}^{*}}$ uniformly at random. Denote the given samples by ${\displaystyle \{(a_{i},b_{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }$. Feed the transformed pairs ${\displaystyle \{(a_{i}+(l,0,\ldots ,0),b_{i}+(lk)/q)\}}$ to the decision problem. It is easy to see that if the guess ${\displaystyle k}$ was correct, the transformation takes the distribution ${\displaystyle A_{s,\chi }}$ to itself, and otherwise takes it to the uniform distribution. Since we have a procedure for the decision version which distinguishes between these two types of distributions, and errs with very small probability, we can test if the guess ${\displaystyle k}$ equals the first co-ordinate. Since ${\displaystyle q}$ is a prime bounded by some polynomial in ${\displaystyle n}$, ${\displaystyle k}$ can only take polynomially many values, and each co-ordinate can be efficiently guessed with high probability.

## Hardness results

### Regev's result

For a n-dimensional lattice ${\displaystyle L}$, let smoothing parameter ${\displaystyle \eta _{\epsilon }(L)}$ denote the smallest ${\displaystyle s}$ such that ${\displaystyle \rho _{1/s}(L^{*}\setminus \{\mathbf {0} \})\leq \epsilon }$ where ${\displaystyle L^*}$ is the dual of ${\displaystyle L}$ and ${\displaystyle \rho _{\alpha }(x)=e^{-\pi (|x|/\alpha )^{2}}}$ is extended to sets by summing over function values at each element in the set. Let ${\displaystyle D_{L,r}}$ denote the discrete Gaussian distribution on ${\displaystyle L}$ of width ${\displaystyle r}$ for a lattice ${\displaystyle L}$ and real ${\displaystyle r > 0}$. The probability of each ${\displaystyle x \in L}$ is proportional to ${\displaystyle \rho _{r}(x)}$.

The discrete Gaussian sampling problem(DGS) is defined as follows: An instance of ${\displaystyle DGS_{\phi }}$ is given by an ${\displaystyle n}$-dimensional lattice ${\displaystyle L}$ and a number ${\displaystyle r\geq \phi (L)}$. The goal is to output a sample from ${\displaystyle D_{L,r}}$. Regev shows that there is a reduction from ${\displaystyle GapSVP_{100{\sqrt {n}}\gamma (n)}}$ to ${\displaystyle DGS_{{\sqrt {n}}\gamma (n)/\lambda (L^{*})}}$ for any function ${\displaystyle \gamma (n)}$.

Regev then shows that there exists an efficient quantum algorithm for ${\displaystyle DGS_{{\sqrt {2n}}\eta _{\epsilon }(L)/\alpha }}$ given access to an oracle for ${\displaystyle LWE_{q,\Psi _{\alpha }}}$ for integer ${\displaystyle q}$ and ${\displaystyle \alpha \in (0, 1)}$ such that ${\displaystyle \alpha q>2{\sqrt {n}}}$. This implies the hardness for ${\displaystyle LWE}$. Although the proof of this assertion works for any ${\displaystyle q}$, for creating a cryptosystem, the ${\displaystyle q}$ has to be polynomial in ${\displaystyle n}$.

### Peikert's result

Peikert proves[2] that there is a probabilistic polynomial time reduction from the ${\displaystyle GapSVP_{\zeta,\gamma}}$ problem in the worst case to solving ${\displaystyle LWE_{q,\Psi _{\alpha }}}$ using ${\displaystyle poly(n)}$ samples for parameters ${\displaystyle \alpha \in (0, 1)}$, ${\displaystyle \gamma (n)\geq n/(\alpha {\sqrt {\log {n}}})}$, ${\displaystyle \zeta (n)\geq \gamma (n)}$ and ${\displaystyle q\geq (\zeta /{\sqrt {n}})\omega {\sqrt {\log {n}}})}$.

## Use in Cryptography

The LWE problem serves as a versatile problem used in construction of several[1][2][3][4] cryptosystems. In 2005, Regev[1] showed that the decision version of LWE is hard assuming quantum hardness of the lattice problems ${\displaystyle GapSVP_\gamma}$ (for ${\displaystyle \gamma}$ as above) and ${\displaystyle SIVP_{t}}$ with t=Õ(n/${\displaystyle \alpha}$). In 2009, Peikert[2] proved a similar result assuming only the classical hardness of the related problem ${\displaystyle GapSVP_{\zeta,\gamma}}$. The disadvantage of Peikert's result is that it bases itself on a non-standard version of an easier (when compared to SIVP) problem GapSVP.

### Public-key cryptosystem

Regev[1] proposed a public-key cryptosystem based on the hardness of the LWE problem. The cryptosystem as well as the proof of security and correctness are completely classical. The system is characterized by ${\displaystyle m,q}$ and a probability distribution ${\displaystyle \chi}$ on ${\displaystyle \mathbb{T}}$. The setting of the parameters used in proofs of correctness and security is

• ${\displaystyle q\geq 2}$, a prime number between ${\displaystyle n^2}$ and ${\displaystyle 2n^2}$.
• ${\displaystyle m=(1+\epsilon )(n+1)\log {q}}$ for an arbitrary constant ${\displaystyle \epsilon}$
• ${\displaystyle \chi =\Psi _{\alpha (n)}}$ for ${\displaystyle \alpha (n)\in o(1/{\sqrt {n}}\log {n})}$

The cryptosystem is then defined by:

• Private Key: Private key is an ${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$ chosen uniformly at random.
• Public Key: Choose ${\displaystyle m}$ vectors ${\displaystyle a_{1},\ldots ,a_{m}\in \mathbb {Z} _{q}^{n}}$ uniformly and independently. Choose error offsets ${\displaystyle e_{1},\ldots ,e_{m}\in \mathbb {T} }$ independently according to ${\displaystyle \chi}$. The public key consists of ${\displaystyle (a_{i},b_{i}=\langle a_{i},\mathbf {s} \rangle /q+e_{i})_{i=1}^{m}}$
• Encryption: The encryption of a bit ${\displaystyle x\in \{0,1\}}$ is done by choosing a random subset ${\displaystyle S}$ of ${\displaystyle [m]}$ and then defining ${\displaystyle Enc(x)}$ as ${\displaystyle (\sum _{i\in S}a_{i},x/2+\sum _{i\in S}b_{i})}$
• Decryption: The decryption of ${\displaystyle (a,b)}$ is ${\displaystyle 0}$ if ${\displaystyle b-\langle a,\mathbf {s} \rangle /q}$ is closer to ${\displaystyle 0}$ than to ${\displaystyle \frac{1}{2}}$, and ${\displaystyle 1}$ otherwise.

The proof of correctness follows from choice of parameters and some probability analysis. The proof of security is by reduction to the decision version of LWE: an algorithm for distinguishing between encryptions (with above parameters) of ${\displaystyle 0}$ and ${\displaystyle 1}$ can be used to distinguish between ${\displaystyle A_{s,\chi }}$ and the uniform distribution over ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {Z} _{q}}$

### CCA-secure cryptosystem

Template:Expand section Peikert[2] proposed a system that is secure even against any chosen-ciphertext attack.