Faster Provable Lattice Sieving with Spherical Codes
ePrint 2026/2388
- Time bound
- 2(0.6078 + ε_μ)n + o(n), ε_μ → 0 as μ → ∞
- Space bound
- 2(0.6078 + ε_μ)n + o(n), ε_μ → 0 as μ → ∞
- Source / version date
- 7 Oct 2026
- Comparison variant
- Constant approximation · large-factor limit
- Cost scale
- 2(c + ε) n, any fixed ε > 0
- Norm
- Euclidean ℓ₂
- Approximation guarantee
- For every ε > 0 choose a sufficiently large constant μ(ε); μ is not uniform in ε
- Success guarantee
- High probability
- Computation model
- Classical randomized; unconditional spherical-code upper bound
Assumptions and source notes
Corollary 3.8 gives unconditional time and space with coefficient 0.6078 + ε_μ, where ε_μ tends to zero as the constant approximation factor μ grows. The stored 0.6078 is the limiting family coefficient; it is not an exact-SVP exponent or a guarantee at every fixed μ. Nearest-neighbor filtering and a perturbation proof give a new provable sieving method. Hhan’s earlier exact-SVP exponent 0.5 already implies a faster constant-approximation bound.
Source location
Theorem 1.1; Theorem 3.7; Corollary 3.8, printed p. 27 (PDF p. 28)
Version: 7 October 2026 preprint; full text checked through eprint.iacr.asia mirror
Selected earlier references
Selected sources cited by this paper.
- New directions in nearest neighbor searching with applications to lattice sieving
Anja Becker · Léo Ducas · Nicolas Gama · Thijs Laarhoven · 2016
Combines spherical-code nearest-neighbor filtering with a provable perturbation analysis. §1.2.4–1.2.5; bibliography [BDGL16]
- Finding a Shortest Vector and More in 2^(n/2+o(n)) Time using q-ary Coset Difference Tree
Minki Hhan · 2026
Concurrent exact-SVP algorithm is faster than the unconditional large-factor bound. §1.1 and §1.4; bibliography [Hha26a]
@misc{aggarwal-morolia-stephens-davidowitz-2026-spherical,
author = {Divesh Aggarwal and Aditya Morolia and Noah Stephens-Davidowitz},
title = {{Faster Provable Lattice Sieving with Spherical Codes}},
year = {2026},
url = {https://eprint.iacr.org/2026/2388},
keywords = {SVP, approximation, provable sieving, spherical codes},
cr_date = {2026-10-07},
cr_date_precision = {day},
cr_status = {preprint},
cr_venue = {Cryptology ePrint Archive 2026/2388},
cr_author_ids = {divesh-aggarwal; aditya-morolia; noah-stephens-davidowitz},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/2388}
}