Learning with errors

From Wikipedia, the free encyclopedia
Jump to: navigation, search

Learning with errors (LWE) is a problem in machine learning that is conjectured to be hard to solve. It is a generalization of the parity learning problem, introduced[1] by Oded Regev in 2005. Regev showed, furthermore, that the LWE problem is as hard to solve as several worst-case lattice problems. The LWE problem has recently[1][2] been used as a hardness assumption to create public-key cryptosystems.

An algorithm is said to solve the LWE problem if, when given access to samples (x,y) where x\in \mathbb{Z}_q^n and y \in \mathbb{Z}_q, with the assurance, for some fixed linear function f:\mathbb{Z}_q^n \rightarrow \mathbb{Z}_q, that y=f(x) with high probability and deviates from it according to some known noise model, the algorithm can recreate f or some close approximation of it with high probability.

Definition[edit]

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

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

For every \alpha > 0, denote by D_\alpha the one-dimensional Gaussian with density function D_\alpha(x)=\rho_\alpha(x)/\alpha where \rho_\alpha(x)=e^{-\pi(|x|/\alpha)^2}, and let \Psi_\alpha be the distribution on \mathbb{T} obtained by considering D_\alpha modulo one. The version of LWE considered in most of the results would be 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 \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 q is a prime bounded by some polynomial in 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 \{(\mathbf{a_i},\mathbf{b_i})\} \subset \mathbb{Z}^n_q \times \mathbb{T}. If the solver returns a candidate \mathbf{s}, for all i, calculate \{\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 \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 \mathbf{s} one coordinate at a time. To obtain the first coordinate, \mathbf{s}_1, make a guess k \in Z_q, and do the following. Choose a number r \in \mathbb{Z}_q uniformly at random. Transform the given samples \{(\mathbf{a_i},\mathbf{b_i})\} \subset \mathbb{Z}^n_q \times \mathbb{T} as follows. Calculate \{(\mathbf{a_i}+(r,0,\ldots,0),\mathbf{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_{\mathbf{s},\chi} 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 \mathbf{s}_1, we follow an analogous procedure for each other coordinate \mathbf{s}_j. Namely, we transform our \mathbf{b_i} samples the same way, and transform our \mathbf{a_i} samples by calculating \mathbf{a_i} + (0, \ldots, r, \ldots, 0), where the r is in the j^{th} coordinate. [1]

Peikert[2] 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 \cdots q_t, for each q_{\ell}, guess and check to see if \mathbf{s}_j is congruent to 0 \mod q_{\ell}, and then use the Chinese remainder theorem to recover \mathbf{s}_j.

Average case hardness[edit]

Regev[1] showed the Random self-reducibility of the LWE and DLWE problems for arbitrary q and \chi. Given samples \{(\mathbf{a_i},\mathbf{b_i})\} from A_{\mathbf{s},\chi}, it is easy to see that \{(\mathbf{a_i},\mathbf{b_i}) + (\langle \mathbf{a_i}, \mathbf{t} \rangle)/q\} are samples from A_{\mathbf{s} + \mathbf{t},\chi}.

So, suppose there was some set \mathcal{S} \subset \mathbb{Z}_q^n such that |\mathcal{S}|/|\mathbb{Z}_q^n| = 1/poly(n), and for distributions A_{\mathbf{s'},\chi}, with \mathbf{s'} \leftarrow \mathcal{S}, DLWE was easy.

Then there would be some distinguisher \mathcal{A}, who, given samples \{(\mathbf{a_i},\mathbf{b_i}) \}, could tell whether they were uniformly random or from A_{\mathbf{s'},\chi}. If we need to distinguish uniformly random samples from A_{\mathbf{s},\chi}, where \mathbf{s} is chosen uniformly at random from \mathbb{Z}_q^n, we could simply try different values \mathbf{t} sampled uniformly at random from \mathbb{Z}_q^n, calculate \{(\mathbf{a_i},\mathbf{b_i}) + (\langle \mathbf{a_i}, \mathbf{t} \rangle)/q\} and feed these samples to \mathcal{A}. Since \mathcal{S} comprises a large fraction of \mathbb{Z}_q^n, with high probability, if we choose a polynomial number of values for \mathbf{t}, we will find one such that \mathbf{s} + \mathbf{t} \in \mathcal{S}, and \mathcal{A} will successfully distinguish the samples.

Thus, no such \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 L, let smoothing parameter \eta_\epsilon(L) denote the smallest s such that \rho_{1/s}(L^*\setminus \{\mathbf{0}\}) \leq \epsilon where L^* is the dual of L and \rho_\alpha(x)=e^{-\pi(|x|/\alpha)^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 \in L is proportional to \rho_r(x).

The discrete Gaussian sampling problem(DGS) is defined as follows: An instance of DGS_\phi is given by an n-dimensional lattice L and a number r \geq \phi(L). The goal is to output a sample from D_{L,r}. Regev shows that there is a reduction from GapSVP_{100\sqrt{n}\gamma(n)} to DGS_{\sqrt{n}\gamma(n)/\lambda(L^*)} for any function \gamma(n).

Regev then shows that there exists an efficient quantum algorithm for DGS_{\sqrt{2n}\eta_\epsilon(L)/\alpha} given access to an oracle for LWE_{q,\Psi_\alpha} for integer q and \alpha \in (0,1) such that \alpha q > 2\sqrt{n}. This implies the hardness for LWE. 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[edit]

Peikert proves[2] that there is a probabilistic polynomial time reduction from the GapSVP_{\zeta,\gamma} problem in the worst case to solving LWE_{q,\Psi_\alpha} using poly(n) samples for parameters \alpha \in (0,1), \gamma(n)\geq n/(\alpha \sqrt{\log{n}}), \zeta(n) \geq \gamma(n) and q \geq (\zeta/\sqrt{n}) \omega \sqrt{\log{n}}).

Use in Cryptography[edit]

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 GapSVP_\gamma (for \gamma as above) and SIVP_{t} with t=Õ(n/\alpha). In 2009, Peikert[2] proved a similar result assuming only the classical hardness of the related problem 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[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 m,q and a probability distribution \chi on \mathbb{T}. The setting of the parameters used in proofs of correctness and security is

  • q \geq 2 , a prime number between n^2 and 2n^2.
  • m=(1+\epsilon)(n+1) \log{q} for an arbitrary constant \epsilon
  • \chi=\Psi_{\alpha(n)} for \alpha(n) \in o(1/\sqrt{n}\log{n})

The cryptosystem is then defined by:

  • Private Key: Private key is an \mathbf{s}\in \mathbb{Z}^n_q chosen uniformly at random.
  • Public Key: Choose m vectors a_1,\ldots,a_m \in  \mathbb{Z}^n_q uniformly and independently. Choose error offsets e_1,\ldots,e_m \in \mathbb{T} independently according to \chi. The public key consists of (a_i,b_i=\langle a_i,\mathbf{s} \rangle/q + e_i)^m_{i=1}
  • Encryption: The encryption of a bit x \in \{0,1\} is done by choosing a random subset S of [m] and then defining Enc(x) as (\sum_{i \in S} a_i, x/2 + \sum_{i \in S} b_i)
  • Decryption: The decryption of (a,b) is 0 if b-\langle a, \mathbf{s} \rangle/q is closer to 0 than to \frac{1}{2}, and 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 0 and 1 can be used to distinguish between A_{s,\chi} and the uniform distribution over \mathbb{Z}^n_q \times \mathbb{Z}_q

CCA-secure cryptosystem[edit]

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

See also[edit]

References[edit]

  1. ^ a b c d e f g h Oded Regev, “On lattices, learning with errors, random linear codes, and cryptography,” in Proceedings of the thirty-seventh annual ACM symposium on Theory of computing (Baltimore, MD, USA: ACM, 2005), 84-93, http://portal.acm.org/citation.cfm?id=1060590.1060603.
  2. ^ a b c d e f Chris Peikert, “Public-key cryptosystems from the worst-case shortest vector problem: extended abstract,” in Proceedings of the 41st annual ACM symposium on Theory of computing (Bethesda, MD, USA: ACM, 2009), 333-342, http://portal.acm.org/citation.cfm?id=1536414.1536461.
  3. ^ Chris Peikert and Brent Waters, “Lossy trapdoor functions and their applications,” in Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, British Columbia, Canada: ACM, 2008), 187-196, http://portal.acm.org/citation.cfm?id=1374406.
  4. ^ Craig Gentry, Chris Peikert, and Vinod Vaikuntanathan, “Trapdoors for hard lattices and new cryptographic constructions,” in Proceedings of the 40th annual ACM symposium on Theory of computing (Victoria, British Columbia, Canada: ACM, 2008), 197-206, http://portal.acm.org/citation.cfm?id=1374407.