Statistical zero-knowledge languages can be recognized in two rounds

摘要

Recently, a hierarchy of probabilistic complexity classes generalizing NP has emerged in the work of Babai [2], Goldwasser, Micali, and Rackoff [8], and Goldwasser and Sipser [12]. The class IP is defined through the computational model of an interactive prover-verifier pair. Both Turing machines in a pair receive a common input and exchange messages. Every move of the verifier as well as its final determination of whether to accept or reject w is the result of random polynomial time computations on the input and all messages sent so far. The prover has no resource bounds. A language, L, is in IP if there is a prover-verifier pair such that (1) when ϵ ϵ L, the verifier accepts with probability at least 1–2−|w| and (2) when ω ∉ L, the verifier interacting with any prover accepts with probability at most 2−|w|. Such a prover-verifier pair is called an interactive proof for L. In addition to defining interactive proofs, Goldwasser, Micali, and Rackoff [8] further defined zero-knowledge interactive proofs. Informally, an interacting pair is a zero-knowledge proof for a language, L, if it is an interactive proof for L with the additional constraint that the prover reveals “nothing” (except language membership) to any verifier that the verifier could not have computed itself. There are three formal definitions for “nothing” which lead to three types of zero-knowledge: perfect, statistical, and computational, each more restrictive than the next. We show that the first and second definitions are very restrictive. Specifically, any language, L, that has a statistical zero-knowledge interactive proof with an unbounded number of interactions has an interactive proof with two interactions. This complements a result by Fortnow [7] who showed that under the same hypothesis, the complement of L has an interactive proof with two interactions.