# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 5 Learning with Errors (LWE)
### The LWE Cryptosystem  
The LWE cryptosystem is initially parameterized by the integer \(n\), which denotes the security parameter and expresses the lattice dimension, the integers \(m\) and \(q\), which express the number of equations and the modulus, respectively, and a real positive \(a\), denoting the noise parameter. Assume that \(\chi\) is a given probability distribution on \(\mathbb{Z}_{q}\) and the LWE distribution \(A_{s,\chi}\) is as described above. The accuracy and security of the cryptographic scheme are determined by the parameters, so they must be chosen carefully. Choose \(q\) to be a prime number such that \(n^{2}\leq q\leq 2n^{2}\), \(m=(1+e)(n+1)\log q\) for some arbitrary constant \(e>0\) and \(a=1/(\sqrt{n}\log^{2}n)\). The LWE cryptosystem has a conventional cryptographic scheme structure, and its steps are as follows. * Private key. A uniformly random vector \(s\in\mathbb{Z}_{q}^{n}\) is chosen. \(s\) is the private key. * Public key. \(m\) vectors \(a_{1},a_{2},\ldots,a_{m}\in\mathbb{Z}_{q}^{n}\) are selected independently from the uniform distribution. There are elements (error offsets) chosen independently, \(e_{1},e_{2},\ldots,e_{m}\in\mathbb{Z}_{q}^{n}\), according to \(\chi\). The public key of the cryptosystem is \((a_{i},b_{i})_{i=1}^{m}\), where \(b_{i}=\langle a_{i},s\rangle+e_{i}\). * Encryption. To be able to encrypt a bit, a random set \(S\) is chosen uniformly among all \(2^{m}\) subsets of \([m]\). The encryption holds (\(\sum_{i\in S}a_{i},\sum_{i\in S}b_{i}\)) if the bit is 0 and (\(\sum_{i\in S}a_{i}\), \(\lfloor\frac{q}{2}\rfloor+\sum_{i\in S}b_{i}\)) if the bit is 1. * Decryption. The decryption of a pair \((a,b)\) is 0 if \(b-\langle a,s\rangle\) is closer to 0 than to \(\lfloor\frac{q}{2}\rfloor\) modulo \(q\). Otherwise, the decryption is 1. The LWE cryptographic scheme serves as the foundation of various protocols, particularly the cryptographic schemes used in post-quantum cryptography. Due to the fact that the LWE problem is considered a challenging mathematical problem, cryptosystems built around it also enjoy extreme security. The following algorithm, Algorithm 1, presents the latest version of the LWE cryptosystem [30] and can be visualized in Figure 6.  
Figure 6: The LWE cryptosystem. Both the private and public keys are denoted in matrix form. The size of the private key changes, and so do the parameters \(t,l\). A function \(f\) maps the message space \(\mathbb{Z}_{q}^{l}\) to the message space \(\mathbb{Z}_{q}^{l}\) by multiplying each coordinate by \(q/t\) and rounding to the nearest integer. It is crucial to define an inverse mapping, \(f^{-1}\), that maps an element of \(\mathbb{Z}_{q}^{l}\) to an element of \(\mathbb{Z}_{q}^{l}\), dividing each coordinate by \(q/t\)[30]. ```
Private key. A matrix \(S\in\mathbb{Z}_{q}^{n\times l}\) is chosen uniformly at random. \(S\) is the private key. Public key. A matrix \(A\in\mathbb{Z}_{q}^{m\times n}\) is chosen uniformly at random and a matrix \(E\in\mathbb{Z}_{q}^{m\times l}\) is chosen, whose each element entries are according to \(\bar{\Psi}_{a}\). The public key is \((A,P=AS+E)\in\mathbb{Z}_{q}^{m\times n}\times\mathbb{Z}_{q}^{m\times l}\). Encryption. Given a message \(v\in\mathbb{Z}_{t}^{l}\) and the public key \((A,P)\), a vector \(a\in\{-r,-r+1,\ldots,r\}^{m}\) is chosen uniformly at random. The output is the ciphertext \((u=A^{T}a,c=P^{T}a+f(v))\in\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}^{l}\). Decryption. Given the private key \(S\in\mathbb{Z}_{q}^{n\times l}\) and the ciphertext \((u,c)\in\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}^{l}\), recover the plaintext \(f^{-1}(c-S^{T}u)\). ```  
**Algorithm 1**LWE  
LWE is believed to be an exceedingly secure cryptosystem. This cryptographic scheme is based on lattices and depends on the assumed difficulty of specific lattice problems, namely the problem of locating the closest lattice point in the presence of random noise. Since LWE-based cryptography is immune to quantum attacks, it has attracted interest as a potential solution for post-quantum cryptography.