# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 5 Learning with Errors (LWE)
### The Learning with Errors Problem
: _Fix a size parameter \(n\geq 1\), \(q\geq 2\) and an error probability distribution \(\chi\) on \(\mathbb{Z}_{q}\). Let \(A_{s,\chi}\) on \(\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}\) be the probability distribution choosing a vector \(a\in\mathbb{Z}_{q}\) uniformly at random, choosing \(e\in\mathbb{Z}_{q}\) according to \(\chi\), and outputting \((a,\langle a,s\rangle+e)\) where additions are performed in \(\mathbb{Z}_{q}\). An algorithm solves the LWE problem with modulus \(q\) and error distribution \(\chi\) if for any \(s\in\mathbb{Z}_{q}^{n}\), vector with \(n\) coefficients, and given enough samples from \(A_{s,\chi}\), it outputs \(s\) with high probability._  
**Definition 27**. : _(search-LWE problem). The search-LWE problem, with parameters \(n,q,\chi,m\), states that, given \(m\) independent samples \((a_{i},b_{i})\in\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}\) derived from a uniformly random \(s\in\mathbb{Z}_{q}^{n}\) and fixed for all samples, find \(s\)._  
The above problem can become a decision problem where the question is which distribution to use. **Definition 28**. : _(decision-LWE problem). The decision-LWE problem with parameters \(n,q,\chi,m\) states that, given \(m\) independent samples \((a_{i},b_{i})\in\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}\), where there is a way to generate samples from \(A_{s,\chi}\) as above and also generate uniformly random distributed samples of \((a_{i},b_{i})\) from \(\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}\) (uniform distribution \(U\)), determine whether the samples are generated from \(A_{s,\chi}\) or \(U\)._  
**Definition 29**. : _A function \(f(n)\) is defined as a negligible function in \(n\), if \(\lim_{n\rightarrow\infty}\ n^{c}f(n)=0\) for any positive constant \(c\)._  
**Definition 30**. : _If \(\phi\) denotes an arbitrary real-valued function on lattices, an instance of the discrete Gaussian sampling (DGS) problem, \(DGS_{\phi}\), is given by an \(n\)-dimensional lattice \(\mathcal{L}\) and a number \(r>\phi(\mathcal{L})\). The task is to extract a sample from \(D_{\mathcal{L}},r\)._  
**Definition 31**. : _For positive real \(\epsilon>0\) and an \(n\)-dimensional lattice \(\mathcal{L}\), the smoothing parameter \(\eta_{\epsilon}(L)\) is defined to be the smallest \(s\) such that \(\rho_{1/s}(L^{*}\setminus\{0\})\leq\epsilon\)._  
**Theorem 4** ([PERSON]). : _Let \(\epsilon=\epsilon(n)\) be some negligible function of \(n\). Also, let \(p=p(n)\) be some integer and \(a=a(n)\in(0,1)\) such that \(ap>2\sqrt{n}\). Assume that we have access to an oracle \(W\) that solves \(LWE_{p,\Psi_{a}}\) given a polynomial number of samples. Then, there exists an efficient quantum algorithm for \(DGS_{\sqrt{2n}\cdot\eta_{\epsilon}(L)/a}\)._The following theorem was proven by [PERSON] [49] and connects the worst-case lattice problems to the LWE problem, providing a robust indication that the LWE problem is hard. For a real positive \(a\), \(\bar{\Psi}_{a}\) denotes the distribution on \(\mathbb{Z}_{q}\) by sampling a normal variable with mean 0 and standard deviation \(aq/\sqrt{2\pi}\), where the result is rounded to the nearest integer and reduced modulo \(q\). **Theorem 5** ([PERSON]). : _Assume that we have access to an oracle that solves the LWE problem with parameters \(n,m,q,\bar{\Psi}_{a}\), where \(ap>2\sqrt{n}\), \(q\leq poly(n)\) is prime and \(m\leq poly(n)\). Then, there exists a quantum algorithm running in time \(poly(n)\) for solving the (worst-case) lattice problems \(SIVP_{\hat{O}(n/a)}\) and (the decision variant of) \(SVP_{\hat{O}(n/a)}\) in any lattice of dimension \(n\)._