Paper 2015/211

Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing

Thijs Laarhoven and Benne de Weger

Abstract

Recently, it was shown that angular locality-sensitive hashing (LSH) can be used to significantly speed up lattice sieving, leading to a heuristic time complexity for solving the shortest vector problem (SVP) of $2^{0.337n + o(n)}$ (and space complexity $2^{0.208n + o(n)}$. We study the possibility of applying other LSH methods to sieving, and show that with the spherical LSH method of Andoni et al.\ we can heuristically solve SVP in time $2^{0.298n + o(n)}$ and space $2^{0.208n + o(n)}$. We further show that a practical variant of the resulting SphereSieve is very similar to Wang et al.'s two-level sieve, with the key difference that we impose an order on the outer list of centers.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. MINOR revision.LATINCRYPT 2015
DOI
10.1007/978-3-319-22174-8_6
Keywords
shortest vector problem (SVP)sieving algorithmsnearest neighbor problemlocality-sensitive hashing (LSH)lattice cryptography
Contact author(s)
mail @ thijs com
History
2018-02-23: last of 2 revisions
2015-03-06: received
See all versions
Short URL
https://ia.cr/2015/211
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/211,
      author = {Thijs Laarhoven and Benne de Weger},
      title = {Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2015/211},
      year = {2015},
      doi = {10.1007/978-3-319-22174-8_6},
      note = {\url{https://eprint.iacr.org/2015/211}},
      url = {https://eprint.iacr.org/2015/211}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.