Paper 2018/038 Original: eprint.iacr.org/2018/038 ↗
On the Message Complexity of Secure Multiparty Computation
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$ 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.
Metadata
- Available format(s)
PDF- Publication info
- Preprint.
- History
- 2018-01-08: last updated
- 2018-01-08: published
- Short URL
- https://ia.cr/2018/038
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2018/038,
author = {Yuval Ishai and Manika Mittal and Rafail Ostrovsky},
title = {On the Message Complexity of Secure Multiparty Computation},
howpublished = {Cryptology {ePrint} Archive, Paper 2018/038},
year = {2018},
url = {https://eprint.iacr.org/2018/038}
}