BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//talks.cam.ac.uk//v3//EN
BEGIN:VTIMEZONE
TZID:Europe/London
BEGIN:DAYLIGHT
TZOFFSETFROM:+0000
TZOFFSETTO:+0100
TZNAME:BST
DTSTART:19700329T010000
RRULE:FREQ=YEARLY;BYMONTH=3;BYDAY=-1SU
END:DAYLIGHT
BEGIN:STANDARD
TZOFFSETFROM:+0100
TZOFFSETTO:+0000
TZNAME:GMT
DTSTART:19701025T020000
RRULE:FREQ=YEARLY;BYMONTH=10;BYDAY=-1SU
END:STANDARD
END:VTIMEZONE
BEGIN:VEVENT
CATEGORIES:CQIF Seminar
SUMMARY:Spatial Isolation Implies Zero Knowledge Even in a
Quantum World - Dr Tom Gur (University of Warwick
)
DTSTART;TZID=Europe/London:20190307T141500
DTEND;TZID=Europe/London:20190307T151500
UID:TALK117997AThttp://talks.cam.ac.uk
URL:http://talks.cam.ac.uk/talk/index/117997
DESCRIPTION:Zero knowledge plays a central role in cryptograph
y and complexity. The seminal work of Ben-Or et al
. (STOC 1988) shows that zero knowledge can be ach
ieved unconditionally for any language in NEXP\, a
s long as one is willing to make a suitable physic
al assumption: if the provers are spatially isolat
ed\, then they can be assumed to be playing indepe
ndent strategies.\n\nQuantum mechanics\, however\,
tells us that this assumption is unrealistic\, be
cause spatially-isolated provers could share a qua
ntum entangled state and realise a non-local corre
lated strategy.\n\nIn this work we study the follo
wing question: does spatial isolation still suffic
e to unconditionally achieve zero knowledge even i
n the presence of quantum entanglement?\n\nWe answ
er this question in the affirmative: we prove that
every language in NEXP has a 2-prover *zero knowl
edge* interactive proof that is sound against enta
ngled provers.\n\nOur proof consists of constructi
ng a zero knowledge interactive PCP with a strong
algebraic structure\, and then lifting it to the M
IP with entangled provers model. This lifting reli
es on a new framework that builds on recent advanc
es in low-degree testing against entangled strateg
ies\, and clearly separates classical and quantum
tools.\n\nOur main technical contribution is the d
evelopment of algebraic techniques for obtaining u
nconditional zero knowledge\; this includes a zero
knowledge variant of the celebrated sumcheck prot
ocol\, a key building block in many probabilistic
proof systems. A core component of our sumcheck pr
otocol is a new algebraic commitment scheme\, whos
e analysis relies on algebraic complexity theory.\
n
LOCATION:MR4\, Centre for Mathematical Sciences\, Wilberfor
ce Road\, Cambridge
CONTACT:Johannes Bausch
END:VEVENT
END:VCALENDAR