Advancements in Interactive Proofs for Efficient Computation
Recent developments in interactive proofs focus on enhancing the efficiency of computations outsourced to untrusted servers, addressing concerns related to correctness and privacy. Solutions like doubly efficient interactive proofs offer a secure way to delegate computations while minimizing reliance on cloud services.
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. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Doubly Efficient Interactive Proofs Ron Rothblum
Outsourcing Computation Weak client outsources computation to the cloud. ? ? = ?(?)
Outsourcing Computation We do not want to blindly trust the cloud. ? ? = ?(?) Key security concerns: Correctness: why should we trust the server s answer? Privacy: keep client s sensitive data secret (closely related to homomorphic encryption)
Interactive Proofs to the Rescue? Interactive Proof [GMR85]: prover ? tries to interactively convince a polynomial-time verifier ? that ? ? = ?. ? ? = ? ? convinces ?. ? ? ? no ? can convince ? wp 1/2. Key Problem: in classical results complexity of proving is actually exponential: IP=PSPACE [LFKN90,Shamir90]: Interactive Proofs for space ? computations with 2poly ?prover, poly(?,?) verification, poly(?) rounds.
Doubly Efficient Interactive Proof [GKR08] Interactive proof for ? ? = ? where the prover is efficient, and the verifier is super efficient. Proportional to complexity of ? Much faster than complexity of ? Soundness holds against any (computationally unbounded) cheating prover.
Doubly Efficient Interactive Proofs: The State of the Art Logspace uniform ?? 1) [GKR08]: Bounded Depth Any bounded-depth circuit. (Almost) linear time verifier, poly-time prover. Number of rounds proportional to circuit depth. 2) [RRR16]: Bounded Space Any bounded-space computation. (Almost) linear time verifier, poly-time prover. ? ? rounds.
Constant-Round Doubly Efficient Interactive Proofs Theorem [RRR16]: ? > 0 s.t. every language computable in poly(?) time and ??space has an unconditionally sound interactive proof where: 1. Verifier is (almost) linear time. 2. Prover is polynomial-time. 3. Constant number of rounds. No cryptographic assumptions or operations Inherent (under reasonable conjectures)
Roadmap: A Taste of the Proof Iterative construction: 1. Start with interactive proof for short computations. 2. Build interactive proof for slightly longer computations. 3. Repeat.
Iterative Construction Suppose we have interactive proofs for time ?/? and space ? computations. Consider a time ? and space ? computation. ? ? ? ?
Divide & Conquer Divide: Prover sends Turing machine configuration in ? ? intermediate steps. ? ? ?(? 1)?/? ??/? ?2?/? Conquer? recurse on all subcomputations. Problem: verification blows up, no savings.
Divide & Conquer Divide: Prover sends Turing machine configuration in ? ? intermediate steps. ? ? ?(? 1)?/? ??/? ?2?/? Conquer? Choose a few at random and recurse. Problem: huge soundness error.
Best of Both Worlds? Can we batch verify ? instances much more efficiently than ? independent executions. Goal: Suppose ? ? can be verified in time ?. Want to verify ?1, ,?? ? in ? ? time.
Warmup: Batch Verification for ?? ?? ?? are all relations with unique accepting witnesses. Theorem [RRR16]: Every ? ??, has an interactive proof for verifying that ?1, ,?? ? with ? ???????(?) + ?(?) communication. ? = witness length
Tool: Probabilistically Checkable Proofs PCP Theorem [ ,ALMSS92, ]: Every NP witness ? has a PCP encoding ? = ???(?,?) that can be verified with a constant number of queries. ? = ??? ?,? ?(?) Furthermore, query locations don t depend on input.
PCPs Batch Verification? ?(??, ,??) ?(??,?? ,??,??) 1. Generate PCP queries ? ?1= ??? ?1,?1 ? ?2= ??? ?2,?2 ?? ? = 2. Accept if PCP verifier accepts all ? statements. ??= ??? ??,?? Extremely efficient just ?(? + ??? ?) communication! Totally insecure soundness of PCP is only guaranteed if PCP proof is written in advance.
Batch Verification via Checksums ?(??, ,??) ?(??,?? ,??,??) ? ?1= ??? ?1,?1 ?2= ??? ?2,?2 ? 1. Generate PCP queries ? ? = ?? 2. Check that PCP verifier accepts all ? statements. ??= ??? ??,?? 3. Check ??consistent with ?. ? = ? ???
Single Deviation Provers In general: not sound. Intuitively the hardest case Relaxed soundness: make two assumptions only one ?? ?. single-deviation ? : in answering queries ?, ? must answer honestly on all rows ? ? . Unjustifiable assumption!
Soundness vs. Single-Deviation Provers ?(??, ,?? , ,??) ? (??,??, ,?? , .??,??) ?
Soundness vs. Single-Deviation Provers ?(??, ,?? , ,??) ? (??,??, ,?? , .??,??) ? ?1= ??? ?1,?1 ?? = ? + ? ? ?? ? = ??= ??? ??,?? ? = ? ??? ? ???
Soundness vs. Single-Deviation Provers ?(??, ,?? , ,??) ? (??,??, ,?? , .??,??) ? ?1= ??? ?1,?1 ?? = ? + ? ? ?? ? 1. Generate PCP queries ? ? = ??= ??? ??,?? ? = ? ??? ? ???
Soundness vs. Single-Deviation Provers ?(??, ,?? , ,??) ? (??,??, ,?? , .??,??) ? ?1= ??? ?1,?1 ?? = ? + ? ? ?? ? 1. Generate PCP queries ? ? = ?? ??= ??? ??,?? 2. Check that PCP verifier accepts all ? statements. ? = 3. Check ??consistent with ?. ? ??? ? ??? Single-deviation ? must answers row ? by ?? ?? defined before queries ? were specified PCP soundness ? can t cheat
Handling General Cheating Provers For ? deviation prover: use fancy checksum of size ? ?. Consider ? = ?. Cheating prover has two options: 1. deviate on ? rows ? deviation, we re fine. 2. deviate on > PCPs of more than ? of rows. ? rows answers disagree with unique Since there is a unique PCP verifier will notice deviation and reject ? selects 100 ? rows at random and asks prover to send the entire PCP for these rows.
Batch Verification for ?? This gives ? multiplicative overhead. Can be improved to polylog ? by recursion. For batch verification of interactive proofs we introduce interactive analogs of ?? and ???.
Constant-Round Doubly Efficient Interactive Proofs Theorem [RRR16]: ? > 0 s.t. every language computable in poly(?) time and ??space has an unconditionally sound interactive proof where: 1. Verifier is (almost) linear time. 2. Prover is polynomial-time. 3. Constant number of rounds.
Open Problems Research directions: Bridge theory and practice. Sublinear time verification. Concrete questions: IP=PSPACE with efficient prover. Batch verification for all of NP. [GR17]: Simpler and more efficient protocols (even for smaller classes).
