key: cord-0061118-z9jmmfdb
authors: Jayanti, Siddhartha; Raghuraman, Srinivasan; Vyas, Nikhil
title: Efficient Constructions for Almost-Everywhere Secure Computation
date: 2020-03-25
journal: Advances in Cryptology - EUROCRYPT 2020
DOI: 10.1007/978-3-030-45724-2_6
sha: 38128686f36d7176f7a845cf7b3bad482730279e
doc_id: 61118
cord_uid: z9jmmfdb

We study the problem of almost-everywhere reliable message transmission; a key component in designing efficient and secure Multi-party Computation (MPC) protocols for sparsely connected networks. The goal is to design low-degree networks which allow a large fraction of honest nodes to communicate reliably even when a small constant fraction of nodes experience byzantine corruption and deviate arbitrarily from the assigned protocol. In this paper, we achieve a [Formula: see text] -degree network with a polylogarithmic work complexity protocol, thereby improving over the state-of-the-art result of Chandran et al. A work efficient version of Dwork et al.’s (STOC 1986) butterfly network. An improvement upon the state of the art protocol of Ben-or and Ron (Information Processing Letters 1996) in the randomized corruption model—both in work-efficiency and in resilience.

Many real world applications involve computing functions on large data sets that are distributed across machines in a global network. For instance, hospitals across the world have confidential patient data that can be used to create accurate disease models and improve treatment plans. Data held by any particular agent may need to be kept private. The ubiquitous need for such distributed private computations has motivated research on efficient multiparty computation (MPC) [2, 9, 14, 22] . MPC protocols enable a set of parties to compute a joint function on their inputs while keeping them private [6] . MPC protocols for various important tasks, such as elections, were discovered in the twentieth century, but most of these protocols have not seen practical application as they were designed for densely connected networks. For MPC to see widespread use, it is important for protocols to rely only on the sparse connectivity that is available in modern large scale networks while simultaneously meeting the efficiency needs of practice. In this paper, we focus on designing sparse networks, and secure communication protocols for these networks that are resilient to large fractions of the machines being hacked, and thereby deviating arbitrarily from the assigned protocols.

All secure distributed protocols rely on the ability of machines to communicate. In particular, if A and B are two nodes in a network, A must be able to send a message to B in a way that satisfies the following two properties: (1) reliable transmission: B receives the message that A intended to send, and (2) authentication: B must be able to confirm that A was indeed the sender of the received message [1] . The first-reliable transmission-is the focus of our paper. Reliable transmission becomes trivial if we assume every pair of nodes has a dedicated secure link to pass messages over. However, it is impractical to create pairwise secure links in modern large scale networks-a network on even just a thousand nodes would need half a million secure links! In a seminal work, Dwork et al. [12] considered the question of designing sparse networks that are tolerant to nodes experiencing byzantine failuresnodes that fail can deviate arbitrarily from the protocol. The problem is to design a network G of degree d on n nodes in which honest nodes can continue to communicate and execute protocols, even after t nodes are corrupted, i.e., experience byzantine failures. The challenge is to make the degree d as small as possible (ideally constant), even while allowing up to t = εn corruptions for some constant ε. Since we allow many more corruptions, t, than the degree of the graph, d, any set of Ω(t/d) honest nodes can be isolated from the other nodes if all of their neighbors are corrupted. Thereby, it is impossible for all the honest nodes to communicate with each other in this failure model. So, Dwork et al. allow x honest nodes to become doomed, and only require that a set of n − t − x honest nodes be able to pairwise communicate with each other after t corruptions occur. This set of honest nodes are called privileged nodes, and the class of primitives that work on these privileged nodes in the presence of byzantine failures are called almost-everywhere (AE) primitives. Our paper's main result, is the design of a new sparse graph and a corresponding communication protocol that improve the state of the art in AE reliable message transmission.

Our protocol for AE reliable message transmission immediately implies an improved protocol for AE Secure Multi-party Computation (MPC) in the following way. The problem of byzantine agreement [18, 20] is one where nodes start with an initial value but wish to agree, at the end of execution of some protocol, on some value, despite malicious or byzantine behavior of some subset of nodes. Prior to [12] , this problem was considered assuming all pairs of nodes had a secure link for communication [10, 18, 20] . Dwork et al. introduced the notion of almost-everywhere agreement where only privileged nodes need to reach agreement. We note that AE reliable message transmission, which would guarantee that a large subset of the network can transmit messages to each other reliably, implies a protocol for AE agreement, and an AE agreement protocol implies a protocol for AE secure MPC that is unconditionally or information-theoretically secure as formulated in the work of Garay and Ostrovsky [13] .

AE reliable transmission protocols are generally compared by the following three properties:

1. degree: the degree, d, of graph of secure links needed for the protocol. 2. resilience: a protocol is (f (n), g(t))-resilient if it can sustain up to t = f (n) corruptions while dooming at most x = g(t) nodes when t nodes are corrupted. 3. work complexity: the total amount of work (both local and message passing) required for a single communication from node u to node v in the network.

The ideal solution would give a protocol on a constant degree graph that is (εn, O(t))-resilient for a small constant ε ∈ (0, 1), and have low work complexity. This ideal remains an open problem. In the remainder of this section, we discuss the three previous results which are mutually incomparable, and thereby, jointly form the state-of-the-art for the AE reliable transmission problem. We remark that ε continues to be used in resilience guarantees throughout the paper, and it simply represents some constant in (0, 1) when it appears. Dwork et al.'s seminal work introduced the AE reliable transmission problem, and gave the first solution to the problem [12] . Their famous Butterfly network is a constant degree graph and their protocol is (εn/ log n, O(t))-resilient, and has linear work complexity. While the Butterfly network is a simple network and Dwork et al.'s protocol, the possibility of increasing the resilience of the network to be resistant to a linear number of corruptions spurred further research into the AE reliable transmission.

Upfal showed the remarkable result that both optimal graph degree and optimal resilience were simultaneously possible [21] . He produced a constant degree graph and a protocol that is (εn, O(t))-resilient on that graph. While these advantages make Upfal's work of great information theoretic importance, his protocol is practically intractable, since it requires nodes to do an exponential amount of computation. In particular, when a node u is sending a message to a node v, Upfal's algorithm requires v to loop through all possible subsets of corrupted nodes before it can correctly decipher the message it has received (even when u and v are both privileged). Thus, the work complexity of Upfal's algorithm is the exponential O n t . The third work at the frontier of the field was Chandran et al.'s protocol. This work tries to combine the work efficiency of Dwork et al.'s protocol with the resiliency of Upfal's work. Chandran et al. succeed in getting a linear work protocol, and in fact achieve the very strong property of (εn, O(t/ log n))-resilience. However, the significant weakness of their work is the complexity and degree of their graph. Unlike the other two works, their protocol is designed for a graph of polylogarithmic-degree.

In summary, the state-of-the-art on the AE reliable transmission problem consisted of three incomparable results: Dwork et al.'s linear work protocol with low resiliency on a constant degree graph, Upfal's exponential work protocol with high resiliency on a constant degree graph, and Chandran et al.'s linear work protocol with high resiliency on a polylogarithmic degree graph.

The primary contribution of our paper is an AE reliable transmission protocol on a graph of logarithmic degree that is (εn, O(t/ log n))-resilient while requiring only polylogarithmic work per communication. The significance of our result lies in the low degree of the graph and the work-efficiency of the protocol. Our result is a strict improvement over Chandran et al.'s result, as our graph's degree is smaller-only logarithmic, compared to polylogarithmic-and our protocol's work complexity is polylogarithmic as opposed to linear, while our protocol's resiliency is the same as their protocol's. Also, our protocol is the first AE reliable transmission protocol to achieve sublinear work complexity. In particular, the small work complexity of our message-passing protocol enables us to simulate any protocol on a (dense) complete graph with only polylogarithmic multiplicative overhead on our nearly-sparse logarithmic degree graph, while all previous protocols required at least linear multiplicative overhead. The primary result of our paper is stated as Theorem 1 below.

For sufficiently large n, there exists an n-node network G wc = (V, E), a protocol Π wc,ef f for message transmission on it, and constants α and β, such that:

Remark 1. The protocoled-network (G wc , Π wc,ef f ) of Theorem 1 is efficiently constructible in the following sense. In the paper, we give an efficient probabilistic construction that takes the number of nodes n and outputs a protocolednetwork satisfying the conditions of the theorem with all but exponentially small probability. However, we do not know how to efficiently verify that the obtained construction indeed satisfies the conditions of the theorem.

We compare our work to previous works in Table 1 . A secondary contribution of our work is an improvement over the state of the art in AE reliable transmission when the adversary corrupts nodes at random. Ben-or and Ron [3] introduced the random corruption model in which nodes are corrupted independently and at random and the protocol only needs to be resilient with some large probability, called the probability of resiliency. So, algorithms in this model are evaluated by four parameters: degree, resiliency, work complexity, and probability of resiliency. (If the probability of resiliency becomes equal to one, then the protocol is resilient in the standard model.) Ben-or and Ron exhibited a constant degree network that is (εn, O(t))-resilient with high probability, and thereby almost resolved the random corruption model [3] . En route to our main construction, we produce a different constant degree network that has the same (εn, O(t))-resilience, just with even higher probability than Ben-or and Ron's construction. Interestingly, the improvement in probability that we attain for the random corruption model drives our ability to get such a low degree graph in the standard model of corruption.

In this section, we describe the main ideas in the paper and how they fit together to build our main result.

At a high level, our AE transmission protocol is constructed in two parts: the first part yields a network and protocol that have the (εn, O(t/ log n))-resilience and logarithmic-degree; this immediately yields an improvement over Chandran et al.'s protocol, which has the same resiliency but polylogarithmic degree. Our construction in the first part, uses the protocol of Dwork et al. on the Butterfly Network as a black box.

In the second part, we improve this communication protocol significantlyreducing the linear work to only polylogarithmic work, while maintaining the resiliency parameters. Modularly replacing the Dwork et al. protocol with the new efficient protocol immediately yields our main theorem: a logarithmic degree graph and a polylogarithmic work protocol with (εn, O(t/ log n))-resilience.

Better Resilience. We achieve a highly resilient graph with low degree in two steps. In the first step, we combine the ideas of Dwork et al. and Upfal to construct a constant degree graph that is resilient to a linear number of corruptions with high probability in the random corruption model. Upfal constructed an exponential work protocol Π Upfal on a constant degree expander graph G Upfal . We notice that while Upfal's protocol is too slow to be run on a full sized graph of n nodes, it can be run on committees of sub-logarithmic size, and thereby split the n nodes into disjoint committees of size O(log log n) each. In order for nodes in one committees to communicate with nodes in other committees, we view the individual committees as super-nodes, and connect these super-nodes through the butterfly network, G But , of Dwork et al. An important theorem we prove at the end of this step shows that this construction (which we fully specify in Sect. 3) along with a carefully constructed protocol gives high resilience in the random corruption model with high probability.

For sufficiently large n, there exists an n-node network G rand = (V, E), a protocol Π rand for message transmission on it, and constants α 3 and β 3 , such that:

1. The network G rand is of constant degree. 2. If a subset of nodes T ⊂ V is randomly corrupt, where |T | ≤ α 3 n, with probability 1 − (t/n) α2t/(4 log(n)) , there exists a set of nodes S ⊂ V where |S| ≥ n − β 3 |T | such that every pair of nodes in S can communicate reliably with each other by invoking Π rand .

In the second step, we strengthen the graph from the first step by adding multiple (perturbed) copies of the edges to it and modify the protocol to get a graph that is resilient to linearly many worst-case corruptions. In particular, let G i rand = (V, E i ) be graphs of the type constructed in the first step where the vertex labels are permuted randomly and independently for each 1 ≤ i ≤ f (n) for some f (n) = O(log n). Our graph in the second step is the union of all of these graphs, i.e., G wc = V,

Since O(log n) different edge sets are combined to form this graph, the degree of the graph goes up to O(log n). However, the graph now has very high probability of being resilient to linearly many worst-case corruptions. Intuitively, this resilience is built from the fact that the protocol from the first step can be executed independently on each set of edges E i , and it suffices if a majority of these protocols succeed. Since there is some probability of success, i.e. that the random graph G wc is indeed resilient to linearly many worst-case corruptions, the probabilistic method yields Theorem 3 (stated below) which strictly improves over the construction of Chandran et al.

For sufficiently large n, there exists an n-node network G wc = (V, E), a protocol Π wc for message transmission on it, and constants α 4 and β 4 , such that:

Better Efficiency. Our protocols for network resiliency used the G But and Dwork et al.'s protocol designed for the graph as primitives. In this part of the paper we design a communication protocol on the Butterfly Network that is more work-efficient than Dwork et al.'s protocol. A communication from node u to node v in Dwork et al.'s protocol floods many paths between u and v in G But with the message and makes v take the majority of the messages it receives to decipher the true message reliably. In this step of our work, we show that if paths are chosen correctly, it suffices to use only polylogarithmically many paths per pair of nodes. Once again, our result goes through the probabilistic method to show that such paths exist.

Ef f for message transmission on it such that the following holds: 1. The network G But has degree 11.

Getting Efficient and Resilient Networks. Modularly substituting the more efficient protocol on the Butterfly graph from the second part for Dwork et al.'s protocol in the highly resilient network from the first part yields the main result of our paper:

Reminder of Theorem 1. For sufficiently large n, there exists an n-node network G wc = (V, E), a protocol Π wc,ef f for message transmission on it, and constants α and β, such that:

There have been a plethora of works asking for various different measures of quality of an agreement or MPC protocol. A sequence of works seek to improve the round complexity of protocols for byzantine consensus [4, 5] . Another goal is to optimize the communication complexity of byzantine agreement protocols [11, [15] [16] [17] . Another model of corruptions is that of edge corruptions [8] . As observed in the work of Chandran et al., an almost-everywhere secure computation protocol for node corruptions can be readily transformed into a corresponding almost-everywhere protocol also tolerating edge corruptions, for a reduced fraction of edge corruptions (by a factor of d, the degree of the network). We note that all our results hence also extend to the edge corruption model, both worst-case and random.

We discuss preliminary notation and definitions in Sect. 2. Next, we describe our network for the randomized corruption model in Sect. 3. We describe our solution in the face of worst-case corruptions in Sect. 4. Our polylogarithmic efficiency protocol on the Butterfly Network is specified in Sect. 5, and our main result which combines resiliency in the face of worst-case corruptions with work efficiency is described in Sect. 5.

For n ∈ N, let [n] = {1, 2, . . . , n}. We assume that all logarithms are taken to the base 2.

Chernoff bound. Let X be a random variable with

Stirling's approximation. For any n, t ∈ N with t ≤ n,

Constructions of expanders of constant degree are known [19] .

Given a graph G = (V, E), a message transmission protocol or simply protocol Π on the graph, is a specification for how messages are routed between every pair of nodes. In particular, Π(u, v) is the protocol for node u ∈ V to transmit to node v ∈ V . A protocol is comprised of discrete synchronous rounds. In each round, we allow each node w ∈ V to perform local computations and pass a different one bit message to each of its neighbors in G.

We call a pair N = (G, Π) a protocoled-network (or simply a network) if Π is a protocol for graph G. We define the following properties of the network, where u and v are two different nodes in G:

1. Work complexity, or, Total work: The total work of Π(u, v) is the number computations, W (u, v), performed across all processors in the network in a transmission from u to v. The total work of Π is

x privileged nodes that can reliably transmit messages between each other, after the nodes in T experience byzantine failure. Nodes in set S are called privileged, nodes in X = V − (S ∪ T ) are called doomed, and nodes in X ∪ T are called unprivileged. We say a network is (f (n), g(t))-resilient if it can sustain an arbitrary set of up to t ≤ f (n) corruptions while dooming at most x = g(t) nodes. When corruptions are randomized (see Sect. 2.7), we say that a network is (f (n), g(t))-resilient with probability p, if it can sustain a random subset of up to t ≤ f (n) corruptions, and at most x = g(t) nodes get doomed with probability at least p. Informally speaking, a network is highly resilient if f (n) is large while g(t) is not too large, and thus the set of privileged nodes is large.

Our goal is to design a highly resilient low degree network of low work complexity.

The notion of almost-everywhere secure primitives was introduced by Dwork et al. [12] . In this setting, we consider a sparse communication network on the nodes. We assume a synchronous network and that the communication is divided into rounds. In every round, each node can send (possibly different) messages on its incident edges; these messages are delivered before the next round. Suppose a certain subset of the nodes may be adversarially corrupt, in particular adaptive, rushing and computationally unbounded. This implies that a protocol for any task on this network must "give up" a certain number of honest nodes on account of their poor connectivity to other honest nodes. We set up the following notation. Consider a network of n nodes connected by a communication network

On executing a protocol Π on this network in the presence of a subset T ⊂ V of adversarial or corrupt nodes, let X ⊂ V be the set of honest nodes that are given up, or doomed, and let P ⊂ V be the set of honest nodes for whom the protocol requirements of correctness and security hold, or privileged nodes. The nodes that are not privileged are unprivileged nodes. Let |T | = t, |X| = x and |S| = s. We have t + x + s = n.

We present some prior networks for almost-everywhere reliable message transmission that will be useful in our constructions.

Dwork, Peleg, Pippenger, Upfal [12] . Dwork et al. define the butterfly protocol-network.

The butterfly network (G But , Π But ) is as follows. Upfal [21] Theorem 6. For sufficiently large n, there exists an n-node network G Upfal = (V, E), a protocol Π Upfal for message transmission on it, and constants α 2 and β 2 , such that:

We consider two models where a subset T of size t in the n node network can be corrupted.

Worst-case Model. The worst-case model is the strongest of our adversary models. In this model, the subset of T corrupt nodes can be chosen adversarially after the network topology and protocol for communication have been fixed.

Random Model. The randomized adversary model assumes that the t corrupted nodes are chosen uniformly at random from the set of n nodes. We call this model of picking a random subset of size t the Hamming Random Model or corruption. Alternately, a randomized adversary may make each node corrupt with probability t/n; we call this the Shannon model. Basic Chernoff bounds show that the Shannon and Hamming models are equivalent up to a constant factor difference in t with all but exponentially small probability. Thus, we freely switch between the two models in our exposition. While this model of corruption is primarily good for simulating phishing and password guessing attacks, our probabilistic approaches show that it can be the starting point for state of the art protocols against random and worst-case adversaries.

In this section we will build a network that is resistant to linearly many random corruptions with an improved success probability as compared to Ben-or and Ron's work [3] . We turn our attention to the protocol of Chandran et al. [7] . Their protocol builds on the following observation. Consider the protocols of Dwork et al. [12] and Upfal [21] where if node A wishes to communicate with node B, A floods all paths from A to B (possibly of a bounded length) with the message. In Dwork et al. [12] , the parameters are set to ensure that a majority of such paths contain no corrupt nodes (for most pairs of nodes A, B) while Upfal [21] employs an exhaustive search to determine which paths may have contained corrupt nodes. These protocols face the disadvantage that paths that pass through even one corrupt node are lost. The work of Chandran et al. [7] introduced the idea of local correction through the use of Bracha committees. If we were able to create committees that had the ability to locally correct the message transmission, we can potentially tolerate a lot more corruptions than in Dwork et al. [12] and perform the final decoding more efficiently than in Upfal [21] . Chandran et al. [7] however considers many overlapping committees in order to ensure that even if a constant fraction of the nodes are corrupt, a sub-constant fraction of the committees are corrupt, where a committee is considered corrupt if a certain fraction of its nodes is corrupt. This calls for a larger degree. We show in this section that in our model of random corruptions, it suffices to construct fewer committees to achieve the same goal. Going forward, we refer to the networks (protocol, resp.) of Upfal [21] by G Upfal (Π Upfal resp.) respectively.

Let the set of nodes that wish to communicate be V = [n] for n ∈ N. We arbitrarily divide the nodes of V into n/s committees of size s = (2/α 2 ) log log n where α 2 is from Theorem 6. Within each committee, we instantiate G Upfal , which is an expander of constant degree d = O (1) . We then connect the n/s committees using the network G But from Theorem 5, where in order to connect two committees, we connect them by means of a perfect matching between the two sets of s nodes.

. The edge set is as follows. Arbitrarily partition the nodes of V into n/s committees of size s = (2/α 2 ) log log n. We let C v denote the committee containing node v, where C u = C v if u and v are in the same committee. Within each committee, we instantiate G Upfal , which is an expander of constant degree d = O (1) . We then connect the n/s committees using the network G But , where in order to connect two committees, we connect them by means of a perfect matching between the two sets of s nodes. Protocol: We now describe the communication protocol Π rand over this network. To this end, we first describe two building block protocols Π edge and Π maj .

-Π edge is the protocol that is invoked when we wish to send a message from one committee, C to another C that are connected in the G But network (connected by means of a perfect matching). We will assume that each node in C is initialized with some message. In the protocol Π edge , each node in C sends its message to the node it is matched to in C . -Π maj is a majority protocol invoked within a committee C. We will assume that each node i in C is initialized with some message m i . The goal of the Π maj protocol is for each node in C to compute the majority function m = maj{m i } i . The protocol proceeds as follows: every node in C invokes Π Upfal to send its message to every other node in C. Each node then simply computes (locally) the majority of the messages it received. We now wish to argue that in the presence of a set T ⊂ V of randomly corrupt nodes with |T | ≤ α 3 n, there exists a set S ⊂ V with |S| ≥ n − β 3 |T | such that every pair of nodes in S can communicate reliably with each other, for appropriately chosen universal constants α 3 , β 3 to be determined later. The proof proceeds as follows. Under these choices of α 3 , β 3 , we first show that most committees must in fact contain less than an α 2 -fraction of corrupt nodes. In such committees, Π Upfal works successfully for all but an = O(α 2 )-fraction of nodes in that committee by Theorem 6. Call such committees as good committees. From Theorem 6, in good committees there exists a set of privileged nodes of size at least s − O(α 2 s) that can communicate reliably with each other.

We now consider nodes A, B that wish to communicate with each other, and are privileged nodes in good committees. Hence, all but an -fraction of the nodes in C A (the committee containing A) receive A's message correctly on executing Π Upfal . On any execution of Π edge between C A and another committee C , all but at most an -fraction of the nodes in C receive the correct value. Now, if C is good, in the execution of the Π maj protocol in C , all but at most a + α 2 = O(α 2 )-fraction of the nodes begin with the correct value and Π Upfal works successfully for all but an -fraction of nodes. This ensures that as long as + α 2 < 1/2, all but at most an -fraction of the nodes compute the majority of the incoming messages correctly. Inductively, this would show that at the end of the emulation of the Π But protocol, all but an -fraction of the nodes in the committee containing B receive A's message correctly and since C B is a good committee and + α 2 < 1/2, B receives A's message correctly as B is privileged.

We now formalize this argument. We call a committee good if the fraction of corrupt nodes in it is at most α 2 and bad otherwise. Let T ⊂ V be a set of randomly corrupt nodes with |T | = t = α 3 n where α 3 ≤ min{α 1 , (α 2 /e) 2 } where the constant α 2 is from Theorem 6. Lemma 1. The probability that a committee is good is at least 1 − (t/n) log log n . as s = (2/α 2 ) log log(n).

log(n) with probability at least 1 − (t/n) α2t/(4 log(n)) .

Proof. Let ζ = (t/n) log log n . Note that 

The probability that the number of bad committees is more than t/s log(n) is ≤ n/s t/(s log(n)) ζ t/(s log(n)) ≤ en/s t/(s log(n)) t/(s log(n)) ζ t/(s log(n)) = ζ · en log(n) t t/(s log(n)) ≤ ζ t/(s log(n)) from (2) = t n log log(n)t 2s log(n) = t n α 2 t 4 log(n)

We have that if C is a good committee with t ≤ α 2 s corrupt nodes, from Theorem 6, there exists a set S C (privileged nodes) of at least s − β 2 t nodes in C that can communicate reliably with each other. We say that a committee holds value v if all the privileged nodes in the committee hold value v. Proof. Since C holds value v, at least s − β 2 α 2 s nodes in C receive the value v after invoking Π edge . Since C is good at most α 2 s nodes in C are corrupt. Hence, at least s − (β 2 + 1)α 2 s nodes in C begin with the value v while invoking Π maj in C . Consider a node Z in the set S C of privileged nodes in C . As C is good, we have |S C | ≥ s − β 2 α 2 s. Nodes in S C receive messages reliably from each other. Out of the messages received by Z from nodes in S C during the execution of Π maj , at most (β 2 + 1)α 2 s may be unequal to v. The messages received by Z from the β 2 α 2 s non-privileged nodes may not be equal to v. Still each node in S C will receive at least s − (2β 2 + 1)α 2 s copies of v. Hence, if (2β 2 + 1)α 2 < 1/2, the claim follows. We note from [21] that it is possible to take α 2 = 1/72 and β 2 = 6 which satisfies (2β 2 + 1)α 2 < 1/2.

Considering the bad committees as corrupt nodes in G But , there are at most t/s log n of them with overwhelming probability by Lemma 2. From Theorem 5, there exists a set of committees P (privileged committees) that can communicate with each other reliably. A and B be two nodes in privileged (good) committees C A ∈ P and C B ∈ P respectively. If A ∈ S CA and B ∈ S CB , then the above protocol guarantees reliable message transmission from A to B.

Proof. Note that if C A = C B , we are done by Theorem 6 as A and B are privileged. We consider the case C A = C B . Since A ∈ S CA , all nodes in S CA receive A's message, m, correctly and C A holds m. Since C A , C B ∈ P , after the invocation of Π But , C B holds m. Since B ∈ S CB , it receives m from each node in S C . Hence B will receive at least s − β 2 α 2 s copies of v. If β 2 α 2 < 1/2, the claim follows. We note from [21] that it is possible to take α 2 = 1/72 and β 2 = 6 which satisfies β 2 α 2 < 1/2.

With probability 1 − (t/n) α2t/(4 log(n)) , there exists a set of nodes S ⊂ V where |S| ≥ n−β 3 |T | such that every pair of nodes in S can communicate reliably with each other.

Proof. The set S consists of nodes that are privileged nodes in privileged committees. We have that the total number of committees is N C = n/s. Let t C denote the number of bad committees. Note that with probability at least 1−(t/n) α2t/(4 log(n)) , t C ≤ t/s log n . Furthermore, since t = α 3 n ≤ α 1 n (by the choice of α 3 ≤ min{α 1 , (α 2 /e) 2 }), t C ≤ t/s log n ≤ α 1 · n/s log n ≤ α 1 · NC log NC . This implies that Theorem 5 is now applicable. 

from Theorem 6. Thus, |S| ≥ n − β 3 t for some constant β 3 .

We summarize the result from this section in the theorem below.

For sufficiently large n, there exists an n-node network G rand = (V, E), a protocol Π rand for message transmission on it, and constants α 3 and β 3 , such that:

1. The network G rand is of constant degree. 2. If a subset of nodes T ⊂ V is randomly corrupt, where |T | ≤ α 3 n, with probability 1 − (t/n) α2t/(4 log(n)) , there exists a set of nodes S ⊂ V where |S| ≥ n − β 3 |T | such that every pair of nodes in S can communicate reliably with each other by invoking Π rand .

Note that at t = Θ(n) we get that the protocol works with probability 1 − 2 −Ω( n log(n) ) which improves upon [3] which achieved 1 − 2 −Ω n log 2 (n) . We end this section with the following remark. Let |T | = t. Note that in [7] , the number of nodes that can communicate with each other reliably is n − t − O(t/ log n), that is, we give up at most O(t/ log n) = o(t) nodes. We remark that this is not achievable in networks of constant degree even in the random model. In an adversarial corruption setting, one can corrupt the neighbors of O(t/d) nodes, and hence if d = O(1), any protocol must give up O(t) nodes. This is true even in the random corruption model: a node has corrupt neighbors with some constant probability if t = O(n) and hence any protocol must give up O(t) nodes. Similarly, in networks of log log n degree, any protocol must give up O(t/(log n) Θ(1) ) nodes.

In the worst-case model, the current best networks are those constructed by Chandran, Garay and Ostrovsky [7] . They construct a graph with degree d = log q n for some fixed constant q > 1, that is resilient to t = O(n) adversarial corruptions. We show using a probabilistic argument the existence of a network of degree O(log n) that is resilient to t = O(n) adversarial corruptions. Furthermore, the probabilistic construction works with all but negligibly small probability.

Our construction is also rather simple, and uses our network that is resilient to random errors as a black box. This style of our argument provides further motivation for studying the random corruption model, even if the ultimate goal is to be resilient to adversarial corruptions.

G wc = (V, E), where V = [n]. The edge set is as follows. Let {G i rand } i = {(V R i , E i )} i be our network, G rand ,

We now describe the communication protocol Π wc over this network. Let Π i rand be the reliable transmission protocol associated with the network G i rand as described in Definition 3, for each 1 ≤ i ≤ z. Now, if a node A wishes to send a message m to node B: (a) A will invoke the protocol Π i rand to transmit the message m to B over the network G i rand . (b) B receives z messages, corresponding to the z executions of Π i rand for 1 ≤ i ≤ z. B takes the majority of all these messages.

Degree. The network constructed is of degree O(log n), since the network is constructed using z = O(log n) copies of the constant degree network G rand from Definition 3.

We proceed to prove resiliency of the protocol. We will first consider an arbitrary fixed adversary T ⊂ V , estimate the probability of resilience against it and finally perform a union bound over all adversaries. Consider an arbitrary fixed adversary. We will say that the i th layer is bad for this fixed adversary if the conditions in Theorem 2 do not hold for G i rand . Correspondingly we call a layer good for this adversary if the conditions in Theorem 2 hold. In Lemma 6, we prove that with high probability only at most (1/5)th of the layers are bad.

Consider a good layer i, for some 1 ≤ i ≤ z. We define D i to be set of doomed nodes in protocol Π i rand . By Theorem 2, |D i | ≤ β 3 |T |. For an arbitrary fixed adversary, we will show that the set D i behaves as a small random set as a result of permuting the vertex set V to obtain V R i over which G i rand is constructed. For any honest node v ∈ V , let L D v denote the set of all good layers i such that v ∈ D i , that is, v is doomed in layer i. We will finally show that, with high probability, for most nodes v, |L D v | is small.

To wrap up the proof, we designate a node v ∈ V as doomed for Π wc with respect to this fixed adversary if |L D v | > (1/10)z. Consider a pair of privileged nodes (nodes that are honest and not designated as doomed for Π wc ) A, B ∈ V . Since, with high probability, at most (1/5)th of the layers are bad and, by definition, A, B are doomed in at most (1/10)th of the good layers, A, B are both privileged in at least (3/5)th of the good layers with respect to this adversary. Hence a majority of the messages sent by A in Π wc reach B correctly and B's majority is computed correctly. By our earlier claim, with high probability, the number of doomed nodes is small, that is, most nodes are privileged and can hence communicate reliably in the presence of this fixed adversary with high probability. Performing a union bound over all possible adversaries, we get our final result.

We now formalize this argument. Let T ⊂ V be an arbitrary set of corrupt nodes with |T | = t = α 4 n where α 4 ≤ min{α 3 , 1/10, Proof. Note that the ith layer is constructing by randomly and independently permuting the vertex set V to obtain V R i over which G i rand is constructed. This is equivalent to constructing G i rand over V and thinking of the adversary as being a random subset of V of size |T |. This enables to apply Theorem 2. By Theorem 2, for a fixed adversary, the ith layer is bad independently with probability ≤ (t/n) α2t/(4 log n) . So the probability that δz out of the z layers are bad is Proof. Consider a fixed adversary and a fixed layer i. Let π i be a permutation of V and let π i

i with respect to this adversary. Note that D R i is fixed by the choice of T R i , or equivalently, by the choice of π i (T ). Let D i ⊂ V \ T be the set of doomed nodes in V . Note that π i (D i ) = D R i . By symmetry, for any two subsets S 1 , Proof. Let layer i be good. This implies that |D i | ≤ β 3 t by Theorem 2. Without loss of generality we can assume that |D i | = β 3 t as more doomed nodes is worse for us. Let v be an arbitrary honest node. By Lemma 7,

as all subsets of honest nodes of size β 3 t are equally likely and the number of honest nodes is n − t. As all layers are sampled independently, we have

where the last inequality follows from t ≤ n/10.

Let u, v be two honest nodes. We have that Pr

Hence the events u ∈ D i and v ∈ D i are anti-correlated. This implies that |L D v | ≥ z/10 and |L D u | ≥ z/10 are also anti-correlated. As we want to upper bound the number of nodes A which satisfy |L D A | ≥ z/10, we can assume that the events |L D v | ≥ z/10 and |L D u | ≥ z/10 are independent.

The probability that for more than β 4 t/ log n honest nodes |L D v | ≥ z/10 with 

As t = n/10 which implies e ≤ n t

Let E A 2 be the event that the number of honest nodes v such that |L D v | ≥ z/10 is at most β 4 t/ log n. Then by Lemma 8 for a fixed adversary Pr

. Let E 2 be the event that E A 2 holds for all adversaries A with t corruptions. By a union bound over all such adversaries, 3 (1) . E 1 implies that for any adversary ≤ 1/5 fraction of the layers are bad. E 2 implies that for any adversary there exists a set of honest nodes S, |S| ≥ n − t − β 4 t log n such that for all v ∈ S L D v ≤ z/10. Hence for any two nodes A, B ∈ S they are both privileged in at least 1 − 1/5 − 1/10 − 1/10 > 1/2 fraction of the layers. Hence the message from A to B will be correctly delivered on > 1/2 fraction of the layers hence B will find the correct message after taking majority. The set S behaves as the privileged set for the network G wc , Π wc .

[E 1 ∧ E 2 ] ≥ 1 − 1/n ω(1) − 1/n ω(1) = 1 − 1/n ω

It is our goal to design low degree graphs with efficient communication protocols for AE reliable message transmission. Our final networks are constructed by composing several simpler graph structures. An important graph that our work builds on is Dwork et al.'s butterfly network [12] . The diameter of a graph is a fundamental lower bound on the amount of work required for message transmission. Any graph with constant degree will necessarily have work complexity Ω(log n). Thus, the logarithmic diameter of the butterfly network is optimal up to constant factors. Since the diameter is a fundamental lower bound on the work complexity of point to point transmissions in a network, we think of a polynomial work complexity in the diameter-polylogarithmic work complexity-as a reasonable definition for work-efficient in this context. Dwork et al.'s protocol which requires Ω(n) work complexity for a single point to point message transmission is thereby work-inefficient. Another weakness of Dwork et al.'s protocol, is that it floods the network, and thus nearly every node in the network is necessarily involved in every point to point message transmission. It would aid both efficiency and parallelizability of higher level protocols to significantly limit the number of nodes used for a point to point transmission.

We make simple modifications to Dwork et al.'s ideas to achieve a workefficient protocol that requires only polylogarithmically many nodes to be active in any point to point communication in this section. Our main observation is that a u to v transmission over the Butterfly network need not flood all Θ(n/ log n) paths in the network to ensure reliable transmission. In fact, we show that picking a set of just Θ(log n) paths between every pair of vertices, and sending the message only over those paths suffices. This reduces both the number of nodes used per point to point transmission and total work to O(log 2 n). 1. The network G But has degree 11. 2. The total work is O(polylog(n)). 3. There is a constant ε ∈ (0, 1) such that Π Ef f is (εn/ log n, O(t log t))-resilient with probability 1 − o(1).

Proof. It is clear that the degree of the network is 11 and that the work complexity in the protocol are O(polylog(n)) as we send Θ(log n) messages on paths of length Θ(log n). We now prove the resilience guarantee. Consider any fixed subset T ⊂ V with t = |T | ≤ α 1 n/ log n, where α 1 is that of Theorem 5. By Theorem 5, we know that there is a set V of size n − β 1 t log t that can communicate reliably with each other by invoking Π But . For any pair of vertices u, v ∈ V , we let P u,v be the set of paths used in message transmissions from u to v by protocol Π But . By Theorem 5 property (3) we know that at least a 2/3 fraction of the paths in each P u,v contain no corrupt node. We will assume that exactly 2/3 fraction of the paths in each P u,v contain no corrupt node as that is only worse for us. If a message is sent through a path with no corrupt nodes, the correct message reaches v. Let Q u,v be a random sample of h = 144 log e (n) ≈ 100 log n paths from P u,v . The protocol Π Ef f sends a message from u to v as follows:

1. u sends the message along all the paths Q u,v , 2. v receives all h messages that were sent along the paths in Q u,v and takes the majority.

We now argue when this majority will be the correct message with high probability. Fix two nodes u, v ∈ V and fix an adversary (the subset of corrupted nodes). We look at the paths Q u,v in a communication from u to v. The expected number of paths, μ, in Q u,v with a corrupted node is μ = h/3. So, we define δ = 1/2 1/3 −1 and by the Chernoff bound from Eq. 1, the probability that a majority of the paths Q u,v contain a corrupt node is: We call a pair of vertices {u, v} a doomed-pair if a majority of paths between them contain a corrupt node. For a fixed adversary, the probability that there are more than g doomed-pairs is bounded above by g < e n 2 g since the probability of pair corruptions is independent conditioned on the adversary. To show that the construction works for an adversarially chosen set of corruptions, we take a union bound over all adversaries. The probability that there is an adversary with t corruptions for which the number of doomed-pairs is at least g is bounded above by: Lemma 9 shows that the network N Ef f = (G But , Π Ef f ) satisfies resilience only with high probability-not deterministically. We now show, via the probabilistic method, that the resilience guarantee can be made deterministic; yet we state it explicitly, because this is the protocol that we use to enable our main theorem.

Reminder of Theorem 4. For the n = m2 m -node network G But = (V, E) there is a protocol Π * Ef f for message transmission on it such that the following holds:

1. The network G But has degree 11. 2. The total work of the protocol is O(polylog(n)).

3. There is a constant ε ∈ (0, 1) such that Π * Ef f is (εn/ log n, O(t log t))-resilient.

Proof. Since Lemma 9 holds with probability greater than 0, and the randomness is just over the protocol Π Ef f , there is some specific protocol Π * Ef f in the support of Π Ef f that has properties (1-3).

We now show how to modularly substitute-in our work-efficient protocol on the Butterfly network, in order to get work-efficient versions of Theorems 2 and 3. The high level idea is simple. The protocol Π rand uses Π But as a blackbox, and the protocol Π wc uses a Π rand as a blackbox. Substituting the efficient protocol Π * Ef f in for Π But into Π rand creates an efficient version of Π rand , which we call Π rand,ef f below; and substituting Π rand,ef f into Π wc creates an efficient version of Π wc , which we call Π wc,ef f below. We describe the details of these subsitutions in the following theorems. We substitute Π * Ef f in for Π But in Π rand to strengthen Theorem 2 to the following: Theorem 7. For sufficiently large n, there exists an n-node network G rand = (V, E), a protocol Π rand,ef f for message transmission on it, and constants α 3 and β 3 , such that:

1. The network G rand,ef f is of constant degree. 2. The Work complexity of GΠ rand,ef f is O(polylog(n)). 3. If a subset of nodes T ⊂ V is randomly corrupt, where |T | ≤ α 3 n, with probability 1 − (t/n) α2t/(4 log(n)) , there exists a set of nodes S ⊂ V where |S| ≥ n − β 3 |T | such that every pair of nodes in S can communicate reliably with each other by invoking Π rand,ef f .

Proof. In Theorem 2 we note that work done inside a single committee was exponential in the size of the committee as we instantiate G Upfal (from Theorem 6) inside every committee. But as the size of the committee is s = O(log log(n)) this is only O(polylog(n)). Thinking of committees as super-nodes we had instantiated G But over super-nodes. The total number of super-nodes used in a single message transmission was Ω(n/s) as we have n/s super-nodes. By using Π ef f instead of Π But we can bring this down to polylog(n/s) ≤ polylog(n), Sending a single message from a super-node to its neighbor requires running G Upfal inside the committee which takes O(polylog(n)) work. Thus the total work is O(polylog(n) · polylog(n)) = O(polylog(n)).

Finally, we substitute Π * rand,ef f in for Π rand in Π wc to strengthen Theorem 3 to our main theorem:

Reminder of Theorem 1. For sufficiently large n, there exists an n-node network G wc = (V, E), a protocol Π wc,ef f for message transmission on it, and constants α and β, such that:

1. The network G wc is of degree O(log n). 2. The Work complexity of Π wc,ef f is O(polylog(n)). 3. Π wc,ef f is (αn, βt/ log n)-resilient.

Secure computation without authentication

Completeness theorems for noncryptographic fault-tolerant distributed computation (extended abstract)

Agreement in the presence of faults, on networks of bounded degree

Asymptotically optimal distributed consensus

Fast consensus in networks of bounded degree

Security and composition of cryptographic protocols: a tutorial (part I)

Improved fault tolerance and secure computation on sparse networks

Edge fault tolerance on sparse networks

Multiparty unconditionally secure protocols (extended abstract)

An efficient algorithm for byzantine agreement without authentication

Bounds on information exchange for Byzantine agreement

Fault tolerance in networks of bounded degree (preliminary version)

Almost-everywhere secure computation

How to play any mental game or a completeness theorem for protocols with honest majority

From almost everywhere to everywhere: Byzantine agreement withÕ(n 3/2 ) bits

Scalable leader election

Towards secure and scalable computation in peer-to-peer networks

The Byzantine generals problem

Explicit expanders and the Ramanujan conjectures

Reaching agreement in the presence of faults

Tolerating linear number of faults in networks of bounded degree

Protocols for secure computations (extended abstract)

Proof. The protocol Π wc uses Π rand as a blackbox O(log n) times, one for each layer. We substitute Π rand with Π rand,ef f . This brings down the work complexity to O(log n · polylogn) = polylogn.