The General Sieve Kernel and New Records in Lattice Reduction
We propose the General Sieve Kernel (G6K, pronounced /Ze.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.
|Series||Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence|
|Project||Cryptanalysis of Lattice-based Cryptography|
|Conference||Advances in Cryptology - EUROCRYPT|
|Grant||This work was funded by the The Netherlands Organisation for Scientific Research (NWO); grant id nwo/639.021.645 - Cryptanalysis of Lattice-based Cryptography|
Albrecht, M, Ducas, L, Herold, G, Kirshanova, E, Postlethwaite, E.W, & Stevens, M.M.J. (2019). The General Sieve Kernel and New Records in Lattice Reduction. In Lecture Notes in Computer Science/Lecture Notes in Artificial Intelligence. doi:10.1007/978-3-030-17656-3_25