Shortest Vector Problem
Find a shortest nonzero lattice vector.
Classical · Haar random
Exact SVP on Haar–Siegel random unimodular lattices
Results
| # | PUBLICATION / AUTHORS | DATE | TIME BOUND | SPACE BOUND | EVIDENCE |
|---|---|---|---|---|---|
| 1 | Smooth Sailing through Spherical Shells: Provable Random-Lattice Sieving in Time 2^(0.292n)arXiv 2609.37482SourceBibTeX / detailsHaar-random | 26 Sept 2026 | (3/2)n/2 + o(n) | 20.2075187496 n + o(n) | PreprintSource checked |
| 1 | Superlattice methods for the shortest vector problem and discrete Gaussian samplingePrint 2026/2761SourceBibTeX / detailsHaar-random classical provable | 4 Nov 2026 | (3/2)n/2 + o(n) | (4/3)n/2 + o(n) | PreprintSource checked |
| 3 | Solving the Shortest Vector Problem in 2^(0.63269n+o(n)) time on Random LatticesEurocrypt 2026SourceBibTeX / detailsHaar-random | 4 Nov 2024 | 20.63269 n + o(n) | 20.5 n + o(n) | PublishedSource checked |
Comparison definition & assumptions
- Regime
- Exact SVP on Haar–Siegel random unimodular lattices
- Computation
- Classical
- Rigor
- Provable
- Instances
- Haar random
- Cost scale
- 2^{c n + o(n)}
- Parameter
- n
- Description
- Average-case theorems for the Haar distribution, distinct from heuristic sieving claims.
- Comparison rules
- Use the Haar–Siegel measure on determinant-one real lattices. Specify probability over the lattice and algorithm. Do not identify Haar randomness with a cryptographic q-ary distribution without a reduction.
- Tags
- Haar-random