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

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

16 Citations (Scopus)

Abstract

Recently, it was shown that angular locality-sensitive hashing (LSH) can be used to significantly speed up lattice sieving, leading to heuristic time and space complexities for solving the shortest vector problem (SVP) of $2^{0.3366n + o(n)}$. We study the possibility of applying other LSH methods to sieving, and show that with the recent spherical LSH method of Andoni et al.\ we can heuristically solve SVP in time and space $2^{0.2972n + 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. Keywords: lattices, shortest vector problem, sieving algorithms, (approximate) nearest neighbor problem, locality-sensitive hashing
Original languageEnglish
Title of host publicationProgress in Cryptology - LATINCRYPT 2015 (Fourth International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015)
EditorsK. Lauter, F. Rodríguez-Henríquez
Place of PublicationBerlin
PublisherSpringer
Pages101-118
ISBN (Print)978-3-319-22173-1
DOIs
Publication statusPublished - 2015

Publication series

NameLecture Notes in Computer Science
Volume9230
ISSN (Print)0302-9743

Fingerprint Dive into the research topics of 'Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing'. Together they form a unique fingerprint.

  • Cite this

    Laarhoven, T. M. M., & Weger, de, B. M. M. (2015). Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing. In K. Lauter, & F. Rodríguez-Henríquez (Eds.), Progress in Cryptology - LATINCRYPT 2015 (Fourth International Conference on Cryptology and Information Security in Latin America, Guadalajara, Mexico, August 23-26, 2015) (pp. 101-118). (Lecture Notes in Computer Science; Vol. 9230). Springer. https://doi.org/10.1007/978-3-319-22174-8_6