International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: On the Message Complexity of Secure Multiparty Computation

Authors:
Yuval Ishai
Manika Mittal
Rafail Ostrovsky
Download:
DOI: 10.1007/978-3-319-76578-5_24
Search ePrint
Search Google
Conference: PKC 2018
Abstract: We study the minimal number of point-to-point messages required for general secure multiparty computation (MPC) in the setting of computational security against semi-honest, static adversaries who may corrupt an arbitrary number of parties.We show that for functionalities that take inputs from n parties and deliver outputs to k parties, $$2n+k-3$$2n+k-3 messages are necessary and sufficient. The negative result holds even when given access to an arbitrary correlated randomness setup. The positive result can be based on any 2-round MPC protocol (which can in turn can be based on 2-message oblivious transfer), or on a one-way function given a correlated randomness setup.
BibTeX
@inproceedings{pkc-2018-28883,
  title={On the Message Complexity of Secure Multiparty Computation},
  booktitle={Public-Key Cryptography – PKC 2018},
  series={Public-Key Cryptography – PKC 2018},
  publisher={Springer},
  volume={10769},
  pages={698-711},
  doi={10.1007/978-3-319-76578-5_24},
  author={Yuval Ishai and Manika Mittal and Rafail Ostrovsky},
  year=2018
}