Codes against online adversaries

• Main Authors: Dey, B.K., Jaggi, S., Langberg, M.
• Format: Conference Proceeding
• Language: English
• Subjects: Additives; Communication channels; Decoding; Delay; Displays; Galois fields; Jamming; Reed-Solomon codes
• DOI: 10.1109/ALLERTON.2009.5394553

In this work we consider the communication of information in the presence of an online adversarial jammer. In the setting under study, a sender wishes to communicate a message to a receiver by transmitting a codeword x = (xi,..., x n ) symbol-by-symbol over a communication channel. The adversarial jammer can view the transmitted symbols x t one at a time, and can change up to a p-fraction of them. However, for each symbol x t the jammer's decision on whether to corrupt it or not (and on how to change it) must depend only on Xj for j ¿ i. This is in contrast to the ¿classical¿ adversarial jammer which may base its decisions on its complete knowledge of x. More generally, for a delay parameter d ¿ (0,1), we study the scenario in which the jammer's decision on the corruption of Xi must depend solely on xj for j ¿ i - dn. In this work, the transmitted symbols are assumed to be over a sufficiently large field F. We present a tight characterization of the amount of information one can transmit in both the 0-delay and, more generally, the d-delay online setting. We show that for 0-delay adversaries, the achievable rate asymptotically equals that of the classical adversarial model. For positive values of d, we consider two types of jamming, additive and overwrite. We also extend our results to a jam-or-listen online model, where the online adversary can either jam a symbol or eavesdrop on it.