Paper 2020/1254

Broadcast-Optimal Two Round MPC with an Honest Majority

Ivan Damgård and Bernardo Magri and Luisa Siniscalchi and Sophia Yakoubov

Abstract

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 in this setting, given broadcast in the first round only, guaranteed output delivery is still achievable. Given broadcast in the second round only, identifiable abort and all weaker guarantees are achievable, but fairness — and thus guaranteed output delivery — are not. Finally, using only peer-to-peer channels, for corruption thresholds $t > 1$ we show that the weakest guarantee — selective abort — is the only one achievable. For $t = 1$ and $n \geq 4$, it is known [IKP10,IKKP15] that guaranteed output delivery (and thus all weaker guarantees) are possible. We show that for $t = 1$ and $n = 3$ the strongest achievable guarantee is selective abort, resolving the question of best achievable guarantees in two-round secure computation protocols.