Learning with errors

Learning with errors (LWE) is a problem in machine learning. A generalization of the parity learning problem, it has recently^[1][2] been used to create public-key cryptosystems based on worst-case hardness of some lattice problems. The problem was introduced^[1] by Oded Regev in 2005.

Given access to samples ${\displaystyle (x,y)}$ where ${\displaystyle x\in \mathbb {Z} _{q}^{n}}$ and ${\displaystyle y\in \mathbb {Z} _{q}}$, with assurance that, for some fixed linear function ${\displaystyle f:\mathbb {Z} _{q}^{n}\rightarrow \mathbb {Z} _{q}}$ ${\displaystyle ,y=f(x)}$ with high probability and deviates from it according to some known noise model, the algorithm must be able to recreate ${\displaystyle f}$ or some close approximation of it.

Definition[]

Denote by ${\displaystyle \mathbb {T} =\mathbb {R} /\mathbb {Z} }$ the additive group on reals modulo one. Denote by ${\displaystyle A_{s,\phi }}$ the distribution on ${\displaystyle \mathbb {Z} _{q}^{n}\times \mathbb {T} }$ obtained by choosing a vector ${\displaystyle \mathbf {a} \in \mathbb {Z} _{q}^{n}}$ uniformly at random, choosing ${\displaystyle e}$ according to a probability distribution ${\displaystyle \phi}$ on ${\displaystyle \mathbb{T}}$ and outputting ${\displaystyle (\mathbf {a} ,\langle \mathbf {a} ,s\rangle /q+e)}$ for some fixed vector ${\displaystyle \mathbf {s} \in \mathbb {Z} _{q}^{n}}$ where the division is done in the field of reals, and the addition in ${\displaystyle \mathbb{T}}$.

The learning with errors problem ${\displaystyle LWE_{q,\phi }}$ is to find ${\displaystyle s\in \mathbb {Z} _{q}^{n}}$, given access to polynomially many samples of choice from ${\displaystyle A_{s,\phi }}$.

For every ${\displaystyle \alpha>0}$, denote by ${\displaystyle D_\alpha}$ denote the one-dimensional Gaussian with density function ${\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 LWE_{q,\Psi _{\alpha }}}$

Decision version[]

The LWE problem described above is the search version of the problem. In the decision version, 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^[1] 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[]

Intuitively, it is easy to see that if we have a procedure for the search problem, the decision version can be solved easily: just feed the input samples for the decision version to the procedure for the search problem, and check if the ${\displaystyle s}$ returned by the search procedure can generate the input pairs modulo some noise.

Solving search assuming decision[]

For the other direction, suppose that we have a procedure for the decision problem, the search version can be solved as follows: Recover the ${\displaystyle s}$ one co-ordinate at a time. Suppose we are guessing the first co-ordinate, and we are trying to test if ${\displaystyle s_{i}=k}$ for a fixed ${\displaystyle k\in Z_{q}}$. Choose a number ${\displaystyle l\in \mathbb {Z} _{q}^{*}}$ uniformly at random. Denote the given samples by ${\displaystyle \{(a_{i},b_{i})\}\subset \mathbb {Z} _{q}^{n}\times \mathbb {T} }$. Feed the transformed pairs ${\displaystyle \{(a_{i}+(l,0,\ldots ,0),b_{i}+(lk)/q)\}}$ to the decision problem. It is easy to see that if the guess ${\displaystyle k}$ was correct, the transformation takes the distribution ${\displaystyle A_{s,\chi }}$ to itself, and otherwise takes it to the uniform distribution. Since we have a procedure for the decision version which distinguishes between these two types of distributions, and errs with very small probability, we can test if the guess ${\displaystyle k}$ equals the first co-ordinate. Since ${\displaystyle q}$ is a prime bounded by some polynomial in ${\displaystyle n}$, ${\displaystyle k}$ can only take polynomially many values, and each co-ordinate can be efficiently guessed with high probability.

Hardness results[]

Regev's result[]

For a n-dimensional lattice ${\displaystyle L}$, let smoothing parameter ${\displaystyle \eta _{\epsilon }(L)}$ denote the smallest ${\displaystyle s}$ such that ${\displaystyle \rho _{1/s}(L^{*}\setminus \{\mathbf {0} \})\leq \epsilon }$ 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}$. The probability of each ${\displaystyle x \in 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 r\geq \phi (L)}$. The goal is to output a sample from ${\displaystyle D_{L,r}}$. Regev shows that there is a reduction from ${\displaystyle GapSVP_{100{\sqrt {n}}\gamma (n)}}$ to ${\displaystyle DGS_{{\sqrt {n}}\gamma (n)/\lambda (L^{*})}}$ for any function ${\displaystyle \gamma (n)}$.

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

Peikert's result[]

Peikert proves^[2] that there is a probabilistic polynomial time reduction from the ${\displaystyle GapSVP_{\zeta,\gamma}}$ problem in the worst case to solving ${\displaystyle LWE_{q,\Psi _{\alpha }}}$ using ${\displaystyle 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 q\geq (\zeta /{\sqrt {n}})\omega {\sqrt {\log {n}}})}$.

Use in Cryptography[]

The LWE problem serves as a versatile problem used in construction of several^[1][2][3][4] cryptosystems. In 2005, Regev^[1] showed that the decision version of LWE is hard assuming quantum hardness of the lattice problems ${\displaystyle GapSVP_\gamma}$ (for ${\displaystyle \gamma}$ as above) and ${\displaystyle SIVP_{t}}$ with t=Õ(n/${\displaystyle \alpha}$). In 2009, Peikert^[2] proved a similar result assuming only the classical hardness of the related problem ${\displaystyle 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[]

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

• ${\displaystyle q\geq 2}$, a prime 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 =\Psi _{\alpha (n)}}$ for ${\displaystyle \alpha (n)\in o(1/{\sqrt {n}}\log {n})}$

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 a_{1},\ldots ,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 (a_{i},b_{i}=\langle a_{i},\mathbf {s} \rangle /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 Enc(x)}$ as ${\displaystyle (\sum _{i\in S}a_{i},x/2+\sum _{i\in S}b_{i})}$
• Decryption: The decryption of ${\displaystyle (a,b)}$ is ${\displaystyle 0}$ if ${\displaystyle b-\langle a,\mathbf {s} \rangle /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 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 {Z} _{q}}$

CCA-secure cryptosystem[]

Template:Expand section Peikert^[2] proposed a system that is secure even against any chosen-ciphertext attack.

See also[]

• Lattice-based cryptography

References[]