In their recent breakthrough result, Slofstra and the second author show that there is a two-player one-round perfect zero-knowledge MIP* protocol for RE (STOC'24). We build on their result to show that there exists a succinct two-player one-round perfect zero-knowledge MIP* protocol for RE against dishonest verifiers with polylog question size and O(1) answer size, or with O(1) question size and polylog answer size. To prove our result, we study the three central compression techniques underlying the MIP*=RE proof (Ji et al. '20): question reduction, oracularization, and answer reduction. We show that question reduction preserves the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol against dishonest verifiers, and oracularization and answer reduction preserve the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol against honest verifiers. Secondly, we show that every constraint-constraint binary constraint system (BCS) nonlocal game, which provides a quantum information characterization of MIP*, can be converted to a synchronous constraint-variable BCS game to preserve perfect completeness for our compression. Lastly, we present a parametrized perfect-zero-knowledge transformation of MIP* protocols, which generalizes the transformation in (Slofstra and Kieran STOC'24) . This transformation allows us to preserve the zero-knowledge property against dishonest verifiers in the recursively oracularized protocols in our compression.
In their recent breakthrough result, Slofstra and the second author show that there is a two-player one-round perfect zero-knowledge MIP* protocol for RE (STOC'24). We build on their result to show that there exists a succinct two-player one-round perfect zero-knowledge MIP* protocol for RE against dishonest verifiers with polylog question size and O(1) answer size, or with O(1) question size and polylog answer size. To prove our result, we study the three central compression techniques underlying the MIP*=RE proof (Ji et al. '20): question reduction, oracularization, and answer reduction. We show that question reduction preserves the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol against dishonest verifiers, and oracularization and answer reduction preserve the perfect (as well as statistical and computational) zero-knowledge properties of the original protocol against honest verifiers. Secondly, we show that every constraint-constraint binary constraint system (BCS) nonlocal game, which provides a quantum information characterization of MIP*, can be converted to a synchronous constraint-variable BCS game to preserve perfect completeness for our compression. Lastly, we present a parametrized perfect-zero-knowledge transformation of MIP* protocols, which generalizes the transformation in (Slofstra and Kieran STOC'24) . This transformation allows us to preserve the zero-knowledge property against dishonest verifiers in the recursively oracularized protocols in our compression.
The recent MIP*=RE theorem of Ji, Natarajan, Vidick, Wright, and Yuen shows that the complexity class MIP* of multiprover proof systems with entangled provers contains all recursively enumerable languages. Prior work of Grilo, Slofstra, and Yuen [FOCS '19] further shows (via a technique called simulatable codes) that every language in MIP* has a perfect zero knowledge (PZK) MIP* protocol. The MIP*=RE theorem uses two-prover one-round proof systems, and hence such systems are complete for MIP*. However, the construction in Grilo, Slofstra, and Yuen uses six provers, and there is no obvious way to get perfect zero knowledge with two provers via simulatable codes. This leads to a natural question: are there two-prover PZK-MIP* protocols for all of MIP*? In this paper, we show that every language in MIP* has a two-prover one-round PZK-MIP* protocol, answering the question in the affirmative. For the proof, we use a new method based on a key consequence of the MIP*=RE theorem, which is that every MIP* protocol can be turned into a family of boolean constraint system (BCS) nonlocal games. This makes it possible to work with MIP* protocols as boolean constraint systems, and in particular allows us to use a variant of a construction due to Dwork, Feige, Kilian, Naor, and Safra [Crypto '92] which gives a classical MIP protocol for 3SAT with perfect zero knowledge. To show quantum soundness of this classical construction, we develop a toolkit for analyzing quantum soundness of reductions between BCS games, which we expect to be useful more broadly. This toolkit also applies to commuting operator strategies, and our argument shows that every language with a commuting operator BCS protocol has a two prover PZK commuting operator protocol.
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.
In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen showed that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP* except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084]. We introduce a new equivalence condition for RE/coRE-complete problems, which we call the weakly compressible condition. We show that both MIP* and MIPco satisfy this condition through the compression theorem, and thereby establish that the uncomputability for MIP* and MIPco can be proved under a unified framework (despite these two complexity classes being different). Notably, this approach also gives an alternative proof of the MIP*=RE theorem, which does not rely on the preservation of the entanglement bound. In addition to non-local games, this new condition could also potentially be applicable to other decision problems.
In 2020, a landmark result by Ji, Natarajan, Vidick, Wright, and Yuen shows that MIP*, the class of languages that can be decided by a classical verifier interacting with multiple computationally unbounded provers sharing entanglement in the tensor product model, is equal to RE. We show that the class MIPco, a complexity class defined similarly to MIP*, except with provers sharing the commuting operator model of entanglement, is equal to the class coRE. This shows that giving the provers two different models of entanglement leads to two completely different computational powers for interactive proof systems. Our proof builds upon the compression theorem used in the proof of MIP*=RE, and we use the tracially embeddable strategies framework to show that the same compression procedure in MIP* =RE also has the same desired property in the commuting operator setting. We also give a more streamlined proof of the compression theorem for non-local games by incorporating the synchronous framework used by Mousavi et al. [STOC 2022], as well as the improved Pauli basis test introduced by de la Salle [ArXiv:2204.07084].
We show that the class MIP* of languages that can be decided by a classical verifier interacting with multiple all-powerful quantum provers sharing entanglement is equal to the class RE of recursively enumerable languages. Our proof builds upon the quantum low-degree test of (Natarajan and Vidick, FOCS 2018) and the classical low-individual degree test of (Ji, et al., 2020) by integrating recent developments from (Natarajan and Wright, FOCS 2019) and combining them with the recursive compression framework of (Fitzsimons et al., STOC 2019). An immediate byproduct of our result is that there is an efficient reduction from the Halting Problem to the problem of deciding whether a two-player nonlocal game has entangled value 1 or at most 1/2. Using a known connection, undecidability of the entangled value implies a negative answer to Tsirelson's problem: we show, by providing an explicit example, that the closure Cqa of the set of quantum tensor product correlations is strictly included in the set Cqc of quantum commuting correlations. Following work of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our results provide a refutation of Connes' embedding conjecture from the theory of von Neumann algebras.
We show that the class MIP* of languages that can be decided by a classical verifier interacting with multiple all-powerful quantum provers sharing entanglement is equal to the class RE of recursively enumerable languages. Our proof builds upon the quantum low-degree test of (Natarajan and Vidick, FOCS 2018) and the classical low-individual degree test of (Ji, et al., 2020) by integrating recent developments from (Natarajan and Wright, FOCS 2019) and combining them with the recursive compression framework of (Fitzsimons et al., STOC 2019). An immediate byproduct of our result is that there is an efficient reduction from the Halting Problem to the problem of deciding whether a two-player nonlocal game has entangled value 1 or at most 1/2. Using a known connection, undecidability of the entangled value implies a negative answer to Tsirelson's problem: we show, by providing an explicit example, that the closure Cqa of the set of quantum tensor product correlations is strictly included in the set Cqc of quantum commuting correlations. Following work of (Fritz, Rev. Math. Phys. 2012) and (Junge et al., J. Math. Phys. 2011) our results provide a refutation of Connes' embedding conjecture from the theory of von Neumann algebras.