Technion
 
         Computer Science Colloquium
 
Time+Place : Tuesday 07/02/2012 14:30 room 337-8 Taub  Bld.
Speaker    : Ivan Damgaard
Affiliation: Aarhus University
Host       : Yuval Ishai
Title      : Multiparty Computation from Somewhat Homomorphic Encryption
 
Abstract   :
 
Multiparty computation allows n players to compute a function on n private
inputs, such that the desired output is the only new information revealed.
This should hold even some of the players are corrupted by an adversary.
 
We propose a general multiparty protocol for this purpose, secure against an
active adversary corrupting n-1 of the n players. The protocol  may be used
to securely compute arithmetic circuits over any finite field F_{p^k}.  Our
protocol consists of a preprocessing phase that is both independent of the
function to be computed and of the inputs, and a much more efficient on-line
phase where the actual computation takes place. The online phase is
unconditionally secure and has total computational (and communication)
complexity linear in n, where earlier work was quadratic in n. Hence, the
work done by each player in the on-line phase is independent of n and
moreover is only a small constant factor larger than what one would need to
compute the circuit in the clear. It is the first protocol in the
preprocessing model with these properties.
 
An implementation of this protocol performs a secure 3-player, 64-bit
multiplication in 0.05 ms. The preprocessing is based on a somewhat
homomorphic cryptosystem. We extend a scheme by Brakersky et al., so that we
can perform distributed decryption and handle many values in parallel in one
ciphertext. The computational complexity of our preprocessing phase is
dominated by the public-key operations, we need
O(n/s) operations per secure multiplication where s is a parameter that
increases with the security parameter of the cryptosystem. Earlier work in
this model needed Omega(n^2) operations. In practice, the preprocessing
prepares a secure 64-bit multiplication for 3 players in about 13 ms, which
is 2-3 orders of magnitude faster than the best previous results.
 
Joint work with Valerio Pastro, Nigel Smart and Sarah Zakarias
 
Short bio:
Ivan Damgaard got his PhD from Aarhus University in 1988, and has been at
CWI Amsterdam before joining Aarhus University where he has been a full
professor since 2006. He has published over 100 peer reviewed papers, is a
member of the TCC Steering committee, and was appointed fellow of the IACR
in 2010.
 
Refreshments served from 14:15 on,
 	Lecture starts at 14:30
 
----------------------------------------------------------
Visit our home page-   <http://www.cs.technion.ac.il/~colloq>
---------------------------------------------------------
Technion Math. Net (TECHMATH)
Editor: Michael Cwikel   <techm@math.technion.ac.il> 
Announcement from: Hadas Heier   <heier@cs.technion.ac.il>