Multi-prover interactive proofs: how to remove intractability assumptions

By Michael Ben-Or, Shafi Goldwasser, Joe Kilian, Avi Wigderson. 1988

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.

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

Citations in the corpus

Prio: Private, Robust, and Scalable Computation of Aggregate Statistics (2017, background): “Prior work has studied interactive proofs in both the many-prover [14,60] and many-verifier settings [1, 10].”
Computational Integrity with a Public Random String from Quasi-Linear PCPs (2017, background): “Probabilistically checkable proof (PCP) systems(8) [4, 3, 2, 1] are a particularly efficient multi-prover interactive proof (MIP) system [8] in terms of the amount of communication between prover and verifier, verification time, the number of rounds of interaction and soundness-error.”
New Algorithms for Secure Outsourcing of Modular Exponentiations (2012, background): “[29] first formalized the notion of verifiable computation to solve the problem of verifiably outsourcing the computation of an arbitrary functions, which has attracted the attention of plenty of researchers [11], [14], [15], [30], [32], [36], [37], [40].”
Foundations of Cryptography: Volume 1, Basic Tools (2001, unknown): “Multi-prover interactive proofs were introduced by Ben-Or, Goldwasser, Kilian, and Wigderson [26].”
How to Securely Outsource Cryptographic Computations (2005, methodology): “The concept of an honest party gaining information from two (or more) possibly dishonest, but physically separated parties was first used by Ben-Or, Goldwasser, Kilian, and Wigderson [4] as a method for obtaining interactive proofs without intractability assumptions.”
Taking Proof-Based Verified Computation a Few Steps Closer to Practicality (2012, methodology): “Applying proof systems to verifiable computation is standard in the theory community [5–7, 10, 16, 32, 37, 38, 43], and the asymptotics continue to improve [13, 14, 23, 46].”
Fast reductions from RAMs to delegatable succinct constraint satisfaction problems: extended abstract (2013, background): “Concretely, they de.ned a complexity-preserving multiprover interactive proof (MIP) [6] to be one where, to check that a randomaccess machine M non-deterministically accepts an input x within T time steps and using at most S memory cells, each MIP prover runs in time (|M | + T ) · polylog(T )and ”