IACR paper details
Title  Improved Delegation of Computation using Fully Homomorphic Encryption 

Booktitle  IACR Eprint archive 

Pages  

Year  2010 

URL  http://eprint.iacr.org/2010/241 

Author  KaiMin Chung 

Author  Yael Kalai 

Author  Salil P. 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 4message (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 rerun the offline construction after errors are detected (assuming errors are not too frequent).


Search for the paper
@misc{eprint201023142,
title={Improved Delegation of Computation using Fully Homomorphic Encryption},
booktitle={IACR Eprint archive},
keywords={cryptographic protocols / verifiable computation, outsourcing computation, worstcase/averagecase reductions, computationally sound proofs, universal argument systems},
url={http://eprint.iacr.org/2010/241},
note={ kmchung@fas.harvard.edu 14728 received 28 Apr 2010, last revised 28 Apr 2010},
author={KaiMin Chung and Yael Kalai and Salil P. Vadhan},
year=2010
}
Download a complete BibTeX file.