Paper 2014/744

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

Thijs Laarhoven

Abstract

By replacing the brute-force list search in sieving algorithms with Charikar's angular locality-sensitive hashing (LSH) method, we get both theoretical and practical speedups for solving the shortest vector problem (SVP) on lattices. Combining angular LSH with a variant of Nguyen and Vidick's heuristic sieve algorithm, we obtain heuristic time and space complexities for solving SVP in dimension n of 2^(0.3366n) and 2^(0.2075n) respectively, while combining the same ideas with Micciancio and Voulgaris' GaussSieve algorithm leads to a practical algorithm with (conjectured) time and space complexities bounded by 2^(0.3366n), leading to the best complexities for solving SVP in high dimensions to date. Experiments show that in moderate dimensions the GaussSieve-based HashSieve algorithm already outperforms the GaussSieve, and the practical increase in the space complexity is smaller than the asymptotic bounds suggest, and can be further reduced with probing. Extrapolating to higher dimensions, we estimate that a fully optimized and parallelized implementation of the GaussSieve-based HashSieve algorithm might need a few core years to solve SVP in dimension 130 or even 140.

Metadata
Available format(s)
PDF
Publication info
A major revision of an IACR publication in CRYPTO 2015
Keywords
latticesshortest vector problem (SVP)sieving algorithmsapproximate nearest neighbor problemlocality-sensitive hashing (LSH)
Contact author(s)
mail @ thijs com
History
2015-07-13: last of 3 revisions
2014-09-26: received
See all versions
Short URL
https://ia.cr/2014/744
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/744,
      author = {Thijs Laarhoven},
      title = {Sieving for shortest vectors in lattices using angular locality-sensitive hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2014/744},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/744}},
      url = {https://eprint.iacr.org/2014/744}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.