### Sieve, Enumerate, Slice, and Lift: Hybrid Lattice Algorithms for SVP via CVPP

Emmanouil Doulgerakis, Thijs Laarhoven, and Benne de Weger

##### Abstract

Motivated by recent results on solving large batches of closest vector problem (CVP) instances, we study how these techniques can be combined with lattice enumeration to obtain faster methods for solving the shortest vector problem (SVP) on high-dimensional lattices. Theoretically, under common heuristic assumptions we show how to solve SVP in dimension $d$ with a cost proportional to running a sieve in dimension $d - \Theta(d / \log d)$, resulting in a $2^{\Theta(d / \log d)}$ speedup and memory reduction compared to running a full sieve. Combined with techniques from [Ducas, Eurocrypt 2018] we can asymptotically get a total of $[\log(13/9) + o(1)] \cdot d / \log d$ dimensions \textit{for free} for solving SVP. Practically, the main obstacles for observing a speedup in moderate dimensions appear to be that the leading constant in the $\Theta(d / \log d)$ term is rather small; that the overhead of the (batched) slicer may be large; and that competitive enumeration algorithms heavily rely on aggressive pruning techniques, which appear to be incompatible with our algorithms. These obstacles prevented this asymptotic speedup (compared to full sieving) from being observed in our experiments. However, it could be expected to become visible once optimized CVPP techniques are used in higher dimensional experiments.

Available format(s)
Category
Foundations
Publication info
Published elsewhere. Africacrypt 2020
Keywords
lattice sievinglattice enumerationrandomized slicershortest vector problem (SVP)closest vector problem (CVP)
Contact author(s)
e doulgerakis @ tue nl
History
Short URL
https://ia.cr/2020/487

CC BY

BibTeX

@misc{cryptoeprint:2020/487,
author = {Emmanouil Doulgerakis and Thijs Laarhoven and Benne de Weger},
title = {Sieve, Enumerate, Slice, and Lift: Hybrid Lattice Algorithms for SVP via CVPP},
howpublished = {Cryptology ePrint Archive, Paper 2020/487},
year = {2020},
note = {\url{https://eprint.iacr.org/2020/487}},
url = {https://eprint.iacr.org/2020/487}
}

Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.