BEGIN:VCALENDAR
PRODID:-//eluceo/ical//2.0/EN
VERSION:2.0
CALSCALE:GREGORIAN
BEGIN:VEVENT
UID:www.tcs.tifr.res.in/event/1103
DTSTAMP:20230914T125950Z
SUMMARY:SNARGs and PPAD Hardness from Sub-exponential LWE
DESCRIPTION:Speaker: Prof. Dakshita Khurana (University of Illinois at Urba
 na-Champaign)\n\nAbstract: \nWe construct a succinct non-interactive publi
 cly-verifiable delegation scheme for any logspace uniform circuit under th
 e sub-exponential Learning With Errors (LWE) assumption. For a circuit C :
  {0\, 1}^N -> {0\, 1} of size S and depth D\, the prover runs in time poly
 (S)\, the communication complexity is D * polylog(S)\, and the verifier ru
 ns in time (D + N) * polylog(S). To obtain this result\, we introduce a ne
 w cryptographic primitive: lossy correlation-intractable hash functions. W
 e use this primitive to soundly instantiate the Fiat-Shamir transform for 
 a large class of interactive proofs\, including the interactive sum-check 
 protocol and the GKR protocol\, assuming the sub-exponential hardness of L
 WE. By relying on the result of Choudhuri et al. (STOC 2019)\, we also est
 ablish the sub-exponential average-case hardness of PPAD\, assuming the su
 b-exponential hardness of LWE. This is based on joint work with Ruta Jawal
 e\, Yael Tauman Kalai and Rachel Zhang.\nYouTube Link- https://www.youtube
 .com/watch?v=H7zwkYuILiQ\n
URL:https://www.tcs.tifr.res.in/web/events/1103
DTSTART;TZID=Asia/Kolkata:20201208T173000
DTEND;TZID=Asia/Kolkata:20201208T183000
END:VEVENT
END:VCALENDAR