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
2962993321 2915900549 2947949186 1987890787
Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben- (STOC 1988) shows that zero knowledge can be achieved unconditionally for any language in NEXP, as long as one is willing to make a suitable *physical assumption*: if the provers are spatially isolated, then they can be assumed to be playing independent strategies. Quantum mechanics, however, tells us that this assumption is unrealistic, because spatially-isolated provers could share a quantum entangled state and realize a non-local correlated strategy. The MIP^* model captures this setting. In this work we study the following question: does spatial isolation still suffice to unconditionally achieve zero knowledge even in the presence of quantum entanglement? We answer this question in the affirmative: we prove that every language in NEXP has a 2-prover *zero knowledge* interactive proof that is sound against entangled provers; that is, NEXP ⊆ ZK-MIP^*. Our proof consists of constructing a zero knowledge interactive PCP with a strong algebraic structure, and then lifting it to the MIP^* model. This lifting relies on a new framework that builds on recent advances in low-degree testing against entangled strategies, and clearly separates classical and quantum tools. Our main technical contribution is the development of algebraic techniques for obtaining unconditional zero knowledge; this includes a zero knowledge variant of the celebrated sumcheck protocol, a key building block in many probabilistic proof systems. A core component of our sumcheck protocol is a new algebraic commitment scheme, whose analysis relies on algebraic complexity theory. Zero-knowledge and multi-prover systems are both central notions in classical and quantum complexity theory. There is, however, little research in quantum multi-prover zero-knowledge systems. This paper studies complexity-theoretical aspects of the quantum multi-prover zero-knowledge systems. This paper has two results: 1.QMIP* systems with honest zero-knowledge can be converted into general zero-knowledge systems without any assumptions. 2.QMIP* has computational quantum zero-knowledge systems if a natural computational conjecture holds. One of the main tools is a test (called the GHZ test) that uses GHZ states shared by the provers, which prevents the verifier's attack in the above two results. Another main tool is what we call the Local Hamiltonian based Interactive protocol (LHI protocol). The LHI protocol makes previous research for Local Hamiltonians applicable to check the history state of interactive proofs, and we then apply 's zero-knowledge protocol for QMA BJSW to quantum multi-prover systems in order to obtain the second result. We study the problem of approximating the commuting-operator value of a two-player non-local game. It is well-known that it is @math -complete to decide whether the classical value of a non-local game is 1 or @math . Furthermore, as long as @math is small enough, this result does not depend on the gap @math . In contrast, a recent result of Fitzsimons, Ji, Vidick, and Yuen shows that the complexity of computing the quantum value grows without bound as the gap @math decreases. In this paper, we show that this also holds for the commuting-operator value of a game. Specifically, in the language of multi-prover interactive proofs, we show that the power of @math (proofs with two provers, one round, completeness probability @math , soundness probability @math , and commuting-operator strategies) can increase without bound as the gap @math gets arbitrarily small. Our results also extend naturally in two ways, to perfect zero-knowledge protocols, and to lower bounds on the complexity of computing the approximately-commuting value of a game. Thus we get lower bounds on the complexity class @math - @math of perfect zero-knowledge multi-prover proofs with approximately-commuting operator strategies, as the gap @math gets arbitrarily small. While we do not know any computable time upper bound on the class @math , a result of the first author and Vidick shows that for @math and @math , the class @math , with constant communication from the provers, is contained in @math . We give a lower bound of @math (ignoring constants inside the function) for this class, which is tight up to polynomial factors assuming the exponential time hypothesis. The wide applicability of zero-knowledge interactive proofs comes from the possibility of using these proofs as subroutines in cryptographic protocols. A basic question concerning this use is whether the (sequential and or parallel) composition of zero-knowledge protocols is zero-knowledge too. We demonstrate the limitations of the composition of zero-knowledge protocols by proving that the original definition of zero-knowledge is not closed under sequential composition; and that even the strong formulations of zero-knowledge (e.g., black-box simulation) are not closed under parallel execution. We present lower bounds on the round complexity of zero-knowledge proofs, with significant implications for the parallelization of zero-knowledge protocols. We prove that three-round interactive proofs and constant-round Arthur--Merlin proofs that are black-box simulation zero-knowledge exist only for languages in BPP. In particular, it follows that the "parallel versions" of the first interactive proofs systems presented for quadratic residuosity, graph isomorphism, and any language in NP, are not black-box simulation zero-knowledge, unless the corresponding languages are in BPP. Whether these parallel versions constitute zero-knowledge proofs was an intriguing open questions arising from the early works on zero-knowledge. Other consequences are a proof of optimality for the round complexity of various known zero-knowledge protocols and the necessity of using secret coins in the design of "parallelizable" constant-round zero-knowledge proofs.