Home > Resources > papers > BGKW88-MIP

Multi-Prover Interactive Proofs: How to Remove Intractability Assumptions (Ben-Or, Goldwasser, Kilian, Wigderson 1988)

Last modified: 2026-10-27

DOI: 10.1145/62212.62223 · URL: https://doi.org/10.1145/62212.62223

Summary

Introduces the multi-prover interactive proof (MIP) model, in which several non-communicating provers convince a verifier, and shows that in this model every NP language has a perfect zero-knowledge proof without any computational (intractability) assumptions. The MIP model later led to MIP = NEXP and to PCPs, and its idea of splitting the prover reappears in modern IOP and polynomial-commitment-based SNARK constructions. (STOC 1988.)

Related resources

• The Knowledge Complexity of Interactive Proof Systems (GMR85) (paper, 1985)