🔢 mathematics

Covert Capacity of Degraded Broadcast Channels

This paper derives a computable capacity region for the degraded broadcast channel under covert communication constraints, demonstrating that superposition coding generally outperforms time-sharing in achieving improved transmission rates against an eavesdropping adversary.

Original authors: Yossef Steinberg, Michèle Wigger

Published 2026-05-12

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Yossef Steinberg, Michèle Wigger

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Imagine a secret agent trying to send two different messages to two different friends, but there's a strict rule: no one else can even know a message is being sent.

In the world of information theory, this "no one else" is called The Warden. The Warden is constantly listening to the communication channel, looking for any statistical "fingerprint" that says, "Hey, someone is talking here!" If the Warden detects anything unusual, the communication is considered a failure.

This paper, by Yossef Steinberg and Michèle Wigger, tackles a specific puzzle: How do you send two secret messages to two different people (a "broadcast") while keeping the Warden completely in the dark?

Here is the breakdown of their findings using simple analogies.

The Setup: The Secret Radio Station

Imagine a radio station (the Transmitter) trying to talk to two listeners:

Listener A (The "Strong" receiver, who hears the signal very clearly).
Listener B (The "Weak" receiver, who hears the signal a bit fuzzily).

There is a third person, The Warden, who is also listening. The Warden knows what "silence" sounds like (let's call it the "Zero Symbol"). If the radio station sends a message, the Warden tries to detect if the sound is different from silence.

The Rule of Stealth: To remain undetected, the radio station must send messages in such a way that the Warden's ears hear a sound that is statistically indistinguishable from silence. The station can't just shout; it has to whisper so quietly that it blends perfectly with the background noise.

The Old Strategy: Taking Turns (Time-Sharing)

Before this paper, the best-known strategy for this problem was called Time-Sharing.

Think of this like a walkie-talkie where you can only talk to one person at a time.

Step 1: The station whispers a secret to Listener A for 50% of the time.
Step 2: The station whispers a secret to Listener B for the other 50% of the time.

The paper notes that for some specific types of channels (like binary channels or Gaussian channels), this "taking turns" method was proven to be the absolute best you could do. You couldn't do better than splitting your time.

The New Discovery: The "Layered Cake" (Superposition Coding)

The authors discovered that for a specific type of channel called a Degraded Broadcast Channel (where Listener B's signal is just a "fuzzier" version of Listener A's signal), Time-Sharing is actually suboptimal. You can do better.

They propose a method called Superposition Coding.

The Analogy:
Imagine you are baking a cake for two people, but you have to hide the fact that you are baking.

The Old Way (Time-Sharing): You bake a cake for Person A, eat it, then bake a cake for Person B. The smell (the signal) is strong in bursts.
The New Way (Superposition): You bake a base layer of cake that is barely noticeable (a whisper) for Person B. Then, you add a top layer of cake that is only visible to Person A (who is standing closer to the oven) but looks like just a tiny bit of extra flour to the Warden.

In technical terms:

The transmitter sends a "common" signal that is very weak (barely detectable). This helps the weaker listener (Listener B) get their message.
On top of that, they send a "private" signal intended for the stronger listener (Listener A). Because Listener A has a better connection, they can peel away the "common" layer and hear the "private" layer clearly.
The Warden, however, only hears the combined "noise" of both layers, which still looks statistically like silence.

The Big Result

The paper proves two main things:

Time-Sharing isn't always the winner: In many scenarios, simply taking turns to talk to the two listeners is inefficient. You are leaving "speed" on the table.
The "Layered Cake" is the winner: By using Superposition Coding (sending signals on top of each other), you can achieve higher data rates for both listeners simultaneously while still keeping the Warden blind.

They provide a mathematical formula (a "computable form") that tells engineers exactly how to mix these signals to get the maximum possible speed without getting caught.

A Real-World Example from the Paper

The authors ran a simulation with a specific set of numbers (a "ternary input alphabet").

They calculated the maximum speed for the "Time-Sharing" method.
They calculated the maximum speed for their new "Superposition" method.
The Result: The new method created a larger "capacity region." In their graph, the new method's boundary (the solid line) stuck out further than the old method's boundary (the dashed line).

This means that for certain types of channels, you can send more information to both friends at the same time without the Warden ever knowing you were talking.

Summary

The Problem: How to send two secret messages to two people without a spy knowing a message exists.
The Old Solution: Take turns talking to each person (Time-Sharing).
The New Solution: Talk to both at once by layering the messages (Superposition Coding).
The Conclusion: For degraded channels (where one receiver is naturally worse than the other), the new "layered" approach is strictly better than taking turns. It allows for faster, more efficient secret communication.

Technical Summary: Covert Capacity of Degraded Broadcast Channels

Problem Statement
This work addresses the fundamental limits of reliable communication over a degraded broadcast channel (DBC) in the presence of an external adversary, referred to as a "Warden." The system involves a transmitter sending individual messages to two legitimate receivers ( $Y_1$ and $Y_2$ ) while ensuring that the communication remains undetectable to the Warden ( $Z$ ). The covertness constraint requires that the Kullback–Leibler (KL) divergence between the Warden's actual output distribution and the distribution induced by a "zero symbol" (representing no communication) remains below a threshold $\delta$ .

While covert capacities for single-user channels and multi-access channels have been established, the capacity region for broadcast channels under covertness constraints remained an open problem. Previous work [11] demonstrated that for specific classes of broadcast channels (including Gaussian and binary symmetric channels, or those satisfying a specific ratio of marginal capacities), time-sharing is the optimal strategy. However, the optimality of time-sharing for general degraded broadcast channels was not established.

Methodology
The authors derive the covert capacity region by analyzing the behavior of the channel as the blocklength $n$ tends to infinity, specifically focusing on the regime where the number of covert bits scales with $\sqrt{n}$ .

Information-Theoretic Formulation: The paper defines an $(n, \nu_1, \nu_2, \epsilon, \delta)$ covert code and establishes the covert rates $L_k = \frac{\log \nu_k}{\sqrt{n\delta}}$ . The analysis relies on the assumption that the zero symbol $x_0$ is not redundant at the Warden's output and that absolute continuity holds for all input symbols.
Superposition Coding: To characterize the capacity region, the authors employ a superposition coding scheme. They construct a joint distribution $P_{U,X}$ involving an auxiliary random variable $U$ . The analysis reveals that to achieve positive covert rates, the distribution of $U$ must contain a subset $B$ whose probability mass vanishes as $n \to \infty$ , while a complementary set $A$ (containing the zero symbol) retains the bulk of the probability mass.
Asymptotic Analysis and Taylor Expansion: The core of the derivation involves a Taylor expansion of the mutual information terms ( $I(X; Y_1|U)$ and $I(U; Y_2)$ ) and the KL divergence constraint ( $D(P_Z || Q_0)$ ) around the point where the input distribution is concentrated on the zero symbol ( $x_0$ ). This expansion is performed with respect to small parameters $\mu_1$ and $\mu_2$ that scale with $1/\sqrt{n}$ .
Computable Characterization: By evaluating the second-order terms of the Taylor expansion, the authors transform the asymptotic capacity region (which involves limits as $n \to \infty$ ) into a computable region $\tilde{L}^{(I)}$ . This region is expressed in terms of $\chi^2$ -distances and Kullback–Leibler divergences between the channel transition laws and the zero-symbol distribution.

Key Contributions and Results
The primary contribution of the paper is the derivation of a computable characterization of the covert capacity region for stochastically degraded broadcast channels.

Capacity Region Characterization: Theorem 1 establishes that the covert capacity region $L^*_\delta$ is equal to the region $L^{(I)}_\delta$ , defined by specific mutual information constraints. Theorem 2 provides a computable equivalent, $\tilde{L}^{(I)}$ , which depends on the $\chi^2$ -distance of the induced Warden distribution and the KL divergences of the legitimate receivers' channels.
Sub-optimality of Time-Sharing: A significant finding is that time-sharing is not generally optimal for degraded broadcast channels. The paper proves that while time-sharing is optimal for specific cases (e.g., when the ratio of marginal capacities satisfies a certain inequality), superposition coding can strictly improve the achievable rate region in general degraded scenarios.
Numerical Evidence: The authors provide two numerical examples.
- Example 1: A ternary input channel where the superposition coding region strictly exceeds the time-sharing region boundary.
- Example 2: A binary input channel where the improvement over time-sharing (quantified by a coefficient $\gamma^*$ ) is observed whenever the condition for time-sharing optimality is violated.

Significance and Claims
The paper claims to resolve the question of optimality for time-sharing in degraded broadcast channels under covertness constraints. It demonstrates that the intuition derived from non-covert broadcast channels or specific covert channel models (where time-sharing is optimal) does not universally apply.

The authors state that their result is in a "computable form," allowing for the numerical evaluation of the capacity region without requiring asymptotic limits. They emphasize that their work extends the understanding of covert communication from single-user and multi-access scenarios to the broadcast setting, showing that advanced coding techniques like superposition coding are necessary to achieve the full capacity region in general degraded settings. The work does not propose new applications or experimental setups but focuses strictly on the theoretical capacity limits.