International Association
for Cryptologic Research

The area of proof-based verified computation (outsourced computation

built atop probabilistically checkable proofs and cryptographic

machinery) has lately seen renewed interest. Although recent work has

made great strides in reducing the overhead of naive applications of the

theory, these schemes still cannot be considered practical. The core

issue is that the work for the prover is immense, in general; it

is near-practical only for hand-compiled computations that can

be expressed in special forms.

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 all

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

_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 parallel GPU

implementation. The result, as indicated by an experimental evaluation,

is a system that is _almost_ usable for real problems -- without

special-purpose tailoring.