Title: Unconditionally reliable and secure message transmission in undirected synchronous networks: possibility, feasibility and optimality

Authors: Arpita Patra, Ashish Choudhury, C. Pandu Rangan, Kannan Srinathan

Addresses: Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai 600036, India. ' Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai 600036, India. ' Department of Computer Science and Engineering, Indian Institute of Technology Madras, Chennai 600036, India. ' Centre for Security, Theory and Algorithmic Research (CSTAR), International Institute of Information Technology, Gachibowli, Hyderabad – 500 032, Andhra Pradesh, India

Abstract: We study the interplay of network connectivity and the issues related to the |possibility|, |feasibility| and |optimality| for unconditionally reliable message transmission (URMT) and unconditionally secure message transmission (USMT) in an undirected synchronous network, under the influence of an adaptive mixed adversary having unbounded computing power, who can corrupt some of the nodes in the network in Byzantine, omission, fail-stop and passive fashion respectively. We consider two types of adversary, namely threshold and non-threshold. One of the important conclusions we arrive at from our study is that allowing a negligible error probability significantly helps in the |possibility|, |feasibility| and |optimality| of both reliable and secure message transmission protocols. To design our protocols, we propose several new techniques which are of independent interest.

Keywords: probabilistic reliability; information theoretic security; mixed adversary; secure message transmission; undirected synchronous networks; reliable message transmission; network connectivity.

DOI: 10.1504/IJACT.2010.038309

International Journal of Applied Cryptography, 2010 Vol.2 No.2, pp.159 - 197

Received: 24 Jul 2008
Accepted: 10 May 2009
Published online: 28 Jan 2011 *

Full-text access for editors Full-text access for subscribers Purchase this article Comment on this article