International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Gottfried Herold

Publications

Year
Venue
Title
2019
EUROCRYPT
The General Sieve Kernel and New Records in Lattice Reduction 📺
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.
2018
PKC
Speed-Ups and Time–Memory Trade-Offs for Tuple Lattice Sieving
In this work we study speed-ups and time–space trade-offs for solving the shortest vector problem (SVP) on Euclidean lattices based on tuple lattice sieving.Our results extend and improve upon previous work of Bai–Laarhoven–Stehlé [ANTS’16] and Herold–Kirshanova [PKC’17], with better complexities for arbitrary tuple sizes and offering tunable time–memory trade-offs. The trade-offs we obtain stem from the generalization and combination of two algorithmic techniques: the configuration framework introduced by Herold–Kirshanova, and the spherical locality-sensitive filters of Becker–Ducas–Gama–Laarhoven [SODA’16].When the available memory scales quasi-linearly with the list size, we show that with triple sieving we can solve SVP in dimension n in time $$2^{0.3588n + o(n)}$$ 20.3588n+o(n) and space $$2^{0.1887n + o(n)}$$ 20.1887n+o(n), improving upon the previous best triple sieve time complexity of $$2^{0.3717n + o(n)}$$ 20.3717n+o(n) of Herold–Kirshanova. Using more memory we obtain better asymptotic time complexities. For instance, we obtain a triple sieve requiring only $$2^{0.3300n + o(n)}$$ 20.3300n+o(n) time and $$2^{0.2075n + o(n)}$$ 20.2075n+o(n) memory to solve SVP in dimension n. This improves upon the best double Gauss sieve of Becker–Ducas–Gama–Laarhoven, which runs in $$2^{0.3685n + o(n)}$$ 20.3685n+o(n) time when using the same amount of space.
2017
PKC
2017
PKC
2017
JOFC
2016
CRYPTO
2014
CRYPTO
2013
CRYPTO
2012
PKC