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:
- 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)}.
- 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)}.