ETH Zürich » Computer Science » Theory » Cryptography

Publications: Abstract

Secure message transmission in asynchronous networks

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

In the {\it Perfectly Secure Message Transmission} (PSMT) problem, a sender {\bf S} and a receiver {\bf R} are part of a distributed network and connected through $n$ node disjoint paths, also called as {\it wires}, among which at most $t$ wires are controlled by a static, Byzantine adversary ${\cal A}_t^{static}$, having {\it unbounded computing power}. {\bf S} has a message $m$, which {\bf S} intends to send to {\bf R}. The challenge is to design a protocol, such that at the end of the protocol, {\bf R} should correctly output $m$ without any error (perfect reliability) and ${\cal A}_t^{static}$ should not get {\it any} information about $m$, what so ever, in information theoretic sense (perfect security).

The problem of {\it Statistically Secure Message Transmission} (SSMT) is same as PSMT, except that {\bf R} should correctly output $m$ with very high probability. Sayeed et al. \cite{SayeedAsynchronous} have given a PSMT protocol in an asynchronous network tolerating ${\cal A}_t^{static}$, where {\bf S} and {\bf 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 {\bf S} to {\bf R}, then any PSMT protocol tolerating ${\cal 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 ${\cal 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 {\bf S} to {\bf R}), then PSMT tolerating ${\cal A}_t^{static}$ is possible iff $n > 3t$, where as if all the wires are bi-directional then PSMT tolerating ${\cal A}_t^{static}$ is possible iff $n > 2t$. This shows that {\it 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 ${\cal A}_t^{static}$, irrespective of whether the $n$ wires are unidirectional from {\bf S} to {\bf 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 {\bf S} to {\bf R} or the $n$ wires are bi-directional. This shows that {\it asynchrony of the network does not demand higher connectivity of the network for SSMT protocols}.