Welcome to the resource topic for 2017/999
Title:
Shortest Vector from Lattice Sieving: a Few Dimensions for Free
Authors: Léo Ducas
Abstract:Asymptotically, the best known algorithms for solving the Shortest Vector Problem (SVP) in a lattice of dimension n are sieve algorithms, which have heuristic complexity estimates ranging from (4/3)^{n+o(n)} down to (3/2)^{n/2 +o(n)} when Locality Sensitive Hashing techniques are used. Sieve algorithms are however outperformed by pruned enumeration algorithms in practice by several orders of magnitude, despite the larger super-exponential asymptotical complexity 2^{\Theta(n \log n)} of the latter. In this work, we show a concrete improvement of sieve-type algorithms. Precisely, we show that a few calls to the sieve algorithm in lattices of dimension less than n-d solves SVP in dimension n, where d = \Theta(n/\log n). Although our improvement is only sub-exponential, its practical effect in relevant dimensions is quite significant. We implemented it over a simple sieve algorithm with (4/3)^{n+o(n)} complexity, and it outperforms the best sieve algorithms from the literature by a factor of 10 in dimensions 70-80. It performs less than an order of magnitude slower than pruned enumeration in the same range. By design, this improvement can also be applied to most other variants of sieve algorithms, including LSH sieve algorithms and tuple-sieve algorithms. In this light, we may expect sieve-techniques to outperform pruned enumeration in practice in the near future.
ePrint: https://eprint.iacr.org/2017/999
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 .