2.1 The Shortest Vector Problem
Finding the shortest nonzero vector in a lattice — the fundamental hard problem underlying modern post-quantum cryptography.
Of all the problems one can pose about a lattice, the most natural is also the hardest: among the infinitely many nonzero vectors in the lattice, which one is shortest? This is the Shortest Vector Problem (SVP). In two dimensions you can draw a picture and see the answer immediately. In 500 dimensions — the scale used in cryptography — no known algorithm can solve it without exponential time.
The Problem Statement
Definition 26 — Shortest Vector Problem (SVP)
Input: A basis $B \in \mathbb{Z}^{n \times n}$ for a lattice $\Lambda = \Lambda(B)$.
Output: A nonzero vector $v \in \Lambda$ such that $\|v\| = \lambda_1(\Lambda)$.
Approximation variant (γ-SVP): Find $v \in \Lambda \setminus \{0\}$ with $\|v\| \leq \gamma \cdot \lambda_1$ for a given approximation factor $\gamma \geq 1$.
Decision variant (GapSVPγ): Given a basis and a distance $d$, decide whether $\lambda_1 \leq d$ (YES) or $\lambda_1 > \gamma d$ (NO).
The decision variant, GapSVP, is the form most useful in security proofs. Regev's reduction from worst-case GapSVP to average-case LWE (§2.3) is the cornerstone of post-quantum security arguments.
Why the Basis Choice Matters
Here is the crux of the difficulty. If you are given a "good" basis — short, nearly orthogonal vectors — you can find the shortest vector easily: it's probably one of the basis vectors themselves, or a small combination. But if you are given a "bad" basis — long, highly skewed vectors — the lattice looks completely different and the short vector is effectively hidden.
This is not just a practical difficulty. It is the mathematical basis for trapdoor cryptography: a trusted party generates a short basis (the trapdoor/secret key) and publishes a highly skewed basis derived from it. Anyone without the trapdoor faces SVP in disguise.
NP-Hardness
Theorem 5 — SVP is NP-Hard (Ajtai 1998, Micciancio 2001)
Exact SVP (in the $\ell_2$ norm) is NP-hard under randomized reductions. Concretely:
If there exists a polynomial-time algorithm solving SVP, then NP ⊆ RP (randomized polynomial time).
The proof is a worst-case to average-case reduction: a random lattice sampled from a natural distribution has an SVP instance as hard as the hardest possible SVP instance. This means you cannot even get lucky with random inputs.
Approximate SVP ($\gamma$-SVP) is also NP-hard for any constant $\gamma$ (Khot 2005 showed hardness up to $\gamma = n^{c/\log \log n}$ under randomized reductions). Proving NP-hardness for larger polynomial approximations remains open.
Algorithms for SVP
Three families of algorithms attack SVP in high dimensions. None achieves polynomial time (assuming NP ≠ P), but their exponential complexity varies significantly, and this variation directly determines the security parameters of cryptographic schemes.
Family 1: Basis Reduction (LLL and BKZ)
LLL (§1.5) runs in polynomial time but only achieves a $2^{n/4}$ approximation. BKZ-$\beta$ achieves $\delta_\beta^n$ approximation by solving SVP in $\beta$-dimensional blocks. For $\beta = n$, BKZ solves SVP exactly — but at exponential cost. BKZ is the practical choice for moderate block sizes.
Family 2: Sieving
Sieving algorithms (Ajtai–Kumar–Sivakumar 2001) find SVP by maintaining a large list of lattice vectors and repeatedly combining pairs to produce shorter vectors. The list converges to contain vectors close to $\lambda_1$. Modern sieving algorithms achieve:
Sieving Complexity
GaussSieve (Micciancio–Voulgaris 2010): $2^{0.415n + o(n)}$ time, $2^{0.208n}$ space. Practical for moderate dimensions.
ListSieve / HashSieve: $2^{0.337n}$ time with locality-sensitive hashing to find close pairs efficiently.
BDGL Sieve (Becker–Ducas–Gama–Laarhoven 2016): $2^{0.2075n + o(n)}$ time and space. Current best classical sieve — uses spherical caps for near-neighbor queries.
Quantum sieve (Laarhoven 2016): $2^{0.2653n}$ time with quantum random access memory (QRAM). The best known quantum SVP algorithm.
Family 3: Enumeration
Enumeration algorithms (Fincke–Pohst 1985, Kannan 1987) exhaustively search the lattice for vectors shorter than a given bound. Combined with clever pruning strategies, they are competitive with sieving for moderate dimensions (up to about $n = 100$) and require less memory, but scale worse for large dimensions.
Enumeration Complexity
Basic Kannan enumeration: $n^{n/(2e)} \approx 2^{0.5n \log_2 n}$ time — super-exponential.
Extreme pruned enumeration (Gama–Nguyen–Regev 2010): $2^{0.18n}$ time in practice, with preprocessing cost. Achieved the best practical SVP results for many years.
Memory advantage: Enumeration uses only polynomial space, unlike sieving which requires exponential space. In memory-constrained settings (e.g., hardware attacks), enumeration may be preferred even when theoretically slower.
Practical SVP Records
The SVP challenge (maintained at latticechallenge.org) tracks the highest dimensions in which SVP has been solved in practice. As of 2024, exact SVP records stand around dimension 160–180 using massive computational resources. For the dimensions used in cryptography (512–1024), exact SVP is completely out of reach.
Complexity comparison
At $n = 512$:
LLL: seconds, but output is $2^{128}$× too long.
BKZ-20: minutes, output still $2^{50}$× too long.
Optimal sieve: $\approx 2^{106}$ operations.
For context: the world's fastest supercomputer performs $\approx 10^{18}$ (about $2^{60}$) operations per second. $2^{106}$ would take $\sim 10^{13}$ years.
Quantum security
Quantum sieving provides only a modest improvement: from $2^{0.2075n}$ to $2^{0.2653n}$ — about 28% more in the exponent. At $n = 512$, this reduces the quantum attack cost to $\approx 2^{136}$ instead of $2^{106}$ classically. Kyber-768 parameters are chosen to keep both above $2^{128}$.
References and Further Reading
Key papers on SVP
Micciancio & Regev, "Lattice-based Cryptography" (2009) — comprehensive survey of SVP hardness and its cryptographic applications. PDF ↗
Regev, "On Lattices, Learning with Errors, Random Linear Codes, and Cryptography" (2005) — foundational paper establishing the LWE reduction from worst-case SVP. ACM ↗
Most-cited papers on lattice reduction algorithms on Academia.edu ↗