2.2 The Closest Vector Problem
Finding the nearest lattice point to an arbitrary target — the geometric problem at the heart of lattice decryption.
The Closest Vector Problem (CVP) is a generalization of SVP: instead of finding the lattice point nearest to the origin, you find the lattice point nearest to an arbitrary target point that may not be on the lattice at all. This seemingly minor change makes CVP at least as hard as SVP, and in practice it is the more cryptographically relevant problem — LWE decryption is directly an instance of CVP, and lattice trapdoor constructions are exactly algorithms for solving CVP efficiently when you hold a secret key.
Beginner's Intuition 💡
Building on our "infinite forest" analogy from SVP: now imagine you are dropped somewhere in that same infinite, repeating forest, but you are not standing exactly where a tree is planted. You are standing somewhere random in the mud between trees, and your goal is to find the single tree closest to your exact location.
This is the Closest Vector Problem (CVP). In lattice cryptography, the mud puddle you're standing in represents an encrypted message, and finding the closest tree (the lattice point) is how you decrypt it!
The Problem Statement
Definition 27 — Closest Vector Problem (CVP)
Input: A basis $B$ for lattice $\Lambda$ and a target point $t \in \mathbb{R}^n$.
Output: The lattice vector $v^* \in \Lambda$ minimizing $\|t - v\|$ over all $v \in \Lambda$.
Approximation variant (γ-CVP): Find $v \in \Lambda$ with $\|t - v\| \leq \gamma \cdot \mathrm{dist}(t, \Lambda)$.
Note: CVP reduces to SVP (via Kannan embedding) and SVP reduces to CVP. The two problems are computationally equivalent up to polynomial factors.
Hardness: Stronger than SVP
CVP is at least as hard as SVP in a formal sense, and its inapproximability results are actually stronger than those known for SVP. While SVP is NP-hard to approximate only up to small constants, CVP is NP-hard to approximate within any constant — a qualitative difference.
Theorem 6 — CVP Hardness (Micciancio 2001, Dinur et al. 2003)
Exact CVP: NP-hard under deterministic polynomial-time reductions — even in the $\ell_\infty$ norm. This is stronger than the randomized reduction known for SVP.
Approximate CVP: For any constant $\gamma > 1$, $\gamma$-CVP is NP-hard (Dinur et al. 2003). This means even a 100× approximation is NP-hard — you cannot get "close enough" without exponential work.
Under stronger assumptions (ETH — the Exponential Time Hypothesis), approximate CVP has sub-exponential lower bounds, suggesting it is fundamentally harder than, say, 3-SAT.
Babai's Nearest Plane Algorithm
Babai's nearest plane algorithm (1986) is the workhorse of lattice decoding — the algorithm that runs inside LWE decryption whenever a sufficiently good basis is available. It solves an approximate version of CVP in polynomial time, with quality depending entirely on the quality of the input basis.
Algorithm — Babai's Nearest Plane (1986)
Input: An LLL-reduced (or better) basis $B = (b_1, \ldots, b_n)$ with Gram–Schmidt orthogonalization $B^* = (b_1^*, \ldots, b_n^*)$, and a target $t \in \mathbb{R}^n$.
Step-by-step:
1. Set $v \leftarrow t$.
2. For $i = n$ down to $1$:
a. Compute the coefficient $c_i = \langle v, b_i^* \rangle / \langle b_i^*, b_i^* \rangle$.
b. Round: subtract $\lfloor c_i \rceil \cdot b_i$ from $v$.
3. Output $t - v$ (the nearest plane lattice point found).
Approximation guarantee: For an LLL-reduced basis, the output $\hat{v}$ satisfies:
$\|t - \hat{v}\| \leq 2^{(n-1)/2} \cdot \mathrm{dist}(t, \Lambda)$
For a near-orthogonal basis (such as the secret key in LWE), the rounding error in each step is at most $\|b_i^*\|/2$. If the target is within $\lambda_1/2$ of the lattice, the algorithm returns the exact closest vector. This is precisely the BDD guarantee exploited in LWE decryption.
The key insight: Babai's algorithm is correct whenever the error $e = t - v^*$ is small relative to the Gram–Schmidt norms $\|b_i^*\|$. A short, nearly orthogonal basis (the secret key) makes all $\|b_i^*\|$ large, ensuring the rounding in each step is correct. A long, skewed basis (the public key) makes some $\|b_i^*\|$ very small, causing the rounding to fail.
Bounded Distance Decoding (BDD)
CVP as stated is worst-case hard. But in cryptographic applications, the target always comes with a crucial guarantee: it is very close to exactly one lattice point. This restricted form, called Bounded Distance Decoding (BDD), is often solvable efficiently — given the right tools.
Definition 28 — Bounded Distance Decoding (BDD)
A BDD instance is a CVP instance with the promise that the target $t$ satisfies:
$\mathrm{dist}(t, \Lambda) < \frac{\lambda_1(\Lambda)}{2}$
Under this guarantee, the closest lattice point is unique (any other lattice point is at distance $\geq \lambda_1 - \mathrm{dist}(t, \Lambda) > \lambda_1/2$ away). Uniqueness means there is a definitive right answer — no ambiguity.
BDD with bound $d \ll \lambda_1/2$ can often be solved in polynomial time given a good (short) basis — this is what Babai's nearest plane algorithm does. Without a good basis, BDD is as hard as CVP.
BDD as LWE decryption: In Kyber, the error vector $e$ satisfies $\|e\|_\infty \leq \eta$ where $\eta = 2$ or $3$, while $\lambda_1 \approx q/2$. The ratio $\|e\|/\lambda_1 \approx 2/1664 \approx 0.001$ — the target is extremely close to the lattice, making BDD easy with the secret basis and hard without it.
LWE Decryption as BDD
Here is why CVP/BDD is the right lens for understanding LWE. An LWE ciphertext $(u, v)$ encodes a message as:
$v = \langle a, s \rangle + e + \text{message encoding}$
The lattice point $\langle a, s \rangle$ is the "true answer," and $e$ is the small error that puts you at distance $\|e\|$ from it. Since $\|e\| < \lambda_1/2$(enforced by parameter choice), this is a BDD instance. The secret key provides a short basis that lets Babai's algorithm find the unique closest lattice point — recovering the message. An attacker without the secret key faces CVP with a bad basis — believed to be computationally infeasible.
CVP vs SVP — The Reduction and Why CVP Is Harder in Practice
SVP and CVP are formally computationally equivalent: each reduces to the other in polynomial time. But in practice — with the algorithms and parameters used in lattice cryptography — CVP is the harder problem from the attacker's perspective. Understanding the asymmetry matters for security analysis.
Kannan's Embedding: CVP reduces to SVP
Given lattice $\Lambda(B)$ and target $t$, construct an extended $(n+1)$-dimensional lattice with basis:
$B^{\prime} = \begin{pmatrix} B & t \\ 0 & M \end{pmatrix} \in \mathbb{R}^{(n+1) \times (n+1)}$
for a scaling factor $M > 0$. If $v^*$ is the CVP solution, then $(v^* - t, M)$ is short in $\Lambda(B^{\prime})$ and can be found by an SVP algorithm. Setting $M \approx \mathrm{dist}(t, \Lambda)$ makes this embedded vector stand out clearly as the unique shortest vector.
The gap: The embedding works cleanly when the CVP solution distance is much smaller than the next-shortest lattice vector. In the BDD regime (LWE decryption), this gap is enormous and the embedding succeeds. In the general CVP regime, the gap may be small, making the embedded vector hard to identify among competitors.
Why CVP Is Harder in Practice
Inapproximability: CVP is NP-hard to approximate within any constant factor (Dinur et al. 2003). SVP is known to be NP-hard only for small constant approximations. For polynomial approximations, only CVP retains provable hardness.
No reduction structure: In the SVP case, the target is the origin — a point with maximal symmetry. For CVP, the arbitrary target breaks this symmetry and eliminates the algebraic tricks that sometimes help with SVP.
Covering radius complication: CVP requires finding the nearest lattice point to a target that could be anywhere in the fundamental domain. Near the covering radius (the maximum distance from any point to the lattice), CVP may have multiple nearly-equally-close solutions — a situation that has no SVP analogue.
Attack complexity: The primal lattice attack on LWE (which embeds CVP as SVP via Kannan embedding) typically performs worse in practice than direct CVP algorithms when the BDD bound is small. Lattice estimator models show CVP-based attacks are computationally dominant for LWE with small error.
Algorithms for CVP
Exact CVP via Enumeration
Exact CVP can be solved by adapting enumeration to search for the nearest lattice point instead of the shortest vector. The complexity is the same order as SVP enumeration: exponential in $n$. Sieving can also be adapted for CVP — a "CVP sieve" starts with vectors near the target and reduces their distance iteratively.
Decoding Algorithms in Coding Theory
CVP has a direct analogue in coding theory: maximum likelihood decoding. A linear code over a finite field is a lattice (or a lattice coset), and decoding a received noisy codeword is exactly finding the nearest codeword — BDD. Many classical decoding algorithms (Berlekamp-Massey, Viterbi) exploit specific algebraic structure. For general lattices, no such structure exists.
The Gap between BDD and CVP
BDD is easy with a trapdoor
Given a short basis (the secret key), BDD with bound $d < \lambda_1/2$ can be solved efficiently by Babai's algorithm. This is what LWE decryption does. The trapdoor is the short basis — exactly what the secret key encodes.
CVP is hard without a trapdoor
An attacker given only the public key (a bad basis) faces CVP or BDD without a good starting point. Worst-case hardness of CVP and NP-hardness of approximation mean no efficient algorithm exists for general inputs. The attacker would need to first solve a hard basis reduction problem — which requires exponential time at cryptographic parameters.
The unique SVP connection
BDD with a very small bound $d \ll \lambda_1$ reduces to unique SVP (uSVP): finding the unique shortest vector in a lattice where the second shortest is much longer. This is the lattice problem underlying the primal lattice attack on LWE, where the target is embedded as a short vector in a higher-dimensional lattice.
The Primal Attack on LWE
The most important CVP-based attack on LWE is the primal attack. It embeds the LWE instance into a higher-dimensional lattice where the solution $(s, e, -1)$ (secret, error, and a −1) forms an unusually short vector. Recovering this short vector via SVP breaks LWE.
The Primal (Kannan) Attack on LWE
Given $m$ LWE samples $(A, b = As + e)$, construct the lattice:
$\Lambda = \{ (x, y) \in \mathbb{Z}^{m+n} : Ax \equiv y \pmod{q} \}$
The vector $(s, e - b) = (s, -As + b - b) = (s, e)$ lies in this lattice and has norm $\approx \sigma \sqrt{m+n}$ where $\sigma$ is the LWE error standard deviation. If this vector is the unique shortest vector in the lattice, BKZ can find it, breaking LWE.
Security parameters are chosen so that the error term is small enough for correctness but large enough that the embedded vector is not unusually short — requiring huge BKZ block size to recover.