Learning with errors – Wikipedia

In cryptography, Learning with errors (LWE) is a mathematical problem that is widely used in cryptography to create secure encryption 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 the computational problem of inferring a linear

${displaystyle n}$

-ary function

${displaystyle f}$

over a finite ring 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 integers modulo

${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}rightarrow 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 yin 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 by Oded Regev in 2005^[3] (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,^[3][4] such as the ring learning with errors key exchange by Peikert.^[5]

Definition[edit]

Denote by

${displaystyle mathbb {T} =mathbb {R} /mathbb {Z} }$

the additive group on reals modulo one.
Let

${displaystyle mathbf {s} in mathbb {Z} _{q}^{n}}$

be a fixed vector.
Let

${displaystyle phi }$

be a fixed probability distribution over

${displaystyle mathbb {T} }$

.
Denote by

${displaystyle A_{mathbf {s} ,phi }}$

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 ein mathbb {T} }$

   from the distribution

   ${displaystyle phi }$

   ,

3. Evaluate
   ${displaystyle t=langle mathbf {a} ,mathbf {s} rangle /q+e}$

   , where

   ${displaystyle textstyle langle mathbf {a} ,mathbf {s} rangle =sum _{i=1}^{n}a_{i}s_{i}}$

   is the standard inner product in

   ${displaystyle mathbb {Z} _{q}^{n}}$

   , the division is done in the field of reals (or more formally, this “division by

   ${displaystyle q}$

   ” is notation for the group homomorphism

   ${displaystyle mathbb {Z} _{q}longrightarrow mathbb {T} }$

   mapping

   ${displaystyle 1in 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)}$

   .

The learning with errors problem

${displaystyle mathrm {LWE} _{q,phi }}$

is to find

${displaystyle mathbf {s} in mathbb {Z} _{q}^{n}}$

, given access to polynomially many samples of choice from

${displaystyle A_{mathbf {s} ,phi }}$

.

For every

${displaystyle alpha >0}$

${displaystyle D_{alpha }}$

the one-dimensional Gaussian with zero mean and variance

${displaystyle alpha ^{2}/(2pi )}$

, 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 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 {LWE} _{q,Psi _{alpha }}}$

Decision version[edit]

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

${displaystyle mathbb {Z} _{q}^{n}times mathbb {T} }$

(practically, some discretized version of it). Regev^[3] 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[edit]

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 {langle mathbf {a} _{i},mathbf {s} rangle -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.

Solving search assuming decision[edit]

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 kin Z_{q}}$

, and do the following. Choose a number

${displaystyle rin 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,ldots ,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,ldots ,r,ldots ,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 0mod q_{ell }}$

, and then use the Chinese remainder theorem to recover

${displaystyle mathbf {s} _{j}}$

.

Average case hardness[edit]

Regev^[3] showed the random self-reducibility of the LWE and DLWE 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}+langle mathbf {a} _{i},mathbf {t} rangle )/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/operatorname {poly} (n)}$

, and for distributions

${displaystyle A_{mathbf {s} ‘,chi }}$

, with

${displaystyle mathbf {s} ‘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} ‘,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}+langle mathbf {a} _{i},mathbf {t} rangle )/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, 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[edit]

Regev’s result[edit]

For a n-dimensional lattice

${displaystyle L}$

, let smoothing parameter

${displaystyle eta _{varepsilon }(L)}$

denote the smallest

${displaystyle s}$

such that

${displaystyle rho _{1/s}(L^{*}setminus {mathbf {0} })leq varepsilon }$

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}$

${displaystyle xin 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 rgeq phi (L)}$

. The goal is to output a sample from

${displaystyle D_{L,r}}$

. Regev shows that there is a reduction from

${displaystyle operatorname {GapSVP} _{100{sqrt {n}}gamma (n)}}$

to

${displaystyle DGS_{{sqrt {n}}gamma (n)/lambda (L^{*})}}$

for any function

${displaystyle gamma (n)geq 1}$

.

Regev then shows that there exists an efficient quantum algorithm for

${displaystyle DGS_{{sqrt {2n}}eta _{varepsilon }(L)/alpha }}$

given access to an oracle for

${displaystyle mathrm {LWE} _{q,Psi _{alpha }}}$

for integer

${displaystyle q}$

and

${displaystyle alpha in (0,1)}$

such that

${displaystyle alpha q>2{sqrt {n}}}$

${displaystyle q}$

, for creating a cryptosystem, the modulus

${displaystyle q}$

has to be polynomial in

${displaystyle n}$

.

Peikert’s result[edit]

Peikert proves^[4] that there is a probabilistic polynomial time reduction from the

${displaystyle operatorname {GapSVP} _{zeta ,gamma }}$

problem in the worst case to solving

${displaystyle mathrm {LWE} _{q,Psi _{alpha }}}$

using

${displaystyle operatorname {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 qgeq (zeta /{sqrt {n}})omega {sqrt {log n}})}$

.

Use in cryptography[edit]

The LWE 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 the lattice problems

${displaystyle mathrm {GapSVP} _{gamma }}$

(for

${displaystyle gamma }$

as above) and

${displaystyle mathrm {SIVP} _{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 {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[edit]

Regev^[3] 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

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},ldots ,mathbf {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 (mathbf {a} _{i},b_{i}=langle mathbf {a} _{i},mathbf {s} rangle /q+e_{i})_{i=1}^{m}}$

  

• Encryption: The encryption of a bit
  ${displaystyle xin {0,1}}$

  is done by choosing a random subset

  ${displaystyle S}$

  of

  ${displaystyle [m]}$

  and then defining

  ${displaystyle operatorname {Enc} (x)}$

  as

${displaystyle left(sum _{iin S}mathbf {a} _{i},{frac {x}{2}}+sum _{iin S}b_{i}right)}$

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 {T} }$

CCA-secure cryptosystem[edit]

This section needs expansion. You can help by adding to it. (December 2009)

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

Key exchange[edit]

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.

See also[edit]

References[edit]