Optimal Coding for Streaming Authentication and Interactive Communication

摘要

We consider the task of communicating a data stream—a long, possibly infinite message not known in advance to the sender—over a channel with adversarial noise. For any given noise rate , we show an efficient, constant-rate scheme that correctly decodes a fraction of the stream sent so far with high probability, or aborts if the noise rate exceeds . In addition, we prove that no constant-rate scheme can recover more than a fraction of the stream sent so far with non-negligible probability, which makes our scheme optimal in that aspect. The parties are assumed to preshare a random string unknown to the channel. Our techniques can also be applied to the task of interactive communication (two-way communication) over a noisy channel. In a recent paper (Braverman and Rao, STOC11), the possibility of two-party interactive communication as long as the noise level is was shown. By allowing the parties to preshare some private random string, we extend this result and construct a (nonefficient) constant-rate interactive protocol that succeeds with overwhelming probability against noise rates up to . We complete this result by proving that no constant-rate protocol can withstand noise rates .