Paper 2024/481
Watermarkable and ZeroKnowledge Verifiable Delay Functions from any Proof of Exponentiation
Abstract
A verifiable delay function $\texttt{VDF}(x,T)\rightarrow (y,\pi)$ maps an input $x$ and time parameter $T$ to an output $y$ together with an efficiently verifiable proof $\pi$ certifying that $y$ was correctly computed. The function runs in $T$ sequential steps, and it should not be possible to compute $y$ much faster than that. The only known practical VDFs use sequential squaring in groups of unknown order as the sequential function, i.e., $y=x^{2^T}$. There are two constructions for the proof of exponentiation (PoE) certifying that $y=x^{2^T}$, with Wesolowski (Eurocrypt'19) having very short proofs, but they are more expensive to compute and the soundness relies on stronger assumptions than the PoE proposed by Pietrzak (ITCS'19). A recent application of VDFs by Arun, Bonneau and Clark (Asiacrypt'22) are shortlived proofs and signatures, which are proofs and signatures which are only sound for some time $t$, but after that can be forged by anyone. For this they rely on "watermarkable VDFs", where the proof embeds a prover chosen watermark. To achieve stronger notions of proofs/signatures with reusable forgeability, they rely on "zeroknowledge VDFs", where instead of the output $y$, one just proves knowledge of this output. The existing proposals for watermarkable and zeroknowledge VDFs all build on Wesolowski's PoE, for the watermarkable VDFs there's currently no security proof. In this work we give the first constructions that transform any PoEs in hidden order groups into watermarkable VDFs and into zkVDFs, solving an open question by Arun et al.. Unlike our watermarkable VDF, the zkVDF (required for reusable forgeability) is not very practical as the number of group elements in the proof is a security parameter. To address this, we introduce the notion of zeroknowledge proofs of sequential work (zkPoSW), a notion that relaxes zkVDFs by not requiring that the output is unique. We show that zkPoSW are sufficient to construct proofs or signatures with reusable forgeability, and construct efficient zkPoSW from any PoE, ultimately achieving short lived proofs and signatures that improve upon Arun et al's construction in several dimensions (faster forging times, weaker assumptions). A key idea underlying our constructions is to not directly construct a (watermarked or zk) proof for $y=x^{2^T}$, but instead give a (watermarked or zk) proof for the more basic statement that $x',y'$ satisfy $x'=x^r,y'=y^r$ for some $r$, together with a normal PoE for $y'=(x')^{2^T}$.
Metadata
 Available format(s)
 Category
 Cryptographic protocols
 Publication info
 Preprint.
 Keywords
 Verifiable Delay FunctionsWatermarkingZero KnowledgeProofs of Exponentiation
 Contact author(s)

charlotte hoffmann @ ista ac at
pietrzak @ ista ac at  History
 20240322: approved
 20240322: received
 See all versions
 Short URL
 https://ia.cr/2024/481
 License

CC BY
BibTeX
@misc{cryptoeprint:2024/481, author = {Charlotte Hoffmann and Krzysztof Pietrzak}, title = {Watermarkable and ZeroKnowledge Verifiable Delay Functions from any Proof of Exponentiation}, howpublished = {Cryptology {ePrint} Archive, Paper 2024/481}, year = {2024}, url = {https://eprint.iacr.org/2024/481} }