International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

The Broadcast Message Complexity of Secure Multiparty Computation

Authors:
Sanjam Garg
Aarushi Goel
Abhishek Jain
Download:
DOI: 10.1007/978-3-030-34578-5_16
Search ePrint
Search Google
Abstract: We study the broadcast message complexity of secure multiparty computation (MPC), namely, the total number of messages that are required for securely computing any functionality in the broadcast model of communication.MPC protocols are traditionally designed in the simultaneous broadcast model, where each round consists of every party broadcasting a message to the other parties. We show that this method of communication is sub-optimal; specifically, by eliminating simultaneity, it is, in fact, possible to reduce the broadcast message complexity of MPC.More specifically, we establish tight lower and upper bounds on the broadcast message complexity of n-party MPC for every $$t<n$$ corruption threshold, both in the plain model as well as common setup models. For example, our results show that the optimal broadcast message complexity of semi-honest MPC can be much lower than 2n, but necessarily requires at least three rounds of communication. We also extend our results to the malicious setting in setup models.
BibTeX
@article{asiacrypt-2019-30023,
  title={The Broadcast Message Complexity of Secure Multiparty Computation},
  booktitle={Advances in Cryptology – ASIACRYPT 2019},
  series={Advances in Cryptology – ASIACRYPT 2019},
  publisher={Springer},
  volume={11921},
  pages={426-455},
  doi={10.1007/978-3-030-34578-5_16},
  author={Sanjam Garg and Aarushi Goel and Abhishek Jain},
  year=2019
}