The problem of unconditionally reliable message transmission (URMT) is to design a protocol which when run by players in a network enables a sender s to deliver a message to a receiver r with high probability, even when some players in the network are under the control of an unbounded adversary. Renault and Tomala [JoC2008] gave a characterization of undirected neighbour networks over which URMT tolerating Byzantine adversary is possible. In this paper, we generalize their result to the case of directed networks. 1
The problem of unconditionally reliable message transmission (URMT) is to design a protocol which when run by players in a network enables a sender s to deliver a message to a receiver r with high probability, even when some players in the network are under the control of an unbounded adversary. Renault and Tomala [JoC2008] gave a characterization of undirected neighbour networks over which URMT tolerating Byzantine adversary is possible. In this paper, we generalize their result to the case of directed networks. 1
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
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 having unbounded computing power, who can corrupt some of the nodes in the network in Byzantine, omission, fail-stop and passive fashion respectively. We consider two types of adversary, namely threshold and non-threshold. One of the important conclusions we arrive at from our study is that allowing a negligible error probability significantly helps in the 'possibility', 'feasibility' and 'optimality' of both reliable and secure message transmission protocols. To design our protocols, we propose several new techniques which are of independent interest.
We study the problem of information-theoretically secure message transmission (SMT) in asynchronous directed networks. In line with the literature, the distrust and failures of the network is captured via a computationally unbounded Byzantine adversary that may corrupt some subset of nodes. We give a characterization of networks over which SMT from sender S to receiver R is possible in both the well-known settings, namely perfect SMT (PSMT) and unconditional SMT (USMT). We distinguish between two variants of USMT: one in which R can output an incorrect message (with small probability) and another in which R never outputs a wrong message, but may choose to abort (with small probability). We also provide efficient protocols for an important class of networks.
We study the problem of perfectly reliable message transmission (PRMT) and perfectly secure message transmission (PSMT) in an undirected synchronous network tolerating an all powerful threshold mobile Byzantine adversary. Specifically, we show that the mobility of the threshold adversary does not affect the possibility and optimality of PRMT and PSMT protocols. We also characterise PSMT in directed networks tolerating mobile adversary. All existing PRMT and PSMT protocols abstract the paths between the sender and the receiver as wires, neglecting the intermediate nodes in the paths, thus causing significant over estimation in the communication and round complexity of protocols. Here, we consider the underlying paths as a whole instead of abstracting them as wires and derive a tight bound on the number of rounds required to achieve reliable communication tolerating a threshold mobile adversary with arbitrary roaming speed. Finally, we briefly study PRMT and PSMT protocols in the presence of non-threshold mobile Byzantine adversary. Even though the characterisation for PRMT/PSMT is shown to be same against both threshold static and threshold mobile adversary (in this article), we show that the characterisation for PRMT/PSMT against non-threshold static and non-threshold mobile adversary are not same.
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.
Consider the following problem: a sender S and a receiver R are part of a directed synchronous network and connected through intermediate nodes. Specifically, there exists n node disjoint paths, also called as wires, which are directed from S to R and u wires, which are directed from R to S. Moreover, the wires from S to R are disjoint from the wires directed from R to S. There exists a centralized, static adversary A static , who has unbounded computing power and who can control at most t wires between S and R in Byzantine fashion. S has a message m S , which we wants to send to R. The challenge is to design a protocol, such that after interacting in phases 5 as per the protocol, R should correctly output m R = m S , except with error probability 2 −(κ) , where κ is the error parameter. This problem is called as statistically reliable message transmission (SRMT). The problem of statistically secure message transmission (SSMT) has an additional requirement that at the end of the protocol, m S should be information theoretically secure from A static . Desmedt et.al [14, 55] have given the necessary and sufficientcondition for the existence of SRMT and SSMT protocols in the above settings. They also presented an SSMT protocol, satisfying their characterization. The authors in [14, 55] claimed that their protocol is efficientand has polynomial computational and communication complexity. However, we show that it is not so. That is, we specify an adversary strategy, which may cause the protocol to have exponential computational and communication complexity 6 . We then present