Weizmann Logo
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



TR19-086 | 7th June 2019 17:40

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 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$^*$
protocols with vanishing promise gap.

ISSN 1433-8092 | Imprint