Cryptology ePrint Archive: Report 2017/1228

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

Gottfried Herold and 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 $n$ in time $2^{0.3588n + o(n)}$ and space $2^{0.1887n + o(n)}$, improving upon the previous best triple sieve time complexity of $2^{0.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)}$ time and $2^{0.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)}$ time when using the same amount of space.

Category / Keywords: lattice-based cryptography, shortest vector problem (SVP), nearest neighbor algorithms, lattice sieving

Original Publication (with major differences): IACR-PKC-2018

Date: received 20 Dec 2017, last revised 22 Dec 2017

Contact author: elena kirshanova at ens-lyon fr

Available format(s): PDF | BibTeX Citation

Note: Fixed a typo in the title

Version: 20171222:204559 (All versions of this report)

Short URL: ia.cr/2017/1228


[ Cryptology ePrint archive ]