# 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].

##### MSC:
 94A60 Cryptography 68W30 Symbolic computation and algebraic computation
Full Text: