Sieving for shortest vectors in lattices using angular locality-sensitive hashing

Research output: Book/ReportReportAcademic

51 Downloads (Pure)

Abstract

By replacing the brute-force list search in sieving algorithms with angular locality-sensitive hashing, we get both theoretical and practical speed-ups for finding shortest vectors in lattices. Optimizing for time, we obtain a heuristic time and space complexity for solving SVP of 2^(0.3366n). Preliminary experiments show that the proposed HashSieve algorithm already outperforms the GaussSieve in low dimensions, and that the practical increase in the space complexity is much smaller than the asymptotic bounds suggest. Using probing we show how we can further reduce the space complexity at the cost of slightly increasing the time complexity. Keywords: lattices, shortest vector problem, sieve algorithms, (approximate) nearest neighbor problem, locality-sensitive hashing
Original languageEnglish
PublisherIACR
Number of pages24
Publication statusPublished - 2014

Publication series

NameCryptology ePrint Archive
Volume2014/744

Fingerprint

Dive into the research topics of 'Sieving for shortest vectors in lattices using angular locality-sensitive hashing'. Together they form a unique fingerprint.

Cite this