Optimal Perfectly Secure Message Transmission

In the perfectly secure message transmission (PSMT) problem, two synchronized non-faulty players (or processors), the SenderS and the ReceiverR 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 phases 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 = \left(\frac{n\ell}{n-2t}\right)$ bits. While no known protocol is simultaneously optimal in both communication and phase complexity, we present one such optimum protocol for the case n=2t+1 when the size of message is large enough, viz., ℓ = Ω(tlog t) bits; that is, our optimal protocol has n=2t+1, r=2 and b=O(nℓ) 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 \geq \left(\frac{n\ell}{n-2t}\right)$ 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).