Paper 2024/766

Breaking Verifiable Delay Functions in the Random Oracle Model

Ziyi Guan, École Polytechnique Fédérale de Lausanne
Artur Riazanov, École Polytechnique Fédérale de Lausanne
Weiqiang Yuan, École Polytechnique Fédérale de Lausanne

A verifiable delay function (VDF) is a cryptographic primitive that takes a long time to compute, but produces a unique output that is efficiently and publicly verifiable. Mahmoody, Smith and Wu (ICALP 2020) prove that VDFs satisfying both perfect completeness and adaptive perfect uniqueness do not exist in the random oracle model. Moreover, Ephraim, Freitag, Komargodski, and Pass (EUROCRYPT 2020) construct a VDF with perfect completeness and computational uniqueness, a much weaker guarantee compare to perfect uniqueness, in the random oracle model under the repeated squaring assumption. In this work, we close the gap between existing constructions and known lower bounds by showing that VDFs with imperfect completeness and non-adaptive computational uniqueness cannot be constructed in the pure random oracle model (without additional computational assumptions).

Available format(s)
Publication info
verifiable delay functionsrandom oracle modelquery complexitydecision trees
Contact author(s)
ziyi guan @ epfl ch
artur riazanov @ epfl ch
weiqiang yuan @ epfl ch
2024-05-20: revised
2024-05-19: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ziyi Guan and Artur Riazanov and Weiqiang Yuan},
      title = {Breaking Verifiable Delay Functions in the Random Oracle Model},
      howpublished = {Cryptology ePrint Archive, Paper 2024/766},
      year = {2024},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.