Cryptology ePrint Archive: Report 2019/1183

Broadcast-Optimal Two-Round MPC

Ran Cohen and Juan Garay and Vassilis Zikas

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 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.

Category / Keywords: cryptographic protocols / two-round MPC, identifiable abort, unanimous abort, selective abort, broadcast

Original Publication (with major differences): IACR-EUROCRYPT-2020

Date: received 10 Oct 2019, last revised 19 Feb 2020

Contact author: rancohen at ccs neu edu, garay at cse tamu edu, vzikas at inf ed ac uk

Available format(s): PDF | BibTeX Citation

Version: 20200219:143146 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]