Computer Science Speakers Series

Back to Listing

Theory Seminar: James Hulett, "SNARGs for P from Sub-exponential DDH and QR"

Event Type
Seminar/Symposium
Sponsor
Chandra Chekuri
Location
https://illinois.zoom.us/j/85054031332?pwd=d1hRNS9wTlVFRmtpTzZmQkxld1YzZz09
Virtual
wifi event
Date
Nov 15, 2021   10:00 am  
Views
15
Originating Calendar
Computer Science Speakers Calendar

Zoom info:

https://illinois.zoom.us/j/85054031332?pwd=d1hRNS9wTlVFRmtpTzZmQkxld1YzZz09

Meeting ID: 850 5403 1332

Passcode: theorycs

 

Title: SNARGs for P from Sub-exponential DDH and QR

Abstract: We obtain publicly verifiable Succinct Non-Interactive Arguments (SNARGs) for arbitrary deterministic computations and bounded space non-deterministic computation from well-studied group-based assumptions.  In particular, assuming the sub-exponential hardness of the Decisional Diffie-Hellman (DDH) and Quadratic Residuosity (QR) assumptions, we obtain the following results, where n denotes the length of the instance:

  1. A SNARG for any language that can be decided in non-deterministic time T and space S with communication complexity and verifier runtime (n + S) · T^{o(1)}.
  2. A SNARG for any language that can be decided in deterministic time T with communication complexity n · T^{o(1)} and verifier runtime poly(n) · T^{o(1)}.
link for robots only