<div dir="ltr">Hi all, <div><br></div><div>I am forwarding the notification of this week&#39;s CIS seminar. Please note the special time and location. </div><div><br></div><div>Best, </div><div>Rachel <br><br><div class="gmail_quote">

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

<br>
<br>_______________________________________________<br>
Seminars mailing list<br>
<a href="mailto:Seminars@lists.csail.mit.edu" target="_blank">Seminars@lists.csail.mit.edu</a><br>
<a href="https://lists.csail.mit.edu/mailman/listinfo/seminars" target="_blank">https://lists.csail.mit.edu/mailman/listinfo/seminars</a><br>
<br></div><br></div></div>