Paper 2010/241

Improved Delegation of Computation using Fully Homomorphic Encryption

Kai-Min Chung, Yael Kalai, and Salil 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 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).

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Unknown where it was published
Keywords
verifiable computationoutsourcing computationworst-caseaverage-case reductionscomputationally sound proofsuniversal argument systems
Contact author(s)
kmchung @ fas harvard edu
History
2010-05-02: received
Short URL
https://ia.cr/2010/241
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2010/241,
      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{https://eprint.iacr.org/2010/241}},
      url = {https://eprint.iacr.org/2010/241}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.