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...