Interactive Oracle Proofs
We initiate the study of a proof system model that naturally combines interactive proofs (IPs) and probabilistically-checkable proofs (PCPs), and generalizes interactive PCPs (which consist of a PCP followed by an IP). We define an interactive oracle proo
- PDF / 658,221 Bytes
- 30 Pages / 439.37 x 666.142 pts Page_size
- 2 Downloads / 220 Views
3
Technion, Haifa, Israel [email protected] 2 UC Berkeley, Berkeley, USA [email protected] University of Toronto, Toronto, Canada [email protected]
Abstract. We initiate the study of a proof system model that naturally combines interactive proofs (IPs) and probabilistically-checkable proofs (PCPs), and generalizes interactive PCPs (which consist of a PCP followed by an IP). We define an interactive oracle proof (IOP) to be 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 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. IOPs have already found several applications, including unconditional zero knowledge [BCGV16], constant-rate constant-query probabilistic checking [BCG+16], and doubly-efficient constant-round IPs for polynomial-time bounded-space computations [RRR16]. 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 that is reminiscent of, but incomparable to, resetting attacks. 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, in expectation, 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 these constructions, and also motivates the study of state restoration attacks, not only for IOPs, but also for IPs and PCPs. Parts of this paper appear in the third author’s master’s thesis (April 2015) in the Department of Computer Science at ETH Zurich, supervised by Alessandro Chiesa and Thomas Holenstein. Independent of our work, [RRR16] introduce the notion of Probabilistically Checkable Interactive Proofs, which is the same as our notion of Interactive Oracle Proofs. c International Association for Cryptologic Research 2016 M. Hirt and A. Smith (Eds.): TCC 2016-B, Part II, LNCS 9986, pp. 31–60, 2016. DOI: 10.1007/978-3-662-53644-5 2
32
E. Ben-Sasson et al. When applied to known IOP constructions, our compiler implies, e.g., blackbox unconditional ZK proofs in the random oracle model with quasilinear prover and polylogarithmic verifier, improving on a result of [IMSX15].
1
Introduction
The notion of proof is central to modern cryptography and complexity theory. The class NP, for example, is the set of la
Data Loading...
