Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing
Latincrypt 2015
- Time bound
- 20.2972 n + o(n)
- Space bound
- —
- Source / version date
- 6 Mar 2015
- Comparison variant
- Classical · heuristic
- Cost scale
- 2c n + o(n)
- Norm
- Euclidean ℓ₂
- Success guarantee
- Under the stated sieve heuristic
- Computation model
- Classical randomized; polynomial factors suppressed
- Heuristic assumption
- Sieve-list heuristic; spherical locality-sensitive hashing
- reference
- LdW15
Assumptions and source notes
LATINCRYPT 2015; first ePrint 6 March 2015. Spherical LSH gives the stated 0.298 time bound. The current 2018-revised abstract states space 0.208, while the original balanced SphereSieve presentation uses space about 0.298. Space is left unspecified on this historical row to avoid silently backdating the later memory refinement. Specify the variant when submitting a tighter space claim. Audit: More precise coefficient for the existing spherical-LSH result; do not create a later improvement from .298 to .2972. Original March paper/version needs checking before changing its space field.
Source location
Section 6.2; thesis Section 14.2.8 also agrees
Version: DCC version, 14 April 2015
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}
}