PDF Run this chapter's code LaTeX source Comments

Chapter 9Shortest Vector Problem (SVP)

9.1What is the shortest vector?#

Recall that a lattice is generated by a basis \[B=(b_1,b_2,\dots,b_n),\] with all integer linear combinations \[L(B)=\left\{\sum_{i=1}^n z_i b_i : z_i\in\mathbb{Z}\right\}.\]

Among all nonzero lattice points, the shortest vector problem asks for the one whose Euclidean norm is minimal. Formally, \[\lambda_1(L)=\min_{v\in L\setminus\{0\}} \|v\|.\] The quantity \(\lambda_1(L)\) is called the first successive minimum. In the literature, this quantity appears again and again in lattice cryptography.

In other words, if we imagine all integer combinations of the basis vectors, the shortest vector is the closest nonzero lattice point to the origin.

9.2Why is two-dimensional SVP easy?#

In low dimensions, the geometry is still visible. In two dimensions, one can often look at the lattice picture and identify the shortest vectors by eye. In three dimensions it is still possible to reason geometrically, but the picture becomes less intuitive. In four dimensions and above, the human intuition becomes weak. By the time we reach 256 dimensions, there is no meaningful way to visualize the geometry directly.

This is why lattice problems become computationally hard in high dimensions. The search space grows exponentially, and a brute-force approach is hopeless.

9.3Why brute force is impossible#

Suppose we try to search a lattice in dimension \(100\). If each coefficient is chosen from \(-5,\dots,5\), then there are \(11\) possibilities per coordinate. The total number of candidate vectors is \[11^{100},\] which is roughly \[1.37\times 10^{104}.\] That is far beyond the number of atoms in the observable universe. Exhaustive search is therefore infeasible.

Stated precisely, brute force is just Algorithm 5 from Chapter 7 with an extra step that tracks the minimum norm seen so far:

The loop body is cheap, but the loop itself visits \((2N+1)^n\) candidates. For \(n=100\) and \(N=5\) that is the \(11^{100}\) figure above; this exponential blow-up in \(n\), not any inefficiency in the inner computation, is what makes exact SVP hard.

9.4A common beginner mistake#

Many beginners assume that the shortest vector must be one of the basis vectors themselves. That is not true. A shortest vector is a lattice vector, but it need not be equal to any single basis vector. For example, the shortest vector can be a combination of basis vectors such as \[b_2-b_1,\] which may be shorter than either basis vector individually.

This means that solving SVP requires looking at the entire lattice structure, not just the basis that happened to be given.

9.5Sage experiment#

We can build a small lattice and ask Sage for its shortest vector.

from sage.modules.free_module_integer import IntegerLattice

B = matrix(ZZ, [[2, 1], [1, 3]])
L = IntegerLattice(B)
print(L.shortest_vector())
print(L.shortest_vector().norm())

The output gives a shortest lattice vector and its Euclidean norm. This is the basic SVP instance.

9.6Minkowski’s theorem#

Minkowski’s theorem is one of the foundational results in lattice theory. It states that a lattice of dimension \(n\) must contain a nonzero vector whose norm is at most \[\sqrt{n}\,\det(L)^{1/n}.\]

The important intuition is simple: if a lattice is dense, then the shortest vector cannot be too large. If the lattice is sparse, then the nearest lattice point is farther away. Minkowski’s theorem guarantees the existence of a vector that is not too long, although it does not tell us how to find it efficiently.

9.7Exact SVP versus approximate SVP#

There is an important distinction between exact SVP and approximate SVP.

• Exact SVP asks for the truly shortest vector.

• Approximate SVP only asks for a vector whose length is within a factor \(\gamma\) of the optimum.

In the notation of the literature, a \(\gamma\)-SVP solver returns a vector of length at most \[\gamma\,\lambda_1(L).\]

This distinction matters because practical algorithms in lattice cryptanalysis usually do not solve exact SVP. Instead, they solve approximate variants, which are much more tractable.

9.8Why LLL does not solve exact SVP#

The LLL algorithm is extremely useful, but its goal is not to find the exact shortest vector. Rather, it transforms a basis into a more reduced basis, often producing a vector that is much shorter than the original one. However, the vector returned by LLL is typically not guaranteed to be the true shortest vector. In many cases, it is only a good approximation.

9.9Why BKZ is stronger#

BKZ improves on LLL by working with local blocks of the lattice. It repeatedly solves small-dimensional SVP instances inside a sliding window, then uses the resulting short vectors to improve the global basis. This makes BKZ stronger than LLL, but it also increases the computational cost substantially. In practice, BKZ can find very short vectors, but it still does not guarantee exact SVP in high dimensions.

9.10Why SVP is hard#

At the present time, the best known classical algorithms for exact SVP are still exponential in the dimension, and no known quantum algorithm provides the dramatic speedup that Shor’s algorithm gives for factoring. As a result, lattice-based cryptography remains a practical and theoretically grounded approach to post-quantum security.

9.11Connection with LWE#

The connection to learning with errors is central. The LWE problem can be viewed as a noisy linear system over a lattice. If one could efficiently solve the relevant lattice problems, including SVP in the appropriate setting, then many LWE-based attacks would become much more powerful. Regev’s reduction runs in the other direction: worst-case lattice problems reduce to average-case LWE, so an efficient algorithm that broke LWE on random instances would solve approximate lattice problems on every lattice. Chapter 11 states the theorem precisely and discusses what it does and does not guarantee at deployed parameters.

9.12Main takeaways#

• SVP asks for the shortest nonzero lattice vector, not merely the shortest basis vector.

• The hardness of SVP grows rapidly with dimension.

• LLL and BKZ solve approximate versions of SVP, not the exact problem in general.

• The connection between SVP and LWE is a core reason why lattice-based cryptography is believed to be secure.