Universal and Affordable Computational Integrity, or, Succinctly, from C to PCP
May 01, 2013
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 succinctnesswhich 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!