Paper 2016/116

Interactive Oracle Proofs

Eli Ben-Sasson, Alessandro Chiesa, and Nicholas Spooner

Abstract

We initiate the study of a proof system model that naturally combines two well-known models: interactive proofs (IPs) and probabilistically-checkable proofs (PCPs). An *interactive oracle proof* (IOP) is an interactive proof in which the verifier is not required to read the prover's messages in their entirety; rather, the verifier has oracle access to the prover's messages, and may probabilistically query them. IOPs simultaneously generalize IPs and PCPs. Thus, IOPs retain the expressiveness of PCPs, capturing NEXP rather than only PSPACE, and also the flexibility of IPs, allowing multiple rounds of communication with the prover. These degrees of freedom allow for more efficient "PCP-like" interactive protocols, because the prover does not have to compute the parts of a PCP that are not requested by the verifier. As a first investigation into IOPs, we offer two main technical contributions. First, we give a compiler that maps any public-coin IOP into a non-interactive proof in the random oracle model. We prove that the soundness of the resulting proof is tightly characterized by the soundness of the IOP against *state restoration attacks*, a class of rewinding attacks on the IOP verifier. Our compiler preserves zero knowledge, proof of knowledge, and time complexity of the underlying IOP. As an application, we obtain blackbox unconditional ZK proofs in the random oracle model with quasilinear prover and polylogarithmic verifier, improving on the result of Ishai et al.\ (2015). Second, we study the notion of state-restoration soundness of an IOP: we prove tight upper and lower bounds in terms of the IOP's (standard) soundness and round complexity; and describe a simple adversarial strategy that is optimal across all state restoration attacks. Our compiler can be viewed as a generalization of the Fiat--Shamir paradigm for public-coin IPs (CRYPTO~'86), and of the "CS proof" constructions of Micali (FOCS~'94) and Valiant (TCC~'08) for PCPs. Our analysis of the compiler gives, in particular, a unified understanding of all of these constructions, and also motivates the study of state restoration attacks, not only for IOPs, but also for IPs and PCPs.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
probabilistically checkable proofsinteractive proofsFiat–Shamir paradigmcomputationally-sound proofs
Contact author(s)
alexch @ berkeley edu
History
2016-04-29: last of 2 revisions
2016-02-11: received
See all versions
Short URL
https://ia.cr/2016/116
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2016/116,
      author = {Eli Ben-Sasson and Alessandro Chiesa and Nicholas Spooner},
      title = {Interactive Oracle Proofs},
      howpublished = {Cryptology ePrint Archive, Paper 2016/116},
      year = {2016},
      note = {\url{https://eprint.iacr.org/2016/116}},
      url = {https://eprint.iacr.org/2016/116}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.