Welcome to the new version of CaltechAUTHORS. Login is currently restricted to library staff. If you notice any issues, please email coda@library.caltech.edu
Published January 2014 | public
Journal Article

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 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.

Additional Information

© 2014 IEEE. Manuscript received December 26, 2013; accepted August 18, 2014. Date of publication November 10, 2014; date of current version December 22, 2014. This material is based upon work supported by the Defense Advanced Research Projects Agency through the U.S. Office of Naval Research under Contract N00014-11-1-0392. The views expressed are those of the author and do not reflect the official policy or position of the Department of Defense or the U.S. Government. R. Ostrovsky was supported in part by the NSF under Grant 0830803, Grant 09165174, Grant 1065276, Grant 1118126, and Grant 1136174, in part by the U.S.–Israel BSF under Grant 2008411, in part by the OKAWA Foundation Research Award, in part by the IBM Faculty Research Award, in part by the Xerox Faculty Research Award, in part by the B. John Garrick Foundation Award, in part by the Teradata Research Award, and in part by the Lockheed-Martin Corporation Research Award. L. J. Schulman was supported by the NSF under Award 1038578.

Additional details

August 19, 2023
October 20, 2023