Upper Bounds on the Capacity of Binary Channels With Causal Adversaries

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

Sure, here's a blog-style summary of the paper "Upper Bounds on the Capacity of Binary Channels With Causal Adversaries":

TL;DR

This paper investigates the fundamental limits of reliable communication over binary channels when an adversary can causally corrupt transmitted bits. The authors introduce a novel "babble-and-push" jamming strategy to derive tighter upper bounds on the channel capacity, showing that a causal adversary is strictly stronger than a delayed adversary.

What Problem Does This Paper Address?

Imagine sending a message over a noisy channel, but the noise isn't random. Instead, it's controlled by a malicious adversary who can flip bits. This paper focuses on a specific type of adversary: one who can only corrupt a bit after observing the bits transmitted so far. This "causal" constraint is more realistic than an adversary who knows the entire message beforehand or one who jams randomly. The challenge is to understand the maximum rate at which information can be reliably transmitted under such a causal, bit-flipping adversary, especially when the sender and receiver don't share any secret randomness. Previous work had established bounds, but this paper aims to tighten these bounds and better understand the adversary's power.

Methods

The core of the paper's contribution lies in a new jamming strategy for the adversary, termed "babble-and-push." This strategy has two phases:

  1. Babble Phase: The adversary injects noise (flips bits) in a way that increases the receiver's uncertainty about the transmitted message. This is done by mimicking a binary symmetric channel for a portion of the transmission.
  2. Push Phase: After gaining some information about the transmitted bits, the adversary "pushes" the received bits towards a chosen codeword. This involves strategically flipping bits to make it harder for the receiver to decode the original message.

The authors use information-theoretic tools, including entropy calculations and a version of Plotkin's bound, to analyze the effectiveness of this strategy. They prove that no matter what coding scheme Alice and Bob use (even probabilistic ones), this "babble-and-push" attack can force a decoding error probability that is bounded away from zero, thus establishing an upper bound on the achievable communication rate. They also analyze the case of deterministic codes, achieving a tighter error bound.

Datasets

Not discussed in the paper.

Key Insights and Ideas

  • Causal Adversary is Powerful: The paper demonstrates that a causal adversary, even with a limited bit-flipping budget, can significantly degrade communication rates compared to simpler noise models or even delayed adversaries.
  • The "Babble-and-Push" Strategy: This novel jamming technique is the key to their improved bounds. It cleverly combines increasing uncertainty with targeted manipulation of the received signal.
  • Tighter Bounds: The derived upper bounds are shown to be tighter than previous results, particularly for certain ranges of the adversary's jamming capability.
  • Stochastic vs. Deterministic Codes: The paper provides bounds for both general stochastic coding schemes and specifically for deterministic codes, showing that the adversary's strategy is effective against both.

Key Results

The paper establishes an upper bound on the capacity of binary causal adversary channels. For a jamming constraint $p$, the capacity $C(p)$ is shown to be:

  • $C(p) = \min_{p \in [0,p]} \alpha(p,p) (1 - H(\alpha(p,p)))$ for $p \in [0, 1/4]$, where $\alpha(p,p) = 1 - 4(p-p)$.
  • $C(p) = 0$ for $p > 1/4$.

The paper also shows that for $p > 0.0804$, the causal adversary is strictly stronger than a delayed adversary. For deterministic codes, they show that the average error probability can be bounded by $\epsilon O(1/\epsilon)$, which is an improvement over the bounds for stochastic codes.

Limitations and Future Work

The authors acknowledge that their analysis for stochastic codes provides a lower bound on the error probability for a given block length, rather than a direct capacity calculation. They also note that their techniques do not fully separate the capacity regions for causal and delayed adversaries when $p$ is small (less than 0.0804). Future work could explore more efficient coding schemes that can better withstand such causal adversarial attacks and further investigate the precise capacity regions for different ranges of $p$. The paper also highlights that the "large alphabet" setting, where communication is generally easier, has been fully characterized, but the binary alphabet case remains more challenging.

Summary updated

Abstract

In this paper, 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 <b xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</b> =( <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">1</sub> , ..., <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">n</sub> ) 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 <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">xi</i> one at a time and can change up to a <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">p</i> -fraction of them. However, the decisions of the jammer must be made in a causal manner. Namely, for each bit <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</sub> , the jammer's decision on whether to corrupt it or not must depend only on <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</i> <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</sub> for <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">j</i> ≤ <i xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">i</i> . This is in contrast to the “classical” adversarial jamming situations in which the jammer has no knowledge of <b xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</b> , or knows <b xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">x</b> completely. In this study, 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