Learning with errors

Definition

Denote by T = R / Z the additive group on reals modulo one. Denote by A s , ϕ the distribution on Z q n × T obtained by choosing a vector a ∈ Z q n uniformly at random, choosing e according to a probability distribution ϕ on T and outputting ( a , ⟨ a , s ⟩ / q + e ) for some fixed vector s ∈ Z q n . Here ⟨ a , s ⟩ = ∑ i = 1 n a i s i is the standard inner product Z q n × Z q n ⟶ Z q , the division is done in the field of reals (or more formally, this "division by q " is notation for the group homomorphism Z q ⟶ T mapping 1 ∈ Z q to 1 / q + Z ∈ T ), and the final addition is in T .

The learning with errors problem L W E q , ϕ is to find s ∈ Z q n , given access to polynomially many samples of choice from A s , ϕ .

For every α > 0 , denote by D α the one-dimensional Gaussian with density function D α ( x ) = ρ α ( x ) / α where ρ α ( x ) = e − π ( | x | / α ) 2 , and let Ψ α be the distribution on T obtained by considering D α modulo one. The version of LWE considered in most of the results would be L W E q , Ψ α

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 Z q n × T (practically, some discretized version of it). Regev showed that the decision and search versions are equivalent when q is a prime bounded by some polynomial in n .

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 { ( a i , b i ) } ⊂ Z q n × T . If the solver returns a candidate s , for all i , calculate { ⟨ a i , s ⟩ − b i } . If the samples are from an LWE distribution, then the results of this calculation will be distributed according χ , 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 s one coordinate at a time. To obtain the first coordinate, s 1 , make a guess k ∈ Z q , and do the following. Choose a number r ∈ Z q uniformly at random. Transform the given samples { ( a i , b i ) } ⊂ Z q n × T as follows. Calculate { ( a i + ( r , 0 , … , 0 ) , b i + ( r k ) / q ) } . Send the transformed samples to the decision solver.

If the guess k was correct, the transformation takes the distribution A s , χ to itself, and otherwise, since 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 q is bounded by some polynomial in n , it only takes polynomial time to guess every possible value for k and use the solver to see which one is correct.

After obtaining s 1 , we follow an analogous procedure for each other coordinate s j . Namely, we transform our b i samples the same way, and transform our a i samples by calculating a i + ( 0 , … , r , … , 0 ) , where the r is in the j t h coordinate.

Peikert showed that this reduction, with a small modification, works for any q that is a product of distinct, small (polynomial in n ) primes. The main idea is if q = q 1 q 2 ⋯ q t , for each q ℓ , guess and check to see if s j is congruent to 0 mod q ℓ , and then use the Chinese remainder theorem to recover s j .

Average case hardness

Regev showed the Random self-reducibility of the LWE and DLWE problems for arbitrary q and χ . Given samples { ( a i , b i ) } from A s , χ , it is easy to see that { ( a i , b i + ⟨ a i , t ⟩ ) / q } are samples from A s + t , χ .

So, suppose there was some set S ⊂ Z q n such that | S | / | Z q n | = 1 / p o l y ( n ) , and for distributions A s ′ , χ , with s ′ ← S , DLWE was easy.

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

Thus, no such S 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.

Regev's result

For a n-dimensional lattice L , let smoothing parameter η ϵ ( L ) denote the smallest s such that ρ 1 / s ( L ∗ ∖ { 0 } ) ≤ ϵ where L ∗ is the dual of L and ρ α ( x ) = e − π ( | x | / α ) 2 is extended to sets by summing over function values at each element in the set. Let D L , r denote the discrete Gaussian distribution on L of width r for a lattice L and real r > 0 . The probability of each x ∈ L is proportional to ρ r ( x ) .

The discrete Gaussian sampling problem(DGS) is defined as follows: An instance of D G S ϕ is given by an n -dimensional lattice L and a number r ≥ ϕ ( L ) . The goal is to output a sample from D L , r . Regev shows that there is a reduction from G a p S V P 100 n γ ( n ) to D G S n γ ( n ) / λ ( L ∗ ) for any function γ ( n ) .

Regev then shows that there exists an efficient quantum algorithm for D G S 2 n η ϵ ( L ) / α given access to an oracle for L W E q , Ψ α for integer q and α ∈ ( 0 , 1 ) such that α q > 2 n . This implies the hardness for L W E . Although the proof of this assertion works for any q , for creating a cryptosystem, the q has to be polynomial in n .

Peikert's result

Peikert proves that there is a probabilistic polynomial time reduction from the G a p S V P ζ , γ problem in the worst case to solving L W E q , Ψ α using p o l y ( n ) samples for parameters α ∈ ( 0 , 1 ) , γ ( n ) ≥ n / ( α log ⁡ n ) , ζ ( n ) ≥ γ ( n ) and q ≥ ( ζ / n ) ω log ⁡ n ) .

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 G a p S V P γ (for γ as above) and S I V P t with t=Õ(n/ α ). In 2009, Peikert proved a similar result assuming only the classical hardness of the related problem G a p S V P ζ , γ . 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 m , q and a probability distribution χ on T . 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 0 and 1 can be used to distinguish between A s , χ and the uniform distribution over Z q n × T

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 LWE problem. In 2014, Peikert presented a key transport scheme following the same basic idea of Ding's, where the new idea of sending additional 1 bit signal for rounding in Ding's construction is also utilized. The "new hope" implementation selected for Google's post quantum experiment, uses Peikert's scheme with variation in the error distribution.