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 .