Making Argument Systems for Outsourced Computation Practical (Sometimes)

Srinath Setty, Richard McPherson, Andrew J. Blumberg, Michael Walfish

Research output: Contribution to conferencePaperpeer-review


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.

Original languageEnglish (US)
StatePublished - 2012
Event19th Annual Network and Distributed System Security Symposium, NDSS 2012 - San Diego, United States
Duration: Feb 5 2012Feb 8 2012


Conference19th Annual Network and Distributed System Security Symposium, NDSS 2012
Country/TerritoryUnited States
CitySan Diego

ASJC Scopus subject areas

  • Computer Networks and Communications
  • Control and Systems Engineering
  • Safety, Risk, Reliability and Quality

Cite this