Electrical Engineering
      and Computer Sciences

Electrical Engineering and Computer Sciences


UC Berkeley


2008 Research Summary

Randomized Coding for Channels with Online Attackers

View Current Project Information

Anand Sarwate and Michael Gastpar

Modern network communication protocols send messages via long strings of packets. Introducing redundancy across packets via error-correcting codes can make the communication more robust against random errors that are independent of the message. If we instead demand that our code recover from an arbitrary pattern of errors generated by an attacker corrupting a fixed fraction of packets, then the problem becomes harder and is the focus of algebraic coding theory research. This is an adversarial model also called the arbitrarily varying channel (AVC). One coding technique that can help is randomized coding, in which the encoder and decoder share a secret key that is unknown to the attacker. We have shown previously that for offline attackers a small key size is sufficient for the Gaussian arbitrarily varying channel [1].

In this work we consider the problem of an online attacker who can read the packets as they come through the network and tamper with a fraction of them. This problem is even more difficult than the AVC, since the pattern of errors can depend on the data itself. Our goal is to prove that a small key size is also sufficient for a general class of AVCs with cost-constrained attackers. We have obtained results for the case where the adversary has access non-causally to the transmitted codeword [2], and our ongoing work focuses on attackers with correlated side information about the transmitted codeword.

A. D. Sarwate and M. Gastpar, "Randomization Bounds on Gaussian Arbitrarily Varying Channels," Proc. Int. Symp. Information Theory (ISIT 2006), Seattle, WA, July 2006.
A. D. Sarwate and M. Gastpar, "Channels with Nosy 'Noise'," Proceedings of the 2007 International Symposium on Information Theory (ISIT 2007), Nice, France, June 2007.