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.
Category / Keywords: cryptographic protocols / Secure Computation, Round Complexity, Minimal Setup Date: received 3 Mar 2022 Contact author: ivan at cs au dk, divya at cs au dk, lsiniscalchi at cs au dk, sophia yakoubov at cs au dk Available format(s): PDF | BibTeX Citation Version: 20220307:124011 (All versions of this report) Short URL: ia.cr/2022/293