Paper 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.

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
CryptanalysisLatticeSievingNearest-Plane.
Contact author(s)
ducas @ cwi nl
History
2017-10-26: revised
2017-10-11: received
See all versions
Short URL
https://ia.cr/2017/999
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2017/999,
      author = {Léo Ducas},
      title = {Shortest Vector from Lattice Sieving: a Few Dimensions for Free},
      howpublished = {Cryptology ePrint Archive, Paper 2017/999},
      year = {2017},
      note = {\url{https://eprint.iacr.org/2017/999}},
      url = {https://eprint.iacr.org/2017/999}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.