No reduction from ROM to VDF
Statement
No reduction of any kind from the random oracle model to verifiable delay functions exists. With running time measured by oracle queries and parallel time by rounds of oracle queries, VDFs with imperfect completeness and non-adaptive computational uniqueness do not exist in the random oracle model when the setup is public-coin — GRY25 — nor when the setup is private-coin, even if it is computationally expensive — AAK+25.
Notes
- An earlier result covers VDFs with perfect uniqueness: an attacker finds the output in roughly as many rounds of queries as verification takes, with queries in total — MSW20.
- For public-coin setup, the impossibility also rules out black-box constructions of VDFs from one-way functions, one-way permutations and collision-resistant hash functions — GRY25.
- With a computational assumption added, the model admits VDFs: assuming the hardness of repeated squaring, there are VDFs with perfect completeness and computational uniqueness in the random oracle model — EFKP20. There the adversaries are efficient algorithms with oracle access, bounded in computation and not only in oracle queries, so the result does not contradict the barrier — standard.