Verifiable Delay Functions and Zero-Knowledge VDFs
Learn about Verifiable Delay Functions (VDFs) and Zero-Knowledge VDFs, their applications, security, and contributions in the field of computational number theory and complexity theory, including watermarkable variants.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.
E N D
Presentation Transcript
Watermarkable Watermarkable and Zero and Zero- -Knowledge Verifiable Delay Functions Knowledge Verifiable Delay Functions from any Proof of Exponentiation Charlotte Hoffmann, Krzysztof Pietrzak Institute of Science and Technology Austria
Introduction Verifiable delay functions (VDFs) were introduced by Boneh, Bonneau, B nz and Fisch [BBBF18] Original application: distributed systems, blockchains Many other applications: Proof systems (polynomial commitments, SNARKS, signatures) Complexity theory (hardness of PPAD) Computational number theory (primality testing) Variant of VDFs: Watermarkable [Wes19] and zero-knowledge VDFs [ABC22] 2
Verifiable Delay Functions (VDFs) [BBBF18] ? ?:? ? a function that takes ? steps to evaluate 1 3 ? 2 ?(?) log? steps to verify Repeated squaring ? ? = ?2? ?,?(?) Proof of Exponentiation (PoE) [Pie19, Wes19] ? accept/reject ? ? 3
Watermarkable Watermarkable Verifiable Delay Functions [Wes19] ?,?(?) ? A watermarkable VDF is a VDF in which the proof can be tied to a prover. Prover can be rewarded for work. 4
Security: Watermark Unforgeability (?,? ? ,?) (?,? ? ,?, ,?) 1 3 ? 2 ? ? [Wes19]: construction without security proof 5
Zero Zero- -Knowledge Knowledge Verifiable Delay Functions [ABC22] ?,?(?) ?(?) ? ? zkPoK A zero-knowledge VDF is a VDF in which no information about ?(?) is revealed. [ABC22] construct a zero-knowledge variant of [Wes19]. Application: Short-lived proofs and signatures 6
Our Contribution We construct watermarkable VDFs and zkVDFs from any PoE in hidden order groups. First watermarkable VDF with security proof First zero-knowledge version of Pietrzak s VDF and all of its variants We introduce zero knowledge proofs of sequential work and give the first construction. Better deniability for short-lived proofs [ABC22] Removes adaptive root assumption [ABC22] 7
VDFs from Repeated Squaring and PoEs ? ? = ?2? in hidden order group ? If ord(?) is known: compute ? 2? mod ord ? and ?? Otherwise: ? sequential squarings ? ?2 ?22 ?23 ?2? PoE Completeness: if ? is honest, ? accepts Soundness: for all ? , if ?2? ?, then ? rejects with high probability 9
Watermarkable VDF Construction A First Attempt ?2?= ? ? Idea: Include unique identifier in Fiat-Shamir transformation [Wes19] ? ? ?2?= ? PoE Watermark unforgeability? Don t know how to prove it for [Wes19] Does not hold for [Pie19] (?,?,?,ID) (?,?,?) ? Hash(?,?,ID) ? Hash(?,?) 10
Watermarkable VDF Construction (?,? = ?2?) Proof of knowledge of ? such that ??= ? and ??= ? ? ? ? ? Hash( ,ID?) ? = (? ,? ,PoE(? ,? ), zkPoK(r)) (?,?,?) ? [2?] ? ?? ? ?? Soundness: Low order assumption Soundness of PoE and zkPoK ? = (? ,? ,PoE(? ,? ), zkPoK(r)) Watermark unforgeability: Zero-Knowledge of PoK Decisional Discrete Log assumption Decisional Iterated Squaring assumption ? 2?= ? Zero knowledge proof of knowledge Need to find ? (DL) or start from scratch 11
Zero Zero- -Knowledge Knowledge VDF Construction ? ? ?2?= ? 0/1 need ? repetitions in hidden order groups ? = (? ,? ,PoE ? ,? , zkPoK(?,?)) ? [2?] ? ?? ? ?? Observation: Zero-Knowledge Proof of Sequential Work is sufficient for application zkPoK ?,? zkPoK ? No guarantee that ? knows ? but proof that ? has evaluated the delay function on some ?? Proof of knowledge of ? and ? such that ??= ? and ??= ? 12
Summary and Open Problems Proof size: |PoE| + 4 elements |PoE| + 2 + 2 elements |PoE| + 4 elements We construct the first Watermarkable VDF with security proof, Zero-knowledge VDF for general PoE, Zero-knowledge proof of sequential work. We show how to obtain short-lived proofs from zkPoSW. Better deniability for short lived-proofs in [ABC22] Open Problem: Reduce proof size of zero-knowledge VDF Questions? 13
