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.
Category / Keywords: BHHO encryption, Compactness, Function Privacy, Homomorphic Encryption, Secure Two-party Computation, Oblivious Transfer, Yao's Garbled Circuits Publication Info: extended abstract in CRYPTO 2010, this is the full version Date: received 16 Mar 2010, last revised 27 May 2010 Contact author: shaih at alum mit edu Available format(s): PDF | BibTeX Citation Version: 20100527:202508 (All versions of this report) Short URL: ia.cr/2010/145