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 — lattice decryption is directly an instance of CVP, and lattice trapdoor constructions are exactly algorithms for solving CVP efficiently when you hold a secret key.
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.
Bounded Distance Decoding
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, calledBounded 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.
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.
Algorithms for CVP
Babai's Nearest Plane Algorithm
Babai's algorithm (1986) solves CVP approximately using a given basis. It performs a greedy projection: round the target's coordinate in the $n$-th Gram–Schmidt direction, update the target, repeat for dimensions $n-1$ down to 1. The result is the closest lattice point within a factor of $2^n$ of optimal.
Babai's Nearest Plane (1986)
For an LLL-reduced basis, the output satisfies:
$\|t - v_{\text{Babai}}\| \leq 2^{(n-1)/2} \cdot \mathrm{dist}(t, \Lambda)$
For a well-reduced basis (e.g., the secret key in LWE), Babai's algorithm often returns the exact closest vector, especially when the target is well within the lattice's covering radius. The algorithm runs in polynomial time given any basis — its quality depends entirely on basis quality.
Kannan's Embedding: Reducing CVP to SVP
Construction 7 — Kannan Embedding
Given lattice $\Lambda(B)$ and target $t$, construct an extended $(n+1)$-dimensional lattice with basis:
$B' = \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')$ and can be found by an SVP algorithm. This reduction shows CVP ≤ SVP in computational complexity.
The embedding factor $M$ controls the quality: too large and the extended vector stands out clearly; too small and other short vectors dominate. Typically $M \approx \mathrm{dist}(t, \Lambda)$.
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.