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