Making Argument Systems for Outsourced Computation Practical (Sometimes)
This paper describes the design, implementation, and evaluation of a system for performing verifiable outsourced computation. It has long been known that this problem can be solved in theory using Probabilistically Checkable Proofs (PCPs) coupled with modern cryptographic tools, and these solutions have wholly impractical performance, according to the conventional (and well-founded) wisdom. The authors' goal is to challenge, with a built system that implements an argument system based on PCPs. They 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.