Optimal Coding for Streaming Authentication and Interactive Communication

Abstract

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 c <; 1, we show an efficient, constant-rate scheme that correctly decodes a (1 - c) fraction of the stream sent so far with high probability, or aborts if the noise rate exceeds c. In addition, we prove that no constant-rate scheme can recover more than a (1 - c) 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 <; 1/4 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 1/2. We complete this result by proving that no constant-rate protocol can withstand noise rates > 1/2.