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