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

Martin Hirt and Jesper Buus Nielsen

Advances in Cryptology — ASIACRYPT 2005, Lecture Notes in Computer Science, Springer-Verlag, vol. 3788, pp. 79–99, Dec 2005.

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} κ)$ is an upper bound for active security with optimal resilience $t < n / 2$ and security parameter $κ$ . 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 (κ)$ 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} κ)$ to $O (c n κ)$ . 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},
}