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
Abstract

A verifiable delay function (VDF) is a cryptographic primitive that requires a long time to compute (even with parallelization), but produces a unique output that is efficiently and publicly verifiable. We prove that VDFs with \emph{imperfect completeness} and \emph{computational uniqueness} do not exist in the random oracle model. This also rules out black-box constructions of VDFs from other cryptographic primitives, such as one-way permutations and collision-resistant hash functions. Prior to our work, Mahmoody, Smith and Wu (ICALP 2020) prove that VDFs satisfying both \emph{perfect completeness} and \emph{perfect uniqueness} do not exist in the random oracle model; on the other hand, Ephraim, Freitag, Komargodski, and Pass (Eurocrypt 2020) construct VDFs with \emph{perfect completeness} and \emph{computational uniqueness} in the random oracle model assuming the hardness of repeated squaring. Our result is optimal -- we bridge the current gap between previously known impossibility results and existing constructions.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
verifiable delay functionsrandom oracle modelquery complexitydecision trees
Contact author(s)
ziyi guan @ epfl ch
artur riazanov @ epfl ch
weiqiang yuan @ epfl ch
History
2024-10-03: last of 2 revisions
2024-05-19: received
See all versions
Short URL
https://ia.cr/2024/766
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/766,
      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},
      url = {https://eprint.iacr.org/2024/766}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.