A hybrid architecture for interactive verifiable computation
Proceedings of the IEEE Symposium on Security and Privacy (S&P (Oakland)) 2013.
View
PDF or BibTeX.
areas
Security
abstract
We consider interactive, proof-based verifiable
computation: how can a client machine specify a computation to a
server, receive an answer, and then engage the server in
an interactive protocol that convinces the client that the answer is
correct, with less work for the client than executing the
computation in the first place? Complexity theory and cryptography offer
solutions in principle, but if implemented naively, they are ludicrously expensive. Recently, however, several strands of work have refined this theory and
implemented the resulting protocols in actual systems. This work is
promising but suffers from one of two problems: either it relies on
expensive cryptography, or else it applies to a restricted class of computations. Worse, it is not always clear which
protocol will perform better for a given problem.
We describe a system that (a) extends optimized refinements of the non-cryptographic
protocols to a much broader class of computations, (b) uses static analysis to fail over to the cryptographic ones when the non-cryptographic ones would be more
expensive, and (c) incorporates this core into a built system that
includes a compiler for a high-level language, a distributed server, and GPU acceleration.
Experimental results indicate that our system
performs better and applies more widely than the best in the literature.