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