ECCC-Report TR18-044https://eccc.weizmann.ac.il/report/2018/044Comments and Revisions published for TR18-044en-usFri, 30 Nov 2018 17:17:32 +0200
Revision 1
| Spatial Isolation Implies Zero Knowledge Even in a Quantum World |
Tom Gur,
Michael Forbes,
Alessandro Chiesa,
Nicholas Spooner
https://eccc.weizmann.ac.il/report/2018/044#revision1Zero 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 \subseteq 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 consists of developing 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.Fri, 30 Nov 2018 17:17:32 +0200https://eccc.weizmann.ac.il/report/2018/044#revision1
Paper TR18-044
| Spatial Isolation Implies Zero Knowledge Even in a Quantum World |
Tom Gur,
Michael Forbes,
Alessandro Chiesa,
Nicholas Spooner
https://eccc.weizmann.ac.il/report/2018/044Zero 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 \subseteq 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 consists of developing 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.Mon, 05 Mar 2018 14:30:27 +0200https://eccc.weizmann.ac.il/report/2018/044