[Pl-seminar] 5/29: Eli Ben-Sasson, Universal and Affordable Computational Integrity, or, Succinctly, from C to PCP

[Vincent St-Amour]

NEU Programming Languages Seminar presents

Eli Ben-Sasson
Technion

Wednesday, 5/29
11:45-1:30
Room 366 WVH (http://www.ccs.neu.edu/home/wand/directions.html)


Universal and Affordable Computational Integrity, or, Succinctly, from C to PCP

Public key cryptography, invented in the 1970′s, revolutionized the world
of computation by displaying a tool-box that builds trust in authenticity
and integrity of data, even when it is transmitted from unknown computers
and relayed via untrusted and possibly corrupt intermediaries. A celebrated
line of theoretical works dating back to the 1980′s envisions a similar
revolution, offering a level of trust in the integrity of arbitrary
computations even when executed on untrusted and possibly malicious
computers. A particularly surprising aspect of these results is
succinctness which means that the running-time needed to verify a
computation is only as costly as reading the program that describes it,
even when this program is exponentially shorter in length than the
computation’s running time!

Common belief has been that it is impractical to build a truly succinct
computational-integrity protocol. We challenge this conception by
describing the first full-scale implementation of it. Our system compiles
programs in standard (ANSI) C into succinctly-verifiable programs, with
asymptotic parameters that match the best-possible bounds predicted by
theory. Joint work with Alessandro Chiesa, Daniel Genkin, Eran Tromer and
Madars Virza.