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.
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
nnodes (modeled as a digraph), the goal of a perfectly secret message transmission (PSMT) protocol is to replicate sender’s message
mat the receiver’s end without revealing any information about
mto a computationally unbounded adversary that eavesdrops on any
tnodes. The adversary may be mobile too that is, it may eavesdrop on a different set of
tnodes in different rounds. We prove a necessary and sufficient condition on the synchronous network for the existence of
r-roundPSMTprotocols, 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:PSMTtolerating a static
t-adversary is possibleif and only ifPSMTtolerating mobile
t-adversary is possible; and 2)mobility does not affect the round optimality:the fastestPSMTprotocol tolerating a static
t-adversary isnot fasterthan the one tolerating a mobile
t-adversary.
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.
In the model that has become known as “Perfectly Secure Message Transmission” (PSMT), a sender Alice is connected to a receiver Bob through n parallel two-way channels. A computationally unbounded adversary Eve controls t of these channels, meaning she can acquire and alter any data that is transmitted over these channels. The sender Alice wishes to communicate a secret message to Bob privately and reliably, i.e. in such a way that Eve gains no information about the message while Bob is able to recover it completely. We focus on PSMT protocols that work in two transmission rounds for n = 2t + 1. We break from previous work by following a conceptually simpler blueprint. This has two consequences: first, we obtain improved efficiency, namely, we reduce the previously best-known communication complexity, i.e. the number of transmitted bits necessary to communicate a 1-bit secret, from O(n3log n) to O(n2log n). Our solution also reaches optimal transmission rate for a secret of size O(n log n), thus answering the hitherto open question of attaining a threshold below O(n2log n) bits. Second, our construction can be adapted to more general scenarios relevant to Network Coding, where the adversary is given more power.
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.