CryptoDB
Speed-Ups and Time–Memory Trade-Offs for Tuple Lattice Sieving
| Authors: | |
|---|---|
| Download: | |
| 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. |
BibTeX
@inproceedings{pkc-2018-28872,
title={Speed-Ups and Time–Memory Trade-Offs for Tuple Lattice Sieving},
booktitle={Public-Key Cryptography – PKC 2018},
series={Public-Key Cryptography – PKC 2018},
publisher={Springer},
volume={10769},
pages={407-436},
doi={10.1007/978-3-319-76578-5_14},
author={Gottfried Herold and Elena Kirshanova and Thijs Laarhoven},
year=2018
}