Making argument systems for outsourced computation practical (sometimes)
Srinath Setty, Richard McPherson, Andrew J. Blumberg, Michael Walfish · 2012
This paper describes the design, implementation, and evalu-ation of a system for performing verifiable outsourced com-putation. 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, ac-cording to the conventional (and well-founded) wisdom. Our goal is to challenge (2), with a built system that im-plements 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 im-prove 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. 1