Spatial isolation implies zero knowledge even in a quantum world

Alessandro Chiesa, Michael A. Forbes, Tom Gur, Nicholas Spooner

Research output: Chapter in Book/Report/Conference proceedingConference contribution

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.

Original languageEnglish (US)
Title of host publicationProceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
EditorsMikkel Thorup
PublisherIEEE Computer Society
Pages755-765
Number of pages11
ISBN (Electronic)9781538642306
DOIs
StatePublished - Nov 30 2018
Event59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 - Paris, France
Duration: Oct 7 2018Oct 9 2018

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2018-October
ISSN (Print)0272-5428

Other

Other59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018
CountryFrance
CityParis
Period10/7/1810/9/18

Keywords

  • Algebraic complexity
  • Interactive PCPs
  • Multi-prover interactive proofs
  • Quantum entangled strategies
  • Sumcheck protocol
  • Zero knowledge

ASJC Scopus subject areas

  • Computer Science(all)

Fingerprint Dive into the research topics of 'Spatial isolation implies zero knowledge even in a quantum world'. Together they form a unique fingerprint.

  • Cite this

    Chiesa, A., Forbes, M. A., Gur, T., & Spooner, N. (2018). Spatial isolation implies zero knowledge even in a quantum world. In M. Thorup (Ed.), Proceedings - 59th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2018 (pp. 755-765). [8555155] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2018-October). IEEE Computer Society. https://doi.org/10.1109/FOCS.2018.00077