#### Paper 2019/1183

Ran Cohen, 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.

Available format(s)
Category
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2020
Keywords
Contact author(s)
rancohen @ ccs neu edu
garay @ cse tamu edu
vzikas @ inf ed ac uk
History
2020-02-19: revised
See all versions
Short URL
https://ia.cr/2019/1183

CC BY

BibTeX

@misc{cryptoeprint:2019/1183,
author = {Ran Cohen and Juan Garay and Vassilis Zikas},