Paper 2021/915

A PCP Theorem for Interactive Proofs and Applications

Gal Arnon, 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.

Note: Minor corrections to section 2.2

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in Eurocrypt 2022
Keywords
interactive proofsprobabilistically checkable proofsinteractive oracle proofs
Contact author(s)
galarnon42 @ gmail com
alexch @ berkeley edu
eylony @ gmail com
History
2022-05-05: last of 6 revisions
2021-07-08: received
See all versions
Short URL
https://ia.cr/2021/915
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/915,
      author = {Gal Arnon and Alessandro Chiesa and Eylon Yogev},
      title = {A PCP Theorem for Interactive Proofs and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/915},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/915}},
      url = {https://eprint.iacr.org/2021/915}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.