Speaker: Alessandro Chiesa (MIT CSAIL)
Time: Thursday August 2nd 2012, 14:00
Place: Schreiber 309, Tel Aviv University
Title: How MIPs and Proof-Carrying Data Make Delegation More Affordable
Abstract:
In this talk, we will discuss two important efficiency aspects of succinct arguments:
(1) the time and space complexity of the prover
(2) the offline complexity of the verifier (a.k.a. preprocessing complexity)
Concretely, we will discuss how well (or badly) do existing constructions perform with respect to the above aspects, and then we will present two different solutions that are essentially optimal in both the above aspects.
The first solution explores the benefits of using MIPs (rather than PCPs) in new succinct argument constructions, either interactive from standard assumptions or non-interactive (i.e., SNARKs) from non-standard assumptions.
The second solution discusses how the framework of proof-carrying data can be used to "bootstrap" SNARKs that suffer from expensive offline complexity or poor prover complexity (or both) into SNARKs that no longer suffer from either.
Material presented in this talk is drawn from two works: [Bitansky and Chiesa, CRYPTO '12] and [Bitansky, Canetti, Chiesa, and Tromer, http://eprint.iacr.org/2012/095].