We study the class of languages, denoted by @math , which have @math -prover games where each prover just sends a bit, with completeness @math and soundness error @math . For the case that @math (i.e., for the case of interactive proofs), Goldreich, Vadhan and Wigderson ( Computational Complexity'02 ) demonstrate that @math exactly characterizes languages having 1-bit proof systems with"non-trivial" soundness (i.e., @math ). We demonstrate that for the case that @math , 1-bit @math -prover games exhibit a significantly richer structure: + (Folklore) When @math , @math ; + When @math , @math ; + When @math , @math ; + For @math and sufficiently large @math , @math ; + For @math , @math . As such, 1-bit @math -prover games yield a natural "quantitative" approach to relating complexity classes such as @math , @math , @math , @math , and @math . We leave open the question of whether a more fine-grained hierarchy (between @math and @math ) can be established for the case when @math .
The work most closely related to our is the work by Goldreich, Vadhan and Wigderson @cite_3 mentioned above which in turn builds on a work by Goldreich and H stad @cite_14 ; just as we do, both these works investigate the complexity of interactive proofs with laconic'' provers. We have taken the question to an extreme in one direction (namely we focus only on provers that send a single bit); on the other hand, we have generalized the question by considering multi-prover interactive proofs, rather than just a single prover (as is the main focus in the above-mentioned works).
@cite_14 @cite_3
2038202352 2416431186 1970259241 2080578129
We continue the investigation of interactive proofs with bounded communication, as initiated by Goldreich & Hastad (1998). Let L be a language that has an interactive proof in which the prover sends few (say b) bits to the verifier. We prove that the complement L has a constant-round interactive proof of complexity that depends only exponentially on b. This provides the first evidence that for NP- complete languages, we cannot expect interactive provers to be much more "laconic" than the standard NP proof. When the proof system is further restricted (e.g., when b = 1, or when we have perfect completeness), we get significantly better upper bounds on the complexity of L. The celebrated IP=PSPACE Theorem of Lund et-al. (J.ACM 1992) and Shamir (J.ACM 1992), allows an all-powerful but untrusted prover to convince a polynomial-time verifier of the validity of extremely complicated statements (as long as they can be evaluated using polynomial space). The interactive proof system designed for this purpose requires a polynomial number of communication rounds and an exponential-time (polynomial-space complete) prover. In this paper, we study the power of more efficient interactive proof systems. Our main result is that for every statement that can be evaluated in polynomial time and bounded-polynomial space there exists an interactive proof that satisfies the following strict efficiency requirements: (1) the honest prover runs in polynomial time, (2) the verifier is almost linear time (and under some conditions even sub linear), and (3) the interaction consists of only a constant number of communication rounds. Prior to this work, very little was known about the power of efficient, constant-round interactive proofs (rather than arguments). This result represents significant progress on the round complexity of interactive proofs (even if we ignore the running time of the honest prover), and on the expressive power of interactive proofs with polynomial-time honest prover (even if we ignore the round complexity). This result has several applications, and in particular it can be used for verifiable delegation of computation. Our construction leverages several new notions of interactive proofs, which may be of independent interest. One of these notions is that of unambiguous interactive proofs where the prover has a unique successful strategy. Another notion is that of probabilistically checkable interactive proofs (PCIPs) where the verifier only reads a few bits of the transcript in checking the proof (this could be viewed as an interactive extension of PCPs). We show that a parallel repetition of any two-prover one-round proof system (MIP(2,1)) decreases the probability of error at an exponential rate. No constructive bound was previously known. The constant in the exponent (in our analysis) depends only on the original probability of error and on the total number of possible answers of the two provers. The dependency on the total number of possible answers is logarithmic, which was recently proved to be almost the best possible [U. Feige and O. Verbitsky, Proc.11th Annual IEEE Conference on Computational Complexity, IEEE Computer Society Press, Los Alamitos, CA, 1996, pp. 70--76]. Quite complex cryptographic machinery has been developed based on the assumption that one-way functions exist, yet we know of only a few possible such candidates. It is important at this time to find alternative foundations to the design of secure cryptography. We introduce a new model of generalized interactive proofs as a step in this direction. We prove that all NP languages have perfect zero-knowledge proof-systems in this model, without making any intractability assumptions. The generalized interactive-proof model consists of two computationally unbounded and untrusted provers, rather than one, who jointly agree on a strategy to convince the verifier of the truth of an assertion and then engage in a polynomial number of message exchanges with the verifier in their attempt to do so. To believe the validity of the assertion, the verifier must make sure that the two provers can not communicate with each other during the course of the proof process. Thus, the complexity assumptions made in previous work, have been traded for a physical separation between the two provers. We call this new model the multi-prover interactive-proof model, and examine its properties and applicability to cryptography.