Paper 2016/713

Tuple lattice sieving

Shi Bai, Thijs Laarhoven, and Damien Stehle

Abstract

Lattice sieving is asymptotically the fastest approach for solving the shortest vector problem (SVP) on Euclidean lattices. All known sieving algorithms for solving SVP require space which (heuristically) grows as $2^{0.2075 n + o(n)}$, where $n$ is the lattice dimension. In high dimensions, the memory requirement becomes a limiting factor for running these algorithms, making them uncompetitive with enumeration algorithms, despite their superior asymptotic time complexity. We generalize sieving algorithms to solve SVP with less memory. We consider reductions of tuples of vectors rather than pairs of vectors as existing sieve algorithms do. For triples, we estimate that the space requirement scales as $2^{0.1887 n + o(n)}$. The naive algorithm for this triple sieve runs in time $2^{0.5661 n + o(n)}$. With appropriate filtering of pairs, we reduce the time complexity to $2^{0.4812 n + o(n)}$ while keeping the same space complexity. We further analyze the effects of using larger tuples for reduction, and conjecture how this provides a continuous tradeoff between the memory-intensive sieving and the asymptotically slower enumeration.

Note: Updated acknowledgments and added DOI reference

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Algorithmic Number Theory Symposium (ANTS-XII) 2016
DOI
10.1112/S1461157016000292
Keywords
latticesshortest vector problem (SVP)sievingenumeration
Contact author(s)
mail @ thijs com
History
2016-09-12: last of 3 revisions
2016-07-21: received
See all versions
Short URL
https://ia.cr/2016/713
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/713,
      author = {Shi Bai and Thijs Laarhoven and Damien Stehle},
      title = {Tuple lattice sieving},
      howpublished = {Cryptology {ePrint} Archive, Paper 2016/713},
      year = {2016},
      doi = {10.1112/S1461157016000292},
      url = {https://eprint.iacr.org/2016/713}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.