## CryptoDB

### Paper: On the Message Complexity of Secure Multiparty Computation

Authors: Yuval Ishai Manika Mittal Rafail Ostrovsky DOI: 10.1007/978-3-319-76578-5_24 Search ePrint Search Google PKC 2018 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
}