How to Bootstrap a SNARK in Public
Speaker: Nir Bitanksy , TAU and BU
Date: May 25 2012
Time: 10:30AM to 12:00PM
Location: 32-G449, Patil/Kiva
Host: Yael Tauman Kalai, Microsoft Research, NE
Contact: Be Blackburn, 3-6098, imbe@mit.edu
Relevant URL: Publicly verifiable succinct non-interactive arguments of knowledge
(SNARKs) are concise, easily-checkable proofs for the correct execution
of long computations. These proofs require a public and reusable
reference string that allows proofs to be created and checked by anyone. Generalizing SNARKs, Proof-carrying data systems (PCDs) provide a powerful tool for verifying correctness of distributed computations. So far, publicly-verifiable SNARKs and PCDs were only known to exist either in the random oracle model or in a "signing oracle" model.
We present recursive composition and bootstrapping techniques for SNARKs and PCDs that:
1. Transform SNARKs that have a long reference string but are otherwise succinct into fully succinct SNARKs.
2. Transform any SNARK into a PCD system for distributed computations over chains of fixed polynomial length.
Applying our transformations to the succinct NIZKs of Groth [ASIACRYPT11], or of Gentry et al. [EPRINT12], whose security is based
on a Knowledge of Exponent assumption in bilinear groups, we obtain the first publicly-verifiable SNARKs and PCDs in the plain model.
Interestingly, the resulting constructions do not rely on the PCP Theorem and enjoy several efficiency benefits. We also obtain analogous
results for privately-verifiable PCDs and SNARKs.
We note that the PCD abstraction plays a central role in our construction and analysis, not only as a goal but also as a main tool.
In particular, PCDs allow us to present and prove our constructions in a relatively clean and concise way.
Joint work with Ran Canetti, Alessandro Chiesa and Eran Tromer.
See other events that are part of CIS Seminars 2011/2012
See other events happening in May 2012
