View all Seminars  |  Download ICal for this event

On the Round Complexity Landscape of Secure Multi-party Computation

Series: Ph.D (Engg.)Thesis Defence -ON-LINE

Speaker: Ms. Divya Ravi

Date/Time: Jan 15 15:00:00

Location: Microsoft Teams - ON-LINE

Faculty Advisor: Dr. Arpita Patra

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:
MPC for small population ([1,2]). 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, unanimous abort, fairness and guaranteed output delivery. 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.
Beyond Traditional Adversaries ([3,4]). 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, Common reference String model (CRS) and PKI model.
Second, we overcome the demarcation of study of round complexity of MPC based on single type of corruption i.e either purely passive or active. 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 CRS model.
Power of Hybrid Networks ([5]). A popular categorization of study of MPC based on network is the synchronous and asynchronous setting. On one hand, asynchronous networks are more realistic but on the other, synchronous protocols 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 to achieve the properties of the fully synchronous protocols. We bridge the existing theoretical feasibility gap between perfectly-secure synchronous and asynchronous VSS and MPC protocols; where verifiable secret sharing (VSS) constitutes a fundamental building block of MPC.
[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.

Microsoft Teams Link:

Speaker Bio:

Host Faculty: