Abstract
This paper explores the communication capacity of binary channels under the influence of a malicious, causal adversary who can erase a fraction $p$ of transmitted bits. We demonstrate that a minimal "jump-start"—delaying the adversary's observations by just a single bit—allows the communication rate to jump from $1-2p$ to $1-p$. Crucially, we prove that this capacity gain is only achievable if the encoder utilizes private randomness (stochastic encoding); deterministic codes remain restricted to the lower rate. Our results bridge the gap between Shannon's statistical noise models and Hamming's worst-case adversarial models.
Introduction
Information theory traditionally distinguishes between Shannon’s approach, which treats noise as a statistical phenomenon, and Hamming’s approach, which considers a worst-case adversary. This research investigates a middle ground by modeling the channel as an adversary named "Calvin." Calvin can erase up to a fraction $p$ of transmitted bits based on his observations of the channel.
The study focuses on the impact of causality and delay:
- Exactly Causal: Calvin observes the current bit $x_i$ before deciding whether to erase it. Previous literature established the capacity in this regime as $1-2p$.
- 1-bit Delay: Calvin observes only up to the previous bit $x_{i-1}$ before deciding on the current bit $x_i$.
The core contribution is determining whether this 1-bit "jump-start" for the transmitter significantly alters capacity and how the nature of the code (deterministic vs. stochastic) influences the outcome.
Methods: Stochastic Encoding and Adversarial Strategies
To establish these results, the authors employ two primary mathematical frameworks:
1. Novel Stochastic Code Construction
To prove that a rate of $1-p$ is achievable with a 1-bit delay, the authors designed a code where the encoder adds "private noise" to a base codeword. The encoder partitions bit positions and applies varying levels of Bernoulli noise to different segments. Decoding involves a two-step process: first, list decoding on a message prefix to narrow down candidates, followed by list disambiguation on the suffix using the specific private noise patterns.
2. The "Wait and Push" Jamming Strategy
To demonstrate the necessity of stochastic encoding, the authors developed a strategy for Calvin. In this scenario, Calvin "waits" until he has observed enough bits to narrow the possible messages to a small set. He then "pushes" by erasing bits strategically to make the received signal consistent with multiple messages, forcing a decoding error for any deterministic code.
Key Results and Insights
The research yields several striking insights into the nature of adversarial channels:
- The Power of the Jump-start: There is a sharp asymmetry between lookahead and delay. While lookahead for the adversary provides little benefit, a single bit of delay for the adversary significantly empowers the transmitter.
- Stochasticity is Mandatory: In binary channels, deterministic codes are too predictable. Calvin can use his knowledge of the codebook to anticipate future bits despite the delay. Stochastic encoding introduces uncertainty that Calvin cannot overcome without seeing the current bit.
- Bridging the Capacity Gap: The results show that the $1-2p$ penalty in causal channels is specifically due to the adversary's ability to see the current bit. With a 1-bit delay and stochasticity, the capacity matches that of a channel with a completely oblivious adversary ($1-p$).
Conclusion and Future Work
The paper concludes that stochastic encoding is essential to exploit an adversary's delay in binary jamming channels. While the theoretical capacity is established, several avenues for future work remain. The current stochastic codes rely on random partitions that may not be computationally efficient for real-world hardware, suggesting a need for more "structured" code versions. Additionally, it remains an open question whether stochastic encoding is strictly necessary to achieve the $1-2p$ rate in the exactly causal case, as current best-performing codes for that scenario already utilize stochasticity.
Summary updated