[Busec] Group meeting - Monday 1PM with Adriana Lopez-Alt, NYU

Sharon Goldberg goldbe at cs.bu.edu
Fri Dec 2 08:12:15 EST 2011


Group meeting is on for Monday, 1PM in MCS137.  We have a visitor from
NYU talking about FHE.


Title:     On-the-Fly Multiparty Computation on the Cloud  via
Multikey Fully Homomorphic Encryption
Speaker: Adriana Lopez-Alt, NYU

 We propose a new notion of secure multiparty computation aided by a
computationally-powerful but untrusted server (a ``cloud'', in modern
parlance). In this notion, on-the-fly MPC, the cloud can
non-interactively perform arbitrary, dynamically chosen computations
on data belonging to arbitrary sets of users chosen on-the-fly. All
user's input data and intermediate results are protected from snooping
by the cloud as well as other users. This extends the standard notion
of fully homomorphic encryption (FHE), where users can only enlist the
cloud's help in evaluating functions on their own encrypted data.

In on-the-fly MPC, each user is involved only when initially uploading
his (encrypted) data to the cloud, and in a final output decryption
phase when outputs are revealed; the complexity of both is independent
of the function being computed and the total number of users in the
system. When users upload their data, they need not decide in advance
which function will be computed, nor who are their peers in the cloud;
they need only retroactively approve the eventually-chosen functions
and on what parties' data the functions were evaluated.

This notion is qualitatively the best possible in mininizing
interaction, since the users' interaction in the decryption stage is
inevitable: we show that removing it would imply generic program
obfuscation and is thus impossible. Our contributions are two-fold:

 1. We define the notion of a multikey fully homomorphic encryption
capable of operating on inputs encrypted under multiple, unrelated
keys. A ciphertext resulting from a multikey evaluation can be jointly
decrypted using the secret keys of all the users involved in the
computation.  We show how to use a multikey FHE scheme to construct an
on-the-fly MPC protocol.

 2. We construct a multikey FHE scheme based on NTRU, a very efficient
public-key encryption scheme proposed in the 1990s. In this scheme,
the ciphertext and key sizes grow only with the number of parties
whose data was fed into the function, and are independent of the total
number of potential parties, and of the evaluated function's
complexity. It was previously not known how to make NTRU fully
homomorphic even for a single  party.

Joint work with Eran Tromer and Vinod Vaikuntanathan

Sharon Goldberg
Computer Science, Boston University

More information about the Busec mailing list