Cryptology ePrint Archive: Report 2021/915

A PCP Theorem for Interactive Proofs and Applications

Gal Arnon and Alessandro Chiesa and Eylon Yogev

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.

Category / Keywords: foundations / interactive proofs; probabilistically checkable proofs; interactive oracle proofs

Date: received 6 Jul 2021, last revised 20 Oct 2021

Contact author: galarnon42 at gmail com, alexch at berkeley edu, eylony at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20211020:085202 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]