In this work we consider a progressive approach to lattice sieving, where we gradually introduce new basis vectors only when the sieve has stabilized on the previous basis vectors. This leads to improved (heuristic) guarantees on finding approximate shortest vectors, a bigger practical impact of the quality of the basis on the run-time, better memory management, a smoother and more predictable behavior of the algorithm, and significantly faster convergence - compared to traditional approaches, we save between a factor $20$ to $40$ in the time complexity for SVP.
Category / Keywords: foundations / lattice-based cryptography, lattice sieving, shortest vector problem (SVP), nearest neighbor searching Original Publication (in the same form): PQCrypto 2018 Date: received 18 Jan 2018, last revised 13 Feb 2018 Contact author: mail at thijs com Available format(s): PDF | BibTeX Citation Version: 20180213:192857 (All versions of this report) Short URL: ia.cr/2018/079