Cryptology ePrint Archive: Report 2017/999

Shortest Vector from Lattice Sieving: a Few Dimensions for Free

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.

Category / Keywords: public-key cryptography / Cryptanalysis, Lattice, Sieving, Nearest-Plane.

Date: received 9 Oct 2017, last revised 26 Oct 2017

Contact author: ducas at cwi nl

Available format(s): PDF | BibTeX Citation

Note: Oct 26, 2017, Edit note: grammatical and typos corrections.

Version: 20171026:111909 (All versions of this report)

Short URL: ia.cr/2017/999

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]