Advancing the Communication Complexity Landscape of Perfectly Secure Multiparty Computation

Abstract

Secure multiparty computation (MPC) allows n distrustful parties to jointly compute a function on their inputs while keeping their inputs private. The distrust is modelled as an adversary that controls up to t parties and coordinates their behaviour. Various settings of secure computation have been considered in the literature depending on factors such as the adversarial power and the allowed probability of error in computation. The feasibility and communication complexity of secure computation have been extensively studied for each of these settings and constitute a vast literature in the area.

The work in this thesis aims to advance the research in secure computation for the most demanding setting of perfect security. Perfect security means that the adversary is all-powerful; that is, the protocol cannot rely on any computational assumptions and has zero probability of error. Such protocols come with desirable properties of unconditional, quantum, and everlasting security. The contributions of this thesis toward advancing the landscape of perfectly-secure multiparty computation in various network settings are abstracted below. While the first three works focus on communication efficiency, the concluding results establish the feasibility of MPC.

(1) Perfectly-Secure Broadcast in the Synchronous Network Model:

Our first work targets the primitive of broadcast, which is essential for secure computation. We focus on optimal resilience with no setup or cryptographic assumptions in the synchronous network setting. While broadcast with worst-case t rounds is impossible, it has been shown how to construct protocols with an expected constant number of rounds in the private channel model. However, those constructions have large communication complexity, which leads to a significant communication blowup in secure computation protocols in this setting. We substantially improve the communication complexity of broadcast in constant expected time. We also consider parallel broadcast, where n parties wish to broadcast L-bit messages in parallel. Our protocol has no asymptotic overhead for a typical communication pattern in perfectly secure MPC protocols, which is also the case in our subsequent work.

(2) Perfectly-Secure MPC in the Synchronous Network Model:

Subsequently, we study secure multiparty computation in the synchronous network setting with perfect security and optimal resilience. There are two families of protocols in this setting: (a) Efficient but slow: These protocols have O(n.logn) communication complexity per multiplication gate, but the running time of these protocols is Omega(n+D) rounds for a circuit with depth D, and (b) Fast but not efficient: This line of protocols run at O(D) expected number of rounds, but require Omega(n^4.logn) communication complexity per multiplication gate. We show that it is possible to achieve the best of both families simultaneously. We design a perfectly-secure, optimally-resilient, secure MPC protocol with O(n.logn) communication complexity per multiplication gate, which runs in O(D) expected rounds.

(3) Perfectly-Secure MPC in the Asynchronous Network Model:

Linear communication overhead forms a natural barrier for general secret-sharing-based MPC protocols. Having matched it in the synchronous network setting, we focus on studying secure multiparty computation in the asynchronous setting with perfect security and optimal resilience. Despite 30 years of research, all protocols in the asynchronous setting require Omega(n^2.logn) communication complexity per multiplication gate. In contrast, for nearly 15 years, it has been known how to achieve O(n.logn) communication complexity in the synchronous setting, albeit with Omega(n+D) rounds prior to our work. The techniques for achieving this result in the synchronous setting are not known to be sufficient for obtaining an analogous result in the asynchronous setting. We close this gap between synchronous and asynchronous secure computation and show the first asynchronous protocol with O(n.logn) communication complexity per multiplication gate that has O(D) expected runtime.

(4) Perfectly-Secure MPC in the Network-agnostic Model:

In a concluding work, deviating from the monolithic view of the network, we study the feasibility of network-agnostic secure multiparty computation with perfect security. While traditionally, MPC is studied by assuming the underlying network is either synchronous or asynchronous, the parties are unaware of the network type in a network-agnostic setting. The feasibility of perfectly-secure MPC based on the corruption threshold in synchronous and asynchronous networks was settled long ago. However, the same question has remained open for the network-agnostic setting. The previous work in this area conjectures a bound of n > 3t_s + t_a for an adversary that can corrupt t_s parties in a synchronous network and t_a parties in an asynchronous network. While they show its sufficiency by constructing a protocol, the question of its necessity remained open. In our work, we resolve this long-standing question and show that perfectly-secure network-agnostic MPC is possible if and only if n > 2 max(t_s,t_a) + max(2t_a,t_s).