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