zbMATH — the first resource for mathematics

Shortest vector from lattice sieving: a few dimensions for free. (English) Zbl 1423.94069
Nielsen, Jesper Buus (ed.) et al., Advances in cryptology – EUROCRYPT 2018. 37th annual international conference on the theory and applications of cryptographic techniques, Tel Aviv, Israel, April 29 – May 3, 2018. Proceedings. Part I. Cham: Springer. Lect. Notes Comput. Sci. 10820, 125-145 (2018).
Summary: 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^{\varTheta(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=\varTheta(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.
For the entire collection see [Zbl 1387.94008].

94A60 Cryptography
68W30 Symbolic computation and algebraic computation
PDF BibTeX Cite
Full Text: DOI