Shortest Vector Problem

The core lattice problem — find the shortest nonzero vector in a high-dimensional lattice — whose hardness anchors LWE's security reductions.

Core Principles & Analysis

• Ajtai proved SVP is NP-hard under randomized reductions in 1998.
• A lattice is a regular grid of points in n-dimensional space; in cryptographic use, n runs into the hundreds.
• Known quantum algorithms give no meaningful speedup against it — the entire bet of lattice cryptography.

Specifications & Metrics

• TYPE: Hard problem
• YEAR: Classical