[Busec] Fwd: TALK:Thursday 5-16-13 Succinct Non-Interactive Arguments via Linear Interactive Proofs

Huijia Lin huijial at gmail.com
Mon May 13 22:22:53 EDT 2013


Hi all,

I am forwarding the notification of this week's CIS seminar. Please note
the special time and location.

Best,
Rachel

---------- Forwarded message ----------
From: CSAIL Event Calendar <eventcalendar at csail.mit.edu>
Date: Mon, May 13, 2013 at 7:49 PM
Subject: TALK:Thursday 5-16-13 Succinct Non-Interactive Arguments via
Linear Interactive Proofs
To: seminars at csail.mit.edu



Succinct Non-Interactive Arguments via Linear Interactive Proofs
CIS Seminars 2012/2013
Speaker: Alessandro Chiesa
Speaker Affiliation: MIT
Host: CIS Seminar

Date: 5-16-2013
Time: 10:30 AM - 12:00 PM
Location: 32-D507

 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.

Relevant URL(S):
For more information please contact: Holly A Jones, 617-253-6098,
hjones01 at csail.mit.edu


_______________________________________________
Seminars mailing list
Seminars at lists.csail.mit.edu
https://lists.csail.mit.edu/mailman/listinfo/seminars
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://cs-mailman.bu.edu/pipermail/busec/attachments/20130513/6408c783/attachment.html>


More information about the Busec mailing list