Falsifiable Assumptions in Non-Interactive Proofs
Explore distributed prover interactive proofs and succinct interactive arguments, delving into the use of non-interactive arguments like SNARKs and the need for non-falsifiable assumptions in the field. Understand the challenges and solutions in achieving interactivity and succinctness in proof systems.
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
Distributed-Prover Interactive Proofs Ilan Komargodski Hebrew University and NTT Research Pratik Soni University of Utah Sourav Das UIUC Elaine Shi Carnegie Mellon University Rex Fernando Aptos Labs
Interactive Arguments x w x Prover Verifier (completeness)
Interactive Arguments ? x x Prover Verifier (soundness)
Succinct Interactive Arguments x Too large! w x
Succinct Interactive Arguments x Too large! w x Want transcript much smaller than |w| Kilian 1992
Our Setting: Distributed Prover x w x Communication between provers must be small too!
Languages? x w x
Solution: Non-Interactive Arguments? (SNARKs) Simple case: let s prove a conjunction ?, ?,?? ? ? ? ? ? ?1 ?2 ?3 ?4 Proves I saw correct proofs for ??and ?? ?1 ?2 ?3 ?4 Recursive composition ?
Solution: Non-Interactive Arguments? Simple case: let s prove a conjunction ?, ?,?? ? ? ? ? ? ?1 ?2 ?3 ?4 Problem 2: how to handle more general statements (not just conjunctions)? Proves I saw correct proofs for ??and ?? ?1 ?2 ?3 ?4 Recursive composition ? Non-interactivity is needed for recursive composition Problem 1: Succinct non-interactivity (SNARKs) requires non-falsifiable assumptions! (Gentry-Wichs 2015)
? w
Our Main Question w Can we do this only using falsifiable assumptions? ? Compiler x w x
Our Main Result w Can we do this only using falsifiable assumptions? Compiler Yes! (with a CRS) Assumption: RSA (or class groups) Round overhead: polylog Space overhead: poly(?) x w x
Our Approach: Polynomial IOP Instantiate with polynomial commitment Polynomial Oracle ? ? ?( ?) w x x
Our Approach: Polynomial IOP BHRRS21: Implemented streaming polynomial commitment Polynomial Oracle Prover streams ?? values (defines deg-? multilinear polynomial) ?1,?2, ? ?( ?) w x x Sumcheck argument over ? Can compute sumcheck prover s messages with streaming access to ? ? ,? ? , (BTVW14)
Our Approach: Polynomial IOP Polynomial Oracle ? ?( ?) x Problem 1: how do we represent distributed interactive verification procedure as a multilinear polynomial ? distributed between the provers? Problem 2: how do we modify polynomial commitment to support distributed commitment/evaluation proofs? Problem 3: how do the provers compute the sumcheck messages in a distributed way? Solutions: see our paper!
