BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Where Delegation Meets Einstein - Tauman Kalai\, Y (Saha Institute
  of Nuclear Physics)
DTSTART:20120412T133000Z
DTEND:20120412T143000Z
UID:TALK37430@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:We show a curious connection between the problem of *computati
 on delegation* and the model of *no-signalling multi-prover interactive pr
 oofs*\, a model that was studied in the context of multi-prover interactiv
 e proofs with provers that share quantum entanglement\, and is motivated b
 y the physical law that information cannot travel instantly (and is\, like
  matter\, limited by the speed of light). We consider the method suggested
  by Aiello et. al. for converting a 1-round multi-prover interactive proof
  (MIP) into a 1-round delegation scheme\, by using a computational private
  information retrieval (PIR) scheme. On one direction\, we show that if th
 e underlying MIP protocol is sound against statistically no-signalling che
 ating provers then the resulting delegation protocol is secure (under the 
 assumption that the underlying PIR is secure for attackers of sub-exponent
 ial size). On the other direction\, we show that if the resulting delegati
 on protocol is secure for every PIR scheme\, and the proof of security is 
 a black-box reduction that reduces the security of the protocol to the sec
 urity of any ``standard'' cryptographic assumption\, and such that the num
 ber of calls made by the reduction to the cheating prover is independent o
 f the security parameter\, then the underlying MIP protocol is sound again
 st statistically no-signalling cheating provers. This is joint work with R
 an Raz and Ron Rothblum 
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR