Learning with errors

Learning with errors (LWE) is the computational problem of inferring a linear formula_1-ary function formula_2 over a finite ring from given samples formula_3 some of which may be erroneous.
The LWE problem is conjectured to be hard to solve, and thus be useful in cryptography.
More precisely, the LWE problem is defined as follows. Let formula_4 denote the ring of integers modulo formula_5 and let
formula_6 denote the set of formula_1-vectors over formula_4. There exists a certain unknown linear function formula_9, and the input to the LWE problem is a sample of pairs formula_10, where formula_11 and formula_12, so that with high probability formula_13. Furthermore, the deviation from the equality is according to some known noise model. The problem calls for finding the function formula_2, 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.
Definition.
Denote by formula_15 the additive group on reals modulo one. 
Let formula_16 be a fixed vector.
Let formula_17 be a fixed probability distribution over formula_18.
Denote by formula_19 the distribution on formula_20 obtained as follows.
The learning with errors problem formula_34 is to find formula_16, given access to polynomially many samples of choice from formula_19.
For every formula_37, denote by formula_38 the one-dimensional Gaussian with zero mean and variance
formula_39, that is, the density function is formula_40 where formula_41, and let formula_42 be the distribution on formula_18 obtained by considering formula_38 modulo one. The version of LWE considered in most of the results would be formula_45
Decision version.
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 formula_20 (practically, some discretized version of it). Regev showed that the "decision" and "search" versions are equivalent when formula_5 is a prime bounded by some polynomial in formula_1.
Solving decision assuming search.
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 formula_49. If the solver returns a candidate formula_50, for all formula_51, calculate formula_52. If the samples are from an LWE distribution, then the results of this calculation will be distributed according formula_53, but if the samples are uniformly random, these quantities will be distributed uniformly as well.
Solving search assuming decision.
For the other direction, given a solver for the decision problem, the search version can be solved as follows: Recover formula_50 one coordinate at a time. To obtain the first coordinate, formula_55, make a guess formula_56, and do the following. Choose a number formula_57 uniformly at random. Transform the given samples formula_49 as follows. Calculate formula_59. Send the transformed samples to the decision solver.
If the guess formula_60 was correct, the transformation takes the distribution formula_61 to itself, and otherwise, since formula_5 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 formula_5 is bounded by some polynomial in formula_1, it only takes polynomial time to guess every possible value for formula_60 and use the solver to see which one is correct.
After obtaining formula_55, we follow an analogous procedure for each other coordinate formula_67. Namely, we transform our formula_68 samples the same way, and transform our formula_69 samples by calculating formula_70, where the formula_71 is in the formula_72 coordinate.
Peikert showed that this reduction, with a small modification, works for any formula_5 that is a product of distinct, small (polynomial in formula_1) primes. The main idea is if formula_75, for each formula_76, guess and check to see if formula_67 is congruent to formula_78, and then use the Chinese remainder theorem to recover formula_67.
Average case hardness.
Regev showed the random self-reducibility of the LWE and DLWE problems for arbitrary formula_5 and formula_53. Given samples formula_82 from formula_61, it is easy to see that formula_84 are samples from formula_85.
So, suppose there was some set formula_86 such that formula_87, and for distributions formula_88, with formula_89, DLWE was easy.
Then there would be some distinguisher formula_90, who, given samples formula_91, could tell whether they were uniformly random or from formula_88. If we need to distinguish uniformly random samples from formula_61, where formula_50 is chosen uniformly at random from formula_27, we could simply try different values formula_96 sampled uniformly at random from formula_27, calculate formula_84 and feed these samples to formula_90. Since formula_100 comprises a large fraction of formula_27, with high probability, if we choose a polynomial number of values for formula_102, we will find one such that formula_103, and formula_90 will successfully distinguish the samples.
Thus, no such formula_100 can exist, meaning LWE and DLWE are (up to a polynomial factor) as hard in the average case as they are in the worst case.
Hardness results.
Regev's result.
For a "n"-dimensional lattice formula_106, let "smoothing parameter" formula_107 denote the smallest formula_108 such that formula_109 where formula_110 is the dual of formula_106 and formula_41 is extended to sets by summing over function values at each element in the set. Let formula_113 denote the discrete Gaussian distribution on formula_106 of width formula_71 for a lattice formula_106 and real formula_117. The probability of each formula_118 is proportional to formula_119.
The "discrete Gaussian sampling problem"(DGS) is defined as follows: An instance of formula_120 is given by an formula_1-dimensional lattice formula_106 and a number formula_123. The goal is to output a sample from formula_113. Regev shows that there is a reduction from formula_125 to formula_126 for any function formula_127.
Regev then shows that there exists an efficient quantum algorithm for formula_128 given access to an oracle for formula_45 for integer formula_5 and formula_131 such that formula_132. This implies the hardness for LWE. Although the proof of this assertion works for any formula_5, for creating a cryptosystem, the formula_5 has to be polynomial in formula_1.
Peikert's result.
Peikert proves that there is a probabilistic polynomial time reduction from the formula_136 problem in the worst case to solving formula_45 using formula_138 samples for parameters formula_131, formula_140, formula_141 and formula_142.
Use in cryptography.
The LWE problem serves as a versatile problem used in construction of several cryptosystems. In 2005, Regev showed that the decision version of LWE is hard assuming quantum hardness of the lattice problems formula_143 (for formula_144 as above) and formula_145 with formula_146). In 2009, Peikert proved a similar result assuming only the classical hardness of the related problem formula_147. 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 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 formula_148 and a probability distribution formula_53 on formula_18. The setting of the parameters used in proofs of correctness and security is
The cryptosystem is then defined by:
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 formula_159 and formula_161 can be used to distinguish between formula_181 and the uniform distribution over formula_182
CCA-secure cryptosystem.
Peikert proposed a system that is secure even against any chosen-ciphertext attack.
Key exchange.
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 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 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 selected for Google's post-quantum experiment, uses Peikert's scheme with variation in the error distribution.