Cryptology ePrint Archive: Report 2021/690

On Communication Models and Best-Achievable Security in Two-Round MPC

Aarushi Goel and Abhishek Jain and Manoj Prabhakaran and Rajeev Raghunath

Abstract: Recently, a sequence of works have made strong advances in two-round (i.e., round-optimal) secure multi-party computation (MPC). In the honest-majority setting -- the focus of this work -- Ananth et al. [CRYPTO'18, EC'19], Applebaum et al. [TCC'18, EC'19] and Garg et al. [TCC'18] have established the feasibility of general two-round MPC in standard communication models involving broadcast (BC) and private point-to-point (P2P) channels.

In this work, we set out to understand what features of the communication model are necessary for these results, and more broadly the design of two-round MPC. Focusing our study on the plain model -- the most natural model for honest-majority MPC -- we obtain the following results:

1. Dishonest majority from Honest majority: In the two round setting, honest-majority MPC and dishonest-majority MPC are surprisingly close, and often equivalent. This follows from our results that the former implies 2-message oblivious transfer, in many settings. (i) We show that without private point-to-point (P2P) channels, i.e., when we use only broadcast (BC) channels, honest-majority MPC implies 2-message oblivious transfer. (ii) Furthermore, this implication holds even when we use both P2P and BC, provided that the MPC protocol is robust against ``fail-stop'' adversaries.

2. The curious case of Identifiable Abort: While security with guaranteed output delivery (and even fairness) against malicious adversaries is impossible in two rounds, nothing is known with regards to the ``next best'' security notion, namely, security with identifiable abort (IA). We show that IA is impossible to achieve with honest-majority even if we use both P2P and BC channels. However, surprisingly, this lower bound can be overcome by replacing P2P channels with a ``bare'' (i.e., untrusted) public-key infrastructure (PKI).

These results ``explain'' that the reliance on P2P channels (together with BC) in the recent two-round protocols was in fact necessary, and that these protocols couldn't have achieved a stronger security guarantee, namely, IA. Overall, our results (put together with prior works) fully determine the best-achievable security for honest-majority MPC in different communication models in two rounds. As a consequence, they yield the following hierarchy of communication models:

BC < PTP < BC+PTP < BC+PKI

This shows that contrary to common perception, BC channel is the weakest communication model, and that a bare PKI setup is strictly stronger than P2P channels.

Category / Keywords: foundations / Secure multiparty computation, Two rounds, Communication channels, oblivious transfer

Date: received 25 May 2021, last revised 25 May 2021

Contact author: aarushig at cs jhu edu, abhishek at cs jhu edu, mp at cse iitb ac in, mrrajeev at cse iitb ac in

Available format(s): PDF | BibTeX Citation

Version: 20210528:091139 (All versions of this report)

Short URL: ia.cr/2021/690


[ Cryptology ePrint archive ]