# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 5 Learning with Errors (LWE)
### Certain Instances of the Variant
#### 5.4.3 An Inverse Transformation  
In general, a linear map \(f:\mathbb{Z}_{q}^{m}\to\mathbb{Z}_{q}^{m}\) is chosen, which is an isomorphism with \(m\times m\) matrix \(F\) and inverse \(m\times m\) matrix \(F^{-1}\). In this case, we choose \(m=l\). In our implementation, we choose \(m=3\). For \(l=3\), we choose the linear isomorphism \(f:(x,y,z)=(2x,4x+y,2x+3y+z)\). In \(Z_{q}^{3}\), we run Algorithm 4. ```
1:\(q,n,m,l,\chi\gets params(\lambda)\)
2:\(S\leftarrow\mathbb{Z}_{q}^{m\times 3}\)
3:for\(i=1\to m\)do
4:\(x_{i}\leftarrow\chi\)
5:\(a_{i}\leftarrow\mathbb{Z}_{q}^{n}\)
6:\(c_{i}\leftarrow\mathbb{Z}_{q}^{m\times 3}\)
7:\(d_{i,1}\gets 2c_{i1}\)
8:\(d_{i,2}\gets 4c_{i1}-c_{i2}\)
9:\(d_{i,3}\gets 2c_{i1}+3c_{i2}-c_{i3}\)
10:\(p_{i}\gets d_{i}+x_{i}\)
11:endfor
12:return\((pk=a_{i},p_{i})\) {\(pk\) stands for public key}
```  
**Algorithm 4** KeyGen(3): Key Generation 3  
Discrete implementation  
The chosen parameters for this particular implementation are: \(n=4\), \(m=3\) and \(q=13\). * The private key is chosen uniformly at random and is such that \[S= \begin{pmatrix}2&3&1\\ 0&5&4\\ 1&4&0\\ 0&1&3\end{pmatrix} \]
* The parameter is \(m=3\), so the public key is generated with the help of the uniformly at random \(A\in\mathbb{Z}_{q}^{3\times 4}\). It is chosen \[A= \begin{pmatrix}1&8&6&2\\ 0&2&1&3\\ 7&1&6&4\end{pmatrix} \]  
Compute the product \(C=AS\), such that \[C= \begin{pmatrix}1&8&6&2\\ 0&2&1&3\\ 7&1&6&4\end{pmatrix}\begin{pmatrix}2&3&1\\ 0&5&4\\ 1&4&0\\ 0&1&3\end{pmatrix} = \begin{pmatrix}8&4&0\\ 1&4&4\\ 7&2&10\end{pmatrix} \] With the aid of the linear map \(f\in\mathbb{Z}_{q}^{3}\to\in\mathbb{Z}_{q}^{3},f:(x,y,z)=(2x,4x+y,2x+3y+z)\), with matrix transformation \[F= \begin{pmatrix}2&0&0\\ 4&1&0\\ 2&3&1\end{pmatrix} \] compute the matrix product \(D=CF\), such that \[D= \begin{pmatrix}6&4&0\\ 0&3&4\\ 3&6&10\end{pmatrix} \]Select matrix \(E\in\mathbb{Z}_{q}^{3\times 3}\), each entry of which is selected according to \(\bar{\Psi}_{a}\). Compute  
\[P=D+E \begin{pmatrix}6&4&0\\ 0&3&4\\ 3&6&10\end{pmatrix} + \begin{pmatrix}-1&0&0\\ 1&0&0\\ 0&1&-1\end{pmatrix} = \begin{pmatrix}5&4&0\\ 1&4&4\\ 3&7&9\end{pmatrix} \]  
The public key is \((A,P=D+E)\in\mathbb{Z}_{q}^{3\times 4}\times\mathbb{Z}_{q}^{3\times 3}\). We wish to decrypt the message  
\[v= \begin{pmatrix}0&1&1\end{pmatrix} \]  
and  
\[t= \begin{pmatrix}0&3&3\end{pmatrix} \]  
For  
\[a= \begin{pmatrix}1&0&0\end{pmatrix} \]  
we compute  
\[u=A^{T}a= \begin{pmatrix}1&0&7\\ 8&2&1\\ 6&1&6\\ 2&3&4\end{pmatrix}\begin{pmatrix}1\\ 0\\ 0\end{pmatrix} = \begin{pmatrix}8&9&7&6\end{pmatrix} \]  
Moreover, we compute  
\[c=P^{T}a+t= \begin{pmatrix}5&1&3\\ 4&4&7\\ 0&4&9\end{pmatrix}\begin{pmatrix}1\\ 0\\ 0\end{pmatrix} +t= \begin{pmatrix}0&3&3\end{pmatrix} = \begin{pmatrix}8&11&9 \end{pmatrix} + \begin{pmatrix}0&3&3\end{pmatrix} = \begin{pmatrix}8&11&12\end{pmatrix} \]  
The ciphertext is the pair  
\[(u,c)= \begin{pmatrix}\begin{pmatrix}8&9&7&6\end{pmatrix},\begin{pmatrix}8&11&12 \end{pmatrix}\end{pmatrix} .\]  
Given the above ciphertext \((u,v)\) and the secret key \(S\), we compute  
\[m=c-S^{T}u= \begin{pmatrix}8&11&12\end{pmatrix} - \begin{pmatrix}2&0&1&0\\ 3&5&4&1\\ 1&4&0&3\end{pmatrix}\begin{pmatrix}8\\ 9\\ 7\\ 6\end{pmatrix} = \begin{pmatrix}8&11&12\end{pmatrix} - \begin{pmatrix}10&12&10 \end{pmatrix} = \begin{pmatrix}11&12&2\end{pmatrix} .\]  
So, the plaintext is  
\[v= \begin{pmatrix}0&1&1\end{pmatrix} \in Z_{4}^{3}\]  
where each coordinate \(v_{i}\) is such that \(m_{i}-t(v_{i})\) is closest to 0 mod 13. Our construction could be appropriate and suitable for heavily based applications to hard encryption, such as file storage services that encrypt data both in transit and at rest, or operating systems that offer the option of full hard disk encryption. Moreover, applications that use strong encryption techniques are those that use end-to-end encryption to secure conversations, e.g., platforms like Signal or WhatsApp.