Computer Science Speaker Series Master Calendar

View Full Calendar

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

Event Type
Chandra Chekuri
wifi event
Nov 15, 2021   10:00 am  
Originating Calendar
Computer Science Speakers Calendar

Zoom info:

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