Abstract. We study the problem of secure communication tolerating generalized mixed adversaries across an underlying completely asynchronous incomplete network. We explore the interplay between the minimal network connectivity required and the degree of security attainable, and completely characterize the network requirements for attaining perfect and unconditional (with negligible error) security. We also consider networks with additional broadcast capabilities and prove that unconditionally secure communication can be achieved with much lesser connectivity if the network assures the broadcast primitive. 1
Abstract. We study the problem of secure communication tolerating generalized mixed adversaries across an underlying completely asynchronous incomplete network. We explore the interplay between the minimal network connectivity required and the degree of security attainable, and completely characterize the network requirements for attaining perfect and unconditional (with negligible error) security. We also consider networks with additional broadcast capabilities and prove that unconditionally secure communication can be achieved with much lesser connectivity if the network assures the broadcast primitive. 1
Abstract. In this paper we give the minimal connectivity required in a synchronous directed network, which is under the influence of a computationally unbounded Byzantine adversary that can corrupt a subset of nodes, so that Secure Message Transmission is possible between sender S and receiver R. We also show that secure communication between a pair of nodes in a given synchronous directed network is possible in both directions if and only if reliable communication is possible between them. We assume that in a network, every node is capable of computation and we model the network along the lines of [14].
In this paper, we re-visit the problem of unconditionally secure message transmission (USMT) from a sender S to a receiver R, who are part of a distributed synchronous network, modeled as an arbitrary directed graph. Some of the intermediate nodes between S and R can be under the control of an adversary having unbounded computing power. Desmedt and Wang [4] have given the characterization of USMT in directed networks. However, in their model, the underlying network is abstracted as directed node disjoint paths (also called as wires/channels) between S and R, where the intermediate nodes are oblivious, message passing nodes and perform no other computation. In this work, we first show that the characterization of USMT given by Desmedt et.al [4] does not hold good for arbitrary directed networks, where the intermediate nodes can perform some computation, beside acting as message forwarding nodes. We then give the characterization of USMT in arbitrary directed networks, considering the entire network as a whole. As far our knowledge is concerned, this is the first ever characterization of USMT in arbitrary directed networks.
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.
We study the interplay of network connectivity and the issues related to the possibility, feasibility and optimality for unconditionally reliable message transmission (URMT) and unconditionally secure message transmission (USMT) in an undirected synchronous network, under the influence of an adaptive mixed adversary A (tb,to,tf,tp), who has unbounded computing power and can corrupt up to tb, to, tf and tp nodes in the network in Byzantine, omission, fail-stop and passive fashion respectively. In URMT problem, a sender S and a receiver R are part of a distributed network, where S and R are connected by intermediate nodes, of which at most tb, to, tf and tp nodes can be under the control of A (tb,to,tf,tp). S wants to send a message m which is a sequence of ℓ (ℓ ≥ 1) field elements from a finite field F to R. The challenge is to design a protocol, such that after interacting in phases1 as per the protocol, R should be able to obtain m with probability at least 1 − δ, where 0 < δ < 1 2, irrespective of any adversarial strategy of A (tb,to,tf,tp). The USMT problem has an additional requirement that A (tb,to,tf,tp) should not know anything about m in information theoretic sense. In this paper, we answer the following in context of URMT and USMT: (a) Possibility: when
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