Paper 2010/241

Improved Delegation of Computation using Fully Homomorphic Encryption

Kai-Min Chung, Yael Kalai, and Salil Vadhan


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).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
verifiable computationoutsourcing computationworst-caseaverage-case reductionscomputationally sound proofsuniversal argument systems
Contact author(s)
kmchung @ fas harvard edu
2010-05-02: received
Short URL
Creative Commons Attribution


      author = {Kai-Min Chung and Yael Kalai and Salil Vadhan},
      title = {Improved Delegation of Computation using Fully Homomorphic Encryption},
      howpublished = {Cryptology ePrint Archive, Paper 2010/241},
      year = {2010},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.