Title: Upper Bounds on the Communication Complexity of Optimally Resilient Cryptographic Multiparty Computation.
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 $\mathcal{O}(cn^2\kappa)$ 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 $\mathcal{O}(n)$ messages (of size $\mathcal{O}(\kappa)$ each) are broadcast during the whole protocol execution, in contrast to previous protocols which require at least $\mathcal{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 $\mathcal{O}(cn^2\kappa)$ to $\mathcal{O}(cn\kappa)$. This improvement is mainly due to a simple observation.
Publication Year: 2004
Publication Date: 2004-01-01
Language: en
Type: preprint
Access and Citation
AI Researcher Chatbot
Get quick answers to your questions about the article from our AI researcher chatbot