The Library
Spatial isolation implies zero knowledge even in a quantum world
Tools
Chiesa, Alessandro, Forbes, Michael, Gur, Tom and Spooner, Nicholas (2018) Spatial isolation implies zero knowledge even in a quantum world. In: 59th Annual IEEE Symposium on Foundations of Computer Science, Paris, France, 7-9 Oct 2018. Published in: 59th Annual IEEE Symposium on Foundations of Computer Science pp. 755-765. ISBN 9781538642306. doi:10.1109/FOCS.2018.00077 ISSN 1523-8288.
|
PDF
WRAP-spatial-isolation-implies-zero-knowledge-quantum-world-Gur-2018.pdf - Accepted Version - Requires a PDF viewer. Download (935Kb) | Preview |
Official URL: https://doi.org/10.1109/FOCS.2018.00077
Abstract
Zero knowledge plays a central role in cryptography and complexity. The seminal work of Ben-Or etal. (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 a2-proverzero 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 sum check protocol, a key building block in many probabilistic proof systems. A core component of our sum check protocol is anew algebraic commitment scheme, whose analysis relies on algebraic complexity theory.
Item Type: | Conference Item (Paper) | ||||||||
---|---|---|---|---|---|---|---|---|---|
Subjects: | Q Science > QA Mathematics > QA76 Electronic computers. Computer science. Computer software | ||||||||
Divisions: | Faculty of Science, Engineering and Medicine > Science > Computer Science | ||||||||
Library of Congress Subject Headings (LCSH): | Zero-knowledge proofs, Cryptography | ||||||||
Series Name: | Annual IEEE Symposium on Foundations of Computer Science | ||||||||
Journal or Publication Title: | 59th Annual IEEE Symposium on Foundations of Computer Science | ||||||||
Publisher: | IEEE | ||||||||
ISBN: | 9781538642306 | ||||||||
ISSN: | 1523-8288 | ||||||||
Official Date: | 2018 | ||||||||
Dates: |
|
||||||||
Page Range: | pp. 755-765 | ||||||||
DOI: | 10.1109/FOCS.2018.00077 | ||||||||
Status: | Peer Reviewed | ||||||||
Publication Status: | Published | ||||||||
Access rights to Published version: | Restricted or Subscription Access | ||||||||
Date of first compliant deposit: | 12 February 2019 | ||||||||
Date of first compliant Open Access: | 12 February 2019 | ||||||||
Conference Paper Type: | Paper | ||||||||
Title of Event: | 59th Annual IEEE Symposium on Foundations of Computer Science | ||||||||
Type of Event: | Conference | ||||||||
Location of Event: | Paris, France | ||||||||
Date(s) of Event: | 7-9 Oct 2018 | ||||||||
Related URLs: | |||||||||
Open Access Version: |
Request changes or add full text files to a record
Repository staff actions (login required)
View Item |
Downloads
Downloads per month over past year