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
-
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}
}
