Broadcast-Optimal Two Round MPC with an Honest Majority

This paper closes the question of the possibility of two-round MPC protocols achieving different security guarantees with and without the availability of broadcast in any given round. Cohen et al. [CGZ20] study this question in the dishonest majority setting; we complete the picture by studying the honest majority setting.

In the honest majority setting, given broadcast in both rounds, it is known that the strongest guarantee—guaranteed output delivery—is achievable [GLS15]. We show that, given broadcast in the first round only, guaranteed output delivery is still achievable. Given broadcast in the second round only, we give a new construction that achieves identifiable abort, and we show that fairness—and thus guaranteed output delivery—are not achievable in this setting. Finally, if only peer-to-peer channels are available, we show that the weakest guarantee—selective abort—is the only one achievable for corruption thresholds t>1 and for t=1 and n=3 . On the other hand, it is already known that selective abort can be achieved in these cases. In the remaining cases, i.e., t=1 and n≥4 , it is known [IKP10, IKKP15] that guaranteed output delivery (and thus all weaker guarantees) are possible.