Paper 2014/202

Efficiently Verifiable Computation on Encrypted Data

Dario Fiore, Rosario Gennaro, and Valerio Pastro

Abstract

We study the task of efficient verifiable delegation of computation on encrypted data. First, we improve previous definitions in order to tolerate adversaries that learn whether or not clients accept the result of a delegated computation. Then, in this strong model, we show a scheme for arbitrary computations, and we propose highly efficient schemes for delegation of various classes of functions, such as linear combinations, high-degree univariate polynomials, and multivariate quadratic polynomials. Notably, the latter class includes many useful statistics. Using our solution, a client can store a large encrypted dataset with a server, query statistics over this data, and receive encrypted results that can be efficiently verified and decrypted. As a key contribution for the efficiency of our schemes, we develop a novel homomorphic hashing technique that allows us to efficiently authenticate computations, at the same cost as if the data were in the clear, avoiding a $10^4$ overhead, which would occur with a naive approach. We confirm our theoretical analysis with extensive implementation tests that show the practical feasibility of our schemes.

Note: Major revision, with additional material and new results

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Major revision. ACM CCS 2014
Keywords
verifiable computationFully Homomorphic Encryptionhomomorphic message authentication codes
Contact author(s)
rosario @ cs ccny cuny edu
History
2015-10-20: last of 2 revisions
2014-03-17: received
See all versions
Short URL
https://ia.cr/2014/202
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2014/202,
      author = {Dario Fiore and Rosario Gennaro and Valerio Pastro},
      title = {Efficiently Verifiable Computation on Encrypted Data},
      howpublished = {Cryptology ePrint Archive, Paper 2014/202},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/202}},
      url = {https://eprint.iacr.org/2014/202}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.