Paper 2018/079

Progressive lattice sieving

Thijs Laarhoven and Artur Mariano

Abstract

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.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. PQCrypto 2018
Keywords
lattice-based cryptographylattice sievingshortest vector problem (SVP)nearest neighbor searching
Contact author(s)
mail @ thijs com
History
2018-02-13: revised
2018-01-23: received
See all versions
Short URL
https://ia.cr/2018/079
License
Creative Commons Attribution
CC BY

BibTeX

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