Consider a synchronous distributed network which is partly controlled by an adversary. In a Perfectly Secret Message Transmission(PSMT) protocol, the sender S wishes to transmit a message to the receiver R such that the adversary learns nothing about the message. We characterize the set of directed graphs that admit PSMT protocols tolerating a dual failure model where up to tp nodes are passively corrupted and further up to any tf nodes may fail.
Consider a synchronous distributed network which is partly controlled by an adversary. In a Perfectly Secret Message Transmission(PSMT) protocol, the sender S wishes to transmit a message to the receiver R such that the adversary learns nothing about the message. We characterize the set of directed graphs that admit PSMT protocols tolerating a dual failure model where up to tp nodes are passively corrupted and further up to any tf nodes may fail.
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.
In a network of n nodes (modeled as a digraph), the goal of a perfectly secret message transmission ( PSMT ) protocol is to replicate sender’s message m at the receiver’s end without revealing any information about m to a computationally unbounded adversary that eavesdrops on any t nodes. The adversary may be mobile too that is, it may eavesdrop on a different set of t nodes in different rounds. We prove a necessary and sufficient condition on the synchronous network for the existence of r -round PSMT protocols, for any given r>0 ; further, we show that round-optimality is achieved without trading-off the communication complexity; specifically, our protocols have an overall communication complexity of O(n) elements of a finite field to perfectly transmit one field element. Apart from optimality/scalability, two interesting implications of our results are: 1) adversarial mobility does not affect its tolerability: PSMT tolerating a static t -adversary is possible if and only if PSMT tolerating mobile t -adversary is possible; and 2) mobility does not affect the round optimality: the fastest PSMT protocol tolerating a static t -adversary is not faster than the one tolerating a mobile t -adversary.
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.
In a network ofnnodes (modeled as a digraph), the goal of a perfectly secret message transmission (PSMT) protocol is to replicate sender’s messagemat the receiver’s end without revealing any information aboutmto a computationally unbounded adversary that eavesdrops on anytnodes. The adversary may be mobile too that is, it may eavesdrop on a different set oftnodes in different rounds. We prove a necessary and sufficient condition on the synchronous network for the existence ofr-roundPSMTprotocols, for any givenr>0; further, we show that round-optimality is achieved without trading-off the communication complexity; specifically, our protocols have an overall communication complexity ofO(n)elements of a finite field to perfectly transmit one field element. Apart from optimality/scalability, two interesting implications of our results are: 1)adversarial mobility does not affect its tolerability:PSMTtolerating a statict-adversary is possibleif and only ifPSMTtolerating mobilet-adversary is possible; and 2)mobility does not affect the round optimality:the fastestPSMTprotocol tolerating a statict-adversary isnot fasterthan the one tolerating a mobilet-adversary.
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 consider the problem of perfect (information-theoretically) secure message transmission (PSMT) from a sender S to a receiver R in asynchronous directed networks tolerating dual adversary. The adversary can control at most tp nodes in a passive fashion and at most tf nodes in a fail-stop fashion. We achieve PSMT in this setting with a new class of message transmission protocols called the quiescent protocols. Quiescent protocols ensure that the players eventually stop sending messages but in contrast to the usual terminating protocols, these protocols do not require the players to go into the halt state, from which they cannot take any further action. To show the significance of quiescent protocols, we first identify conditions in which it is impossible for any terminating protocol to achieve PSMT. To circumvent this impossibility, we transform the existing synchronous PSMT protocol into a quiescent protocol which accomplishes PSMT. By focusing on designing quiescent protocols rather than terminating protocols, we show that asynchrony in the network does not demand any extra connectivity over its state-of-the-art synchronous counterpart. This shows that quiescent protocols are befitted to solve PSMT in asynchronous networks with fail-stop faults.