# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 5 Learning with Errors (LWE)
### Attacks and Threats  
Cryptanalysis involves studying and analyzing the weaknesses of the underlying problem of a cryptographic scheme in order to decrypt ciphertexts and codes or obtain hidden information. The LWE problem is based on the hardness of finding a unique solution to a system of linear equations in the presence of some random errors. It is believed to be secure because solving these systems of equations is considered to be computationally hard, even for quantum computers. However, many attempts have been made to find vulnerabilities or attacks carried out on cryptographic systems based on this problem, especially now that the LWE cryptosystem and its variants are regarded as candidates for secure communication in the post-quantum era. Due to the fact that the LWE cryptographic scheme is based on lattices, lattice reduction attacks remain an active field of research. These types of attacks attempt to find short lattice vectors and can be applied to break certain instances of LWE, especially when the parameters are not selected properly. Given \(n\) samples, \((a_{i},b_{i})\) is created by an \(n\times m\) matrix \(A\) with rows and vectors \(a_{i}\), and a lattice \(\mathcal{L}\) is being formed by \(b\), the columns of the matrix \(A\) and certain parameters. In these types of attacks, the secret \(s\) is recovered by locating the shortest vector in the above lattice \(\mathcal{L}\). [PERSON] et al. presented a study in 2015, where the hardness of LWE was analyzed and the running times of algorithms, such as the LLL and BKZ algorithms, were calculated [56]. A strategy to solve the LWE problem is by solving the SIS problem, i.e., finding a short vector \(v\) in the scaled dual lattice \(\mathcal{L}=\{w\in\mathbb{Z}_{q}^{m}|wA\equiv 0\text{ mod }q\}\). Assuming that we have \(m\) samples \((A,c)\), either from \(\mathcal{L}_{s,x}\) satisfying \(c=As+e\) or \(c\) is uniformly random, the main aim is to find a short vector \(v\) with \(v\cdot A=0\). With this strategy, an eavesdropper solves the distinguishing LWE problem, i.e., a sample is an LWE instance \((A,t=A^{t}s+e)\) or it comes from a uniform distribution at random [30]. In this method, the adversary locates a nonzero short vector \(v\) such that \(Av=0\text{ mod }q\), and examines if the inner product \(\langle v,t\rangle\) is near to zero modulo \(q\). In the case that \(t\) is uniform, there is a probability of \(\frac{1}{2}\) of the test's acceptance. In the case that \(t=A^{t}s+e\), where \(e\) comes from a Gaussian distribution with parameter \(s\), it states \(\langle v,t\rangle=\langle v,e\rangle\text{ mod }q\), which is a Gaussian with parameter \(\|v\|\cdot s\). When the value of this parameter is less than \(q\), the uniform distribution could be distinguished from the Gaussian with an advantage near to \(exp(-\pi\cdot(\|v\|\cdot s/q)^{2})\). Finding a short vector in the dual lattice is necessary for the dual attack to succeed, but this may not always be possible, particularly for carefully selected parameters that defy lattice reduction strategies. The choice of parameters, such as the modulus and lattice dimension, influences how hard it is to solve this problem. The problem becomes more complex with higher dimensions and greater noise distributions. [PERSON] and [PERSON] introduced a simple analysis of a dual attack [57], which is presented below and described in Algorithm 5. Assuming an LWE sample \((A,b)\) is given and \(s\in\mathbb{Z}_{q}^{n}\) is a secret, such that \(b=As+e\) for an unknown \(e\in\mathbb{Z}_{q}^{m}\). In the dual attack, in its most basic variation, the secret \(s\) is divided into two parts, \(s_{guess}\in\mathbb{Z}_{q}^{n_{guess}}\) and \(s_{dual}\in\mathbb{Z}_{q}^{n_{dual}}\), where \(n=n_{guess}+n_{dual}\). Consequently, the matrix \(A\in\mathbb{Z}_{q}^{m\times n}\) is seperated into two parts \(A=[A_{guess}\quad A_{dual}]\). So, we have  
\[b=As+e=\big{(}A_{guess}\quad A_{dual}\big{)}\Big{(} \begin{matrix}s_{guess}\\ s_{dual}\end{matrix}