Optimal perfectly secure message transmission

In the perfectly secure message transmission (PSMT) problem, two synchronized non-faulty players (or processors), the Sender S and the Receiver R are connected by n wires (each of which facilitates 2-way communication); S has an -bit message that he wishes to send to R; after exchanging messages in phases1 R should correctly obtain S's message, while an adversary listening on and actively controlling any set of t (or less) wires should have no information about S's message. We measure the quality of a protocol for securely transmitting an -bit message using the following parameters: the number of wires n, the number of phases r and the total number of bits transmitted b. The optima for n and r are respectively 2t +1 and 2. We prove that any 2-phase reliable message transmission protocol, and hence any secure protocol, over n wires out of which at most t are faulty is required to transmit at least b = (nl/n-2t) bits. While no known protocol is simultaneously optimal in both communication and phase complexity, we present one such optimum protocol for the case n = 2l+1 when the size of message is large enough, viz., l = Ω(tlogt) bits; that is, our optimal protocol has n = 2t+l, r = 2 and b = O(nl) bits. Note that privacy is for free, if the message is large enough. We also demonstrate how randomness can effectively improve the phase complexity. Specifically, while the (worst-case) lower bound on r is 2, we design an efficient optimally tolerant protocol for PSMT that terminates in a single phase with arbitrarily high probability. Finally, we consider the case when the adversary is mobile, that is, he could corrupt a different set of t wires in different phases. Again, the optima for n and r are respectively 2t+1 and 2; However we show that b ≥ ( nl/n-2t) bits irrespective of r. We present the first protocol that is (asymptotically) optimum in b for n = 2t +1. Our protocol has a phase complexity of O(t). © International Association for Cryptologic Research 2004.