We describe a refinement of a powerful interactive proof protocol due to Goldwasser, Kalai, and Rothblum. Cormode, Mitzenmacher, and Thaler show how to implement the prover in this protocol in time $O(S \log S)$, where $S$ is the size of an arithmetic circuit computing the function of interest. Our refinements apply to circuits with sufficiently ``regular'' wiring patterns; for these circuits, we bring the runtime of the prover down to $O(S)$. That is, our prover can evaluate the circuit with a guarantee of correctness, with only a constant-factor blowup in work compared to evaluating the circuit with no guarantee.
We argue that our refinements capture a large class of circuits, and we complement our theoretical results with experiments on problems such as matrix multiplication and determining the number of distinct elements in a data stream. Experimentally, our refinements yield a 200x speedup for the prover over the implementation of Cormode et al., and our prover is less than 10x slower than a C++ program that simply evaluates the circuit. Along the way, we describe a special-purpose protocol for matrix multiplication that is of interest in its own right.
Our final contribution is the design of an interactive proof protocol targeted at general data parallel computation. Compared to prior work, this protocol can more efficiently verify complicated computations as long as that computation is applied independently to many different pieces of data.Category / Keywords: foundations / interactive proofs, verifiable computation, circuit evaluation Publication Info: This is the full version of a Crypto 2013 paper by the same title. Date: received 6 Jun 2013, last revised 8 Feb 2017 Contact author: justin thaler at georgetown edu Available format(s): PDF | BibTeX Citation Note: This is the full version of a Crypto 2013 paper by the same title. This version corrects a typographical error in Section 7. We are grateful to Michael Walfish for identifying the error. Version: 20170208:190200 (All versions of this report) Short URL: ia.cr/2013/351 Discussion forum: Show discussion | Start new discussion