CaltechAUTHORS
  A Caltech Library Service

Optimal Coding for Streaming Authentication and Interactive Communication

Franklin, Matthew and Gelles, Ran and Ostrovsky, Rafail and Schulman, Leonard J. (2013) Optimal Coding for Streaming Authentication and Interactive Communication. Electronic Colloquium on Computational Complexity . report 104. ISSN 1433-8092. https://resolver.caltech.edu/CaltechAUTHORS:20170427-170911967

[img] PDF - Published Version
See Usage Policy.

940Kb

Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20170427-170911967

Abstract

Error correction and message authentication are well studied in the literature, and various efficient solutions have been suggested and analyzed. This is however not the case for data streams in which the message is very long, possibly infinite, and not known in advance to the sender. Trivial solutions for error-correcting and authenticating data streams either suffer from a long delay at the receiver's end or cannot perform well when the communication channel is noisy. In this work we suggest a constant-rate error-correction scheme and an efficient authentication scheme for data streams over a noisy channel (one-way communication, no feedback) in the shared-randomness model. Our first scheme does not assume shared randomness and (non-efficiently) recovers a (1−2c)-fraction prefix of the stream sent so far, assuming the noise level is at most c12 . The length of the recovered prefix is tight. To be able to overcome the c=12 barrier we relax the model and assume the parties pre-share a secret key. Under this assumption we show that for any given noise rate c1, there exists a scheme that correctly decodes a (1−c)-fraction of the stream sent so far with high probability, and moreover, the scheme is efficient. Furthermore, if the noise rate exceeds c, the scheme aborts with high probability. We also show that no constant-rate authentication scheme recovers more than a (1−c)-fraction of the stream sent so far with non-negligible probability, thus the relation between the noise rate and recoverable fraction of the stream is tight, and our scheme is optimal. Our techniques also apply to the task of interactive communication (two-way communication) over a noisy channel. In a recent paper, Braverman and Rao [STOC 2011] show that any function of two inputs has a constant-rate interactive protocol for two users that withstands a noise rate up to 1/4. By assuming that the parties share a secret random string, we extend this result and construct an interactive protocol that succeeds with overwhelming probability against noise rates up to 1/2. We also show that no constant-rate protocol exists for noise rates above 1/2 for functions that require two-way communication. This is contrasted with our first result in which computing the "function" requires only one-way communication and the noise rate can go up to 1.


Item Type:Article
Related URLs:
URLURL TypeDescription
https://eccc.weizmann.ac.il/report/2012/104/PublisherReport
ORCID:
AuthorORCID
Schulman, Leonard J.0000-0001-9901-2797
Additional Information:Supported in part by NSF grants 0830803, 09165174, 1065276, 1118126 and 1136174, US-Israel BSF grant 2008411, OKAWA Foundation Research Award, IBM Faculty Research Award, Xerox Faculty Research Award, B. John Garrick Foundation Award, Teradata Research Award, and Lockheed-Martin Corporation Research Award. 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. Supported in part by NSF Award 1038578.
Funders:
Funding AgencyGrant Number
NSFCNS-0830803
NSF09165174
NSFIIS-1065276
NSFCNS-1118126
NSFCNS-1136174
Binational Science Foundation (USA-Israel)2008411
Okawa FoundationUNSPECIFIED
IBMUNSPECIFIED
XeroxUNSPECIFIED
B. John Garrick FoundationUNSPECIFIED
TeradataUNSPECIFIED
Lockheed-Martin CorporationUNSPECIFIED
Office of Naval Research (ONR)N00014-11-1-0392
NSFCCF-1038578
Subject Keywords:data stream, private codes, adversarial noise, authentication, tree codes, interactive communication
Record Number:CaltechAUTHORS:20170427-170911967
Persistent URL:https://resolver.caltech.edu/CaltechAUTHORS:20170427-170911967
Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:77034
Collection:CaltechAUTHORS
Deposited By: Kristin Buxton
Deposited On:28 Apr 2017 14:58
Last Modified:09 Mar 2020 13:19

Repository Staff Only: item control page