Paper 2020/1254

Broadcast-Optimal Two Round MPC with an Honest Majority

Ivan Damgård, Bernardo Magri, Divya Ravi, Luisa Siniscalchi, and Sophia Yakoubov


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. (Eurocrypt 2020) 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 (Gordon et al. Crypto 2015). 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 > 3$, it is known (from the work of Ishai et al. at Crypto 2010, and Ishai et al. at Crypto 2015) that guaranteed output delivery (and thus all weaker guarantees) are possible.

Available format(s)
Publication info
Preprint. MINOR revision.
MPCtwo-round MPChonest majoritybroadcast
Contact author(s)
ivan @ cs au dk
magri @ cs au dk
divya @ cs au dk
lsiniscalchi @ cs au dk
sophia yakoubov @ gmail com
2021-06-11: last of 2 revisions
2020-10-14: received
See all versions
Short URL
Creative Commons Attribution


      author = {Ivan Damgård and Bernardo Magri and Divya Ravi and Luisa Siniscalchi and Sophia Yakoubov},
      title = {Broadcast-Optimal Two Round MPC with an Honest Majority},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1254},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.