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.

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

We provide a complete characterization of directed networks in which probabilistic reliable communication is possible. We also outline a round optimal protocol for the same.

Abstract

We consider perfect verifiable secret sharing (VSS) in a synchronous network of n processors (players) where a designated player called the dealer wishes to distribute a secret s among the players in a way that no t of them obtain any information, but any t + 1 players obtain full information about the secret. The round complexity of a VSS protocol is defined as the number of rounds performed in the sharing phase. Gennaro, Ishai, Kushilevitz and Rabin showed that three rounds are necessary and sufficient when n > 3t. Sufficiency, however, was only demonstrated by means of an inefficient (i.e., exponential-time) protocol, and the construction of an efficient three-round protocol was left as an open problem. In this paper, we present an efficient three-round protocol for VSS. The solution is based on a three-round solution of so-called weak verifiable secret sharing (WSS), for which we also prove that three rounds is a lower bound. Furthermore, we also demonstrate that one round is sufficient for WSS when n > 4t, and that VSS can be achieved in 1 + ε amortized rounds (for any ε > 0 ) when n>3t.