Solving the Shortest Vector Problem in 2^(0.63269n+o(n)) time on Random Lattices

Amaury Pouly · Yixin Shen

Eurocrypt 2026

Time bound

2^{0.63269 n + o(n)}

Space bound

2^{0.5 n + o(n)}

Source / version date

4 Nov 2024

Comparison variant

Classical · Haar random

Cost scale

2^{c n + o(n)}

Norm

Euclidean ℓ₂

Success guarantee

High probability

Computation model

Classical randomized; polynomial factors suppressed

Lattice distribution

Haar–Siegel random real lattices

reference

PS26

Assumptions and source notes

EUROCRYPT 2026, first ePrint in 2024. Exact SVP on most Haar–Siegel random lattices. The 0.5-time theorem in the same work is approximate SVP and is not mixed into this exact-SVP category.

Primary source ↗

@misc{paper-90fa5a162759,
  author = {Amaury Pouly and Yixin Shen},
  title = {{Solving the Shortest Vector Problem in 2^(0.63269n+o(n)) time on Random Lattices}},
  year = {2026},
  url = {https://eprint.iacr.org/2024/1805},
  cr_date = {2024-11-04},
  cr_status = {published},
  cr_venue = {EUROCRYPT 2026},
  cr_author_ids = {amaury-pouly; yixin-shen},
  howpublished = {EUROCRYPT 2026; full version Cryptology ePrint Archive, Paper 2024/1805}
}