
Speaker Bryan Parno Host Vinod Vaikuntanathan Affiliation MSR 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 dynamicallychosen 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 computationallysound, noninteractive proof that can be verified in O(m * poly(lambda)) time, where m is the bitlength of the output of F, and lambda is a security parameter. The protocol requires a onetime preprocessing 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.
