Learning with errors
Introduction 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 -ary function  over a finite ring from given samples  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  denote the ring of integers modulo  and let denote the set of -vectors over . There exists a certain unknown linear function , and the input to the LWE problem is a sample of pairs , where  and , so that with high probability . Furthermore, the deviation from the equality is according to some known noise model. The problem calls for finding the function , 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  the additive group on reals modulo one. Let  be a fixed vector.Let  be a fixed probability distribution over .Denote by  the distribution on  obtained as follows.# Pick a vector  from the uniform distribution over , # Pick a number  from the distribution ,# Evaluate , where  is the standard inner product in , the division is done in the field of reals (or more formally, this "division by " is notation for the group homomorphism  mapping  to ), and the final addition is in .# Output the pair .The '''learning with errors problem'''  is to find , given access to polynomially many samples of choice from .For every , denote by  the one-dimensional Gaussian with zero mean and variance, that is, the density function is  where , and let  be the distribution on  obtained by considering  modulo one. The version of LWE considered in most of the results would be
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  (practically, some discretized version of it). Regev showed that the ''decision'' and ''search'' versions are equivalent when  is a prime bounded by some polynomial in .=== 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 . If the solver returns a candidate , for all , calculate . 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  one coordinate at a time. To obtain the first coordinate, , make a guess , and do the following. Choose a number  uniformly at random. Transform the given samples  as follows. Calculate . Send the transformed samples to the decision solver.If the guess  was correct, the transformation takes the distribution  to itself, and otherwise, since  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  is bounded by some polynomial in , it only takes polynomial time to guess every possible value for  and use the solver to see which one is correct.After obtaining , we follow an analogous procedure for each other coordinate . Namely, we transform our  samples the same way, and transform our  samples by calculating , where the  is in the  coordinate.Peikert showed that this reduction, with a small modification, works for any  that is a product of distinct, small (polynomial in ) primes. The main idea is if , for each , guess and check to see if  is congruent to , and then use the Chinese remainder theorem to recover .=== Average case hardness ===Regev showed the random self-reducibility of the '''LWE''' and '''DLWE''' problems for arbitrary  and . Given samples  from , it is easy to see that  are samples from .So, suppose there was some set  such that , and for distributions , with , '''DLWE''' was easy.Then there would be some distinguisher , who, given samples , could tell whether they were uniformly random or from . If we need to distinguish uniformly random samples from , where  is chosen uniformly at random from , we could simply try different values  sampled uniformly at random from , calculate  and feed these samples to . Since  comprises a large fraction of , with high probability, if we choose a polynomial number of values for , we will find one such that , and  will successfully distinguish the samples.Thus, no such  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 , let ''smoothing parameter''  denote the smallest  such that  where  is the dual of  and  is extended to sets by summing over function values at each element in the set. Let  denote the discrete Gaussian distribution on  of width  for a lattice  and real . The probability of each  is proportional to .The ''discrete Gaussian sampling problem''(DGS) is defined as follows: An instance of  is given by an -dimensional lattice  and a number . The goal is to output a sample from . Regev shows that there is a reduction from  to  for any function .Regev then shows that there exists an efficient quantum algorithm for  given access to an oracle for  for integer  and  such that . This implies the hardness for LWE. Although the proof of this assertion works for any , for creating a cryptosystem, the modulus  has to be polynomial in .=== Peikert's result ===Peikert proves that there is a probabilistic polynomial time reduction from the  problem in the worst case to solving  using  samples for parameters , ,  and .
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  (for  as above) and  with ). In 2009, Peikert proved a similar result assuming only the classical hardness of the related problem . 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  and a probability distribution  on . The setting of the parameters used in proofs of correctness and security is* , usually a prime number between  and . *  for an arbitrary constant *  for , where  is a probability distribution obtained by sampling a normal variable with mean  and standard variation  and reducing the result modulo .The cryptosystem is then defined by:* ''Private key'': Private key is an  chosen uniformly at random. * ''Public key'': Choose  vectors  uniformly and independently. Choose error offsets  independently according to . The public key consists of * ''Encryption'': The encryption of a bit  is done by choosing a random subset  of  and then defining  as:: * ''Decryption'': The decryption of  is  if  is closer to  than to , and  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  and  can be used to distinguish between  and the uniform distribution over === 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.=== Ring learning with errors signature (RLWE-SIG) ===Main article: Ring learning with errors signatureA RLWE version of the classic Feige–Fiat–Shamir Identification protocol was created and converted to a digital 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.
See also *Post-quantum cryptography*Ring learning with errors*Lattice-based cryptography*Ring learning with errors key exchange*Short integer solution (SIS) problem* Kyber
References