This paper addresses that problem. Provided one is willing to batch verification, we develop a protocol that achieves the efficiency of the best manually constructed protocols in the literature yet applies to most computations. Our protocol is built on the observation that the recently-proposed QAPs of Gennaro et al. (ePrint 2012/215) yield a linear PCP that works with the efficient argument protocol of Setty et al. (ePrint 2012/598, Security 2012, NDSS 2012), itself based on the proposal of Ishai et al. (CCC 2007). The consequence is a prover whose total work is not much more than \emph{linear} in the running time of the computation. We implement the protocol in the context of a built system that includes a compiler and a GPU implementation. The result, as indicated by an experimental evaluation, is a system that is {\em almost} usable for real problems---without special-purpose tailoring.
Category / Keywords: cryptographic protocols / verified computation applications implementation Publication Info: This is the full version of a paper at Eurosys 2013. Date: received 2 Nov 2012, last revised 11 Mar 2013 Contact author: mwalfish at cs utexas edu Available format(s): PDF | BibTeX Citation Note: Update proofs, experimental results, and exposition. Version: 20130312:051837 (All versions of this report) Short URL: ia.cr/2012/622 Discussion forum: Show discussion | Start new discussion