Making argument systems for outsourced computation practical (sometimes)
Proceedings of the Network & Distributed System Security Symposium (NDSS) 2012.
View
PDF or BibTeX.
areas
Security
abstract
This paper describes the design, implementation, and evaluation of a system for performing verifiable outsourced computation. It has long been known that (1) this problem can
be solved in theory using probabilistically checkable proofs
(PCPs) coupled with modern cryptographic tools, and (2)
these solutions have wholly impractical performance, according to the conventional (and well-founded) wisdom.
Our goal is to challenge (2), with a built system that implements an argument system based on PCPs. We describe
a general-purpose system that builds on work of Ishai et al. (CCC ’07) and incorporates new theoretical work to improve performance by 20 orders of magnitude. The system
is (arguably) practical in some cases, suggesting that, as a
tool for building secure systems, PCPs are not a lost cause.