Welcome to the resource topic for 2017/1228
Title:
Speed-ups and time-memory trade-offs for tuple lattice sieving
Authors: Gottfried Herold, Elena Kirshanova, 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.
ePrint: https://eprint.iacr.org/2017/1228
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .