Paper 2024/873

Cryptanalysis of Algebraic Verifiable Delay Functions

Alex Biryukov, University of Luxembourg, Esch-sur-Alzette, Luxembourg
Ben Fisch, Yale University, New Haven, USA
Gottfried Herold, Ethereum Foundation, Bonn, Germany
Dmitry Khovratovich, Ethereum Foundation, Luxembourg, Luxembourg
Gaëtan Leurent, INRIA, Paris, France
María Naya-Plasencia, INRIA, Paris, France
Benjamin Wesolowski, CNRS, ENS Lyon, Lyon, France
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 $\log_2 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.

Metadata
Available format(s)
PDF
Category
Attacks and cryptanalysis
Publication info
A minor revision of an IACR publication in CRYPTO 2024
Keywords
Verifiable Delay FunctionsMinRootVeedoSloth++cryptanalysissmoothness
Contact author(s)
gottfried herold @ ethereum org
gaetan leurent @ inria fr
maria naya_plasencia @ inria fr
History
2024-06-05: approved
2024-06-01: received
See all versions
Short URL
https://ia.cr/2024/873
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2024/873,
      author = {Alex Biryukov and Ben Fisch and Gottfried Herold and Dmitry Khovratovich and Gaëtan Leurent and María Naya-Plasencia and Benjamin Wesolowski},
      title = {Cryptanalysis of Algebraic Verifiable Delay Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2024/873},
      year = {2024},
      note = {\url{https://eprint.iacr.org/2024/873}},
      url = {https://eprint.iacr.org/2024/873}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.