The Library
Spatial isolation implies zero knowledge even in a quantum world
Tools
Tools
Tools
Chiesa, Alessandro, Forbes, Michael, Gur, Tom and Spooner, Nicholas (2022) Spatial isolation implies zero knowledge even in a quantum world. Journal of the ACM, 69 (2). 15. doi:10.1145/3511100 ISSN 0004-5411.
|
PDF
WRAP-spatial-isolation-zero-quantum-world-Gur-2019.pdf - Accepted Version - Requires a PDF viewer. Download (1198Kb) | Preview |
Official URL: 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 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 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.
| Item Type: | Journal Article | ||||||||
|---|---|---|---|---|---|---|---|---|---|
| Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
| Journal or Publication Title: | Journal of the ACM | ||||||||
| Publisher: | Association for Computing Machinery, Inc. | ||||||||
| ISSN: | 0004-5411 | ||||||||
| Official Date: | April 2022 | ||||||||
| Dates: |
|
||||||||
| Volume: | 69 | ||||||||
| Number: | 2 | ||||||||
| Article Number: | 15 | ||||||||
| DOI: | 10.1145/3511100 | ||||||||
| Status: | Peer Reviewed | ||||||||
| Publication Status: | Published | ||||||||
| Reuse Statement (publisher, data, author rights): | "© ACM, 2022. This is the author's version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Journal of the ACM, 69,2, 15http://doi.acm.org/10.1145/3511100 | ||||||||
| Access rights to Published version: | Restricted or Subscription Access | ||||||||
| Date of first compliant deposit: | 10 December 2019 | ||||||||
| Date of first compliant Open Access: | 10 December 2019 | ||||||||
| Related URLs: |
Request changes or add full text files to a record
Repository staff actions (login required)
 |
View Item |
Downloads
Downloads per month over past year
