In this work we consider the interplay between multiprover interactive proofs, quantum entanglement, and zero knowledge proofs - notions that are central pillars of complexity theory, quantum information and cryptography. In particular, we study the relationship between the complexity class MIP @math , the set of languages decidable by multiprover interactive proofs with quantumly entangled provers, and the class PZKMIP @math , which is the set of languages decidable by MIP @math protocols that furthermore possess the perfect zero knowledge property. Our main result is that the two classes are equal, i.e., MIP @math PZKMIP @math . This result provides a quantum analogue of the celebrated result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC 1988) who show that MIP @math PZKMIP (in other words, all classical multiprover interactive protocols can be made zero knowledge). We prove our result by showing that every MIP @math protocol can be efficiently transformed into an equivalent zero knowledge MIP @math protocol in a manner that preserves the completeness-soundness gap. Combining our transformation with previous results by Slofstra (Forum of Mathematics, Pi 2019) and Fitzsimons, Ji, Vidick and Yuen (STOC 2019), we obtain the corollary that all co-recursively enumerable languages (which include undecidable problems as well as all decidable problems) have zero knowledge MIP @math protocols with vanishing promise gap.
Finally, Cr ' e peau and Yang @cite_27 refined the notion of zero knowledge, requiring the simulator to be local, i.e., that there are non-communicating classical simulators that simulate the (joint) output distribution of the provers. We note that our result does not fulfill this modified definition, and we leave it as an open problem (dis)proving that all @math can be made zero knowledge in this setting.
@cite_27
2950183140
In multi-prover interactive proofs (MIPs), the verifier is usually non-adaptive. This stems from an implicit problem which we call contamination'' by the verifier. We make explicit the verifier contamination problem, and identify a solution by constructing a generalization of the MIP model. This new model quantifies non-locality as a new dimension in the characterization of MIPs. A new property of zero-knowledge emerges naturally as a result by also quantifying the non-locality of the simulator.