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