Closest Vector Problem (CVP) and Babai's Algorithm

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.

Intuition

Building on the forest picture from SVP: now you are dropped somewhere in the same repeating forest, but not on a tree. You stand in the mud between trees, and you want the tree closest to where you are.

That is the Closest Vector Problem (CVP). In lattice encryption a ciphertext is a point slightly off the lattice. The key holder can find the nearest lattice point quickly because they know a good basis; without it, finding that point is hard.

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 the Exponential Time Hypothesis (ETH), exact CVP in dimension $n$ cannot be solved in $2^{o(n)}$ time (Bennett–Golovnev–Stephens-Davidowitz 2017): exponential-time algorithms are essentially the best one can hope for.

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 $\tilde{B} = (\tilde{b}_1, \ldots, \tilde{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, \tilde{b}_i \rangle / \langle \tilde{b}_i, \tilde{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 $\|\tilde{b}_i\|/2$ . If the error $e = t - v^*$ satisfies $|\langle e, \tilde{b}_i \rangle| / \|\tilde{b}_i\|^2 < 1/2$ for every $i$ (for example, whenever $\|e\| < \min_i \|\tilde{b}_i\|/2$ ), the algorithm returns the exact closest vector $v^*$ . This is precisely the BDD guarantee exploited in LWE decryption. Note that it depends on the basis: it does not cover every target within $\lambda_1/2$ of the lattice.

The key insight: Babai’s algorithm is correct whenever the error $e = t - v^*$ is small relative to the Gram–Schmidt norms $\|\tilde{b}_i\|$ . A short, nearly orthogonal basis (the secret key) makes all $\|\tilde{b}_i\|$ large, ensuring the rounding in each step is correct. A long, skewed basis (the public key) makes some $\|\tilde{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 one extra 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$ , tiny compared with $q = 3329$ . Decryption only needs the accumulated noise in each coefficient to stay below $q/4 \approx 832$ , so the target is extremely close to the lattice, making BDD easy with the secret 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, and even within $n^{c/\log \log n}$ under deterministic reductions (Dinur et al. 2003); the comparable results for SVP need randomized reductions. For polynomial approximation factors, neither problem is known to be NP-hard.

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: In practice, attacks on LWE with small error go through lattice reduction: the primal attack (Kannan embedding into unique-SVP, then BKZ), its BDD variants, and the dual attack. Lattice estimators compute all of them, and which is cheapest depends on the parameters.

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 a bound that is small compared with that basis’s Gram–Schmidt lengths 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, w) \in \mathbb{Z}^{n+m+1} : Ax + y + w\, b \equiv 0 \pmod{q} \}$

The vector $(s, e, -1)$ lies in this lattice, since $As + e - b = 0$ , 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 does not stand out enough for BKZ to find it — recovering it would require a huge block size.

Check Your Understanding

Q1. How does CVP differ from SVP?
Q2. Bounded Distance Decoding (BDD) promises the target is within λ₁/2 of the lattice. Why does that promise matter?
Q3. Babai’s nearest plane algorithm is run on the same target twice: once with a short, nearly orthogonal basis and once with a long, skewed basis of the same lattice. What happens?
Q4. In the primal attack on LWE, what does the attacker actually try to find?

References and Further Reading

Key papers on CVP

Micciancio & Regev, “Lattice-based Cryptography” (2009) — §3–4 cover CVP hardness in depth. PDF ↗

Regev, “On Lattices, Learning with Errors...” (2005) — shows LWE decryption is BDD, and BDD reduces to worst-case lattice problems. ACM ↗

← Previous2.1Shortest Vector Problem Next →2.3LWE & Ring-LWEHide a secret in noise. The equation quantum computers can't crack.

Unfamiliar symbol? The math reference explains the notation used across the site.

Found a mistake or something unclear? Report it on GitHub or email hello@ovasylenko.com.