Secure message transmission in asynchronous networks

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 Atstatic, 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 A tstatic should not get any information about m, whatsoever, 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 and Abu-Amara (1995) [37] have given a PSMT protocol in an asynchronous network tolerating Atstatic, 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 Atstatic 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 A tstatic is possible iff n>3t. This is quite surprising because for synchronous networks, by the results of Dolev et al. (1993) [16], if all the wires are unidirectional (directed from S to R), then PSMT tolerating Atstatic is possible iff n>3t, where as if all the wires are bi-directional then PSMT tolerating Atstatic 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 A tstatic , irrespective of whether the n wires are unidirectional from S to R or the n wires are bi-directional. By the results of Franklin and Wright (2000) [18] and Kurosawa and Suzuki (2009) [22], n>2t wires 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. © 2011 Elsevier Inc. All rights reserved.