Universal and affordable Computational Integrity, or, succinctly, from C to PCP
Date and Time
Thursday, March 14, 2013 - 12:30pm to Friday, February 8, 2013 - 1:30pm
Location
Friend Center Convocation Room
Type
Talk
Speaker
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. 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.
