Paper 2018/079

Progressive lattice sieving

Thijs Laarhoven and Artur Mariano


Most algorithms for hard lattice problems are based on the principle of rank reduction: to solve a problem in a $d$-dimensional lattice, one first solves one or more problem instances in a sublattice of rank $d - 1$, and then uses this information to find a solution to the original problem. Existing lattice sieving methods, however, tackle lattice problems such as the shortest vector problem (SVP) directly, and work with the full-rank lattice from the start. Lattice sieving further seems to benefit less from starting with reduced bases than other methods, and finding an approximate solution almost takes as long as finding an exact solution. These properties currently set sieving apart from other methods. 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.

Available format(s)
Publication info
Published elsewhere. PQCrypto 2018
lattice-based cryptographylattice sievingshortest vector problem (SVP)nearest neighbor searching
Contact author(s)
mail @ thijs com
2018-02-13: revised
2018-01-23: received
See all versions
Short URL
Creative Commons Attribution


      author = {Thijs Laarhoven and Artur Mariano},
      title = {Progressive lattice sieving},
      howpublished = {Cryptology ePrint Archive, Paper 2018/079},
      year = {2018},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.