Paper 2015/823

Efficient (ideal) lattice sieving using cross-polytope LSH

Anja Becker and Thijs Laarhoven

Abstract

Combining the efficient cross-polytope locality-sensitive hash family of Terasawa and Tanaka with the heuristic lattice sieve algorithm of Micciancio and Voulgaris, we show how to obtain heuristic and practical speedups for solving the shortest vector problem (SVP) on both arbitrary and ideal lattices. In both cases, the asymptotic time complexity for solving SVP in dimension n is 2^(0.298n). For any lattice, hashes can be computed in polynomial time, which makes our CPSieve algorithm much more practical than the SphereSieve of Laarhoven and De Weger, while the better asymptotic complexities imply that this algorithm will outperform the GaussSieve of Micciancio and Voulgaris and the HashSieve of Laarhoven in moderate dimensions as well. We performed tests to show this improvement in practice. For ideal lattices, by observing that the hash of a shifted vector is a shift of the hash value of the original vector and constructing rerandomization matrices which preserve this property, we obtain not only a linear decrease in the space complexity, but also a linear speedup of the overall algorithm. We demonstrate the practicability of our cross-polytope ideal lattice sieve IdealCPSieve by applying the algorithm to cyclotomic ideal lattices from the ideal SVP challenge and to lattices which appear in the cryptanalysis of NTRU.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Minor revision. AFRICACRYPT 2016
DOI
10.1007/978-3-319-31517-1_1
Keywords
(ideal) latticesshortest vector problemsieving algorithmslocality-sensitive hashing
Contact author(s)
mail @ thijs com
History
2018-02-23: last of 2 revisions
2015-08-24: received
See all versions
Short URL
https://ia.cr/2015/823
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2015/823,
      author = {Anja Becker and Thijs Laarhoven},
      title = {Efficient (ideal) lattice sieving using cross-polytope LSH},
      howpublished = {Cryptology ePrint Archive, Paper 2015/823},
      year = {2015},
      doi = {10.1007/978-3-319-31517-1_1},
      note = {\url{https://eprint.iacr.org/2015/823}},
      url = {https://eprint.iacr.org/2015/823}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.