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 S and a recipient 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 S to 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 S and 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 e ε > 0. In this case, optimal communication complexity is O(ℓ) bits. © International Association for Cryptologic Research 2007.