Sieve Algorithms for the Shortest Vector Problem are Practical
Journal of Mathematical Cryptology 2008
- Time bound
- (4/3)n + o(n)
- Space bound
- 20.20751874963942188 n + o(n)
- Source / version date
- 11 Sept 2008
- Comparison variant
- Heuristic · minimal list space
- Cost scale
- 2c n + o(n)
- Norm
- Euclidean ℓ₂
- success
- Under the stated sieve heuristic
- model
- Classical randomized; polynomial factors suppressed
- Heuristic assumption
- Sieve-list uniformity heuristic
- Reference
- NV08
Assumptions and source notes
Heuristic AKS variant: limiting time coefficient log₂(4/3) ≈ 0.4150 and space coefficient ½log₂(4/3) ≈ 0.2075. The source states (4/3+ε)^n time for every fixed ε>0. Chronology uses the 11 September 2008 online-publication date reported by the institutional repository, https://authors.library.caltech.edu/records/etxts-sdp80; it does not assert the earliest circulated draft date. This row is the source variant satisfying the baseline-list-space constraint.
Selected earlier references
Selected sources cited by this paper.
- A sieve algorithm for the shortest lattice vector problem
Miklós Ajtai · Ravi Kumar · Dandapani Sivakumar · 2001
reanalyses the AKS sieve §3, paragraph before Theorem 3.1; references [4]
- 2^{O(n)}-time algorithm for SVP
Oded Regev · Michael Khanevsky · 2004
compares 5.9 time with the fixed-parameter 16 bound §3 immediately after Theorem 3.1; references [29]
@article{paper-601546f46af3,
author = {Phong Q. Nguyen and Thomas Vidick},
title = {{Sieve Algorithms for the Shortest Vector Problem are Practical}},
journal = {Journal of Mathematical Cryptology},
year = {2008},
volume = {2},
number = {2},
pages = {181--207},
doi = {10.1515/jmc.2008.009},
url = {https://people.csail.mit.edu/vidick/JoMC08.pdf},
cr_date = {2008-09-11},
cr_status = {published},
cr_venue = {Journal of Mathematical Cryptology},
cr_author_ids = {phong-q-nguyen; thomas-vidick}
}