Information Security and Cryptography Research Group

Secure message transmission in asynchronous networks

Ashish Choudhury, Arpita Patra, B. V. Ashwinkumar, Kannan Srinathan, and C. Pandu Rangan

J. Parallel Distrib. Comput., vol. 71, no. 8, pp. 1067-1074, 2011.

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,
}