# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 5 Learning with Errors (LWE)
### An Efficient Variant of LWE  
Since the introduction of the LWE cryptographic scheme, numerous diverse cryptosystems have been proposed and studied because it is one of the most commonly used and researched lattice-based protocols. The cryptographic scheme we introduce bears a strong resemblance to the original proposed cryptosystem of [PERSON] [49]. The main new idea is the existence of a map \(f:K\to L\), \(K,L\subseteq\mathbb{R}^{k}\), where \(1\leq k\leq n\) (e.g., a multilinear map) is the construction of the cryptosystem in the key generation step of the cryptographic algorithm. It is important that the mapping \(f\) satisfy certain conditions, such as the dimension of the spaces \(K,L\). This step does not affect the security of the cryptographic scheme, as its safety is based on the LWE assumption but maintains the efficiency of the protocol. Since the procedure of key generation becomes increasingly intricate, the cryptographic scheme remains secure and the risks of an algebraic-analytical attack under the hardness LWE assumption do not increase. Our variation cryptographic scheme supports addition and multiplication, and the key idea is that, by using a transform \(f\) and its matrix, the elements of the product of the secret key \(S\) and the random matrix \(A\) in the second step of the LWE algorithm are mapped to new elements. This procedure is ineffective for the complexity of the algorithm since the operations of addition and multiplication correspond to matrices' and vectors' addition and multiplication, which inherently offer opportunities for parallelism. Additionally, key generation involves matrix operations and sampling from distributions, which can be parallelized to some extent; therefore, parallelism is achieved. The error vector is added after matrix operations, so our scheme is also secure due to the underlying LWE hardness assumption. The LWE cryptographic scheme can be visualized, as in Figure 7, where a lattice is generated by the public matrix A and the lattice point \((S,AS)\). As shown, the public point \(t=(0,B)\) is distinct from the lattice point \((S,AS))\) and the vector \((S,\)\"-\(E\)\") separates it from the point. With our transformation, we are changing this public point to improve both efficiency and security. Our variant of the LWE cryptosystem is described below. The parametrization is the same as that of LWE, and all operations are performed over \(\mathbb{Z}_{q}\). \(T\) is the function that maps the message space \(\mathbb{Z}_{p}^{l}\) to the space \(\mathbb{Z}_{p}^{l}\). Let \(v\in\mathbb{Z}_{p}\) be a message vector, and we define \(t(v)=\lfloor v\cdot\frac{q}{p}\rceil\in\mathbb{Z}_{q}\). * Private key. Choose a matrix \(S\leftarrow\mathbb{Z}_{q}^{n\times l}\) uniformly at random. \(S\) is the private key. * Public key. Choose a matrix \(A\leftarrow\mathbb{Z}_{q}^{n\times n}\) uniformly at random and compute the matrix product \(AS\). Choose a suitable mapping \(f:K\to L\), \(K,L\subseteq\mathbb{R}^{k}\), where \(1\leq k\leq n\) transforms the elements of the matrix \(AS=C\) and maps them to elements of a matrix \(D\), i.e., \(f\) is a suitable correspondence. \(D\) is the matrix product \(CF\), where \(F\) is the matrix transformation of \(f\). Choose an error matrix \(E\in\mathbb{Z}_{q}^{m\times l}\), where each entry \(x_{ij}\leftarrow\chi\) is chosen independently from an error distribution \(\chi\). The public key is \((A\leftarrow\mathbb{Z}_{q}^{m\times n},P=D+E\in\mathbb{Z}_{q}^{m\times l})\). The \((i,j)th\) entry of \(P\) is \(p_{ij}=d_{ij}+x_{ij}\), where \(d_{ij}\) is the element of the matrix \(D\) yielding the linear transformation and the matrix \(C\). * Encryption. To encrypt a message \(v\in\mathbb{Z}_{p}^{l}\), define the vector \(t=t(v)\in\mathbb{Z}_{p}^{l}\) by applying \(t(\cdot)\) coordinate-wise to \(v\). Choose a vector \(a\leftarrow\{0,1\}^{m}\subset\mathbb{Z}_{q}^{m}\) uniformly at random. The pair \((u,c)=(A^{T}a,P^{T}a+t)\in\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}^{l}\) is the resulting ciphertext. * Decryption.