A Caltech Library Service

Optimal Coding for Streaming Authentication and Interactive Communication

Franklin, Matthew and Gelles, Ran and Ostrovsky, Rafail and Schulman, Leonard J. (2014) Optimal Coding for Streaming Authentication and Interactive Communication. IEEE Transactions on Information Theory, 61 (1). pp. 133-145. ISSN 0018-9448.

Full text is not posted in this repository. Consult Related URLs below.

Use this Persistent URL to link to this item:


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.

Item Type:Article
Related URLs:
URLURL TypeDescription
Schulman, Leonard J.0000-0001-9901-2797
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.
Funding AgencyGrant Number
Office of Naval Research (ONR)N00014-11-1-0392
Binational Science Foundation (USA-Israel)2008411
B. John Garrick FoundationUNSPECIFIED
Lockheed-Martin CorporationUNSPECIFIED
Defense Advanced Research Projects Agency (DARPA)UNSPECIFIED
Subject Keywords:Data streams, reliable communication, adversarial noise, tree codes, interactive communication, blueberry codes
Issue or Number:1
Record Number:CaltechAUTHORS:20150202-090030427
Persistent URL:
Official Citation:Franklin, M.; Gelles, R.; Ostrovsky, R.; Schulman, L.J., "Optimal Coding for Streaming Authentication and Interactive Communication," Information Theory, IEEE Transactions on , vol.61, no.1, pp.133,145, Jan. 2015 doi: 10.1109/TIT.2014.2367094
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:54279
Deposited By: Ruth Sustaita
Deposited On:02 Feb 2015 17:33
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page