Abstract
This work we consider the communication of information in the
presence of a causal adversarial jammer. In the setting under study,
a sender wishes to communicate a message to a receiver by transmitting
a codeword x=(x_1,...,x_n) symbol-by-symbol over a communication
channel. The adversarial jammer can view the transmitted symbols x_i
one at a time, and can change up to a p-fraction of them. However, the
decisions of the jammer must be made in an online or causal manner.
Namely, for each symbol x_i the jammer's decision on whether to
corrupt it or not (and on how to change it) must depend only on x_j
for j <= i.
This is in contrast to the "classical" adversarial jammer which may
base its decisions on its complete knowledge of x. We consider two
settings.
For the binary channel we present a non-trivial upper bound on the
amount of information that can be communicated. We show that the
achievable rate can be asymptotically no greater than
min{1-H(p),(1-4p)^+}. Here H(.) is the binary entropy function, and
(1-4p)^+ equals 1-4p for p 0.25, and 0 otherwise. For
"large"-alphabet channels, for a delay parameter 0<1,
we study the
scenario in which the jammer's decision on the corruption of x_i must
depend solely on x_j for j < i - dn. In this work, we initiate the
study of codes for online adversaries, and 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 prove
tight results for both additive and overwrite jammers when the
transmitted symbols are assumed to be over a sufficiently large field
F. Finally, we extend our results to a jam-or-listen online model,
where the online adversary can either jam a symbol or eavesdrop on it.
We again provide a tight characterization of the achievable rate for
this model. The rate-regions we prove for each model are
informational-theoretic in nature and hold for computationally
unbounded adversaries. The rate regions are characterized by "simple"
piecewise linear functions of p and d. The codes we construct to
attain the optimal rate for
each scenario are computationally efficient.