Share on Facebook Tweet on Twitter Share on LinkedIn Share by email
Non-Interactive Verifiable Computing

Speaker  Bryan Parno

Affiliation  MSR

Host  Vinod Vaikuntanathan

Duration  00:58:53

Date recorded  3 March 2011

We introduce and formalize the notion of Verifiable Computation, which enables a computationally weak client to "outsource" the computation of a function F on various dynamically-chosen inputs to one or more workers. The primary constraint is that the verification of the results should require substantially less effort than computing F from scratch.

We present a protocol that allows the worker to return a computationally-sound, non-interactive proof that can be verified in O(m * poly(lambda)) time, where m is the bit-length of the output of F, and lambda is a security parameter. The protocol requires a one-time pre-processing stage by the client which takes O(|C| * poly(lambda)) time, where C is the smallest known Boolean circuit computing F.

Finally, we present new constructions that promise substantially better performance in practice, though current instantiations do not achieve the full set of desirable properties for verifiable computing.

©2011 Microsoft Corporation. All rights reserved.
> Non-Interactive Verifiable Computing