Cryptology ePrint Archive: Report 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.

Category / Keywords: shortest vector problem (SVP), sieving algorithms, nearest neighbor problem, locality-sensitive hashing (LSH), lattice cryptography

Original Publication (with minor differences): LATINCRYPT-2015

Date: received 6 Mar 2015, last revised 3 Jun 2015

Contact author: mail at thijs com

Available format(s): PDF | BibTeX Citation

Version: 20150603:092450 (All versions of this report)

Short URL: ia.cr/2015/211

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]