Channel
Codes Against Causal Adversaries
By

Professor
Sidharth Jaggi

Department
of Information Engineering

The
Chinese University of Hong Kong


Date:
Mar 9, 2009 
Time:
4:30pm  5:30 pm 
Venue:
Rm. 121, Ho Sin Hang Engineering Building, CUHK 
Abstract
:
In
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) symbolbysymbol over a communication
channel. The adversarial jammer can view the transmitted
symbols x_i one at a time, and can change up to a
pfraction 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 nontrivial upper bound on the amount
of information that can be communicated. We show that
the achievable rate can be asymptotically no greater
than min{1H(p),(14p)^+}. Here H(.) is the binary
entropy function, and (14p)^+ equals 14p 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 0delay
and, more generally, the ddelay 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 jamorlisten 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 rateregions
we prove for each model are informationaltheoretic
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.
