No subject

====================================


Computer programs are succinct blueprints of computations that often are long and have unpredictable outcomes. Verifying computational integrity, i.e., obtaining reliable guarantees for output-correctness, is a notoriously hard but extremely important challenge.

Here we present the first implementation (written in C++) that solves the computational integrity problem: Using it, a programmer can out-source the execution of any program written in C to an untrusted party, and later on verify output-correctness via a computation that is only as costly as re-reading the program. In contrast, previous implementations of computational integrity protocols demanded a set-up running time that is as costly as executing the program whose integrity we seek to verify.

Our system is also the first full-scale implementation of a succinct reduction from the bounded-halting problem for universal RAM machines to a probabilistically checkable proof (PCP), and demonstrates the applicability of PCPs to practical settings.

Joint work with Alessandro Chiesa, Daniel Genkin, Eran Tromer and Madars Virza
====================
_______________________________________________
Theory-Read mailing list
Theory-Read at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/theory-read
_______________________________________________
pvsnp-all mailing list
pvsnp-all at lists.cs.princeton.edu
https://lists.cs.princeton.edu/mailman/listinfo/pvsnp-all