Improved Fault Tolerance and Secure Computation on Sparse Networks

In the problem of almost-everywhere agreement (denoted a.e. agreement), introduced by Dwork, Peleg, Pippenger, and Upfal [STOC ’86], n parties want to reach agreement on an initially held value, despite the possible disruptive and malicious behavior of up to t of them. So far this is reminiscent of the classical Byzantine agreement problem, except that in the alternative formulation the underlying connectivity graph is sparse—i.e., not all parties share point-to-point reliable channels—thus modeling the actual connectivity of real communication networks. In this setting, one may not be able to guarantee agreement amongst all honest parties, and some of them, say x, must be given up. Thus, in this line of work the goal is to be able to tolerate a high value for t (a constant fraction of n is the best possible) while minimizing x. As shown in the original paper, the dependency on d, the degree of the network, to achieve this goal is paramount.

Indeed, the best polynomial-time a.e. agreement protocol tolerating a constant fraction of corruptions t = αn, for some constant α> 0 (presented in the original paper, over two decades ago) has parameters, d = n ^ε for constant ε> 0 and x = μt for some constant μ> 1. In this work, we significantly improve on the above parameters obtaining a protocol with t = αn, d=O(logq⁡n)">d=O(logqn), for constant q > 0 and x=O(tlog⁡n)">x=O(tlogn). Our approach follows that of Dwork et al. of reducing the a.e. agreement problem to constructing a reliable transmission scheme between pairs of nodes for a large fraction of them; however, given our setting’s more stringent conditions—poly-logarithmic degree and a linear number of corruptions, such a task is significantly harder.

We also consider the problem of secure computation on partially connected networks, as formulated by Garay and Ostrovsky [Eurocrypt ’08], and as a corollary to our main result obtain an almost-everywhere secure multi-party computation protocol with the same parameters as above, again significantly improving on the bound on the number of left-out parties—x=O(tlog⁡n)">x=O (tlogn)  for t ≤ αn corruptions, as opposed to x=O(t)">x=O(t) in the original work.