The closest-vector problem in 16 seconds

What you’re seeing

A lattice is a grid of points generated by two basis vectors. Given a target that isn’t on the grid, the closest-vector problem asks for the nearest lattice point. In two dimensions you can just look. A computer can also round: write the target in terms of the basis vectors and round each coordinate to the nearest whole number.

With a short, nearly square basis, rounding finds the nearest point about nine times in ten. Describe the same lattice with long, nearly parallel vectors and rounding is right less than one time in five. In hundreds of dimensions, no efficient algorithm is known for finding the nearest point without a good basis, classical or quantum. Lattice-based schemes such as FN-DSA (Falcon) build on exactly this gap, and ML-KEM on a close cousin of the problem.

The full explanation, with an interactive you can encrypt with, is in Lesson 13: Lattices and Learning With Errors.

Transcript

0:00 Find the nearest point on the lattice. Simple rounding gets it right.

0:00–0:06 A target moves across a two-dimensional lattice. A solid line joins it to the nearest lattice point. With a short, nearly square basis, rounding the target's coordinates lands on that same point every time: the readout says “same point”.

0:06 Same lattice. Skewed basis. Now rounding keeps picking the wrong point.

0:06–0:12 The basis switches to two long, nearly parallel vectors that describe exactly the same lattice. Rounding in this basis now usually lands on a different, farther point, marked with a cross and a dashed line, while the true nearest point is unchanged.

0:12 Post-quantum cryptography, from first principles. 18 free interactive lessons, from “what is encryption?” to the internals of ML-KEM. quantumdefenseservices.com. A course by Kyeson Blake Utley.