Vinod Vaikuntanathan, Microsoft Research Redmond
TWO TALKS ON DEVELOPMENTS IN HOMOMORPHIC ENCRYPTION AND LEAKAGE RESILIENT CRYPTOGRAPHY
1) FULLY HOMOMORPHIC ENCRYPTION OVER THE INTEGERS
2) RERANDOMIZABLE YAO CIRCUITS AND i-HOP HOMOMORPHIC ENCRYPTION
ABSTRACTS
1) FULLY HOMOMORPHIC ENCRYPTION OVER THE INTEGERS
We construct a simple fully homomorphic encryption scheme, using only
elementary modular arithmetic. The security of our scheme relies on the
hardness of the approximate integer greatest common divisors (gcd) problem
-- namely, given a list of integers that are "near-multiples" of a hidden
integer, output that hidden integer.
Joint work with Marten van Dijk, Craig Gentry, and Shai Halevi.
2) RERANDOMIZABLE YAO CIRCUITS AND i-HOP HOMOMORPHIC ENCRYPTION
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 Shai Halevi and Craig Gentry