International Association
for Cryptologic Research

Verifiable Delay Functions (VDF) are a class of cryptographic primitives aiming to guarantee a minimum computation time, even for an adversary with massive parallel computational power. They are useful in blockchain protocols, and several practical candidates have been proposed based on exponentiation in a large finite field: Sloth++, Veedo, MinRoot. The underlying assumption of these constructions is that computing an exponentiation x^e requires at least log2(e) sequential multiplications. In this work, we analyze the security of these algebraic VDF candidates. In particular, we show that the latency of exponentiation can be reduced using parallel computation, against the preliminary assumptions.

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.

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.