Speed-ups and time-memory trade-offs for tuple lattice sieving

Gottfried Herold; Elena Kirshanova; Thijs Laarhoven

Paper 2017/1228

Speed-ups and time-memory trade-offs for tuple lattice sieving

Gottfried Herold, Elena Kirshanova, and Thijs Laarhoven

Abstract

In this work we study speed-ups and time-space trade-offs for solving the shortest vector problem (SVP) on Euclidean lattices based on tuple lattice sieving. Our results extend and improve upon previous work of Bai-Laarhoven-Stehlë [ANTS'16] and Herold-Kirshanova [PKC'17], with better complexities for arbitrary tuple sizes and offering tunable time-memory trade-offs.The trade-offs we obtain stem from the generalization and combination of two algorithmic techniques: the configuration framework introduced by Herold-Kirshanova, and the spherical locality-sensitive filters of Becker-Ducas-Gama-Laarhoven [SODA'16]. When the available memory scales quasi-linearly with the list size, we show that with triple sieving we can solve SVP in dimension in time and space , improving upon the previous best triple sieve time complexity of of Herold-Kirshanova. Using more memory we obtain better asymptotic time complexities. For instance, we obtain a triple sieve requiring only time and memory to solve SVP in dimension . This improves upon the best double Gauss sieve of Becker-Ducas-Gama-Laarhoven, which runs in time when using the same amount of space.

Note: Fixed a typo in the title

Metadata

Available format(s): PDF
Publication info: A major revision of an IACR publication in PKC 2018
Keywords: lattice-based cryptography shortest vector problem (SVP)nearest neighbor algorithms lattice sieving
Contact author(s): elena kirshanova @ ens-lyon fr
History: 2017-12-22: revised; 2017-12-22: received; See all versions
Short URL: https://ia.cr/2017/1228
License: CC BY

BibTeX

@misc{cryptoeprint:2017/1228,
      author = {Gottfried Herold and Elena Kirshanova and Thijs Laarhoven},
      title = {Speed-ups and time-memory trade-offs for tuple lattice sieving},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/1228},
      year = {2017},
      url = {https://eprint.iacr.org/2017/1228}
}