Multi-prover interactive proofs: how to remove intractability assumptions

ABSTRACT

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.

REFERENCES

• AL: Angluin, Dana and David Lichtenstein. "Provable Security of Cryptosystems: a Survey," YALEU/DGS/TR- 288, 1983. Proceeding of the 17th STOC, 1985, pp. 421-429.
• Ba: D A Barrington, Bounded-width polynomial-size branching programs recognize exactly those languages in NC¹, Proceedings of the eighteenth annual ACM symposium on Theory of computing, p.1-5, May 28-30, 1986, Berkeley, California, United States [doi>10.1145/12130.12131]
• Bl: Blum, M., Private Communication.
• BC: Brazsard, Gilles and Claude Cr6peau. "Zero- Knowledge Simulation of Boolean Circuits," Proceedings of the 27th FOG'S, IEEE, 1986, 188-195.
• BHZ: R. B. Boppana , J. Hastad , S. Zachos, Does co-NP have short interactive proofs?, Information Processing Letters, v.25 n.2, p.127-132, 6 May 1987 [doi>10.1016/0020-0190(87)90232-8]
• CDvdG: David Chaum , Ivan Damgård , Jeroen van de Graaf, Multiparty Computations Ensuring Privacy of Each Party's Input and Correctness of the Result, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.87-119, August 16-20, 1987
• CG: Chor, B, Goldreich G, "Unbiased Bits from Sources of Weak Randomness and Probabilistic Communication Complexity", Proceedings of the ~6th FOGS, 1985.
• Ck: Cr6peau C., Kilian J., Private Communication.
• CW: Carter L., Wegman M., "Universal Classes of Hash FUnctions", JCSS 18, 1979, pp. 143-154.
• C: Cr6peau Claude, "On the Equivalence of Two Types of Oblivious Ti-ansfer', Crypto87.
• FST: Feige, U., Shamir, A., Tennenholtz, M., "The Noisy Oracle Problem", Private Communication of Manuscript
• F: L. Fortnow, The complexity of perfect zero-knowledge, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.204-209, January 1987, New York, New York, United States [doi>10.1145/28395.28418]
• FRS: Fortnow, Lance., Rompel J., Sipser M., "On the Power of Multi. Prover Interactive Proofs" In preparation
• FMR: Fischer M., Micali S., Rackoff C., alld Wittenberg S., "An Oblivious Transfer Protocol Equivalent to Factoring'', In Preparation.
• GM: Goldwasser S., and MicMi S., "Probabillstlc Encryptlon", JCSS, vol. ~8, no. 2, 1984, pp. 270-299.
• GHY: Galil Z., Haber :3., and Yung M., "A Private Interactive Test of a Boolean Predicate and Minimum- Knowledge Public-Key Cryptosystern", Proceedings of the ~6th FOGS, 1985, pp. 360-371.
• EGL: Shimon Even , Oded Goldreich , Abraham Lempel, A randomized protocol for signing contracts, Communications of the ACM, v.28 n.6, p.637-647, June 1985 [doi>10.1145/3812.3818]
• GMS: Goldreich O.,, Mansour Y.,, and Sipser M.,, "Interactive Proof Systems: Provers that Never Fail and Random Selection", Proceedings o} the ~gth FOGS, 1987, pp. 449- 462.
• GMW1: Goldreich, Oded, Silvio Micali, and Avi Wigderson. "Proofs that Yield Noticing but tl~e Validity of the Assertion, and a Methodology of Cryl,tographic Protocol Design," Proceedings oJ lhe 27th FOGS, IEEE, 1986, 174- 187.
• GMW2: O. Goldreich , S. Micali , A. Wigderson, How to play ANY mental game, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.218-229, January 1987, New York, New York, United States [doi>10.1145/28395.28420]
• GV: Oded Goldreich , Ronen Vainish, How to Solve any Protocol Problem - An Efficiency Improvement, A Conference on the Theory and Applications of Cryptographic Techniques on Advances in Cryptology, p.73-86, August 16-20, 1987
• GMR: S Goldwasser , S Micali , C Rackoff, The knowledge complexity of interactive proof-systems, Proceedings of the seventeenth annual ACM symposium on Theory of computing, p.291-304, May 06-08, 1985, Providence, Rhode Island, United States [doi>10.1145/22145.22178]
• HM: Hastad J., Mansour Y., "Private Communication"
• K: Killan, J. "On the Power of Oblivious Transfer,"Pr0ceedi~gs o} this conf~Tence
• L: Lautemann C., "BPP and the Polynomial Time Hierarchy'', IPL, 14, 1983, pp. 215-217.
• R: Rabin, M., "How to exchange secrets by oblivious transfer", Tech. Memo TH-81, Aiken Computation Laboratory, Harvard University, 1981.
• Yao82: Yao, Andrew C. "Protocols for Secure Computations," Proceedings of the 23rd FOCS, IEEE, 1982, 160- 164.
• Yao86a: Yao, Andrew C. "How to Generate and Exchange Secrets," Proceedings of the 27th FOC~, IEEE, 1986, 162-167.
• Yao86b: Yao, Andrew C. "Theory and Applications of Trapdoor Functions", Proc. of the 23rd FOCS, 1982, IEEE, pp.80-91.

INDEX TERMS

Primary Classification:
  F. Theory of Computation
  F.4 MATHEMATICAL LOGIC AND FORMAL LANGUAGES
      F.4.1 Mathematical Logic
          Subjects: Model theory

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

General Terms:
Algorithms, Design, Performance, Theory