# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 5 Learning with Errors (LWE)
### Attacks and Threats
\Big{)}=A_{guess}s_{guess}+A_{dual}s_{dual}+e\]  
The algorithm makes an effort to guess \(\tilde{s}_{guess}\in\mathbb{Z}_{q}^{n_{guess}}\) on the value of \(s_{guess}\) and if this guess holds true. Assume we have the lattice  
\[L_{q}^{*}(A_{dual})=\{x\in\mathbb{Z}^{m}:x^{T}A_{dual}=0\text{ mod }q\}\]  
and the inequality \(det(L_{q}^{*}(A_{dual}))\leq q^{n_{dual}}\) holds true. Thus, for every \(x\in L_{q}^{*}(A_{dual})\), we have  
\[x^{T}b=x^{T}A_{guess}g_{guess}+x^{T}A_{dual}s_{dual}+x^{T}e=x^{T}A_{guess}s_{guess }+x^{T}e(\operatorname{mod}q)\]  
So,  
\[x^{T}(b-A_{guess}g_{guess})=x^{T}(A_{guess}(s_{guess}-g_{guess})+x^{T}e( \operatorname{mod}q)\]  
At this point, the basic remark is that if the algorithm's guess is correct, i.e., \(\tilde{s}_{guess}=s_{guess}\), then \(x^{T}(b-A_{guess}\tilde{s}_{guess})=x^{T}e(\operatorname{mod}q)\) comes from a Gaussian distribution. Otherwise, if the algorithm's guess is wrong, then \(x^{T}(b-A_{guess}g_{guess})=x^{T}e(\operatorname{mod}q)\) follows a uniform distribution. This results from the fact that \(x\
eq 0\) and \(A\) was chosen uniformly at random. Let \(q\) be a prime power, \(\delta>0\), \(N\in\mathbb{N}\) and LWE samples \((A^{(i)},b^{(i)}),1\leq\ i\leq N\). ```
1:Input: \(q,m,\delta,N,n=n_{guess}+n_{dual}\)
2:Input: list of \((A^{(1)},b^{(1)}),\dots,(A^{(N)},b^{(N)})\)
3:Output: the first \(n_{guess}\) coordinates of the secret or \(\bot\)
4:for\(j=1\) to \(N\)do
5: Compute a basis of \(L_{q}^{*}(A^{(j)})\)
6: Compute a short vector \(x_{j}\in L_{q}^{*}(A^{(j)})\)
7:endfor
8:for\(\tilde{s}_{guess}\in\mathbb{Z}_{q}^{n_{guess}}\)do
9: Compute the list \(y_{1},\dots,y_{N}\) where \(y_{j}=x_{j}^{T}(b^{(j)}-A_{guess}^{(j)}\tilde{s}_{guess})\)
10:\(S\leftarrow\sum_{j=1}^{N}cos(2\pi y_{j}/q)\)
11:if\(S\geq N\delta\)then
12:return\(\tilde{s}_{guess}\)
13:endif
14:endfor
15:return\(\bot\)
```  
**Algorithm 5**Dual Attack  
In 2010, [PERSON] and [PERSON] performed a new type of attack, optimizing the simple distinguishing attack and solving the LWE problem by solving the BBD problem [58]. Another important type of attack against LWE is the dual attack, which tries to recover the secret key by working in the dual lattice space and works best against LWE instances where the plaintext messages are small. The dual attack mathematically attempts to solve the short integer solution (SIS) problem in a dual lattice by performing a lattice reduction algorithm to find short vectors. Typically, dual attacks rely on taking advantage of flaws or structures in the LWE-based schemes' implementation or particular parameters. They may not work with every example of LWE-based cryptography and frequently require fine-tuning of parameters. One popular example of a dual attack is the dual reconciliation attack. This is an attack that targets particular parameter sets where a certain sublattice of the dual lattice is located near the secret key [59]. More effectively than a direct attack on the LWE problem itself, it attempts to recover the secret key by taking advantage of this proximity. Hybrid attacks are attacks that leverage multiple vulnerabilities or combine different techniques to compromise LWE-based systems. To undermine the security assumptions of LWE, a hybrid attack, for example, might combine lattice reduction techniques with algebraic property exploitation [60]. Moreover, hybrid attacks could involve analyzing the statistical properties of the error distribution in LWE instances while simultaneously applying computational methods, like lattice reduction, to exploit potential biases or weaknesses. Exploring the effectiveness of combining multiple attack techniques, such as lattice reduction, algebraic methods, statistical analyses, and potentially quantum algorithms,to create stronger attacks against LWE-based schemes is an active scientific area. The exploration of novel combinations or variations of these attacks remains an open field of study. Continuing efforts are being made to strengthen security proofs for LWE-based cryptographic schemes.