Paper 2018/038

On the Message Complexity of Secure Multiparty Computation

Yuval Ishai, Manika Mittal, and Rafail Ostrovsky


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.

Available format(s)
Publication info
Published by the IACR in PKC 2018
Secure Multiparty Computation
Contact author(s)
yuvali @ cs technion ac il
manikamittal22 @ gmail com
rafail @ cs ucla edu
2018-01-08: received
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.