On the Round Complexity Landscape of Secure Multi-party Computation

Abstract

In secure multi-party computation (MPC), n parties wish to jointly perform a computation on their private inputs in a secure way, so that no adversary corrupting a subset of the parties can learn more information than their outputs (privacy), nor can they affect the outputs of the computation other than by choosing their own inputs (correctness). The round complexity of MPC protocols is a fundamental question in the area of secure computation and its study constitutes a phenomenal body of work in the MPC literature. The research goal of this thesis is to advance the state of the art by expanding this study of round complexity to various adversarial settings and network models. Following are the main contributions of this thesis organized into three broad categories:

(1) MPC for small population- We begin with the study of round-optimal (more generally, round-efficient) MPC protocols for small population, namely involving 3 (3PC) and 4 (4PC) parties tolerating single active corruption (honest majority). On the theoretical side, we settle the exact round complexity of 3PC in honest-majority setting, for a range of security notions such as selective abort (adversary can selectively deprive some honest parties of the output), unanimous abort (either all or none of the honest parties get the output), fairness (adversary gets output only if honest parties do) and guaranteed output delivery (adversary cannot prevent honest parties from obtaining the output). On the practical side, we present efficient, constant-round 3PC and 4PC protocols with fairness and guaranteed output delivery; suitable for high-latency networks such as the Internet. This work is based on [1, 2].

(2) Beyond Traditional Adversaries - We extend the study of round complexity beyond the traditional adversarial settings. First, we overcome the demarcation of study of round complexity of MPC based on resilience (i.e. honest majority or dishonest majority settings) and investigate an interesting class of protocols called the Best-of-both-Worlds (BoBW) MPC which simultaneously achieve fairness / guaranteed output delivery in honest majority and unanimous abort in dishonest majority. We nearly settle the question of exact round complexity of BoBW protocols for several popular setups of MPC such as the plain model, public setup and private setup. This work is based on [3].

Second, we overcome the demarcation of study of round complexity of MPC based on single type of corruption i.e. either purely passive (adversary follows the protocol steps but tries to learn more information) or active (adversary is allowed to deviate from the protocol in any arbitrary way). We consider a generalized adversarial setting where the adversary can simultaneously perform both kinds of corruptions. We settle the question of exact round complexity of MPC protocols achieving fairness and guaranteed output delivery against two such generalized and powerful adversaries called the dynamic and boundary adversaries; in the public setup model. These results appear in [4].

(3) Power of Hybrid Networks - A popular categorization of study of MPC based on network is the synchronous and asynchronous setting. On one hand, asynchronous networks (channels are allowed to have arbitrary delays) are more realistic but on the other, synchronous protocols (channels have bounded delay) are known to have better fault tolerance and properties compared to their asynchronous counterparts. With the goal of combining their best features, we explore hybrid networks that is asynchronous in nature and yet supports a few synchronous rounds at the onset of a protocol execution.

We address fundamental questions that throw light on the minimal synchrony assumption needed (in terms of the number of initial synchronous rounds in the hybrid network) to achieve the properties of the fully synchronous protocols. We bridge the existing theoretical feasibility gap between perfectly-secure (tolerate unbounded adversaries with no error) synchronous and asynchronous VSS and MPC protocols; where verifiable secret sharing (VSS) constitutes a fundamental building block of MPC. These results appear in [5].

References: [1] Arpita Patra and Divya Ravi. On the exact round complexity of secure three-party computation. In CRYPTO, 2018.

[2] Megha Byali, Arun Joseph, Arpita Patra, and Divya Ravi. Fast secure computation for small population over the internet. In ACM Conference of Computer and Communications Security (CCS), 2018.

[3] Arpita Patra, Divya Ravi and Swati Singla. On the Exact Round Complexity of Best-of-both-Worlds Multi-party Computation. In ASIACRYPT, 2020.

[4] Arpita Patra and Divya Ravi. Beyond honest majority: The round complexity of fair and robust multi-party computation. In ASIACRYPT, 2019.

[5] Arpita Patra and Divya Ravi. On the power of hybrid networks in multi-party computation. IEEE Trans. Inf. Theory, 64(6):4207–4227, 2018.