The General Sieve Kernel and New Records in Lattice Reduction
2019
textabstractWe 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.
Keywords:
- Correction
- Source
- Cite
- Save
- Machine Reading By IdeaReader
39
References
60
Citations
NaN
KQI