[Busec] BUsec this week: Nir Bitansky (Tues (Tomorrow!) 11AM)

Sharon Goldberg goldbe at cs.bu.edu
Mon Apr 16 20:46:07 EDT 2012

Hi All,

This week, our own Nir Bitansky will be hunting SNARKs.  Lunch will be
served, and we meet in MCS148 (111 Cummington St) at 11AM Tuesday
(tomorrow) as usual.

See you there!

The Hunting of the SNARK
Speaker: Nir Bitansky, Tel Aviv University

The existence of succinct non-interactive arguments for NP (i.e.,
non-interactive computationally-sound proofs where the verifier’s work
is essentially independent of the complexity of the NP
nondeterministic verifier) has been an intriguing question for the
past two decades. Other than CS proofs in the random oracle model
[Micali,FOCS ’94], the only existing candidate construction is based
on an elaborate assumption that is tailored to a specific protocol [Di
Crescenzo and Lipmaa, CiE ’08].

We formulate a general and relatively natural notion of an extractable
collision-resistant hash function (ECRH) and show that, if ECRHs
exist, then a modified version of Di Crescenzo and Lipmaa’s protocol
is a succinct non-interactive argument for NP. Furthermore, the
modified protocol is actually a succinct non-interactive adaptive
argument of knowledge (SNARK). We then propose several candidate
constructions for ECRHs and relaxations thereof. We demonstrate the
applicability of SNARKs to various forms of delegation of computation,
to succinct non-interactive zero knowledge arguments, and to succinct
two-party secure computation. Finally, we show that SNARKs essentially
imply the existence of ECRHs, thus demonstrating the necessity of the

Based on joint work with Ran Canetti, Alessandro Chiesa, Shafi Goldwasser,
Rachel Lin, Aviad Rubinstein and Eran Tromer.

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list