[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.


---------- 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
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
proven later. Recent constructions of preprocessing SNARGs have achieved
attractive features: they are publicly-verifiable, proofs consist of only
encrypted (or encoded) field elements, and verification is via arithmetic
circuits of size linear in the NP statement. Additionally, these
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
achieved by studying a natural extension of the interactive proof model that
considers algebraically-bounded provers; this new setting is analogous to
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

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
-------------- 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