# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 3 Lattices
### Computational Lattice Problems
#### 3.2.1 Shortest Vector Problem (SVP)  
A computationally challenging lattice problem that has been widely researched over the years is the shortest vector problem (SVP). Renowned mathematicians, like [PERSON], studied lattices and developed algorithms for locating the shortest nonzero vector in two-dimensional lattices. Given a lattice \(\mathcal{L}\), the problem of finding the shortest vector in the lattice is a crucial question in lattice theory and is called the shortest vector problem.  
Therefore, the requested issue can be considered a search problem. The SVP is defined as follows.  
**Definition 17**.: _(Shortest Vector Problem). Given a basis \(B=\{b_{1},b_{2},\ldots,b_{n}\}\) of a lattice \(\mathcal{L}(B)\), find the nonzero shortest vector \(v\), i.e., find \(v\in\mathcal{L}\) for which \(\|v\|=\lambda_{1}(\mathcal{L})\)._  
Therefore, we search for the nonzero vector \(v\) with the minimum norm, i.e., the vector with the minimum distance from the origin, as is shown in Figure 2. Calculating the length of the shortest nonzero vector in the lattice \(\mathcal{L}\) without necessarily locating the vector, is a variation of the shortest vector problem. The following theorem is considered one of the most important in lattice theory.  
**Theorem 2**.: _[PERSON]'s first theorem. The shortest nonzero vector in any \(n\)-dimensional lattice \(\mathcal{L}\) has a length, at most, of \(\gamma_{n}det(\mathcal{L})^{1/n}\), where \(\gamma_{n}\) is an absolute constant (approximately equals to \(\sqrt{n}\)) that only depends only on the dimension \(n\) and \(det(\mathcal{L})\) is the determinant of the lattice._  
Moreover, the same problem can be examined from another perspective, as a decision problem: given a fixed norm, determine if there is a vector with a length less than or equal to this norm. The decision version of the shortest vector problem is denoted as GAPSVP.  
For this instance of SVP, we denote \(\gamma=\gamma(n)\geq 1\) as an approximate factor, and we want to determine if there is a vector whose norm is less than a certain norm multiplied by \(\gamma(n)\). This version of the problem can be visualized in Figure 3.  
**Definition 18**.: _(GAPSVP\({}_{\gamma}\)). Let \(\mathcal{L}\) be an \(n\)-dimensional lattice and \(d\) a positive number; an instance of GAPSVP\({}_{\gamma}\) is given. In YES instances, \(\lambda_{1}(\mathcal{L})\leq d\), whereas in NO instances, \(\lambda_{1}(\mathcal{L})>\gamma(n)\cdot d\)._  
The shortest vector problem is regarded as a challenging mathematical issue, and its hardness is a continuous subject of study. In 1996, [PERSON] proved that the SVP is NP-hard for a random class of lattices [17], and two years later, [PERSON] proved that GAPSVP\({}_{\gamma}\) is NP-hard for an approximation factor inferior to \(\sqrt{2}\), using the Euclidean norm [18]. The relation between the approximation factor and the hardness of the decisional problem has been studied and improved upon in recent years [19].  
Figure 2: The shortest vector problem.  
Due to that fact, the SVP serves as a building block for cryptographic techniques that can be proven to be safe, such as lattice-based encryption.