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

Onderzoeksoutput: Boek/rapportRapportAcademic

166 Downloads (Pure)

Samenvatting

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
Originele taal-2Engels
UitgeverijIACR
Aantal pagina's15
StatusGepubliceerd - 2015

Publicatie series

NaamCryptology ePrint Archive
Volume2015/211

Vingerafdruk Duik in de onderzoeksthema's van 'Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing'. Samen vormen ze een unieke vingerafdruk.

  • Citeer dit