Separating Verifiable Delay Functions and Time-Lock Puzzles
摘要
Verifiable Delay Functions (VDFs) and Time-Lock Puzzles (TLPs) are central to timed cryptography and have many applications to randomness beacons, fair multiparty computation, proofs of replication, and resource-efficient blockchains – to mention just a few. Constructions of VDFs and TLPs follow two general approaches. The first is direct constructions from suitable sequentiality assumptions (e.g., repeated squarings in hidden-order groups and the existence of non-parallelizing languages) and possibly additional cryptographic assumptions. The second approach is generic constructions of VDFs and TLPs from each other, possibly relying on additional non-sequential assumptions. While there is an impressive body of results following the first approach, the second is far less successful. In particular, we are only aware of the results of (a) Abusalah et al. [PKC’26], who construct one-time VDFs (restricted VDFs that don’t provide preprocessing security) from TLPs and indistinguishability obfuscation, and (b) Renawi [bachelor thesis 2020], who constructs TLPs from VDFs and (extractable) witness encryption. In this paper, we study fully-black-box (FBB) constructions of VDFs and TLPs from each other and prove the impossibility of such constructions. In particular, we prove the impossibility of (a) oracle-aided VDFs from oracle-aided TLPs, and (b) oracle-aided TLPs from oracle-aided VDFs. Besides their theoretic relevance, our results partially explain the lack of success of constructing VDFs and TLPs from each other in a black-box way and leave open the possibility of non-black-box constructions and constructions that rely on additional assumptions.