Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers

Rosario Gennaro, Craig Gentry, and Bryan Parno

August 2010

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 x_{1},...,x_{k} to one or more workers. The workers return the result of the function evaluation, e.g., y_{i}=F(x_{i}), as well as a proof that the computation of F was carried out correctly on the given value x_{i}. The primary constraint is that the verification of the proof should require substantially less computational effort than computing F(x_{i}) 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. Unlike previous work in this area, our scheme also provides (at no additional cost) input and output privacy for the client, meaning that the workers do not learn any information about the x_{i} or y_{i} values.

Publication type | Inproceedings |

Published in | Proceedings of the International Cryptology Conference (CRYPTO) |

Publisher | Springer Verlag All copyrights reserved by Springer 2010. |

- Bootstrapping Trust in a "Trusted" Platform
- Internet Ballistics: Retrieving Forensic Data From Network Scans
- SNAPP: Stateless Network-Authenticated Path Pinning

> Publications > Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers