Time+Place: Monday 21/07/2014 11:30 Room 337-8 Taub Bld.
Title: Scalable Zero Knowledge via Cycles of Elliptic Curves
Speaker: Alessandro Chiesa - CSpecial Lecture - Note unusual day and time http://people.csail.mit.edu/alexch/
Affiliation: M I T
Host: Eli Ben-Sasson

Abstract:


Non-interactive zero-knowledge proofs for general NP statements are a
powerful cryptographic primitive. Recent work has achieved theoretical
constructions and working implementations of zero-knowledge proofs that 
are short and easy to verify.

Alas, all prior implementations suffer from severe scalability limitations:
the proving key's size and the prover's space complexity grow with the 
size of the computation being proved.

The bootstrapping technique of Bitansky et al. (STOC 2013), following
Valiant (TCC 2008), offers an approach to scalability, by recursively
composing proofs, but it has never been realized in practice, due to
enormous computational cost.

In this work, by leveraging new elliptic-curve cryptographic techniques, 
we achieve the first practical implementation of recursive proof 
composition, and thereby achieve the first implementation of *scalable zero 
knowledge*.

Joint work with Eli Ben-Sasson, Eran Tromer, and Madars Virza.