Perfect zero knowledge for quantum Multiprover Interactive Proofs

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, the set of languages decidable by multiprover interactive proofs with quantumly entangled provers, and the class PZK-MIP∗, which is the set of languages decidable by MIP∗ protocols that furthermore possess the perfect zero knowledge property. Our main result is that the two classes are equal, i.e., MIP∗ = PZK-MIP∗. This result provides a quantum analogue of the celebrated result of Ben-Or, Goldwasser, Kilian, and Wigderson (STOC 1988) who show that MIP = PZK-MIP (in other words, all classical multiprover interactive protocols can be made zero knowledge). We prove our result by showing that every MIP∗ protocol can be efficiently transformed into an equivalent zero knowledge MIP∗ protocol in a manner that preserves the completeness-soundness gap. Combining our transformation with previous results, we obtain the corollaries that i) all languages that can be solved in non-deterministic double exponential time have zero knowledge MIP∗ protocols and ii) all co-recursively enumerable languages (which include undecidable problems as well as all decidable problems) have zero knowledge MIP∗ protocols with vanishing promise gap.

• View at Publisher