Edge Fault Tolerance on Sparse Networks
Nishanth Chandran, Juan Garay, Rafail Ostrovskly
Abstract:
Byzantine agreement, which requires nprocessors ( nodes) in a completely connected network to agree on a value dependent on their initial values and despite the arbitrary, possible malicious behavior of some of them, is perhaps the most popular paradigm in fault-tolerant distributed systems. However, partially connected networks are far more realistic than fully connected networks, which led Dwork, Peleg, Pippenger and Upfal [STOC’86] to formulate the notion of almost-everywhere (a.e)agreement which shares the same aim with the original problem, except that now not all pairs of nodes are connected by reliable and authenticated channels. In such a setting, agreement amongst all correct nodes cannot be guaranteed due to possible poor connectivity with other correct nodes, and some of them must be given up. The number of such nodes is a function of the underlying communication graph and adversarial set nodes. The proximity-testing problem can be reduced to the private equality testing n(PET) problem, in which parties find out whether or not they hold the same input (drawn from a low-entropy distribution) without revealing any other information about their inputs to each other. While previous works analyze the 2-party PET special case (and its LBS application) in this work we consider highly-efficient schemes for the multiparty case with no honest majority. We provide schemes for both a direct-communication setting and setting with a honest but-curious mediating server that does not learn the user’s inputs. Our most efficient scheme takes 2 rounds where in each round each user sends only a couple of EIGamal ciphertexts.
In this work we introduce the notion of almost everywhere agreement with edge corruptions Which is exactly the same problem as described above, except that we additionally allow the adversary to completely control some of the communication channels between two correct nodes i.e. STO ″corrupt″ edges in the network. While it is easy to see that an a.e. agreement protocol for the original node-corruption model is also an a.e. (agreement protocol tolerating edge corruptions (albeit for a reuced fraction of edge corruptions which respect to the bound for node corruptions), no polynomial-time protocol is known in the case where a constant fraction of the edges can be corrupted and the degree of the network is sub-linear.
We make progress on this front, by constructing graphs of degree O(N ε) (for arbitrary constant o< ε <1). on which we can run a.e. agreement protocols tolerating a constant fraction of adversarial edges. The number of given-up nodes in our construction is μn (for some constant o< μ< 1 that depends on the fraction of corrupted edges), which is asymptotically optimal. We remark that allowing an adversary to corrupt edges in the network can be seen as taking a step closer towards guaranteeing a.e. agreement almost honest nodes even on adversarially chosen communication networks, as opposed to earlier results where the communication graph is specially constructed.
In addition, building upon the work of Garay and Ostrovsky [Eurocrypt′08] we obtain a protocol for a.e. secure computation tolerating edge corruptions on the above graphs.
comment: ICALP 2012 PP:452-463
Fetch PDF file of the paper
| Back to Publications List |