Impossibility of VDFs in the ROM: The Complete Picture

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

doi:10.1007/978-3-032-25330-9_1

Impossibility of VDFs in the ROM: The Complete Picture

Hamza Abusalah (Corresponding author)
, Karen Azari
, Chethan Kamath
, Erkan Tairi
, Maximilian von Consbruch

Research Group Theory and Applications of Algorithms

Publications: Contribution to book › Contribution to proceedings › Peer Reviewed

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.

Original language	English
Title of host publication	Advances in Cryptology – EUROCRYPT 2026
Subtitle of host publication	45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings
Editors	Joan Daemen, Emmanuel Thomé
Place of Publication	Cham
Publisher	Springer
Pages	3-32
Number of pages	30
Volume	5
ISBN (Electronic)	978-3-032-25330-9
ISBN (Print)	9783032253293
DOIs	https://doi.org/10.1007/978-3-032-25330-9_1
Publication status	Published - 1 May 2026

Publication series

Series	Lecture Notes in Computer Science
Volume	16545
ISSN	0302-9743

Funding

Hamza Abusalah is supported by the PICOCRYPT project that has received funding from the European Research Council (ERC) under the European Unions Horizon 2020 research and innovation programme (Grant agreement No. 101001283), partially supported by ESPADA (PID2022-142290OB-I00) and CEX2024-001471-M funded by MCIN/AEI/10.13039/501100011033/. Erkan Tairi is supported in part by the France 2030 ANR-22-PECY-003 SecureCompute Project, by the Austrian Science Fund (FWF) Project J4879-N, by the Bakar Funds and Peder Sather Funds.

Austrian Fields of Science 2012

102017 Cryptology

Access to Document

10.1007/978-3-032-25330-9_1

http://eprints.cs.univie.ac.at/8697/

Cite this

Abusalah, H., Azari, K., Kamath, C., Tairi, E., & Consbruch, M. V. (2026). Impossibility of VDFs in the ROM: The Complete Picture. In J. Daemen, & E. Thomé (Eds.), Advances in Cryptology – EUROCRYPT 2026: 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings (Vol. 5, pp. 3-32). Springer. https://doi.org/10.1007/978-3-032-25330-9_1

Abusalah, Hamza ; Azari, Karen ; Kamath, Chethan et al. / Impossibility of VDFs in the ROM: The Complete Picture. Advances in Cryptology – EUROCRYPT 2026: 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings. editor / Joan Daemen ; Emmanuel Thomé. Vol. 5 Cham : Springer, 2026. pp. 3-32 (Lecture Notes in Computer Science, Vol. 16545).

@inproceedings{6d3c43c961444d4592a7a36965ac976d,

title = "Impossibility of VDFs in the ROM: The Complete Picture",

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.",

author = "Hamza Abusalah and Karen Azari and Chethan Kamath and Erkan Tairi and Consbruch, \{Maximilian von\}",

note = "Publisher Copyright: {\textcopyright} International Association for Cryptologic Research 2026.",

year = "2026",

month = may,

day = "1",

doi = "10.1007/978-3-032-25330-9\_1",

language = "English",

isbn = "9783032253293",

volume = "5",

series = "Lecture Notes in Computer Science",

publisher = "Springer",

pages = "3--32",

editor = "Joan Daemen and Emmanuel Thom{\'e}",

booktitle = "Advances in Cryptology – EUROCRYPT 2026",

}

Abusalah, H, Azari, K, Kamath, C, Tairi, E & Consbruch, MV 2026, Impossibility of VDFs in the ROM: The Complete Picture. in J Daemen & E Thomé (eds), Advances in Cryptology – EUROCRYPT 2026: 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings. vol. 5, Springer, Cham, Lecture Notes in Computer Science, vol. 16545, pp. 3-32. https://doi.org/10.1007/978-3-032-25330-9_1

Impossibility of VDFs in the ROM: The Complete Picture. / Abusalah, Hamza (Corresponding author); Azari, Karen; Kamath, Chethan et al.
Advances in Cryptology – EUROCRYPT 2026: 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings. ed. / Joan Daemen; Emmanuel Thomé. Vol. 5 Cham: Springer, 2026. p. 3-32 (Lecture Notes in Computer Science, Vol. 16545).

Publications: Contribution to book › Contribution to proceedings › Peer Reviewed

TY - GEN

T1 - Impossibility of VDFs in the ROM: The Complete Picture

AU - Abusalah, Hamza

AU - Azari, Karen

AU - Kamath, Chethan

AU - Tairi, Erkan

AU - Consbruch, Maximilian von

PY - 2026/5/1

Y1 - 2026/5/1

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/105040154531

U2 - 10.1007/978-3-032-25330-9_1

DO - 10.1007/978-3-032-25330-9_1

M3 - Contribution to proceedings

SN - 9783032253293

VL - 5

T3 - Lecture Notes in Computer Science

SP - 3

EP - 32

BT - Advances in Cryptology – EUROCRYPT 2026

A2 - Daemen, Joan

A2 - Thomé, Emmanuel

PB - Springer

CY - Cham

ER -

Abusalah H, Azari K, Kamath C, Tairi E, Consbruch MV. Impossibility of VDFs in the ROM: The Complete Picture. In Daemen J, Thomé E, editors, Advances in Cryptology – EUROCRYPT 2026: 45th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Rome, Italy, May 10–14, 2026, Proceedings. Vol. 5. Cham: Springer. 2026. p. 3-32. (Lecture Notes in Computer Science, Vol. 16545). doi: 10.1007/978-3-032-25330-9_1

Impossibility of VDFs in the ROM: The Complete Picture

Abstract

Publication series

Funding

Austrian Fields of Science 2012

Access to Document

Other files and links

Cite this