Rafail Ostrovsky - Publications

Improved Fault Tolerance and Secure Computation on Sparse Networks

Nishanth Chandran, Juan Garay, Rafail Ostrovsky


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 classical Byzantine agreement problem, except 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 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=an, for some constant a> ο(presented in the original paper, over two decades ago) has parameters, d=nε for constant ε > ο and x=mt for some constant μ> 1. In this work, we significantly improve on the above parameters obtaining a protocol with t=an, d=O(logqn), for constant q> οand x=ο(t/log n). 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 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 o8], 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= ο (t/log n) for t ≤ an corruptions, as opposed to x= ο(t) in the original work.

comment: ICALP 2010:249-260

Fetch PDF file of the paper

Back to Publications List