International Association for Cryptologic Research

International Association
for Cryptologic Research


Broadcast-Optimal Two-Round MPC

Ran Cohen , Northeastern University
Juan Garay , Texas A&M University
Vassilis Zikas , University of Edinburgh and IOHK
DOI: 10.1007/978-3-030-45724-2_28 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2020
Abstract: 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 se- cure 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.
Video from EUROCRYPT 2020
  title={Broadcast-Optimal Two-Round MPC},
  booktitle={39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Zagreb, Croatia, May 10–14, 2020, Proceedings},
  series={Lecture Notes in Computer Science},
  author={Ran Cohen and Juan Garay and Vassilis Zikas},