Impossibility of VDFs in the ROM: The Complete Picture

Hamza Abusalah; Karen Azari; Chethan Kamath; Erkan Tairi; Maximilian von Consbruch

Paper 2025/1773

Impossibility of VDFs in the ROM: The Complete Picture

Hamza Abusalah

, IMDEA Software Institute

Karen Azari

, University of Vienna, Austria

Chethan Kamath

, IIT Bombay

Erkan Tairi

, University of California, Berkeley

Maximilian von Consbruch, University of Vienna, Austria

Abstract

We study whether Verifiable Delay Functions (VDFs) can be constructed in the (plain) Random Oracle Model (ROM) without any computational assumptions. A first partial answer to this question is due to Mahmoody, Smith, and Wu [ICALP 2020] where they rule out perfectly unique VDFs in the ROM. Building on this result, Guan, Riazanov, and Yuan [CRYPTO 2025] prove that VDFs with computational uniqueness and public-coin setup are impossible in the ROM. These works leave open the possibility of constructing computationally unique VDFs with private-coin setup in the ROM. We resolve this problem and additionally rule out computationally-unique VDFs with computationally expensive private-coin setup in the ROM.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Published by the IACR in EUROCRYPT 2026
Keywords: Verifiable Delay Functions Random Oracle Model Timed Cryptography
Contact author(s): hamza abusalah @ imdea org
karen azari @ univie ac at
ckamath @ cse iitb ac in
erkan tairi @ berkeley edu
mvconsbruch @ mailbox org
History: 2026-03-05: revised; 2025-09-28: received; See all versions
Short URL: https://ia.cr/2025/1773
License: CC BY

BibTeX

@misc{cryptoeprint:2025/1773,
      author = {Hamza Abusalah and Karen Azari and Chethan Kamath and Erkan Tairi and Maximilian von Consbruch},
      title = {Impossibility of {VDFs} in the {ROM}: The Complete Picture},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/1773},
      year = {2025},
      url = {https://eprint.iacr.org/2025/1773}
}