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

This work resolves the open problem of whether verifiable delay functions (VDFs) can be constructed in the random oracle model. A 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 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 functions, one-way permutations and collision-resistant hash functions. Prior to our work, Mahmoody, Smith and Wu (ICALP 2020) prove that \emph{perfectly unique} VDFs (a much stronger form of VDFs) do not exist in the random oracle model; on the other hand, Ephraim, Freitag, Komargodski, and Pass (Eurocrypt 2020) construct VDFs 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. We initiate the study of \emph{proof of work functions}, a new cryptographic primitive that shares similarities with both VDFs and proof of works. We show that a stronger form of it does not exist in the random oracle model, leaving open the fascinating possibility of a random-oracle-based construction.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint.
Keywords
verifiable delay functionsproof of work functionsrandom oracle modelquery complexity
Contact author(s)
ziyi guan @ epfl ch
artur riazanov @ epfl ch
weiqiang yuan @ epfl ch
History
2025-02-17: last of 5 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.