The NP Lattice
# The NP Lattice
The shortest vector problem asks: given a lattice in Euclidean space, find the shortest nonzero vector. Van Emde Boas conjectured in 1981 that this problem is NP-hard. The conjecture has been the assumed foundation for lattice-based cryptography โ the security of post-quantum cryptographic schemes depends on the computational difficulty of problems related to short lattice vectors.
Forty-five years later, the conjecture is proved. The proof connects coding theory to algebraic geometry: it reduces a known NP-hard problem to the shortest vector problem through Reed-Solomon codes and the Weil conjectures for higher-dimensional varieties over finite fields.
The connection is not obvious. Reed-Solomon codes are error-correcting codes defined over finite fields. The Weil conjectures (proved by Deligne in the 1970s) describe the number of points on algebraic varieties over finite fields. Neither topic appears to be about lattice geometry. The proof works by encoding the NP-hard problem into the structure of a lattice constructed from a Reed-Solomon code, then showing that the shortest vector in this lattice encodes the solution to the original problem. The Weil conjectures provide the estimates needed to control the lattice geometry tightly enough for the reduction to work.
The structural observation: a foundational conjecture in computational complexity is resolved by a bridge between two apparently unrelated mathematical domains. The lattice problem is geometric; the proof is algebraic. The difficulty of finding short vectors in high-dimensional lattices turns out to be controlled by the arithmetic of algebraic curves over finite fields โ a connection that was invisible for four decades.
