Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
Latincrypt 2015
- Time bound
- 20.2972 n + o(n)
- Space bound
- (4/3)n/2+o(n)
- Source / version date
- Aug 2015
- Comparison variant
- Heuristic · minimal list space
- Cost scale
- 2c n + o(n)
- model
- Nguyen–Vidick variant with one hash table stored at a time
- version
- LATINCRYPT 2015 published chapter, pages 101–118
Assumptions and source notes
The published LATINCRYPT 2015 chapter, Theorem 1, explicitly gives time exponent 0.2972 with baseline list space by processing hash tables sequentially. This is distinct from Proposition 1's balanced time/space point. Date is a conservative cutoff for the August 2015 published chapter; it does not assert that this memory refinement was present in the first March preprint.
Source location
Theorem 1, printed page 111; preceding sequential-table argument
Version: Published LATINCRYPT 2015 chapter
Selected earlier references
Selected sources cited by this paper.
- Sieve Algorithms for the Shortest Vector Problem are Practical
Phong Q. Nguyen · Thomas Vidick · 2008
Retains the Nguyen–Vidick sieve list size while processing spherical hash tables sequentially. Introduction, reference [35]; Theorem 1
- Sieving for shortest vectors in lattices using angular locality-sensitive hashing
Thijs Laarhoven · 2015
Extends the earlier angular-locality-sensitive-hashing sieve and its sequential-table idea. Introduction, reference [24]; sequential-table discussion before Theorem 1
@misc{paper-2b6476ef7d09,
author = {Thijs Laarhoven and Benne de Weger},
title = {{Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing}},
year = {2015},
doi = {10.1007/978-3-319-22174-8_6},
url = {https://eprint.iacr.org/2015/211},
cr_date = {2015-03-06},
cr_status = {published},
cr_venue = {LATINCRYPT 2015},
cr_author_ids = {thijs-laarhoven; benne-de-weger},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/211}
}