Paper 2019/089

The General Sieve Kernel and New Records in Lattice Reduction

Martin R. Albrecht, Léo Ducas, Gottfried Herold, Elena Kirshanova, Eamonn W. Postlethwaite, and Marc Stevens

Abstract

We propose the General Sieve Kernel (G6K, pronounced /ʒe.si.ka/), an abstract stateful machine supporting a wide variety of lattice reduction strategies based on sieving algorithms. Using the basic instruction set of this abstract stateful machine, we first give concise formulations of previous sieving strategies from the literature and then propose new ones. We then also give a light variant of BKZ exploiting the features of our abstract stateful machine. This encapsulates several recent suggestions (Ducas at Eurocrypt 2018; Laarhoven and Mariano at PQCrypto 2018) to move beyond treating sieving as a blackbox SVP oracle and to utilise strong lattice reduction as preprocessing for sieving. Furthermore, we propose new tricks to minimise the sieving computation required for a given reduction quality with mechanisms such as recycling vectors between sieves, on-the-fly lifting and flexible insertions akin to Deep LLL and recent variants of Random Sampling Reduction. Moreover, we provide a highly optimised, multi-threaded and tweakable implementation of this machine which we make open-source. We then illustrate the performance of this implementation of our sieving strategies by applying G6K to various lattice challenges. In particular, our approach allows us to solve previously unsolved instances of the Darmstadt SVP (151, 153, 155) and LWE (e.g. (75, 0.005)) challenges. Our solution for the SVP-151 challenge was found 400 times faster than the time reported for the SVP-150 challenge, the previous record. For exact SVP, we observe a performance crossover between G6K and FPLLL's state of the art implementation of enumeration at dimension 70.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
cryptanalysislattice reductionsievingSVPLWEBKZ
Contact author(s)
ducas @ cwi nl
History
2019-01-28: received
Short URL
https://ia.cr/2019/089
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/089,
      author = {Martin R.  Albrecht and Léo Ducas and Gottfried Herold and Elena Kirshanova and Eamonn W.  Postlethwaite and Marc Stevens},
      title = {The General Sieve Kernel and New Records in Lattice Reduction},
      howpublished = {Cryptology ePrint Archive, Paper 2019/089},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/089}},
      url = {https://eprint.iacr.org/2019/089}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.