Algorithms for the Shortest and Closest Lattice Vector Problems
IWCC 2011
- Time bound
- 22.648 n + o(n)
- Space bound
- 21.325 n + o(n)
- Source / version date
- 2013
- Comparison variant
- Classical · worst case
- Cost scale
- 2c n + o(n)
- Norm
- Euclidean ℓ₂
- Success guarantee
- At least 1/2 − o(1); polynomial repetition amplifies
- Computation model
- Classical; polynomial input-size factors suppressed
Assumptions and source notes
Corrected birthday-paradox analysis at γ ≈ 0.609 and ξ = 1. This replaces the obsolete 2.571/1.407 pair still repeated in some later literature. The coefficients are dated to the corrected 2013 source, not automatically to the original 2011 proceedings chapter. This is a historical variant, not an improvement over the 2009 ListSieveBirthday time record.
Source location
§4.1 birthday discussion, PDF p. 17; Appendix A, final paragraph, PDF p. 33
Version: Corrected version – 02/01/2013
Selected earlier references
Selected sources cited by this paper.
- Sieve Algorithms for the Shortest Vector Problem are Practical
Phong Q. Nguyen · Thomas Vidick · 2008
traces the earlier rigorous AKS constant analysis §4 introduction and reference [65]
- Faster exponential time algorithms for the shortest vector problem
Daniele Micciancio · Panagiotis Voulgaris · 2010
reanalyzes ListSieve and its bounds §4.2 and Appendix B, reference [58]
- Solving the Shortest Lattice Vector Problem in Time 2^(2.465n)
Xavier Pujol · Damien Stehlé · 2009
presents the ListSieve birthday refinement §4.2, Theorem 4.4 and Appendix B, reference [68]
- Improved Analysis of Kannan's Shortest Lattice Vector Algorithm
Guillaume Hanrot · Damien Stehlé · 2007
reviews the improved enumeration analysis Introduction and §5, reference [32]
- A Deterministic Single Exponential Time Algorithm for Most Lattice Problems Based on Voronoi Cell Computations
Daniele Micciancio · Panagiotis Voulgaris · 2013
already presents the 2^{2n} Voronoi bound before the 2012 ECCC revision Original uncorrected 2011 author PDF, introduction and Table 1 (PDF p. 3); §3.1 (PDF pp. 8–10); end of §3.2 (PDF p. 13)
@inproceedings{hanrot-pujol-stehle-2011,
author = {Guillaume Hanrot and Xavier Pujol and Damien Stehlé},
title = {{Algorithms for the Shortest and Closest Lattice Vector Problems}},
booktitle = {Coding and Cryptology: IWCC 2011},
year = {2011},
volume = {6639},
pages = {159--190},
doi = {10.1007/978-3-642-20901-7_10},
url = {https://perso.ens-lyon.fr/damien.stehle/downloads/SVPCVP.pdf},
cr_date = {2011-12-31},
cr_date_precision = {year},
cr_status = {published},
cr_venue = {IWCC 2011},
cr_author_ids = {guillaume-hanrot; xavier-pujol; damien-stehle},
note = {Author PDF headed Corrected version -- 02/01/2013},
series = {Lecture Notes in Computer Science}
}