Paper 2014/202

Efficiently Verifiable Computation on Encrypted Data

Dario Fiore, Rosario Gennaro, and Valerio Pastro


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

Available format(s)
Publication info
Published elsewhere. MAJOR revision.ACM CCS 2014
verifiable computationFully Homomorphic Encryptionhomomorphic message authentication codes
Contact author(s)
rosario @ cs ccny cuny edu
2015-10-20: last of 2 revisions
2014-03-17: received
See all versions
Short URL
Creative Commons Attribution


      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{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.