We consider the problem of reliable message transmission between two synchronous players connected by n wires, some t < frac(n, 2) of which may be faulty. We show how to get reliability "for free"-reliable transmission of b bits involves a total communication of only O (b) bits, when b is large enough. We also construct an efficient Perfectly Secure Message Transmission Protocol. © 2006 Elsevier B.V. All rights reserved.

C Pandu Rangan

Department of Computer Science and Engineering

Arvind Narayanan

Bit error rate

Fault tolerant computer systems

reliability

Security of data

RELIABLE TRANSMISSION

Security

SYNCHRONOUS PLAYERS

Data transfer

IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Information Processing Letters

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. Copyright © 2010 Inderscience Enterprises Ltd.

Fulltext

International Journal of Applied Cryptography

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

Proceedings of the twenty-second annual symposium on Principles of distributed computing - PODC '03

Journal	Information Processing Letters
ISSN	00200190
Open Access	No