Constant Round Interactive Proofs for Delegating Computations
"The research explores techniques for securely delegating computations to the cloud, addressing concerns of correctness and privacy through interactive proofs and efficient verification methods. It compares classical and doubly efficient interactive proofs, emphasizing the importance of computational soundness in bounded-depth circuits."
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
Constant Round Interactive Proofs for Delegating Computations Ron Rothblum MIT Joint work with Omer Reingold and Guy Rothblum
Delegating Computation Motivation: allow a computationally weak client to outsource its computation to the cloud. ? ? = ?(?)
Delegating Computation We do not want to blindly trust the cloud. ? ? = ?(?)
Secure Delegation Main security concerns: 1. Correctness: ? = ? ? ? 2. Privacy: cloud learns our secret data ?.
Secure Delegation Main security concerns: 1. Correctness: ? = ? ? ? 2. Privacy: cloud learns our secret data ?.
Doubly Efficient Interactive Proofs [GKR08] Goal: allow the client to verify the correctness of the result. Much faster than the time to compute ? Double efficiency requirement: 1. The verifier should be super efficient. 2. The prover should be relatively efficient. Also want to minimize the interaction. Proving should not be much harder than computing
Comparison with Classical Interactive Proofs [GMR85] In an interactive proof, an unbounded prover convinces a poly-time verifier that ? ?. Classical Interactive Proof Doubly Efficient Interactive Proof Verifier Poly-time Linear-time Honest Prover Unbounded (Poly-space) Poly-time
Doubly Efficient Interactive Proofs ? ?? Prover ? Verifier ? Completeness: ? ?, P??? ? ??????? = 1. Soundness: ? ? and ? ???? ? ??????? 1/2. Running time of ?: ? ? . Running time of ?: ????(?).
Prior Work [GKR08]: Bounded-depth circuits (logspace- uniform NC). Number of rounds grows with the circuit depth Computational Soundness: [Killian94]: 2-round for NP based on CRH. [KRR14]: 1-round for P based on quasi-poly PIR. * Many other results in related models or under strong cryptographic assumptions.
Main Result Thm: Every language computable in poly(?) time and ??space has a constant-round public-coin doubly-efficient interactive proof. Sufficiently small constant
Tightness Define IPDEas class of languages having doubly efficient interactive proofs. DTISP poly ? ,?? IPDE P SPACE( ?(?))
Tightness Define IPDEas class of languages having doubly efficient interactive proofs. DTISP poly ? ,?? IPDE P SPACE( ?(?))
Tightness Define IPDEas class of languages having doubly efficient interactive proofs. DTISP poly ? ,?? IPDE P SPACE( ?(?))
Main Result (General) Thm: Let ? > 0 be a constant. Every ? DTISP(?,?) has a public-coin interactive proof with: 1. Verifier time: ?? poly ? + ? polylog(?). 2. Prover time: ?1+? poly(?). 3. Communication: ?? poly(?). 4. Rounds: 2 ? 1/?. 1 ? > ? log ? for sufficiently small c > 0 Some dependence on ? seems inherent
Comparison with Previous Work Two main improvements: 1. The class IPDEis much larger than previously known (even disregarding #rounds). 2. Previously constant round IP with linear-time verifier not known even for LOGSPACE (even with unbounded prover).
Corollaries Succinct constant-round zero knowledge proofs for NP statements with bounded-space witness relation. Constant-round interactive proof of proximity (IPP) with sublinear verification for bounded- space computations (via [RVW13]). Doubly efficient interactive proofs for NC with significantly broader uniformity (via [GKR08]).
Proof Outline Let ? DTISP ?,? . ? ? Goal: construct interactive proof for ? with verifier time ?.
Proof Outline Let ? DTISP ?,? . ??/??2?/? ?(? 1)?/? Idea: Prover sends Turing machine configuration in ? ? intermediate steps.
Proof Outline Let ? DTISP ?,? . ??/??2?/? ?(? 1)?/? Idea: subcomputations are in DTISP(?/?,?) so just recurse on all. Problem: takes ? time
Proof Outline Let ? DTISP ?,? . ??/??2?/? ?(? 1)?/? Idea 2: choose just a few at random and recurse. Problem: huge soundness error.
Proof Outline Want best of both: verify ? computations much more efficiently than ? independent executions (with good soundness). Hope: suppose ? has interactive proof with complexity ? interactive proof for verifying that ?1, ,?? ? with ? ? complexity. We call this amortizing interactive proofs since the relative cost per instance decreases with ?.
Amortizing NP Statements For this talk focus on simpler task: amortizing NP statements. Prover given ?1, ,?? and witnesses (?1, ,??) of length ? and needs to interactively convince verifier with communication ? ?. We do this for NP statements with a unique witness (general question still open).
Amortizing UP Statements Recall: UP is a restriction of NP in which YES instances have a unique accepting witness. Example: unique-SAT, distinguish unsatisfiable formulas from formulas with exactly one satisfying assignment.
Amortizing UP Statements Thm: Suppose ? UP. There is an interactive proof for verifying that ?1, ,?? ? with parameters*: Communication: O(?) + poly ?,log? Verifier time: ? ? ? + poly ?,log? Prover time: poly ?,? Rounds: O(log ?) Can tradeoff rounds with other parameters (important for constant-round interactive proofs) * Hiding some polylog factors
Proof Overview: How to Amortize UP
Amortizing UP Statements First Try Assume that location of PCP queries does not depend on input ?(??, ,??) ?(??, ,??,??, ,??) 1. Generate PCP queries ? ?1= ??? ?1,?1 ? ?2= ??? ?2,?2 ?? ? = 2. Accept if PCP verifier accepts all ? statements. ??= ??? ??,??
Amortizing UP Statements First Try Extremely efficient just ?(? + log?) comm.! Totally insecure soundness of PCP is only guaranteed if PCP proof is written in advance. Prover can easily cheat if it is allowed to answer after seeing the queries.
Amortizing UP Statements Second Try ?(??, ,??) ?(??, ,??,??, ,??) 1. Generate PCP queries ? ? ?1= ??? ?1,?1 ?2= ??? ?2,?2 ? ? = ?? 2. Check that PCP verifier accepts all ? statements. ??= ??? ??,?? 3. Check AQconsistent with ?. ? = ? ??? ? ???
Single Deviations Provers Intuitively the hardest case Not sound in general but we ll make two relaxations: Suppose only one ?? ?. Assume single-deviation prover: when sending ??, prover must answer honestly on all rows ? ? . Unrealistic assumption! ? commits prover to a PCP for ?? ? = ? + ? ? ?? Assumption ??consistent with ? soundness!
Amortizing UP Statements Third Try Plan: a fancier (and slightly longer) commitment. ? ? Main tool: Encoding ?: 0,1? 0,1 ? ? bits ~? bits ? ? ?(?) for every ? ? of distance < ?.
Amortizing UP Statements Third Try ?(??, ,??) ?(??, ,??,??, ,??) 1. Generate PCP queries ? ? ?1= ??? ?1,?1 ?2= ??? ?2,?2 ? ? = ?? 2. Check that PCP verifier accepts all ? statements. ??= ??? ??,?? 3. Check AQconsistent with ?. ? =
Soundness Prover has two options: 1. deviate on ? rows intuitively we are fine. 2. deviate on > ? rows it s answers are inconsistent with the unique PCPs of ? rows. Using uniqueness! Verifier chooses at random ?/? statements and asks prover to send the entire ??? for these statements.
Amortizing UP Statements ?(??, ,??) ?(??, ,??,??, ,??) 1. Generate PCP queries ? ? ?1= ??? ?1,?1 ?2= ??? ?2,?2 ? ? = ?? 2. Check that PCP verifier accepts all ? statements. ??= ??? ??,?? 3. Check AQconsistent with ?. ? = ? 4. ? ?[?] of ? = ?/? ?? ? ? 5. Check PCPs correct and consistent with ??.
Amortizing UP Statements Complexity Communication: ? ? poly(?) + ? ? +? ? poly(?) ? Set ? = ? ? poly(?) + ?(?)
Better Amortization For every ? ? want to verify: 1. ?? ?. 2. Value of ??at a few particular locations. ?/? slightly more complicated ?? statements solve by recursively amortizing them. Original ??is a PCP for the new statement (with higher query complexity).
Amortizing UP Statements Thm: Suppose ? UP. There is an interactive proof for verifying that ?1, ,?? ? with parameters*: Verifier time: ? ? ? + poly ?,log? Prover time: poly ?,? Communication: O(?) + poly ?,log? Rounds: O(log ?) * Hiding some polylog factors
Amortizing Interactive Proofs To extend these ideas to the interactive setting need interactive analogs of PCPs and UP. Non-Interactive Interactive UP Unambiguous ?? Uniqueness Local checking PCP Probabilistically Checkable ??
Unambiguous Interactive Proofs (UIP) Unambiguity: if ? ? and prover deviates from the protocol at any point, then whp over remaining coins, verifier rejects at the end of the protocol. Example: sumcheck protocol. UP corresponds to 1-message deterministic UIP.
Probabilistically Checkable Interactive Proofs (PCIP) Standard public-coin interactive proof but at the end of the protocol the verifier only needs to reads a few bits from the transcript. One round version is exactly ???! Related to (but different from) Interactive PCPs [KR07]. Also need a notion of unambiguous PCIP.
From Amortization to Interactive Proofs Assume unambiguous PCIPs for length ? computations, use amortization to get unambiguous PCIPs for length ? ? computations. Problem: amortization increases number of PCIP queries so we can t just keep amortizing. Solution: a query reduction transformation on PCIPs. The interactive proof is constructed by interleaving amortization and query reduction steps (ala zig-zig product).
Summary Main result: Constant-round interactive proofs with linear-time verification for polynomial-time bounded polynomial-space. New concepts: amortizing IP/NP, unambiguous IP, PCIP. Open: IP = PSPACE with efficient prover. General NP amortization Improve: number of rounds, polynomial dependence on space, etc
