Paper 2009/547

Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers

Rosario Gennaro, 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.

Note: Acknowledged two additional funding sources.

Metadata
Available format(s)
PDF PS
Category
Cryptographic protocols
Publication info
Published elsewhere. Published in CRYPTO 2010.
Keywords
VerifiableIntegrityOutsourcingProtocolsPublic-key Cryptography
Contact author(s)
parno @ cmu edu
History
2010-09-01: last of 3 revisions
2009-11-10: received
See all versions
Short URL
https://ia.cr/2009/547
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2009/547,
      author = {Rosario Gennaro and Craig Gentry and Bryan Parno},
      title = {Non-Interactive Verifiable Computing: Outsourcing Computation to Untrusted Workers},
      howpublished = {Cryptology ePrint Archive, Paper 2009/547},
      year = {2009},
      note = {\url{https://eprint.iacr.org/2009/547}},
      url = {https://eprint.iacr.org/2009/547}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.