In the problem of "perfectly secure message transmission" (PSMT), a sender S and a recipient R 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(n^3 L) bits, where Lis the length of the message. A recent solution appearing in Crypto'06 is provably communication-optimal by achieving an asymptotic communication complexity of O(nL) bits; however, it requires the messages to be exponentially large, i.e., L = \Omega(2^n).
In this talk I'll describe 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+\eps)t, for any arbitrarily small constant \eps > 0.
This is joint work with Matthias Fitzi, Matt Franklin, and C. Harsha Vardhan.
Audio (MP3 File, Podcast Ready)
Copyright. All Rights Reserved.