Improved Delegation of Computation using Fully Homomorphic Encryption by Kai-Min Chung, Harvard

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)$. There may be an ``offline stage'' where the delegator work hard to produce some private key and publish some public key, and later in the ``online stage'', the delegator needs to do less work than computing $F(x_i)$'s by itself. 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. In this talk, we present two improved schemes that eliminate the large public key from the Gennaro et al. scheme. In our first 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). We will also discuss a ``reusability'' issue of delegation schemes.
Joanne Talbot Hanley
Last modified: Mon Aug 16 11:11:28 EDT 2010