# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 5 Learning with Errors (LWE)
### An Efficient Variant of LWE
Given a ciphertext \((u,c)\in\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}^{l}\) and the private key \(S\leftarrow\mathbb{Z}_{q}^{n\times l}\), compute \(m=c-S^{T}u\in\mathbb{Z}_{q}^{l}\). Output the plaintext \(v\in\mathbb{Z}_{p}^{l}\), where each \(v_{i}\) is such that \(m_{i}-t(v_{i})\in\mathbb{Z}_{q}\) is closest to \(0\bmod q\). Figure 7: Learning with errors (LWE). Efficiency. Our construction is relatively simple to implement, as it only requires addition and multiplication operations modulo \(q\), and parallelization can be achieved. The parameters are chosen as in [30]. For the message space, the integer \(p\) is chosen to be \(p=poly(n)\geq 2\) and \(l=poly(n)\geq 1\). If \(p\) is chosen to be a power of two, converting an input message to an element of the message space is simpler. It is assumed that the security parameter of the system is \(\lambda\) and the parameters of the Gaussian parameters are \(s,\sigma\) for the distribution \(\chi=D_{Z,s}\), as defined above. Assuming that the output is less than \(b=s\sqrt{\lambda}\), the distribution is negligibly affected. Correctness. The decryption algorithm of our construction computes the vector  
\[m=c-S^{T}u=(S^{T}A+E)a+t-S^{T}Aa=Ea+t\in\mathbb{Z}_{q}^{l}\]  
where \(S\) is the secret key chosen uniformly at random, \((A,P=D+E)\) is the public key, with \(A\) being arbitrary and \(E\) being chosen according to the distribution we described above. Remember that \((u,c)=(A^{T}a,P^{T}a+t)\) is the ciphertext, where \(a\in\{0,1\}^{m}\) and \(t=t(v)\) for the message vector \(v\). For each coordinate \(j\in[l]\), the value \((Ea)_{j}\) determines the distance from \(d_{j}\) to \(t_{j}\) (modulo \(q\)) and is at most \(q/4p\) away from 0 (modulo \(q\)), so \(d_{j}\) is nearest to \(t(v_{j})\). Security. [PERSON] proved that the search-LWE problem is at least as hard as worst-case lattice problems [49] for the appropriate parameters, i.e., \(aq\geq\sqrt{n}\). The above variant of LWE is also considered secure against possible attack under the assumption that the decision-LWE problem with variants \(n,q,\chi,m\) is hard for the same parameters' choice. The proof of security is similar to the proof presented by [PERSON] [49]. First, the public key \((A,P)\) is chosen uniformly at random from \(\mathbb{Z}_{q}^{m\times n}\times\mathbb{Z}_{q}^{m\times l}\). Therefore, if the parametrization of the system is such that the LWE problem is hard, the public keys generated by the cryptosystem are indistinguishable from pairs chosen uniformly at random. Second, for an arbitrary public key \((A,P)\) chosen at random with \(c\) an encryption of a fixed bit \(\mu\), it is indistinguishable for \(\mu=0,1\), i.e., the result gives us no information about the encrypted message. So, the task is to prove that the LWE problem remains hard by using \(a_{j}\) public vectors multiplied with secret vectors \(s_{i}\) corresponding to \(d_{i}\) vectors and \(x_{i}\) independent error vectors for each sample, which works following a similar argument to [49, 55]. Assume that we have hybrid distributions \(H_{0},H_{1},\ldots H_{l}\) for the public key \((A,P)\), which operate as follows: in the distribution \(H_{k}\), the matrix \(A\) and the \(k\) rows of the matrix \(P\) are uniform, and the remaining rows of \(P\) are generated according to the key generation of our variant, using \(s_{i}\) secret vectors and error terms \(x_{ij}\) for all \(i>k\) and \(j\in[m]\). Therefore, \(H_{0}\) is the distribution yielded by the key generation algorithm, \(H_{l}\) is completely uniform and we prove that the random \(H_{k-1}\) and \(H_{k}\) are computationally indistinguishable. Suppose for any \(k\in[l]\) that there is a simulator algorithm \(X^{\mathcal{O}}\) that, having an oracle \(\mathcal{O}\), returns samples from either the distribution \(A_{s},\chi\), where \(s\in\mathbb{Z}_{q}^{n}\) or from the uniform distribution \(\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}\).