**Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers**

*Rosario Gennaro and Craig Gentry and Bryan Parno*

**Abstract: **Verifiable Computation enables a computationally weak client to "outsource" the computation of a function F on various 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 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) time, where m is the bit-length of the output of F. The protocol requires a one-time pre-processing stage by the client which takes O(|C|) time, where C is the smallest Boolean circuit computing F. Our scheme also provides input and output privacy for the client, meaning that the workers do not learn any information about the x_i or y_i values.

**Category / Keywords: **cryptographic protocols / Verifiable, Integrity, Outsourcing, Protocols, Public-key Cryptography

**Publication Info: **Published in CRYPTO 2010.

**Date: **received 7 Nov 2009, last revised 31 Aug 2010

**Contact author: **parno at cmu edu

**Available format(s): **Postscript (PS) | Compressed Postscript (PS.GZ) | PDF | BibTeX Citation

**Note: **Acknowledged two additional funding sources.

**Version: **20100901:002910 (All versions of this report)

**Short URL: **ia.cr/2009/547

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]