Secure message transmission in asynchronous networks
Ashish Choudhury, Arpita Patra, B. V. Ashwinkumar, Kannan Srinathan, and C. Pandu Rangan
In the Perfectly Secure Message Transmission (PSMT) problem, a sender S and a receiver R are part of a distributed network and connected through $n$ node disjoint paths, also called as wires, among which at most $t$ wires are controlled by a static, Byzantine adversary ${\mathcal A}_t^{static}$, having unbounded computing power. S has a message $m$, which S intends to send to R. The challenge is to design a protocol, such that at the end of the protocol, R should correctly output $m$ without any error (perfect reliability) and ${\mathcal A}_t^{static}$ should not get any information about $m$, what so ever, in information theoretic sense (perfect security).
The problem of Statistically Secure Message Transmission (SSMT) is same as PSMT, except that R should correctly output $m$ with very high probability. Sayeed et al. \cite{SayeedAsynchronous} have given a PSMT protocol in an asynchronous network tolerating ${\mathcal A}_t^{static}$, where S and R are connected by $n = 2t+1$ wires. However, we show that their protocol does not provide perfect security. We then prove that in an asynchronous network, if all the $n$ wires are directed from S to R, then any PSMT protocol tolerating ${\mathcal A}_t^{static}$ is possible iff $n > 3t$. Surprisingly, we also prove that even if all the $n$ wires are bi-directional, then any PSMT protocol in asynchronous network tolerating ${\mathcal A}_t^{static}$ is possible iff $n > 3t$. This is quite surprising because for synchronous networks, by the results of Dolev et al. \cite{Dolev}, if all the wires are unidirectional (directed from S to R), then PSMT tolerating ${\mathcal A}_t^{static}$ is possible iff $n > 3t$, where as if all the wires are bi-directional then PSMT tolerating ${\mathcal A}_t^{static}$ is possible iff $n > 2t$. This shows that asynchrony of the network demands higher connectivity of the network for the existence of PSMT protocols. Interestingly, we further show that $n > 2t$ wires are necessary and sufficient for the existence of any SSMT protocol in asynchronous network tolerating ${\mathcal A}_t^{static}$, irrespective of whether the $n$ wires are unidirectional from S to R or the $n$ wires are bi-directional. By the results of \cite{Franklin,KurosawaUSMT07}, $n > 2t$ are necessary and sufficient for the existence of SSMT in synchronous networks, irrespective of whether the $n$ wires are unidirectional from S to R or the $n$ wires are bi-directional. This shows that asynchrony of the network does not demand higher connectivity of the network for SSMT protocols.
BibTeX Citation
@article{CPVKR11,
author = {Ashish Choudhury and Arpita Patra and B. V. Ashwinkumar and Kannan Srinathan and C. Pandu Rangan},
title = {Secure message transmission in asynchronous networks},
journal = {J. Parallel Distrib. Comput.},
pages = {1067-1074},
number = {8},
volume = {71},
year = {2011},
}