# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 5 Learning with Errors (LWE)
### The Learning with Errors Problem  
The Gauss elimination algorithm is efficient in solving a system of \(m\) equations, finding \(s=(s_{1},s_{2},\ldots,s_{n})\) in the following form:  
\[ \begin{array}{l}a_{11}s_{1}+a_{12}s_{2}+\ldots+a_{1n}s_{n}=b_{1}\\ a_{21}s_{1}+a_{22}s_{2}+\ldots+a_{2n}s_{n}=b_{2}\\ \vdots\\ a_{m1}s_{1}+a_{m2}s_{2}+\ldots+a_{mn}s_{n}=b_{m}\end{array} \]  
An example of the above system of equations in matrix form, given a \(m\times n\) matrix \(A\), a \(n\times 1\) matrix \(s\) and a \(n\times 1\) matrix \(b\), would be like \(A\cdot s=b\), where  
\[A= \begin{pmatrix}11&2&\ldots&3\\ 1&4&\ldots&1\\ \vdots&\ddots&\vdots\\ 5&3&\ldots&9\end{pmatrix} ,\,s= \begin{pmatrix}s_{1}\\ s_{2}\\ \vdots\\ s_{n}\end{pmatrix} ,\,b= \begin{pmatrix}8\\ 13\\ \vdots\\ 2\end{pmatrix} \]  
It is obvious that by adding a matrix \(n\times 1\) matrix \(e\) to the product \(A\cdot s\), even with small values, the equation system becomes  
\[A\cdot s+e=b \tag{1}\]  
The LWE problem states that, given a secret vector \(s=(s_{1},s_{2},...,s_{n})\in\mathbb{Z}^{n}\) with coefficient integer numbers and \(m\) linear equations, such that  
\[ \begin{array}{l}a_{11}s_{1}+a_{12}s_{2}+\ldots+a_{1n}s_{n}\approx b_{1}\\ a_{21}s_{1}+a_{22}s_{2}+\ldots+a_{2n}s_{n}\approx b_{2}\\ \vdots\\ a_{m1}s_{1}+a_{m2}s_{2}+\ldots+a_{mn}s_{n}\approx b_{m}\end{array} \]  
adding a small error to each equation recovers \(s\). The symbol \"\(\approx\)\" is used to claim that, within a certain error, the value approaches the actual response. This problem becomes hard for the Gauss elimination algorithm, and it gives no information from the resulting equations. This problem is considered to be a hard problem as the addition and multiplication of the rows increases the number of errors in each equation, thus the response will be far from the true value and the final row reduced state will be meaningless. Occasionally, short solutions to Equation (1) are required. Therefore, the solution is asked to lie in a subset \(S\subset\mathbb{Z}_{q}^{m}\), where \(S\) can be a subset such that \(S=\{0,1\}\) or, in general, the set of all solutions \(S=[-C,\ldots,C]^{m}\), and each coordinate takes an absolute value bounded by some number \(C\ll q/2\). Another option of the set is the Euclidean ball of asmall radius \(r\), \(S=\mathit{Ball}_{r}^{2}\). The above problem is defined as the short integer solution (SIS) problem, which was first presented in 1996 by [PERSON] [17]. **Definition 24**. : _(Short integer solution problem). The short integer solution problem states that, given \(m\) uniformly random vectors \(a_{i}\in\mathbb{Z}_{q}^{n}\) forming the columns of a matrix \(A\in\mathbb{Z}_{q}^{n\times m}\), find a nonzero integer vector \(z\in\mathbb{Z}^{m}\) of norm \(\|z\|\leq\beta\), such that_  
\[f_{A}(z):=Az=\sum_{i}a_{i}z_{i}=0\in\mathbb{Z}_{q}^{n}.\]  
In terms of a lattice problem, the SIS problem states that, given a lattice \(\mathcal{L}\) generated by \(A\), find a vector \(v\) on the scaled (by \(q\)) dual lattice of \(\mathcal{L}\), i.e., it expresses an average-case SVP on the lattice  
\[\mathcal{L}=\{u\in\mathbb{Z}_{q}^{m}|uA\equiv 0\bmod q\}.\]  
The LWE problem is regarded as an analog of the SIS problem, and for its comprehension and the construction of the LWE cryptosystem, some basic definitions are given below. **Definition 25**. : _Let \(s\in\mathbb{Z}_{q}^{n}\) be a secret vector and \(\chi\) a given distribution on \(\mathbb{Z}_{q}\). The LWE distribution \(A_{s,n,q,\chi}\) generates a sample \((a,b)\in\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}\) or \((A,b)\in\mathbb{Z}_{q}^{m\times n}\times\mathbb{Z}_{q}^{m}\), where \(a\in\mathbb{Z}_{q}^{n}\) is uniformly distributed, and \(b=\langle a,s\rangle+e\), where \(e\leftarrow\chi\) and \(\langle a,s\rangle\) is the inner product of \(a\) and \(s\) in \(\mathbb{Z}_{q}\). If \(b\in\mathbb{Z}_{q}\) is uniformly distributed, then it is called the uniform LWE distribution._  
**Definition 26**.