This articlemay be too technical for most readers to understand. Pleasehelp improve it tomake it understandable to non-experts, without removing the technical details.(October 2018) (Learn how and when to remove this message)

Incryptography,learning with errors (LWE) is a mathematical problem that is widely used to create secureencryption algorithms.^[1] 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.^[2] In more technical terms, it refers to thecomputational problem of inferring a linear${\displaystyle n}$-ary function${\displaystyle f}$ over a finitering 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,^[1] 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 integersmodulo${\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\to {\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 byOded Regev in 2005^[3] (who won the 2018Gödel Prize for this work); it is a generalization of theparity learning problem. Regev showed that the LWE problem is as hard to solve as several worst-caselattice problems. Subsequently, the LWE problem has been used as ahardness assumption to createpublic-key cryptosystems,^[3][4] such as thering learning with errors key exchange by Peikert.^[5]

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

1. Pick a vector${\displaystyle \mathbf{a}\in {\mathbb{Z}}_q^n}$ from the uniform distribution over${\displaystyle {\mathbb{Z}}_q^n}$,
2. Pick a number${\displaystyle e\in \mathbb{T}}$ from the distribution${\displaystyle \varphi }$,
3. Evaluate${\displaystyle t=⟨\mathbf{a},\mathbf{s}⟩/q+e}$, where${\displaystyle ⟨\mathbf{a},\mathbf{s}⟩=\sum _{i=1}^n{a}_i{s}_i}$ is the standard inner product in${\displaystyle {\mathbb{Z}}_q^n}$, the division is done in thefield of reals (or more formally, this "division by${\displaystyle q}$" is notation for the group homomorphism${\displaystyle {\mathbb{Z}}_q⟶\mathbb{T}}$ mapping${\displaystyle 1\in {\mathbb{Z}}_q}$ to${\displaystyle 1/q+\mathbb{Z}\in \mathbb{T}}$), and the final addition is in${\displaystyle \mathbb{T}}$.
4. Output the pair${\displaystyle (\mathbf{a},t)}$.

Thelearning with errors problem${\displaystyle {\mathrm{L}\mathrm{W}\mathrm{E}}_{q,\varphi }}$ is to find${\displaystyle \mathbf{s}\in {\mathbb{Z}}_q^n}$, given access to polynomially many samples of choice from${\displaystyle A_{\mathbf{s},\varphi }}$.

For every${\displaystyle \alpha >0}$, denote by${\displaystyle D_{\alpha }}$ the one-dimensionalGaussian 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 {\mathrm{\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{L}\mathrm{W}\mathrm{E}}_{q,{\mathrm{\Psi }}_{\alpha }}}$

TheLWE problem described above is thesearch version of the problem. In thedecision 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^[3] showed that thedecision andsearch 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 \{⟨{\mathbf{a}}_i,\mathbf{s}⟩-{\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.

For the other direction, given a solver for the decision problem, the search version can be solved as follows: Recover${\displaystyle \mathbf{s}}$ one coordinate at a time. To obtain the first coordinate,${\displaystyle {\mathbf{s}}_1}$, make a guess${\displaystyle k\in {\mathbb{Z}}_q}$, and do the following. Choose a number${\displaystyle r\in {\mathbb{Z}}_q}$ uniformly at random. Transform the given samples${\displaystyle \{({\mathbf{a}}_i,{\mathbf{b}}_i)\}\subset {\mathbb{Z}}_q^n\times \mathbb{T}}$ as follows. Calculate${\displaystyle \{({\mathbf{a}}_i+(r,0,\dots ,0),{\mathbf{b}}_i+(rk)/q)\}}$. Send the transformed samples to the decision solver.

If the guess${\displaystyle k}$ was correct, the transformation takes the distribution${\displaystyle A_{\mathbf{s},\chi }}$ to itself, and otherwise, since${\displaystyle q}$ is prime, it takes it to the uniform distribution. So, given a polynomial-time solver for the decision problem that errs with very small probability, since${\displaystyle q}$ is bounded by some polynomial in${\displaystyle n}$, it only takes polynomial time to guess every possible value for${\displaystyle k}$ and use the solver to see which one is correct.

After obtaining${\displaystyle {\mathbf{s}}_1}$, we follow an analogous procedure for each other coordinate${\displaystyle {\mathbf{s}}_j}$. Namely, we transform our${\displaystyle {\mathbf{b}}_i}$ samples the same way, and transform our${\displaystyle {\mathbf{a}}_i}$ samples by calculating${\displaystyle {\mathbf{a}}_i+(0,\dots ,r,\dots ,0)}$, where the${\displaystyle r}$ is in the${\displaystyle j^{\text{th}}}$ coordinate.^[3]

Peikert^[4] showed that this reduction, with a small modification, works for any${\displaystyle q}$ that is a product of distinct, small (polynomial in${\displaystyle n}$) primes. The main idea is if${\displaystyle q=q_1{q}_2\cdots q_t}$, for each${\displaystyle q_{\ell }}$, guess and check to see if${\displaystyle {\mathbf{s}}_j}$ is congruent to${\displaystyle 0\mathrm{mod}{q}_{\ell }}$, and then use theChinese remainder theorem to recover${\displaystyle {\mathbf{s}}_j}$.

Regev^[3] showed therandom self-reducibility of theLWE andDLWE problems for arbitrary${\displaystyle q}$ and${\displaystyle \chi }$. Given samples${\displaystyle \{({\mathbf{a}}_i,{\mathbf{b}}_i)\}}$ from${\displaystyle A_{\mathbf{s},\chi }}$, it is easy to see that${\displaystyle \{({\mathbf{a}}_i,{\mathbf{b}}_i+⟨{\mathbf{a}}_i,\mathbf{t}⟩)/q\}}$ are samples from${\displaystyle A_{\mathbf{s}+\mathbf{t},\chi }}$.

So, suppose there was some set${\displaystyle \mathcal{S}\subset {\mathbb{Z}}_q^n}$ such that${\displaystyle |\mathcal{S}|/|{\mathbb{Z}}_q^n|=1/\mathrm{poly}(n)}$, and for distributions${\displaystyle A_{{\mathbf{s}}^{\prime },\chi }}$, with${\displaystyle {\mathbf{s}}^{\prime }\leftarrow \mathcal{S}}$,DLWE was easy.

Then there would be some distinguisher${\displaystyle \mathcal{A}}$, who, given samples${\displaystyle \{({\mathbf{a}}_i,{\mathbf{b}}_i)\}}$, could tell whether they were uniformly random or from${\displaystyle A_{{\mathbf{s}}^{\prime },\chi }}$. If we need to distinguish uniformly random samples from${\displaystyle A_{\mathbf{s},\chi }}$, where${\displaystyle \mathbf{s}}$ is chosen uniformly at random from${\displaystyle {\mathbb{Z}}_q^n}$, we could simply try different values${\displaystyle \mathbf{t}}$ sampled uniformly at random from${\displaystyle {\mathbb{Z}}_q^n}$, calculate${\displaystyle \{({\mathbf{a}}_i,{\mathbf{b}}_i+⟨{\mathbf{a}}_i,\mathbf{t}⟩)/q\}}$ and feed these samples to${\displaystyle \mathcal{A}}$. Since${\displaystyle \mathcal{S}}$ comprises a large fraction of${\displaystyle {\mathbb{Z}}_q^n}$, with high probability, if we choose a polynomial number of values for${\displaystyle \mathbf{t}}$, we will find one such that${\displaystyle \mathbf{s}+\mathbf{t}\in \mathcal{S}}$, and${\displaystyle \mathcal{A}}$ will successfully distinguish the samples.

Thus, no such${\displaystyle \mathcal{S}}$ can exist, meaningLWE andDLWE are (up to a polynomial factor) as hard in the average case as they are in the worst case.

For an-dimensional lattice${\displaystyle L}$, letsmoothing parameter${\displaystyle {\eta }_{\epsilon }(L)}$ denote the smallest${\displaystyle s}$ such that${\displaystyle {\rho }_{1/s}(L^{\ast }\setminus \{\mathbf{0}\})\le \epsilon }$ where${\displaystyle L^{\ast }}$ 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)}$.

Thediscrete Gaussian sampling problem (DGS) is defined as follows: An instance of${\displaystyle DG{S}_{\varphi }}$ is given by an${\displaystyle n}$-dimensional lattice${\displaystyle L}$ and a number${\displaystyle r\ge \varphi (L)}$. The goal is to output a sample from${\displaystyle D_{L,r}}$. Regev shows that there is a reduction from${\displaystyle {\mathrm{GapSVP}}_{100\sqrt{n}\gamma (n)}}$ to${\displaystyle DG{S}_{\sqrt{n}\gamma (n)/\lambda (L^{\ast })}}$ for any function${\displaystyle \gamma (n)\ge 1}$.

Regev then shows that there exists an efficientquantum algorithm for${\displaystyle DG{S}_{\sqrt{2n}{\eta }_{\epsilon }(L)/\alpha }}$ given access to an oracle for${\displaystyle {\mathrm{L}\mathrm{W}\mathrm{E}}_{q,{\mathrm{\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 LWE. Although the proof of this assertion works for any${\displaystyle q}$, for creating a cryptosystem, the modulus${\displaystyle q}$ has to be polynomial in${\displaystyle n}$.

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

TheLWE problem serves as a versatile problem used in construction of several^[3][4][6][7] cryptosystems. In 2005, Regev^[3] showed that the decision version of LWE is hard assuming quantum hardness of thelattice problems${\displaystyle {\mathrm{G}\mathrm{a}\mathrm{p}\mathrm{S}\mathrm{V}\mathrm{P}}_{\gamma }}$ (for${\displaystyle \gamma }$ as above) and${\displaystyle {\mathrm{S}\mathrm{I}\mathrm{V}\mathrm{P}}_t}$ with${\displaystyle t=O(n/\alpha )}$). In 2009, Peikert^[4] proved a similar result assuming only the classical hardness of the related problem${\displaystyle {\mathrm{G}\mathrm{a}\mathrm{p}\mathrm{S}\mathrm{V}\mathrm{P}}_{\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.

Regev^[3] proposed apublic-key cryptosystem based on the hardness of theLWE 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\ge 2}$, usually aprime 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 ={\mathrm{\Psi }}_{\alpha (n)}}$ for${\displaystyle \alpha (n)\in o(1/\sqrt{n}\log n)}$, where${\displaystyle {\mathrm{\Psi }}_{\beta }}$ is a probability distribution obtained by sampling a normal variable with mean${\displaystyle 0}$ and standard variation${\displaystyle \frac{\beta }{\sqrt{2\pi }}}$ and reducing the result modulo${\displaystyle 1}$.

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 {\mathbf{a}}_1,\dots ,{\mathbf{a}}_m\in {\mathbb{Z}}_q^n}$ uniformly and independently. Choose error offsets${\displaystyle e_1,\dots ,e_m\in \mathbb{T}}$ independently according to${\displaystyle \chi }$. The public key consists of${\displaystyle ({\mathbf{a}}_i,b_i=⟨{\mathbf{a}}_i,\mathbf{s}⟩/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 \mathrm{Enc}(x)}$ as

${\displaystyle \left(\sum _{i\in S}{\mathbf{a}}_i,\frac{x}{2}+\sum _{i\in S}{b}_i\right)}$

• Decryption: The decryption of${\displaystyle (\mathbf{a},b)}$ is${\displaystyle 0}$ if${\displaystyle b-⟨\mathbf{a},\mathbf{s}⟩/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 ofLWE: 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{T}}$

This sectionneeds expansion. You can help byadding missing information.(December 2009)

Peikert^[4] proposed a system that is secure even against anychosen-ciphertext attack.

The idea of using LWE and Ring LWE for key exchange was proposed and filed at the University of Cincinnati in 2011 by Jintai Ding. The idea comes from the associativity of matrix multiplications, and the errors are used to provide the security. The paper^[8] appeared in 2012 after a provisional patent application was filed in 2012.

The security of the protocol is proven based on the hardness of solving the LWE problem. In 2014, Peikert presented a key-transport scheme^[9] following the same basic idea of Ding's, where the new idea of sending an additional 1-bit signal for rounding in Ding's construction is also used. The "new hope" implementation^[10] selected for Google's post-quantum experiment,^[11] uses Peikert's scheme with variation in the error distribution.

A RLWE version of the classicFeige–Fiat–Shamir Identification protocol was created and converted to adigital signature in 2011 by Lyubashevsky. The details of this signature were extended in 2012 by Gunesyu, Lyubashevsky, and Popplemann in 2012 and published in their paper "Practical Lattice Based Cryptography – A Signature Scheme for Embedded Systems." These papers laid the groundwork for a variety of recent signature algorithms some based directly on the ring learning with errors problem and some which are not tied to the same hard RLWE problems.

• Post-quantum cryptography
• Ring learning with errors
• Lattice-based cryptography
• Ring learning with errors key exchange
• Short integer solution (SIS) problem
• Kyber

• Post-quantum cryptography

• CS1 maint: multiple names: authors list
• Articles with short description
• Short description is different from Wikidata
• Wikipedia articles that are too technical from October 2018
• All articles that are too technical
• Articles to be expanded from December 2009
• All articles to be expanded