Resolving the conflict between generality and plausibility in verified computation

Srinath Setty, Benjamin Braun, Victor Vu, Andrew J. Blumberg, Bryan Parno, Michael Walfish
The University of Texas at Austin, Austin, TX
Cryptology ePrint (ePrint), 2012


   Author={Srinath Setty and Benjamin Braun and Victor Vu and Andrew J. Blumberg and Bryan Parno and Michael Walfish},

   Title={Resolving the conflict between generality and plausibility in verified computation},



Download Download (PDF)   View View   Source Source   



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.
No votes yet.
Please wait...

* * *

* * *

HGPU group © 2010-2021 hgpu.org

All rights belong to the respective authors

Contact us: