SPEAKER: Shai Halevi TITLE: i-Hop Homomorphic Encryption Schemes AUTHORS: Craig Gentry, Shai Halevi and Vinod Vaikuntanathan ABSTRACT: A homomorphic encryption scheme enables computing on encrypted data by means of a public evaluation procedure on ciphertexts, making it possible for anyone to transform an encryption of $x$ into an encryption of $f(x)$ (for any function $f$). But evaluated ciphertexts may differ from freshly encrypted ones, which brings up the question of whether one can keep computing on evaluated ciphertexts. Namely, is it still possible for anyone to transform the encryption of $f(x)$ into an encryption of $g(f(x))$? An $i$-hop homomorphic encryption is a scheme where the evaluation procedure can be called on its own output upto $i$ times (while still being able to decrypt the result). A multi-hop homomorphic encryption is a scheme that is $i$-hop for all $i$. In this work we study $i$-hop and multi-hop schemes, in conjunction with the properties of circuit-privacy (i.e., the evaluation procedure hides the function) and compactness (i.e., the output of evaluation is short). We provide appropriate formal definitions for all these properties and show three constructions: * We show a DDH-based construction, which is multi-hop and circuit private (but not compact), and where the size of the ciphertext is linear in the size of the composed circuit, but independent of the number of hops. * More generically, for any constant $i$, an $i$-hop circuit-private homomorphic encryption can be constructed from any two-flow protocol for two-party SFE. (Conversely, a two-flow protocol for two-party SFE can be constructed from any 1-hop circuit-private homomorphic encryption.) * For any polynomial $i$, an $i$-hop compact and circuit-private homomorphic encryption can be constructed from a 1-hop compact homomorphic encryption and a 1-hop circuit-private homomorphic encryption, where the size of the public key grows linearly with $i$. Moreover, a multi-hop scheme can be constructed by making an additional circular-security assumption. For the first construction, we describe a *re-randomizable* variant of Yao's garbled-circuits. Namely, given a garbled circuit, anyone can re-garble it in such a way that even the party that generated that circuit (in collusion with the intended recipient) will not be able to recognize it. This construction may be of independent interest. LINKS: http://eprint.iacr.org/2010/145