mar
14
2013

Eli Ben-Sasson – Universal and Affordable Computational Integrity, or, Succinctly, from C to PCP

CITP Luncheon Series

Date: Thursday, March 14, 2013
Location: Friend Center Convocation Room (please note the location change)
Streaming Live: https://www.youtube.com/user/citpprinceton
Food and discussion begins at 12:30 pm. Everyone invited.

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 {\em 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 {\em computations} even when executed on untrusted and possibly malicious computers. A particularly surprising aspect of these results is {\em 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.m Our system compiles programs in standard C into succinctly-verifiable programs, with asymptotic parameters that match the best-possible bounds predicted by theory.

Joint work with Alessandro Chiesa, Daniel Genkin and Eran Tromer.