Paper 2019/156

Efficient Constructions for Almost-everywhere Secure Computation

Siddhartha Jayanti, Srinivasan Raghuraman, and Nikhil Vyas

Abstract

The importance of efficient MPC in today's world needs no retelling. An obvious barebones requirement to execute protocols for MPC is the ability of parties to communicate with each other. Traditionally, we solve this problem by assuming that every pair of parties in the network share a dedicated secure link that enables reliable message transmission. This assumption is clearly impractical as the number of nodes in the network grows, as it has today. In their seminal work, Dwork, Peleg, Pippenger and Upfal introduced the notion of almost-everywhere secure primitives in an effort to model the reality of large scale global networks and study the impact of limited connectivity on the properties of fundamental fault-tolerant distributed tasks. In this model, the underlying communication network is sparse and hence some nodes may not even be in a position to participate in the protocol (all their neighbors may be corrupt, for instance). A protocol for almost everywhere reliable message transmission, which would guarantee that a large subset of the network can transmit messages to each other reliably, implies a protocol for almost-everywhere agreement where nodes are required to agree on a value despite malicious or byzantine behavior of some subset of nodes, and an almost-everywhere agreement protocol implies a protocol almost-everywhere secure MPC that is unconditionally or information-theoretically secure. The parameters of interest are the degree $d$ of the network, the number $t$ of corrupted nodes that can be tolerated and the number $x$ of nodes that the protocol may give up. Prior work achieves $d = O(1)$ for $t = O(n/\log n)$ and $d = O(\log^{q}n)$ for $t = O(n)$ for some fixed constant $q > 1$. In this work, we first derive message protocols which are efficient with respect to the total number of computations done across the network. We use this result to show an abundance of networks with $d = O(1)$ that are resilient to $t = O(n)$ random corruptions. This randomized result helps us build networks which are resistant to worst-case adversaries. In particular, we improve the state of the art in the almost everywhere reliable message transmission problem in the worst-case adversary model by showing the existence of an abundance of networks that satisfy $d = O(\log n)$ for $t = O(n)$, thus making progress on this question after nearly a decade. Finally, we define a new adversarial model of corruptions that is suitable for networks shared amongst a large group of corporations that: (1) do not trust each other, and (2) may collude, and construct optimal networks achieving $d = O(1)$ for $t = O(n)$ in this model.