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
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
}