Cryptology ePrint Archive: Report 2010/241

Improved Delegation of Computation using Fully Homomorphic Encryption

Kai-Min Chung and Yael Kalai and Salil Vadhan

Abstract: Following Gennaro, Gentry, and Parno (Cryptology ePrint Archive 2009/547), we use fully homomorphic encryption to design improved schemes for delegating computation. In such schemes, a delegator outsources the computation of a function $F$ on many, dynamically chosen inputs $x_i$ to a worker in such a way that it is infeasible for the worker to make the delegator accept a result other than $F(x_i)$. The "online stage" of the Gennaro et al. scheme is very efficient: the parties exchange two messages, the delegator runs in time $poly(log T)$, and the worker runs in time $poly(T)$, where $T$ is the time complexity of $F$. However, the "offline stage" (which depends on the function $F$ but not the inputs to be delegated) is inefficient: the delegator runs in time $poly(T)$ and generates a public key of length $poly(T)$ that needs to be accessed by the worker during the online stage.

Our first construction eliminates the large public key from the Gennaro et al. scheme. The delegator still invests $poly(T)$ time in the offline stage, but does not need to communicate or publish anything. Our second construction reduces the work of the delegator in the offline stage to $poly(log T)$ at the price of a 4-message (offline) interaction with a $poly(T)$-time worker (which need not be the same as the workers used in the online stage). Finally, we describe a "pipelined" implementation of the second construction that avoids the need to re-run the offline construction after errors are detected (assuming errors are not too frequent).

Category / Keywords: cryptographic protocols / verifiable computation, outsourcing computation, worst-case/average-case reductions, computationally sound proofs, universal argument systems

Date: received 28 Apr 2010, last revised 28 Apr 2010

Contact author: kmchung at fas harvard edu

Available format(s): PDF | BibTeX Citation

Version: 20100502:164820 (All versions of this report)

Short URL: ia.cr/2010/241

Discussion forum: Show discussion | Start new discussion