International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: Improved Delegation of Computation using Fully Homomorphic Encryption

Kai-Min Chung
Yael Tauman Kalai
Salil P. Vadhan
Search ePrint
Search Google
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).
  title={Improved Delegation of Computation using Fully Homomorphic Encryption},
  booktitle={IACR Eprint archive},
  keywords={cryptographic protocols / verifiable computation, outsourcing computation, worst-case/average-case reductions, computationally sound proofs, universal argument systems},
  note={ 14728 received 28 Apr 2010, last revised 28 Apr 2010},
  author={Kai-Min Chung and Yael Tauman Kalai and Salil P. Vadhan},