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.