Message authentication is well studied in the literature, and various efficient solutions have been suggested and analyzed. This is however not the case for authentication of data streams in which the message is very long, possibly infinite, and not known in advance to the sender. Trivial solutions for authenticating data streams either suffer from a long delay at the receiver’s end or cannot perform well when the communication channel is noisy.
We suggest an efficient, constant rate, authentication scheme for data streams over a noisy channel in the shared-randomness model. We show that for every given noise rate c < 1, there exists a scheme that correctly decodes and authenticates a (1−c)-fraction of the stream sent so far, with high probability. We also show that no constant-rate authentication scheme recovers more than a (1−c)-fraction of the stream, which implies that our scheme is optimal.
Joint work with Matthew Franklin, Rafail Ostrovsky, and Leonard Schulman.
Speaker Biography
Ran Gelles is a PhD student in the Computer Science Department at UCLA. He works in the Theory and Cryptography lab with Professor Rafail Ostrovsky and Professor Amit Sahai.
He received B.Sc. in Computer Engineering in 2003, and M.Sc in Computer Science in 2009, both from Technion, Israel.