Abstract

The growth of ``cloud computing’’ and the proliferation of mobile devices contribute to a desire to outsource computing from a client device to an online service. However, in these applications, how can the client verify that the result returned is correct, without redoing the computation herself? We formalize this setting by introducing the notion of verifiable computation, and we provide a protocol that achieves asymptotically optimal performance (amortized over multiple inputs). We then extend the definition of verifiable computation in two important directions: public delegation and public verifiability, which have important applications in many practical delegation scenarios. To achieve these new properties, we establish an important (and somewhat surprising) connection between verifiable computation and attribute-based encryption. Finally, we introduce a new characterization of NP that lends itself to very efficient cryptographic applications, including verifiable computation, succinct non-interactive arguments, and non-interactive zero knowledge proofs.

Bryan Parno is a researcher in the Security and Privacy Group within Microsoft Research, Redmond. His interests span a broad range of security topics, including network and system security, applied cryptography, usable security, and data privacy. Currently, he is investigating next-generation application models, privacy-preserving online services, and cryptographic techniques for securely outsourcing computation. He completed his PhD at Carnegie Mellon University, where he was advised by Adrian Perrig. His dissertation received the 2010 ACM Doctoral Dissertation Award, and he recently co-authored the book “Bootstrapping Trust in Modern Computers”.