International Association for Cryptologic Research

International Association
for Cryptologic Research


Speed-Ups and Time–Memory Trade-Offs for Tuple Lattice Sieving

Gottfried Herold
Elena Kirshanova
Thijs Laarhoven
DOI: 10.1007/978-3-319-76578-5_14
Search ePrint
Search Google
Conference: PKC 2018
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 n in time $$2^{0.3588n + o(n)}$$ 20.3588n+o(n) and space $$2^{0.1887n + o(n)}$$ 20.1887n+o(n), improving upon the previous best triple sieve time complexity of $$2^{0.3717n + o(n)}$$ 20.3717n+o(n) of Herold–Kirshanova. Using more memory we obtain better asymptotic time complexities. For instance, we obtain a triple sieve requiring only $$2^{0.3300n + o(n)}$$ 20.3300n+o(n) time and $$2^{0.2075n + o(n)}$$ 20.2075n+o(n) memory to solve SVP in dimension n. This improves upon the best double Gauss sieve of Becker–Ducas–Gama–Laarhoven, which runs in $$2^{0.3685n + o(n)}$$ 20.3685n+o(n) time when using the same amount of space.
  title={Speed-Ups and Time–Memory Trade-Offs for Tuple Lattice Sieving},
  booktitle={Public-Key Cryptography – PKC 2018},
  series={Public-Key Cryptography – PKC 2018},
  author={Gottfried Herold and Elena Kirshanova and Thijs Laarhoven},