Duration: 59:16

492 views

8

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.