From: CSAIL Event Calendar <email@example.com>
Date: Mon, May 13, 2013 at 7:49 PM
Subject: TALK:Thursday 5-16-13 Succinct Non-Interactive Arguments via Linear Interactive Proofs
Succinct Non-Interactive Arguments via Linear Interactive Proofs
CIS Seminars 2012/2013
Speaker: Alessandro Chiesa
Speaker Affiliation: MIT
Host: CIS Seminar
Time: 10:30 AM - 12:00 PM
Succinct non-interactive arguments (SNARGs) enable verifying NP statements
with lower complexity than required for classical NP verification.
Traditionally, the focus has been on minimizing the length of such arguments;
nowadays researchers have focused also on minimizing verification time, by
drawing motivation from the problem of delegating computation.
A common relaxation is a preprocessing SNARG, which allows the verifier to
conduct an expensive offline phase that is independent of the statement to be
proven later. Recent constructions of preprocessing SNARGs have achieved
attractive features: they are publicly-verifiable, proofs consist of only O(1)
encrypted (or encoded) field elements, and verification is via arithmetic
circuits of size linear in the NP statement. Additionally, these constructions
seem to have "escaped the hegemony" of probabilistically-checkable proofs
(PCPs) as a basic building block of succinct arguments.
We present a general methodology for the construction of preprocessing
SNARGs, as well as resulting concrete efficiency improvements. Our results are
achieved by studying a natural extension of the interactive proof model that
considers algebraically-bounded provers; this new setting is analogous to the
common study of algebraically-bounded "adversaries" in other fields, such
as pseudorandomness and randomness extraction. More concretely, in this work
we focus on linear (or affine) provers, and provide several constructions of
(succinct two-message) linear-interactive proofs (LIPs) for NP. We then show
how to generically compile LIPs into preprocessing SNARGs.
Joint work with Nir Bitansky, Yuval Ishai, Rafail Ostrovsky, and Omer Paneth.
For more information please contact: Holly A Jones, 617-253-6098, firstname.lastname@example.org
Seminars mailing list