Sieve Algorithms for the Shortest Vector Problem are Practical
Journal of Mathematical Cryptology 2008
- Time bound
- 25.9 n + o(n)
- Space bound
- 22.95 n + o(n)
- Source / version date
- 11 Sept 2008
- Comparison variant
- Classical · worst case
- Cost scale
- 2c n + o(n)
- Norm
- Euclidean ℓ₂
- Success guarantee
- Exponentially close to 1
- Computation model
- Classical; polynomial input-size factors suppressed
Assumptions and source notes
Theorem 3.1 gives the rigorous exact-SVP AKS analysis. This is a different claim from this paper’s heuristic (4/3)^n sieve already in the database. The theorem’s guarantee and constants were read directly in the author PDF. The date follows the existing institutional-repository online-publication chronology.
Source location
Theorem 3.1, printed p. 5 (PDF p. 5); parameter optimization, printed p. 12
Version: Author manuscript, To appear in J. Math. Crypt. (2008)
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}
}