Welcome to the resource topic for 2010/145
Title:
i-Hop Homomorphic Encryption and Rerandomizable Yao Circuits
Authors: Craig Gentry, Shai Halevi, and Vinod Vaikuntanathan
Abstract:Homomorphic encryption (HE) schemes enable computing functions on encrypted data, by means of a public \Eval procedure that can be applied to ciphertexts. But the evaluated ciphertexts so generated may differ from freshly encrypted ones. This brings up the question of whether one can keep computing on evaluated ciphertexts. An \emph{i-hop} homomorphic encryption scheme is one where \Eval can be called on its own output up to i~times, while still being able to decrypt the result. A \emph{multi-hop} homomorphic encryption is a scheme which is i-hop for all~i. In this work we study i-hop and multi-hop schemes in conjunction with the properties of function-privacy (i.e., \Eval's output hides the function) and compactness (i.e., the output of \Eval is short). We provide formal definitions and describe several constructions. First, we observe that “bootstrapping” techniques can be used to convert any (1-hop) homomorphic encryption scheme into an i-hop scheme for any~i, and the result inherits the function-privacy and/or compactness of the underlying scheme. However, if the underlying scheme is not compact (such as schemes derived from Yao circuits) then the complexity of the resulting i-hop scheme can be as high as k^{O(i)}. We then describe a specific DDH-based multi-hop homomorphic encryption scheme that does not suffer from this exponential blowup. Although not compact, this scheme has complexity linear in the size of the composed function, independently of the number of hops. The main technical ingredient in this solution is a \emph{re-randomizable} variant of the Yao circuits. Namely, given a garbled circuit, anyone can re-garble it in such a way that even the party that generated the original garbled circuit cannot recognize it. This construction may be of independent interest.
ePrint: https://eprint.iacr.org/2010/145
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .