Upper Bounds on the Capacity of Binary Channels with Causal Adversaries

Bikash Kumar Dey, Sidharth Jaggi, Michael Langberg, Anand D. Sarwate

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_1,...,x_n)$ bit-by-bit over a communication channel. The sender and the receiver do not share common randomness. The adversarial jammer can view the transmitted bits $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 a causal manner. Namely, for each bit $x_i$ the jammer's decision on whether to corrupt it or not must depend only on $x_j$ for $j \leq i$. This is in contrast to the "classical" adversarial jamming situations in which the jammer has no knowledge of $(x_1,...,x_n)$, or knows $(x_1,...,x_n)$ completely. In this work, we present upper bounds (that hold under both the average and maximal probability of error criteria) on the capacity which hold for both deterministic and stochastic encoding schemes.

Introduction

Information theory typically deals with two noise extremes: the Shannon model, where noise is stochastic and independent, and the Hamming model, where an omniscient adversary flips bits strategically with full knowledge of the codeword. This research investigates the intermediate causal adversary.

In this model, a jammer (Calvin) observes Alice's bits sequentially. While Calvin has a budget to flip a $p$-fraction of bits, he is constrained by causality: his decision at time $i$ depends only on the history $x_1, \dots, x_i$. The central question is whether this causality constraint renders the adversary as weak as random noise or as potent as a worst-case jammer. While previous literature suggested that even minimal delay allows Alice to reach Shannon capacity, this work focuses on the zero-delay scenario.

The "Babble-and-Push" Strategy

The authors derive their upper bound by introducing a two-phase jamming strategy:

  1. The Babble Phase: Initially, Calvin acts as a Binary Symmetric Channel (BSC), flipping bits randomly with probability $\bar{p}$. This "babbling" consumes part of his budget but crucially increases the receiver's uncertainty (entropy), making it harder to distinguish the true codeword.
  2. The Push Phase: Calvin then identifies a "fake" codeword consistent with the received history and uses his remaining budget to "push" the transmission toward this alternative.

This strategy aims for symmetrization, where the received signal becomes equally likely to have originated from the actual message or the fake one, forcing the receiver to guess and ensuring a high error probability. The analysis utilizes the Plotkin bound and probabilistic tools to prove effectiveness even against stochastic encoding.

Key Results

The primary contribution is a tighter upper bound on the capacity $C(p)$. For a noise fraction $p \in [0, 1/4]$, the capacity is bounded by: $$C(p) \leq \min_{\bar{p} \in [0,p]} \alpha(p, \bar{p}) \left[ 1 - H\left(\frac{\bar{p}}{\alpha(p, \bar{p})}\right) \right]$$ where $\alpha(p, \bar{p}) = 1 - 4(p - \bar{p})$.

Comparison of the new upper bound against the Shannon capacity $1-H(p)$ and the previous HL bound.

As shown in the figure, the new bound is strictly tighter than the previous "HL bound" (based on wait-and-push strategies). Key observations include:

  • The 0.0804 Threshold: For $p < 0.0804$, the bound matches the Shannon capacity $1-H(p)$. Beyond this point, the causal adversary becomes strictly more powerful than random noise.
  • Zero Capacity: At $p = 1/4$, the capacity reaches zero, confirming that an adversary flipping 25% of bits can completely block communication.
  • Resilience to Randomness: The bound holds even if Alice employs private randomness (stochastic coding) to obscure her codewords.

Conclusion and Future Work

This work demonstrates that causality is not a complete defense against adversarial jamming. By injecting noise early ("babbling"), a jammer can effectively prepare for a decisive "push" later in the transmission.

However, a gap remains between these upper bounds and the best known achievable rates. Furthermore, the current techniques do not improve upon the Shannon limit in the very low-noise regime ($p < 0.0804$). While the binary case remains a significant challenge, these results provide the most accurate characterization to date of the limits of communication under causal adversarial constraints.

Summary updated

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_1,...,x_n)$ bit-by-bit over a communication channel. The sender and the receiver do not share common randomness. The adversarial jammer can view the transmitted bits $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 a causal manner. Namely, for each bit $x_i$ the jammer's decision on whether to corrupt it or not must depend only on $x_j$ for $j \leq i$. This is in contrast to the "classical" adversarial jamming situations in which the jammer has no knowledge of $(x_1,...,x_n)$, or knows $(x_1,...,x_n)$ completely. In this work, we present upper bounds (that hold under both the average and maximal probability of error criteria) on the capacity which hold for both deterministic and stochastic encoding schemes.
BibTeX
@article{dey2013upper,
  author = {Bikash Kumar Dey and Sidharth Jaggi and Michael Langberg and Anand D. Sarwate},
  title = {{Upper Bounds on the Capacity of Binary Channels with Causal Adversaries}},
  journal = {IEEE Trans. Information Theory},
  year = {2013},
  doi = {10.1109/tit.2013.2245721},
}
Figure