Short Vectors: SVP and CVP

Two problems about lattices are assumed hard, and every lattice cryptosystem rests on one or the other. Both are easy to state. Both are easy to solve in the pictures on this page. Neither is solvable in the dimensions that matter.

01.What "short" means

The length of a vector $v = (v_1, v_2, \ldots, v_n)$ is

$$\|v\| \;=\; \sqrt{v_1^2 + v_2^2 + \cdots + v_n^2},$$

which is Pythagoras extended to $n$ components. It is called the Euclidean norm, and the double bars are the standard notation.

Two examples from the running lattice:

$$\|(3,1)\| = \sqrt{9 + 1} = \sqrt{10} \approx 3.162, \qquad \|(-2,1)\| = \sqrt{4 + 1} = \sqrt{5} \approx 2.236 .$$

Shorter means closer to the origin. That is all the geometry needed.

02.The shortest vector problem

SVP. Given a basis of a lattice $\mathcal{L}$, find the shortest non-zero vector in $\mathcal{L}$.

The exclusion of zero is necessary rather than fussy. The origin is a lattice point in every lattice, taking all coefficients zero, and it has length $0$. Without the exclusion every instance would have the same trivial answer.

Solve it on the running lattice. Points near the origin, with their lengths:

The shortest length is $\sqrt{5}$, achieved by three different points, all of which are the same two vectors up to sign. Minkowski promised something no longer than $\sqrt{10} \approx 3.162$, and $\sqrt{5}$ obliges.

That took about a minute by hand, because the lattice is two-dimensional and drawn.

Cryptography does not need the exact shortest vector, and a relaxed version is what actually gets assumed hard. For an approximation factor $\gamma \geq 1$, $\gamma$-approximate SVP asks for any non-zero lattice vector no longer than $\gamma$ times the true shortest. Taking $\gamma = 1$ recovers exact SVP. The interesting regime for cryptography is $\gamma$ growing polynomially with the dimension, which is still believed hard, and which is precisely the regime the LLL and BKZ algorithms from Good and Bad Bases fail to reach.

03.The closest vector problem

CVP. Given a basis of a lattice $\mathcal{L}$ and an arbitrary target point $t$ which need not be on the lattice, find the lattice point closest to $t$.

CVP is the problem that matters most for what follows, because it is what decryption turns out to be.

Work an instance. Take the target $t = (4.2,\; 2.7)$, which is not a lattice point. Candidates nearby, with their distances to $t$:

The point $(4,3)$ gives $\sqrt{(4.2-4)^2 + (2.7-3)^2} = \sqrt{0.04 + 0.09} = \sqrt{0.13} \approx 0.361$.

The point $(3,1)$ gives $\sqrt{1.44 + 2.89} = \sqrt{4.33} \approx 2.081$.

The point $(5,0)$, which is $2b_1 - b_2$, gives $\sqrt{0.64 + 7.29} = \sqrt{7.93} \approx 2.816$.

So $(4,3)$ wins comfortably. The target sits very close to a lattice point, and finding it was a matter of looking.

The two problems are closely related. CVP is at least as hard as SVP, and an algorithm for either gives you something useful about the other. The cryptographic constructions in Chapters 5 and 6 are built on a restricted form of CVP called bounded-distance decoding, where you are promised in advance that the target is unusually close to some lattice point. That promise is exactly what the honest decryptor has and the attacker does not.

04.Why these are hard in high dimension

Nothing above was hard. Two dimensions, a picture, five candidates checked. So where does the difficulty come from?

It comes from the number of candidates.

To find a short vector you have to search over integer coefficient vectors $(x_1, \ldots, x_n)$. Suppose you know, generously, that each coefficient of the answer lies between $-10$ and $10$. That is $21$ choices per coefficient, so the number of combinations to check is

$$21^n .$$

At $n = 2$ that is $441$, which is a short afternoon by hand. At $n = 10$ it is about $1.7 \times 10^{13}$, a few hours on a machine. At $n = 50$ it is about $10^{66}$. At $n = 256$, the dimension of one ML-KEM polynomial, it is beyond any physical description.

And the good algorithms do far better than this brute-force count. That is the point of LLL and BKZ. What they cannot do is get the approximation factor down to something useful at high dimension, and the parameters of a real scheme are chosen precisely so that they cannot.

There is a second, less obvious source of difficulty. In high dimension, geometric intuition simply fails. The volume of a high-dimensional ball is concentrated near its surface. Randomly chosen vectors are almost always nearly perpendicular to each other. The "just look at it and see which is closest" strategy that worked on the page has no high-dimensional analogue, and even the sharpened versions of it lose their grip.

05.Why Shor does not apply

This is the load-bearing paragraph of the chapter, so it is worth being precise about what is and is not being claimed.

Shor's algorithm works by turning a problem into a question about periodicity and then using quantum interference to read the period off. Factoring becomes the period of $a^1, a^2, a^3, \ldots$ modulo $n$. Discrete logarithms become a position inside a repeating cycle. Both problems have a hidden repeating structure, and the quantum Fourier transform is a machine for finding hidden repeating structures.

More generally, the technique solves what is called the hidden subgroup problem over commutative groups, and factoring and discrete logarithms are both instances of it.

SVP and CVP are not. They can be phrased as a hidden subgroup problem, but over a group that is not commutative, the dihedral group, and the quantum Fourier transform does not deliver there. Nobody has found a way to make the amplitudes cancel correctly. The gap has been open since the late 1990s and has had a great deal of attention.

What quantum computers do offer against lattices is Grover's algorithm, the generic square-root speedup on unstructured search. Applied to the enumeration inside lattice algorithms it takes $2^{n}$ down to roughly $2^{n/2}$. That is a genuine improvement and it is accounted for in the parameter choices, which is one reason the standardised parameter sets are more conservative than a classical-only analysis would require. It is nothing like Shor. A square root is a change of exponent. Shor is a change of category, from exponential to polynomial.

So the honest statement is not that lattices are proven quantum-resistant. It is that they have no known structure of the kind Shor exploits, that finding one has resisted three decades of effort, and that the best known quantum attack is a generic speedup rather than a break. That is the same standard of evidence factoring enjoyed before 1994, which is exactly why SLH-DSA exists as a hash-based backup with completely different assumptions.

The second half of this chapter takes these geometric problems and turns them into something a computer can actually encrypt with.