CryptoDB

Paper: Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation

Authors: Martin Hirt Jesper Buus Nielsen URL: http://eprint.iacr.org/2004/318 Search ePrint Search Google We give improved upper bounds on the communication complexity of optimally-resilient secure multiparty computation in the cryptographic model. We consider evaluating an $n$-party randomized function and show that if $f$ can be computed by a circuit of size $c$, then $\O(c n^2 \kappa)$ is an upper bound for active security with optimal resilience $t < n/2$ and security parameter $\kappa$. This improves on the communication complexity of previous protocols by a factor of at least $n$. This improvement comes from the fact that in the new protocol, only $\O(n)$ messages (of size $\O(\kappa)$ each) are broadcast during the \emph{whole} protocol execution, in contrast to previous protocols which require at least $\O(n)$ broadcasts \emph{per gate}. Furthermore, we improve the upper bound on the communication complexity of passive secure multiparty computation with resilience \$t
BibTeX
@misc{eprint-2004-12284,
title={Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation},
booktitle={IACR Eprint archive},
keywords={cryptographic protocols /},
url={http://eprint.iacr.org/2004/318},
note={Asiacrypt 2005 hirt@inf.ethz.ch 13278 received 23 Nov 2004, last revised 10 May 2006},
author={Martin Hirt and Jesper Buus Nielsen},
year=2004
}