CryptoDB
A PCP Theorem for Interactive Proofs and Applications
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | EUROCRYPT 2022 |
| Abstract: | The celebrated PCP Theorem states that any language in NP can be decided via a verifier that reads O(1) bits from a polynomially long proof. Interactive oracle proofs (IOP), a generalization of PCPs, allow the verifier to interact with the prover for multiple rounds while reading a small number of bits from each prover message. While PCPs are relatively well understood, the power captured by IOPs (beyond $\NP$) has yet to be fully explored. We present a generalization of the PCP theorem for interactive languages. We show that any language decidable by a k(n)-round IP has a k(n)-round public-coin IOP, where the verifier makes its decision by reading only O(1) bits from each (polynomially long) prover message and $O(1)$ bits from each of its own (random) messages to the prover. Our result and the underlying techniques have several applications. We get a new hardness of approximation result for a stochastic satisfiability problem, we show IOP-to-IOP transformations that previously were known to hold only for IPs, and we formulate a new notion of PCPs (index-decodable PCPs) that enables us to obtain a commit-and-prove SNARK in the random oracle model for nondeterministic computations. |
Video from EUROCRYPT 2022
BibTeX
@inproceedings{eurocrypt-2022-31845,
title={A PCP Theorem for Interactive Proofs and Applications},
publisher={Springer-Verlag},
author={Gal Arnon and Alessandro Chiesa and Eylon Yogev},
year=2022
}