Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation
Martin Hirt and Jesper Buus Nielsen
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 whole protocol execution, in contrast to previous protocols which require at least $\O(n)$ broadcasts per gate.
Furthermore, we improve the upper bound on the communication complexity of passive secure multiparty computation with resilience $t<n$ from $\O(c n^2 \kappa)$ to $\O(c n \kappa)$. This improvement is mainly due to a simple observation.
BibTeX Citation
@inproceedings{HirNie05,
author = {Martin Hirt and Jesper Buus Nielsen},
title = {Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation},
editor = {Bimal Roy},
booktitle = {Advances in Cryptology --- ASIACRYPT 2005},
pages = 79--99,
series = {Lecture Notes in Computer Science},
volume = 3788,
year = 2005,
month = 12,
publisher = {Springer-Verlag},
}