Broadcast is a primitive which allows a specific party to distribute a message consistently among n parties, even if up to t parties exhibit malicious behaviour.In the classical model with a complete network of bilateral authenticated channels, the seminal result of [15] shows that broadcast is achievable if and only if t < n/3.There are two generalizations suggested for the broadcast problem -with respect to the adversarial model and the communication model.Fitzi and Maurer [10] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of n parties.On the other hand, [4] extends the standard model of bilateral channels with the existence of b-minicast channels that allow to locally broadcast among any subset of b parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to t corrupted parties is possible if and only if t < b-1 b+1 n.These generalizations are unified in [14] where Raykov studies the problem of achieving broadcast from a complete set of b-minicast channels that is secure under general adversaries, and gives a tight characterization of the possible corrupted subsets of parties against which broadcast is (im)possible.This thesis initiates the study of achievability of broadcast in scenarios where only some subset of b-minicast channels are available, thereby addressing an open problem posed by [14].Even though the broadcast problem has been studied for the concrete case of incomplete 3minicast networks in [16] and [12], not much work has been done with respect to general b-minicast models.Our major contribution is the identification of types of minicast channels that are essential for broadcast secure against general adversaries.In particular, this allows us to derive a bound on the amount of b-minicasts required for some party to broadcast.Inspired by the result of [14], the thesis also proves some properties for an interesting class of adversaries, named chain adversaries, that are relevant to the problem at hand, and proposes a hierarchy over all possible general adversaries targeting a set of n parties.We conclude the discussion by showing why a prominent method to construct broadcast protocols -used by [16] for 3-minicast models -is not feasible when it comes to incomplete b-minicast models.
Broadcast is a primitive which allows a specific party to distribute a message consistently among n parties, even if up to t parties exhibit malicious behaviour.In the classical model with a complete network of bilateral authenticated channels, the seminal result of [15] shows that broadcast is achievable if and only if t < n/3.There are two generalizations suggested for the broadcast problem -with respect to the adversarial model and the communication model.Fitzi and Maurer [10] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of n parties.On the other hand, [4] extends the standard model of bilateral channels with the existence of b-minicast channels that allow to locally broadcast among any subset of b parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to t corrupted parties is possible if and only if t < b-1 b+1 n.These generalizations are unified in [14] where Raykov studies the problem of achieving broadcast from a complete set of b-minicast channels that is secure under general adversaries, and gives a tight characterization of the possible corrupted subsets of parties against which broadcast is (im)possible.This thesis initiates the study of achievability of broadcast in scenarios where only some subset of b-minicast channels are available, thereby addressing an open problem posed by [14].Even though the broadcast problem has been studied for the concrete case of incomplete 3minicast networks in [16] and [12], not much work has been done with respect to general b-minicast models.Our major contribution is the identification of types of minicast channels that are essential for broadcast secure against general adversaries.In particular, this allows us to derive a bound on the amount of b-minicasts required for some party to broadcast.Inspired by the result of [14], the thesis also proves some properties for an interesting class of adversaries, named chain adversaries, that are relevant to the problem at hand, and proposes a hierarchy over all possible general adversaries targeting a set of n parties.We conclude the discussion by showing why a prominent method to construct broadcast protocols -used by [16] for 3-minicast models -is not feasible when it comes to incomplete b-minicast models.
Broadcast is a primitive which allows a specific party to distribute a message consistently among n parties, even if up to t parties exhibit malicious behaviour. In the classical model with a complete network of bilateral authenticated channels, the seminal result of Pease et al. [Pease et al., 1980] shows that broadcast is achievable if and only if t < n/3. There are two generalizations suggested for the broadcast problem - with respect to the adversarial model and the communication model. Fitzi and Maurer [Fitzi and Maurer, 1998] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of n parties. On the other hand, Considine et al. [Considine et al., 2005] extend the standard model of bilateral channels with the existence of b-minicast channels that allow to locally broadcast among any subset of b parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to t corrupted parties is possible if and only if t < (b-1)/(b+1)n. These generalizations are unified in the work by Raykov [Raykov P., 2015], where a tight condition on the possible corrupted sets is presented such that broadcast is achievable from a complete set of b-minicasts. This paper investigates the achievability of broadcast in general networks, i.e., networks where only some subsets of minicast channels may be available, thereby addressing open problems posed in [Jaffe et al., 2012; Raykov P., 2015]. To that end, we propose a hierarchy over all possible general adversaries, and identify for each class of general adversaries 1) a set of minicast channels that are necessary to achieve broadcast and 2) a set of minicast channels that are sufficient to achieve broadcast. In particular, this allows us to derive bounds on the amount of b-minicasts that are necessary and that suffice towards constructing broadcast in general b-minicast networks.
Byzantine broadcast is a primitive which allows a specific party to distribute a message consistently among n parties, even if up to t parties exhibit malicious behaviour. In the classical model with a complete network of bilateral authenticated channels, the seminal result of Pease et al. [Pease et al., 1980] shows that broadcast is achievable if and only if t < n/3. There are two generalizations suggested for the broadcast problem - w.r.t. the adversarial model and the communication model. Fitzi and Maurer [Fitzi and Maurer, 1998] consider a (non-threshold) general adversary that is characterized by the subsets of parties that could be corrupted, and show that broadcast can be realized from bilateral channels if and only if the union of no three possible corrupted sets equals the entire set of n parties. On the other hand, Considine et al. [Considine et al., 2005] extend the standard model of bilateral channels with the existence of b-minicast channels that allow to locally broadcast among any subset of b parties; the authors show that in this enhanced model of communication, secure broadcast tolerating up to t corrupted parties is possible if and only if t < (b-1)/(b+1) n. These generalizations are unified in the work by Raykov [Raykov P., 2015], where a tight condition on the possible corrupted sets such that broadcast is achievable from a complete set of b-minicasts is shown. This paper investigates the achievability of broadcast in general networks, i.e., networks where only some subsets of minicast channels may be available, thereby addressing open problems posed in [Jaffe et al., 2012; Raykov P., 2015]. Our contributions include: 1) proposing a hierarchy over all possible general adversaries for a clean analysis of the broadcast problem in general networks, 2) showing the infeasibility of a prominent technique - used to achieve broadcast in general 3-minicast networks [Ravikant et al., 2004] - with regard to higher b-minicast networks, and 3) providing some necessary conditions on general networks for broadcast to be possible while tolerating general adversaries.
Abstract. A broadcast protocol allows a sender to distribute a message through a point-to-point network to a set of parties, such that (i) all parties receive the same message, even if the sender is corrupted, and (ii) this is the sender’s message, if he is honest. Broadcast protocols satisfying these properties are known to exist if and only if t < n/3, where n denotes the total number of parties, and t denotes the maximal number of corruptions. When a setup allowing signatures is available to the parties, then such protocols exist even for t < n. Broadcast is the probably most fundamental primitive in distributed cryptography, and is used in almost any cryptographic (multi-party) protocol. However, a broadcast protocol “only ” satisfying the above properties might be insecure when being used in the context of another protocol. In order to be safely usable within other protocols, a broadcast protocol must satisfy a simulation-based security notion, which is secure under composition. In this work, we show that most broadcast protocols in the literature do not satisfy a (natural) simulation-based security notion. We do not know of any broadcast protocol which could be securely invoked in a multi-party computation protocol in the secure-channels model. The problem is that existing protocols for broadcast do not preserve the secrecy of the message while being broadcasted, and in particular allow the adversary to corrupt the sender (and change the message), depending on the message being broadcasted. For example, when every party should broadcast a random bit, the adversary could corrupt those parties that want to broadcast 0, and make them broadcast 1. More concretely, we show that simulatable broadcast in a model with secure channels is possible if and only if t < n/3, respectively t ≤ n/2 when a signature setup is available. The positive results are proven by constructing secure broadcast protocols.
Broadcast is a fundamental primitive in distributed computing.It allows a sender to consistently distribute a message among n recipients.The seminal result of Pease et al. [JACM'80] shows that in a complete network of synchronous bilateral channels, achieving broadcast is possible if and only if the number of corruptions is bounded by t < n/3.To overcome this bound, Fitzi and Maurer [STOC'00], Considine et al. [JC'05], and Raykov [ICALP'15] strengthen the communication network by assuming partial broadcast channels, which guarantee consistency among a subset of recipients.We extend this line of research to the asynchronous setting.We consider asynchronous broadcast protocols assuming a communication network where each party can broadcast to any subset of b -1 recipients.A natural question is to investigate the trade-off between the size b and the corruption threshold t.We answer this question by showing feasibility and impossibility results:• An asynchronous broadcast protocol Π n,3 BC for b = 3, that is secure up to t < n/2 corruptions.• An asynchronous broadcast protocol Π n,n BC for b = n, that is secure up to t < n -1 corruptions.• An asynchronous broadcast protocol Π n,(b,n) BC I would like to express my deepest gratitude to Dr. Martin Hirt and Chen-Da Liu Zhang for offering me the opportunity to work on such an interesting problem, and for closely supervising every step towards the completion of my thesis.Each result of this work is based on the guidance and motivation they gave me during our countless inspiring discussions filled with enthusiasm.I am extremely grateful to my five-times host at Google, Dr. Holger Brandsmeier, for inspiring and encouraging me to study at ETH, while proposing me unique challenges that helped me push my limits and widen my ambitions.Besides, I thank the whole team for creating an enjoyable work environment, especially last summer, when I mixed work with the exams session.I want to thank my mother, Carmen Mincȃ, and my grandmother, Ana Mincȃ, for raising me to follow my dreams
In the theory of distributed systems and in cryptography one considers a set of n parties which wish to securely perform a certain computation, even if some of the parties are dishonest. Broadcast, one of the most fundamental and widely used such primitives, allows one (possibly cheating) party to distribute a value m consistently to the other parties, in a context where only bilateral (authenticated) channels between parties are available. A well-known result [LSP82] states that this is possible if and only if strictly less than a third of the parties are dishonest. Broadcast guarantees a very strong form of consistency. This paper investigates generalizations of the broadcast setting in two directions: weaker forms of consistency guarantees are considered, and other resources than merely bilateral channels are assumed to be available. The ultimate goal of this line of work is to arrive at a complete classification of consistency specifications [Mau04]. As a concrete result in this direction we present a complete classification of three-party specifications with a binary input and binary outputs.
In this dissertation, we consider the design of broadcast and secure multi-party computation (MPC) protocols in the presence of adversarial faults.
Secure multi-party computation is the most generic problem in fault-tolerant distributed computing. In principle, a multi-party computation protocol can be used to solve any distributed cryptographic problem. Informally, the problem of multi-party computation is the following: suppose we have n parties P1, P2,…, Pn where each party Pi has a private input xi. Together, the parties want to compute a function of their inputs (y1, y2,…, yn) = f(x1,x2,…, xn). However, some parties can be corrupted and do not execute a prescribed protocol faithfully. Even worse, they may be controlled by an adversary and attack the protocol in a coordinated manner. Despite the presence of such an adversary, a secure MPC protocol should ensure that each (corrupted) party Pi learn only its output yi but nothing more.
Broadcast in the presence of adversarial faults is one of the simplest special cases of multi-party computation and important component of larger protocols. In short, broadcast allows a party to send the same message to all parties, and all parties to be assured they have received identical messages.
The contribution of this dissertation is twofold. First, we construct broadcast and secure multi-party computation protocols for honest majority in a point-to-point network whose round complexities improve significantly upon prior work. In particular, we give the first expected constant-round authenticated broadcast protocol for honest majority assuming only public-key infrastructure and signatures. Second, we initiate the study of broadcast in radio networks in the presence of adversarial faults. In radio networks, parties communicate through multicasting messages; a message can only be received by the parties within some radius from the sender. Feasibility and impossibility results are given, and our bounds are tight.