International Association for Cryptologic Research

International Association
for Cryptologic Research


Cryptanalysis of Algebraic Verifiable Delay Functions

Alex Biryukov , University of Luxembourg
Ben Fisch , Yale, USA
Gottfried Herold , Ethereum Foundation
Dmitry Khovratovich , Ethereum Foundation
Gaëtan Leurent , INRIA, France
María Naya-Plasencia , INRIA, France
Benjamin Wesolowski , ENS Lyon, France
Search ePrint
Search Google
Conference: CRYPTO 2024
Abstract: 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.
  title={Cryptanalysis of Algebraic Verifiable Delay Functions},
  author={Alex Biryukov and Ben Fisch and Gottfried Herold and Dmitry Khovratovich and Gaëtan Leurent and María Naya-Plasencia and Benjamin Wesolowski},