Paper 2019/1183

Broadcast-Optimal Two-Round MPC

Ran Cohen, Juan Garay, and Vassilis Zikas


An intensive effort by the cryptographic community to minimize the round complexity of secure multi-party computation (MPC) has recently led to optimal two-round protocols from minimal assumptions. Most of the proposed solutions, however, make use of a broadcast channel in every round, and it is unclear if the broadcast channel can be replaced by standard point-to-point communication in a round-preserving manner, and if so, at what cost on the resulting security. In this work, we provide a complete characterization of the trade-off between number of broadcast rounds and achievable security level for two-round MPC tolerating arbitrarily many active corruptions. Specifically, we consider all possible combinations of broadcast and point-to-point rounds against the three standard levels of security for maliciously secure MPC protocols, namely, security with identifiable, unanimous, and selective abort. For each of these notions and each combination of broadcast and point-to-point rounds, we provide either a tight feasibility or an infeasibility result of two-round MPC. Our feasibility results hold assuming two-round OT in the CRS model, whereas our impossibility results hold given any correlated randomness.

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
two-round MPCidentifiable abortunanimous abortselective abortbroadcast
Contact author(s)
rancohen @ ccs neu edu
garay @ cse tamu edu
vzikas @ inf ed ac uk
2020-02-19: revised
2019-10-15: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ran Cohen and Juan Garay and Vassilis Zikas},
      title = {Broadcast-Optimal Two-Round MPC},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1183},
      year = {2019},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.