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>