Abstract

We consider the problem of reliable message transmission between two synchronous players connected by n wires, some t< 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.

Abstract

In this paper, we study the problem of perfectly reliable message transmission(PRMT) and perfectly secure message transmission(PSMT) between a sender S and a receiver R in a synchronous network, where S and R are connected by n vertex disjoint paths called wires, each of which facilitates bidirectional communication. We assume that atmost t of these wires are under the control of adversary. We present two-phase-bit optimal PRMT protocol considering Byzantine adversary as well as mixed adversary. We also present a three phase PRMT protocol which reliably sends a message containing l field elements by overall communicating O(l) field elements. This is a significant improvement over the PRMT protocol proposed in [10] to achieve the same task which takes log(t) phases. We also present a three-phase-bit-optimal PSMT protocol which securely sends a message consisting of t field elements by communicating O(t 2) field elements.