Multi-prover interactive proofs: how to remove intractability assumptions.

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 strat,egy 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. *Supported by Alon Fellowship. 1 Supported in prrt by NSF grant 865727~CCR, AR0 grant DAALO%SGK-017, and US-Israel BSF grant 86 00301. Jerusalem, Ismel. t Supported by a Fannie and John Hertz Foundation fellowship. SSupported by Alon Fellowship I’cmission IO copy wiltlout t’cc at1 or par1 ol’ this makriat is graIlled providrd that the copi arc not made or dislributett for direct commercial advantage. the ACM copyright notice and the title of the publication and its date appear. and notice is given Ihat copying is by permission of the Association for Computing Machinery. To copy otherwise, or to republish, requires a fee and/or specfic permission. @ 1988 ACM-O-89791-264-O/88/0005/01 I3 $1.50 We call this new model the multi-prover interactive-proof model, and examine its properties and applicability to cryptography.