ECCC-Report TR19-086https://eccc.weizmann.ac.il/report/2019/086Comments and Revisions published for TR19-086en-usSun, 09 Jun 2019 13:46:57 +0300
Paper TR19-086
| Perfect zero knowledge for quantum multiprover interactive proofs |
Alex Bredariol Grilo,
William Slofstra,
Henry Yuen
https://eccc.weizmann.ac.il/report/2019/086In 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.Sun, 09 Jun 2019 13:46:57 +0300https://eccc.weizmann.ac.il/report/2019/086