Shortest Vector Problem

Shortest Vector Problem (SVP) is a fundamental problem in the geometry of numbers and lattice-based cryptography. Given a lattice — a discrete set of points in n-dimensional space generated by integer linear combinations of basis vectors — the problem asks for the shortest non-zero vector in the lattice. Despite its geometric simplicity, SVP is believed to be computationally intractable for high dimensions, and this hardness underpins the security of \'\'\'Learning With Errors\'\'\' and other post-quantum cryptographic schemes.

The problem exists in several variants. The \'\'\'exact SVP\'\'\' asks for the shortest vector exactly; the \'\'\'approximate SVP\'\'\' (γ-SVP) asks for a vector within a factor γ of the shortest. The exact version is NP-hard under randomized reductions. The approximate version is NP-hard for any constant approximation factor, but becomes easier as γ grows. The \'\'\'gap version\'\'\' (GapSVP) asks to distinguish between lattices where the shortest vector is very short and lattices where all non-zero vectors are long.

The connection to \'\'\'Learning With Errors\'\'\' is through worst-case to average-case reduction: Regev proved that solving LWE on average is at least as hard as solving approximate SVP in the worst case. This reduction is what makes LWE-based cryptography trustworthy: breaking the cryptosystem would require solving a problem that is hard even in the worst case, not just on typical instances.

From a systems perspective, SVP represents a shift from number-theoretic to geometric hardness. The difficulty of factoring depends on the structure of prime numbers; the difficulty of SVP depends on the geometry of high-dimensional spaces. This geometric foundation may be more robust against quantum attacks than number-theoretic foundations, since quantum computers are known to solve factoring efficiently but are not known to solve SVP efficiently.