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 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 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
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].
The problem of secure message transmission (SMT), due to its importance in both \npractice and theory, has been studied extensively. Given a communication network in \nwhich a sender S and a receiver R are indirectly connected by unreliable and distrusted \nchannels, the aim of SMT is to enable messages to be transmitted from S to R with a \nreasonably high level of privacy and reliability. SMT must be achieved in the presence \nof a Byzantine adversary who has unlimited computational power and can corrupt the \ntransmission. In the general adversary model, the adversary is characterized by an \nadversary structure. We study two diff�erent measures of security: perfect (PSMT) and \nalmost perfect (APSMT). Moreover, reliable (but not private) message transmission (RMT) are considered as a specifi�c part of SMT. In this thesis, we study RMT, APSMT \nand PSMT in two di�fferent network settings: point-to-point and multicast. \nTo prepare the study of SMT in these two network settings, we present some ideas \nand observations on secret sharing schemes (SSSs), generalized linear codes and critical \npaths. First, we prove that the error-correcting capability of an almost perfect SSS is \nthe same as a perfect SSS. Next, we regard general access structures as linear codes, \nand introduce some new properties that allow us to construct pseudo-basis for efficient \nPSMT protocol design. In addition, we de�fine adversary structures over "critical paths", \nand observe their properties. Having these new developments, the contributions on SMT \nin the aforementioned two network settings can be presented as follows. \nThe results on SMT in point-to-point networks are obtained in three aspects. First, \nwe show a Guessing Attack on some existing PSMT protocols. This attack is critically \nimportant to the design of PSMT protocols in asymmetric networks. Second, we determine necessary and sufficient conditions for di�fferent levels of RMT and APSMT. \nIn particular, by applying the result on almost perfect SSS, we show that relaxing the \nrequirement of privacy does not weaken the minimal network connectivity. Our �final \ncontribution in the point-to-point model is to give the �first ever efficient, constant round \nPSMT protocols in the general adversary model. These protocols are designed using \nlinear codes and critical paths, and they signifi�cantly improve some previous results in \nterms of communication complexity and round complexity. \nRegarding SMT in multicast networks, we solve a problem that has been open for \nover a decade. That is, we show the necessary and sufficient conditions for all levels of \nSMT in di�fferent adversary models. First, we give an Extended Characterization of the \nnetwork graphs based on our observation on the eavesdropping and separating activities \nof the adversary. Next, we determine the necessary and sufficient conditions for SMT \nin the general adversary model with the new Extended Characterization. Finally, we \napply the results to the threshold adversary model to completely solve the problem of \nSMT in general multicast network graphs.
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.
In a distributed network, we consider two special nodes called the sender S and the receiver R that are connected by n node-disjoint (except for S and R) bi-directional wires. Out of these n wires, the adversary can control at most t wires (of its choice) in Byzantine fashion. In this setting, our goal is to design a message transmission protocol Π that assures the following two conditions hold: (1) by the end of the protocol Π, R gets the correct message m transmitted by S without any error (perfect reliability), and (2) the adversary learns no information about m, whatsoever, in information theoretic sense (perfect secrecy). Protocols that satisfy these two conditions are known as the Perfectly Secure Message Transmission (PSMT) protocols.
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.