SVP & CVP — The Hard Problems Behind Lattice Cryptography

Everything in lattice cryptography ultimately rests on the belief that two geometric problems are computationally hard. Not just hard in practice — hard in a deep, provable sense that holds even against quantum computers. Those problems are the Shortest Vector Problem (SVP) and the Closest Vector Problem (CVP).

To understand why they're hard, first understand what they're asking. You're given a set of basis vectors that define a lattice. The lattice looks fine on paper. But finding the shortest nonzero vector in it — or the lattice point closest to some target — turns out to be like finding a needle in an infinite haystack that grows exponentially with dimension.

Beginner's Intuition 💡

Imagine standing in the middle of a dense, infinitely large forest where the trees are planted in a perfectly repeating grid.

SVP (Shortest Vector Problem): Finding the tree that is closest to you. If the trees are planted in a skewed, complex pattern (a "bad basis"), finding the closest one is incredibly difficult without checking almost every tree.

CVP (Closest Vector Problem): Now imagine you are randomly dropped in the mud somewhere in that forest. Your goal is to find the single tree closest to your exact location. In cryptography, your location is an encrypted message, and finding the closest tree decrypts it!

The Shortest Vector Problem (SVP)

Imagine you're standing at the origin of a lattice in 1000 dimensions. Infinitely many lattice points surround you in every direction. Which one is closest? That's SVP: find the lattice point nearest to the origin (other than the origin itself), which is the same as finding the shortest nonzero lattice vector.

Definition 12 — Shortest Vector Problem (SVP)

Input: A basis $B$ for a lattice $Λ$ .
Goal: Find a nonzero vector $v \in Λ$ such that $∥ v ∥ = λ_{1} (Λ)$ — the shortest possible length.

The approximate version, called $γ$ -SVP, asks for a nonzero vector of length at most $γ \cdot λ_{1}$ . When $γ = 1$ , that's exact SVP. When $γ = 2$ , you're allowed to return something up to twice the optimal length — still very hard for large dimensions.

In 2D, SVP is trivial — you can just look at the picture. In 10 dimensions, clever algorithms can solve it. In 500 dimensions, the best known algorithms take astronomical time. This exponential growth with dimension is what makes SVP useful for cryptography.

The Closest Vector Problem (CVP)

CVP is like SVP but with a twist: instead of finding the shortest vector from the origin, you're given an arbitrary target point (which is probably not a lattice point) and asked to find the nearest lattice point to it.

Definition 13 — Closest Vector Problem (CVP)

Input: A basis $B$ and a target point $t \in R^{n}$ (not necessarily on the lattice).
Goal: Find the lattice vector $v \in Λ$ minimizing $∥ t - v ∥$ — the distance from $t$ to the lattice.

CVP is at least as hard as SVP: any CVP solver can be used to solve SVP by setting the target appropriately. Conversely, SVP is a special case of CVP with target $t = 0$ .

Why CVP is the Core of LWE Decryption

In an LWE-based encryption scheme, a ciphertext is (secretly) a lattice point plus a small error vector — i.e., a point very close to a lattice point. Decryption means finding that lattice point. This is exactly CVP. The twist that makes it tractable for the authorized decryptor is that they have the secret key — a short basis that makes CVP easy. An attacker has only the public key, a badly skewed basis from which CVP is believed to be intractable.

Bounded Distance Decoding: CVP with a Guarantee

In practice, cryptographic CVP instances come with a useful guarantee: the target is very close to exactly one lattice point. This restricted form is called Bounded Distance Decoding (BDD).

Definition 14 — Bounded Distance Decoding (BDD)

A BDD instance guarantees that the target $t$ is within distance $d < λ_{1} /2$ of some lattice point. Because the closest lattice point is more than twice as close as any other, there is a unique answer — no ambiguity.

With a well-reduced basis (like the secret key in LWE), BDD can be solved efficiently using Babai's nearest plane algorithm. Without a good basis, BDD is as hard as general CVP.

The gap between "easy with a good basis, hard without one" is precisely what makes BDD useful for cryptography. The secret key is the good basis; the public key is the bad one.

How Hard Are SVP and CVP? The Hardness Results

These aren't just believed to be hard — they've been proven hard under well-established complexity assumptions. Here is the state of the theory:

SVP is NP-hard

Ajtai (1998) proved that exact SVP is NP-hard under randomized reductions. This means: if you could solve SVP efficiently, you could solve any problem in NP efficiently. Since we believe NP ≠ P, SVP must be hard. The proof works by showing a random reduction: a random lattice has an SVP that is as hard as the worst-case SVP.

CVP is NP-hard (and hard to approximate)

CVP is NP-hard exactly (Micciancio, 2001) and NP-hard to approximate within any constant factor (Dinur et al., 2003). This is stronger than for SVP — even getting a 2× or 100× approximation is computationally as hard as solving arbitrary NP problems.

Quantum computers don't help much

The best quantum algorithms for SVP and CVP are sieving algorithms with quantum speedups in inner loops. They improve the exponent by only about 10% compared to classical algorithms. There is no quantum analogue of Shor's algorithm for lattice problems — no known exponential quantum speedup.

From Worst-Case to Average-Case: Ajtai's Breakthrough

Most cryptographic hardness assumptions say: "this specific random problem is hard on average." Lattice cryptography goes further. Ajtai's 1996 theorem was the first to show that an average-case problem — breaking a random lattice-based scheme — is as hard as a worst-case problem. This is a significantly stronger guarantee.

Specifically: if you can break a random instance of the Short Integer Solution (SIS) problem — which underlies digital signatures like Dilithium — then you can solve SVP on the hardest possible lattice in that dimension. In other words, breaking lattice signatures is at least as hard as the hardest possible lattice problem, not just a hard average case.

The Security Reduction Chain

The chain of reductions underlying LWE security is:

Step 1. Worst-case SVP on any lattice is hard (NP-hardness).
Step 2. Solving worst-case SVP with a quantum computer implies solving LWE (Regev's 2005 quantum reduction).
Step 3. Solving LWE implies breaking LWE-based encryption.

Contrapositive: if LWE-based encryption is broken, then quantum computers can solve worst-case SVP. Since we believe they can't, LWE-based encryption is secure. This is the strongest possible foundation for a cryptographic security proof.

Known Algorithms and Their Complexity

Despite hardness proofs, we do have algorithms for SVP and CVP — they're just exponentially slow. Understanding their complexity tells us what dimension we need for security.

LLL basis reduction

Runs in polynomial time. Finds a vector at most $2^{n /4}$ times longer than the shortest. Very fast in practice — useful for preliminary reduction but not for finding the actual shortest vector. The backbone of all practical lattice algorithms.

BKZ-β (Block Korkine–Zolotarev)

Runs LLL in overlapping blocks of size $β$ , solving SVP inside each block as a subroutine. Better output quality as $β$ grows. Time: roughly $2^{c n / β}$ calls to an SVP oracle. The main tool in cryptanalysis — security estimates assume the best BKZ attack.

Sieving algorithms

Find SVP by repeatedly combining close vector pairs to produce shorter ones. Best known: BDGL sieve runs in $2^{0.2075 n}$ time and space. With quantum speedup: $2^{0.2653 n}$ . For $n = 512$ , this is about $2^{106}$ operations — far beyond any computer.

Enumeration (Kannan's algorithm)

Exhaustively searches a ball of radius $λ_{1}$ . Super-exponential in the worst case: $2^{O (n l o g n)}$ . Pruned enumeration with clever strategies achieves $\approx 2^{0.18 n}$ in practice — better than sieving in low dimensions, worse in high dimensions.

The Kannan Embedding: Reducing CVP to SVP

A useful algorithmic trick: CVP instances can be converted into SVP instances by embedding the lattice in one higher dimension. This means algorithms for SVP can also attack CVP, and the two problems are closely related in complexity.

Construction — Kannan Embedding

To find the lattice vector nearest to target $t$ , build a new $(n + 1)$ -dimensional lattice by appending $t$ as an extra column and adding a large weight $M$ in the new dimension. In this extended lattice, the vector corresponding to the CVP solution is uniquely short. Finding it via SVP solves the original CVP.

This construction shows: solving SVP is "at least as hard as" CVP (since you can use an SVP solver for CVP), confirming that SVP and CVP have essentially the same computational complexity.