Towards Optimal and Efficient Perfectly Secure Message Transmission.

Perfectly secure message transmission (PSMT), a problem formulated by Dolev, Dwork, Waarts and Yung, involves a sender ${\cal S}$ and a recipient ${\cal R}$ who are connected by n synchronous channels of which up to t may be corrupted by an active adversary. The goal is to transmit, with perfect security, a message from ${\cal S}$ to ${\cal R}$. PSMT is achievable if and only if n > 2t. For the case n > 2t, the lower bound on the number of communication rounds between ${\cal S}$ and ${\cal R}$ required for PSMT is 2, and the only known efficient (i.e., polynomial in n) two-round protocol involves a communication complexity of O(n3ℓ) bits, where ℓ is the length of the message. A recent solution by Agarwal, Cramer and de Haan is provably communication-optimal by achieving an asymptotic communication complexity of O(nℓ) bits; however, it requires the messages to be exponentially large, i.e., ℓ = Ω(2n). In this paper we present an efficient communication-optimal two-round PSMT protocol for messages of length polynomial in n that is almost optimally resilient in that it requires a number of channels n ≥ (2 + ε)t, for any arbitrarily small constant ε > 0. In this case, optimal communication complexity is O(ℓ) bits. [ABSTRACT FROM AUTHOR]