Cryptology ePrint Archive: Report 2014/202
Efficiently Verifiable Computation on Encrypted Data
Dario Fiore and 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.
Category / Keywords: verifiable computation, Fully Homomorphic Encryption, homomorphic message authentication codes
Original Publication (with major differences): ACM CCS 2014
Date: received 17 Mar 2014, last revised 20 Oct 2015
Contact author: rosario at cs ccny cuny edu
Available format(s): PDF | BibTeX Citation
Note: Major revision, with additional material and new results
Version: 20151020:101505 (All versions of this report)
Short URL: ia.cr/2014/202
Discussion forum: Show discussion | Start new discussion
[ Cryptology ePrint archive ]