Spatial Isolation Implies Zero Knowledge Even in a Quantum World
- 31 January 2022
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in Journal of the ACM
- Vol. 69 (2), 1-44
- https://doi.org/10.1145/3511100
Abstract
Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or et al. (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 probabilistically checkable proof 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 new 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.Keywords
Funding Information
- UKRI Future Leaders Fellowship (MR/S031545/1)
This publication has 39 references indexed in Scilit:
- Entangled Games Are Hard to ApproximateSIAM Journal on Computing, 2011
- AlgebrizationACM Transactions on Computation Theory, 2009
- Robust locally testable codes and products of codesRandom Structures & Algorithms, 2006
- Coding theorem and strong converse for quantum channelsIEEE Transactions on Information Theory, 1999
- Power Sums over Finite Subspaces of a FieldFinite Fields and Their Applications, 1999
- Algebraic methods for interactive proof systemsJournal of the ACM, 1992
- Proofs that yield nothing but their validity or all languages in NP have zero-knowledge proof systemsJournal of the ACM, 1991
- Statistical zero-knowledge languages can be recognized in two roundsJournal of Computer and System Sciences, 1991
- Non-deterministic exponential time has two-prover interactive protocolscomputational complexity, 1991
- Does co-NP have short interactive proofs?Information Processing Letters, 1987