Welcome to the resource topic for
**2004/318**

**Title:**

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

**Authors:**
Martin Hirt, Jesper Buus Nielsen

**Abstract:**

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<n from \O(c n^2 \kappa) to \O(c n \kappa). This improvement is mainly due to a simple observation.

**ePrint:**
https://eprint.iacr.org/2004/318

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

**Example resources include:**
implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .