BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Spatial Isolation Implies Zero Knowledge Even in a Quantum World -
  Dr Tom Gur (University of Warwick)
DTSTART:20190307T141500Z
DTEND:20190307T151500Z
UID:TALK117997@talks.cam.ac.uk
CONTACT:Johannes Bausch
DESCRIPTION:Zero knowledge plays a central role in cryptography and comple
 xity. The seminal work of Ben-Or et al. (STOC 1988) shows that zero knowle
 dge 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 st
 rategies.\n\nQuantum mechanics\, however\, tells us that this assumption i
 s unrealistic\, because spatially-isolated provers could share a quantum e
 ntangled state and realise a non-local correlated strategy.\n\nIn this wor
 k we study the following question: does spatial isolation still suffice to
  unconditionally achieve zero knowledge even in the presence of quantum en
 tanglement?\n\nWe answer this question in the affirmative: we prove that e
 very language in NEXP has a 2-prover *zero knowledge* interactive proof th
 at is sound against entangled provers.\n\nOur proof consists of constructi
 ng a zero knowledge interactive PCP with a strong algebraic structure\, an
 d then lifting it to the MIP with entangled provers model. This lifting re
 lies on a new framework that builds on recent advances in low-degree testi
 ng against entangled strategies\, and clearly separates classical and quan
 tum tools.\n\nOur main technical contribution is the development of algebr
 aic techniques for obtaining unconditional zero knowledge\; this includes 
 a zero knowledge variant of the celebrated sumcheck protocol\, a key build
 ing block in many probabilistic proof systems. A core component of our sum
 check protocol is a new algebraic commitment scheme\, whose analysis relie
 s on algebraic complexity theory.\n
LOCATION:MR4\, Centre for Mathematical Sciences\, Wilberforce Road\, Cambr
 idge
END:VEVENT
END:VCALENDAR