i-Hop Homomorphic Encryption Schemes
Speaker: Shai Halevi , IBM T. J. Watson Research Center
Date: April 2 2010
Time: 10:30AM to 12:00PM
Location: Microsoft NE, One Memorial Drive
Host: Yael Tauman Kalai, Microsoft, NE
Contact: Be Blackburn , 3-6098, imbe@mit.edu
Relevant URL: 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.
Joint work with Craig Gentry and Vinod Vaikuntanathan
See other events that are part of CIS/Microsoft Seminars 2009/2010
See other events happening in April 2010
