Spatial Isolation Implies Zero Knowledge Even in a Quantum World

Add to your list(s) Download to your calendar using vCal

• Dr Tom Gur (University of Warwick)
• Thursday 07 March 2019, 14:15-15:15
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge.

If you have a question about this talk, please contact Johannes Bausch.

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 realise a non-local correlated strategy.

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.

Our proof consists of constructing a zero knowledge interactive PCP with a strong algebraic structure, and then lifting it to the MIP with entangled provers 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 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.

This talk is part of the CQIF Seminar series.

This talk is included in these lists:

• All CMS events
• CMS Events
• CQIF Seminar
• DAMTP info aggregator
• Hanchen DaDaDash
• Interested Talks
• MR4, Centre for Mathematical Sciences, Wilberforce Road, Cambridge
• bld31

Note that ex-directory lists are not shown.