zbMATH — the first resource for mathematics

Statistical zero-knowledge languages can be recognized in two rounds. (English) Zbl 0732.68038
Summary: Recently, a hierarchy of probabilistic complexity classes generalizing NP has emerged in the work of L. Babai [Trading group theory for randomness, Proc. 17th Symp. on Theory of Computing, Providence/RI, 421- 429 (1985)], S. Goldwasser, S. Micali and C. Rackoff [The knowledge complexity of interactive proofs, Proc. 17th Symp. on Theory of Computing, Providence/RI, 291-305 (1985)], and S. Goldwasser and M. Sipser [Private coins versus public coins in interactive proof systems, Proc. 18th Symp. on Theory of Computing, Berkeley/CA, 59-68 (1986)]. 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 computation on the input and all messages sent so far. The prover has no resource bounds. A language, \({\mathcal L}\) is in IP if there is a prover-verifier pair such that (1) when \(w\in {\mathcal L}\), the verifier accepts with probability at least \(1-2^{-| w|}\) and (2) when \(w\not\in {\mathcal 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 \({\mathcal L}\). In addition to defining interactive proofs, Goldwasser, Micali, and Rackoff [loc. cit.] further defined zero-knowledge interactive proofs. Informally, an interacting pair is a zero-knowledge proof for a language \({\mathcal L}\), if it is an interactive proof for \({\mathcal 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 leads 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 \({\mathcal 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 L. Fortnow [The complexity of perfect zero- knowledge, Proc. 19th Symp. on Theory of Computing, Providence/RI, 204- 209 (1987)] who showed that under the same hypothesis, the complement of \({\mathcal L}\) has an interactive proof with two interactions.

68Q15 Complexity classes (hierarchies, relations among complexity classes, etc.)
68P25 Data encryption (aspects in computer science)
Full Text: DOI
[1] {\scW. AIELLO, S. GOLDWASSER, AND J. HASTAD}, On the Power of Interaction, Combinatorica, to appear.
[2] Babai, L., Trading group theory for randomness, (), 421-429, Providence, RI
[3] Babai, L.; Moran, S., Arthur merlin games: A randomized proof system and a hierarchy of complexity classes, J. comput. system sci., 36, 254-276, (1988) · Zbl 0652.03029
[4] Boppana, R.; Hastad, J.; Zachos, S., Does co-NP have short interactive proofs, Inform. process. lett., 25, No.2, 127-132, (1987) · Zbl 0653.68037
[5] Ben Or, M.; Goldreich, O.; Goldwasser, S.; Hastad, J.; Kilian, J.; Micali, S.; Rogaway, P., Everything provable is provable in zero-knowledge, () · Zbl 0718.68033
[6] Carter, J.L.; Wegman, N.M., Universal classes of hash functions, J. comput. system sci., 18, 143-154, (1979) · Zbl 0412.68090
[7] Fortnow, L., The complexity of perfect zero-knowledge, (), 204-209, New York
[8] Goldwasser, S.; Micali, S.; Rackoff, C., The knowledge complexity of interactive proofs, (), 291-305, Providence, RI · Zbl 0900.94025
[9] Goldwasser, S.; Micali, S.; Rackoff, C., Proofs, knowledge, and computation, SIAM J. comput., 18, No. 1, 186-208, (1989) · Zbl 0677.68062
[10] Goldreich, O.; Mansour, Y.; Sipser, M., Interactive proof systems: provers that never fail and random selection, (), 449-461, Los Angeles, CA
[11] Goldreich, O.; Micali, S.; Wigderson, A., Proofs that yield nothing but their validity and a methodology of cryptographic protocol design, (), 174-187, Toronto, Canada
[12] Goldwasser, S.; Sipser, M., Private coins versus public coins in interactive proof systems, (), 59-68, Berkeley, CA
[13] Impagliazzo, R.; Yung, M., Direct minimum-knowledge computations, (), 40-51, Santa Barbara, CA
[14] Oren, Y., On the cunning powers of cheating verifiers: some observations about zero-knowledge proofs, (), 462-471, Los Angeles, CA
[15] Tompa, M.; Woll, H., Random self-reducibility and zero-knowledge interactive proofs of possession of information, (), 472-482, Los Angeles, CA
[16] Sipser, M., A complexity theoretic approach to randomness, (), 330-335, Boston, MA
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.