Cryptology ePrint Archive: Report 2012/622

Resolving the conflict between generality and plausibility in verified computation

Srinath Setty and Benjamin Braun and Victor Vu and Andrew J. Blumberg and Bryan Parno and Michael Walfish

Abstract: 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. A 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 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)

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]