Paper 2022/293

Minimizing Setup in Broadcast-Optimal Two Round MPC

Ivan Damgård and Divya Ravi and Luisa Siniscalchi and Sophia Yakoubov

Abstract

In this paper we consider two-round secure computation protocols which use different communication channels in different rounds: namely, protocols where broadcast is available in neither round, both rounds, only the first round, or only the second round. The prior works of Cohen, Garay and Zikas (Eurocrypt 2020) and Damgård, Magri, Ravi, Siniscalchi and Yakoubov (Crypto 2021) give tight characterizations of which security guarantees are achievable for various thresholds in each of the communication structures. In this paper, we determine what is possible in the honest majority setting without a PKI, closing a question left open by Damgård et al. We show that without a PKI, having an honest majority does not make it possible to achieve stronger security guarantees compared to the dishonest majority setting. However, if two thirds of the parties are guaranteed to be honest, identifiable abort is additionally achievable using broadcast only in the second round. We use fundamentally different techniques from the previous works in order to avoid relying on private communication in the first round when a PKI is not available, since assuming such private channels without the availability of public encryption keys is unrealistic. We also show that, somewhat surprisingly, the availability of private channels in the first round does not enable stronger security guarantees unless the corruption threshold is one. In that case, prior work has shown that with private channels in the first round, guaranteed output delivery is always achievable; we show that without these channels, fairness is unachievable even with broadcast in both rounds, and unanimous abort is unachievable without broadcast in the second round.