BEGIN:VCALENDAR
VERSION:2.0
PRODID:-//Talks.cam//talks.cam.ac.uk//
X-WR-CALNAME:Talks.cam
BEGIN:VEVENT
SUMMARY:Quadratic Span Programs for Succinct NIZKs without PCPs - Gentry\,
  C (IBM Research)
DTSTART:20120411T133000Z
DTEND:20120411T143000Z
UID:TALK37408@talks.cam.ac.uk
CONTACT:Mustapha Amrani
DESCRIPTION:We introduce a new characterization of the NP complexity class
 \, called "Quadratic Span Programs" (QSPs)\, which is a natural extension 
 of "span programs" by Karchmer and Wigderson. Our main motivation is the c
 onstruction of succinct arguments of NP-statements that are quickly constr
 uctible and verifiable. QSPs seem well-suited for this task\, perhaps even
  better than Probabilistically Checkable Proofs (PCPs). In 2010\, Groth co
 nstructed a NIZK argument in the common reference string (CRS) model for C
 ircuit-SAT consisting of only 42 elements in a bilinear group. Interesting
 ly\, his argument does not (explicitly) use PCPs. But his scheme has some 
 disadvantages -- namely\, the CRS size and prover computation are both qua
 dratic in the circuit size. In 2011\, Lipmaa reduced the CRS size to quasi
 -linear\, but with prover computation still quadratic. Using QSPs we const
 ruct a NIZK argument in the CRS model for Circuit-SAT consisting of just 7
  group elements. The CRS size is linear in the circuit size\, and prover c
 omputation is quasi-linear\, making our scheme seemingly quite practical. 
 (The prover only needs to do a linear number of group operations\; the qua
 si-linear computation is a multipoint evaluation.) Our results are complem
 entary to those of Valiant (TCC 2008) and Bitansky et al. (2012)\, who use
  ``bootstrapping" (recursive composition) of arguments to reduce CRS size 
 and prover and verifier computation. QSPs also provide a crisp mathematica
 l abstraction of some of the techniques underlying Groth's and Lipmaa's co
 nstructions. Joint work with Rosario Gennaro\, Bryan Parno\, and Mariana R
 aykova.
LOCATION:Seminar Room 1\, Newton Institute
END:VEVENT
END:VCALENDAR