Time+Place: Sunday 20/07/2014 11:30 Room 337-8 Taub Bld.
Title: Succinct Non-Interactive Zero Knowledge for a von Neumann Architecture
Speaker: Madars Virza - CSpecial Lecture - Note unusual time http://www.csail.mit.edu/user/2615
Affiliation: MIT
Host: Eli Ben-Sasson

Abstract:


We build a system that provides succinct non-interactive zero-knowledge
proofs (zk-SNARKs) for program executions on a von Neumann RISC
architecture. The system has two components: a cryptographic proof 
system for verifying satisfiability of arithmetic circuits, and a circuit 
generator to translate program executions to such circuits.

Our design of both components improves in functionality and efficiency 
over prior work:
(1) Our circuit generator is the first to be universal: it does not need 
to know the program, but only a bound on its running time; moreover, the 
size of the output circuit depends additively (rather than multiplicatively) 
on program size, allowing verification of larger programs.
(2) The cryptographic proof system improves proving and verification 
times, by leveraging new algorithms and a pairing library tailored to the 
protocol.

Joint work with Eli Ben-Sasson, Alessandro Chiesa, and Eran Tromer.