Zero-Error Communication over Adversarial MACs

Yihan Zhang

Abstract

This paper investigates the fundamental limits of communication over a two-user Multiple Access Channel (MAC) subject to an omniscient, malicious adversary. Unlike classical Shannon theory, which models noise stochastically, this work adopts a zero-error criterion where no probability of error is tolerated under adversarial jamming. By bridging information theory and combinatorial coding theory, the author provides a complete characterization of the dimensionality (zero-th order asymptotics) of the zero-error capacity region. The results reveal the exact conditions under which both, one, or neither transmitter can achieve positive communication rates, highlighting the role of "good distributions" and geometric duality in determining achievability.

Introduction

In classical information theory, channel noise is typically modeled as a random process. However, in security-sensitive applications, noise may be injected by a malicious jammer who possesses full knowledge of the transmitted signals and actively seeks to disrupt communication. This paper addresses the two-transmitter Multiple Access Channel (MAC) under such an omniscient adversarial model. The system operates under a strict zero-error criterion with deterministic encoders and decoders, precluding the use of shared randomness or secret keys. The central challenge lies in identifying the conditions under which communication is even possible—specifically, when the capacity region has a non-zero interior or dimension.

System Model

The model consists of two encoders, $Enc_1$ and $Enc_2$, transmitting messages $m^1$ and $m^2$ respectively. An omniscient jammer observes the transmitted sequences $\underline{x}^1$ and $\underline{x}^2$ and selects a jamming sequence $\underline{s}$ to influence the channel output $\underline{y}$. The decoder must then recover both messages without error.

Block diagram of the two-user Multiple Access Channel (MAC) with an omniscient jammer.

Methodology

The paper employs a combination of Shannon-theoretic techniques and combinatorial coding theory to establish its results.

  • Achievability: To prove that positive rates are possible, the author utilizes random coding with expurgation and "coded time-sharing." Codes are sampled from specific mixtures of product distributions, termed "good distributions," ensuring that joint codeword types concentrate around distributions that the adversary cannot confuse.
  • Converse: The converse proof establishes the impossibility of communication by generalizing the classical Plotkin bound to the multiuser setting. Using Ramsey's theorem to extract structured "equicoupled" subcodes, the author leverages a novel geometric duality between the cone of "good distributions" and "co-good tensors" to prove that if a code fails to utilize these distributions, its rate must asymptotically vanish.

Key Insights

  • Confusability Sets: The paper rigorously defines joint and marginal confusability, characterizing the distributional conditions under which an adversary can force the receiver to confuse different pairs of codewords.
  • Sufficiency of "Good" Distributions: A critical finding is that only a specific class of distributions—convex combinations of independent random variables—needs to be considered. If positive rates are not achievable with these distributions, they are not achievable at all.
  • Geometric Duality: The duality between "good distributions" and "co-good tensors" provides the mathematical framework for the generalized Plotkin bound.
  • Non-convexity: Unlike standard MAC capacity regions, the adversarial zero-error capacity region can be highly non-convex, sometimes appearing as an 'L' shape where users can communicate individually but not simultaneously.

Capacity Region Characterization

The author provides a complete five-case characterization of the capacity region's dimensionality based on the intersection of "good distributions" and "confusability sets":

  1. 2D Region: Both users can transmit at positive rates simultaneously (non-empty interior).
  2. 1D 'L' Shape: Users can transmit individually, but joint transmission is impossible (two perpendicular line segments along the axes).
  3. 1D Segment (User 1): Only the first user can achieve a positive rate.
  4. 1D Segment (User 2): Only the second user can achieve a positive rate.
  5. 0D Point: The adversary can block all communication, resulting in a capacity of (0,0).

Conclusion and Future Work

While this work characterizes the positivity of the capacity region, it does not determine the exact maximum rates (first-order asymptotics). The model is currently constrained to finite alphabets and deterministic channels. Future research directions include extending these results to continuous alphabets, exploring stochastic channels where maximum error is not equivalent to zero error, and considering "myopic" adversaries with limited knowledge of the transmitted sequences.

Summary updated

BibTeX
@article{zhang2021zero,
  author = {Yihan Zhang},
  title = {{Zero-Error Communication over Adversarial MACs}},
  journal = {IEEE Trans. Information Theory},
  year = {2021},
  doi = {10.1109/tit.2023.3257239},
}
Figure