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