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

Thijs Laarhoven; Benne de Weger

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.337 n + o (n)}$ (and space complexity $2^{0.208 n + 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.298 n + o (n)}$ and space $2^{0.208 n + 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 algorithms nearest neighbor problem locality-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: 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},
      url = {https://eprint.iacr.org/2015/211}
}