# Learning with Errors: A Lattice-Based Keystone of Post-Quantum Cryptography
## 3 Lattices
### Computational Lattice Problems
#### 3.2.2 Closest Vector Problem (CVP)  
Another computational lattice problem that is important for cryptography and is closely related to the shortest vector problem is the closest vector problem (CVP). The CVP asks to find the lattice point of a lattice closest to a given target point.  
Let \(\mathcal{L}\) be a lattice and a fixed point \(t\in\mathbb{R}^{n}\), the distance is defined as follows:  
\[d(t,\mathcal{L}):\mathit{min}_{x\in\mathcal{L}}\|x-t\|.\]  
**Definition 19**.: _(Closest Vector Problem). Given a basis \(B=\{b_{1},b_{2},\ldots,b_{n}\}\) of a lattice \(\mathcal{L}(B)\) and a target vector \(t\), not necessarily in the lattice, find the lattice point \(v\in\mathcal{L}(B)\) closest to \(t\)._  
Therefore, the requested nonzero vector \(v\in\mathcal{L}\) is the one for which \(\|t-v\|\) is minimal, i.e., \(\|v\|=d(t,\mathcal{L})\), as presented in Figure 4.  
Another useful variation of the CVP calculates the target's distance from the lattice without determining the lattice's closest vector, as many applications just require the determination of a lattice vector that is reasonably close to the target, not necessarily the closest one.  
For the approximate factor \(\gamma=\gamma(n)\geq 1\), the \(\gamma\)-approximate closest vector problem (CVP\({}_{\gamma}\)) is defined as follows.  
Figure 4: The closest vector problem.  
Figure 3: The GAPSVP\({}_{\gamma}\).  
**Definition 20**.: _(\(C\text{VP}_{\gamma}\)). Given a basis \(B=\{b_{1},b_{2},\ldots,b_{n}\}\) of a lattice \(\mathcal{L}(B)\subset\mathbb{R}^{n}\) and a point \(t\in\mathbb{R}^{n}\), find a \(v\in\mathcal{L}\) such that \(\|t-v\|\leq\gamma(n)\cdot dist(t,\mathcal{L})\)._  
Likewise, the \(\text{CVP}_{\gamma}\) asks to find a vector of the lattice coset \(t+\mathcal{L}\) having norm at most \(\gamma(n)\cdot\lambda(t+\mathcal{L})\), where  
\[\lambda(t+\mathcal{L}):=\min_{x\in t+\mathcal{L}}\|x\|=dist(t,\mathcal{L}).\]  
In 1986, [PERSON] presented the first approximate polynomial time algorithm to solve the closest vector problem [20] and, in addition, other algorithms have been proposed. One of them is the embedding technique, thanks to [PERSON] [21] and the Micciancio-Voulgaris algorithm, that solves the closest vector problem in \(2^{\mathcal{O}(n)}\) space and time [22].  
The closest vector problem is assumed to be roughly NP-hard to solve within any constant factor [23]. In addition to being an open topic in lattice theory, the task of developing a suitable CVP approximation method with approximation factors that grow as a polynomial in the lattice's dimension finds many applications in computer science. For all these facts, numerous lattice cryptography systems, in which the decryption process equates to a CVP computation, are based on the CVP.  
A similar problem to the approximate closest vector problem \(\text{CVP}_{\gamma}\) is the bounded-distance decoding problem \(\text{BDD}_{\gamma}\).  
**Definition 21**.: _(\(BDD_{\gamma}\)). Given a basis \(B=\{b_{1},b_{2},\ldots,b_{n}\}\) of an \(n\)-dimensional lattice \(\mathcal{L}(B)\) and a target point \(t\in\mathbb{R}^{n}\), for which stands \(dist(t,\mathcal{L})<d=\lambda_{1}(\mathcal{L})/(2\gamma(n))\), find the unique vector \(v\) of the lattice \(\mathcal{L}\) such that \(\|t-v\|<d\)._  
This problem is a principal basis in modern cryptosystems, and an average-case of BBD has been employed in innumerable cryptographic schemes, including those that share a lattice among multiple users. The bounded distance decoding problem is proven to be NP-hard, and in 2020, [PERSON] and [PERSON] proved its hardness on lattices in \(l_{p}\) norms under randomized reductions [24].