In traditional secure communication, the goal is cryptography: hiding the meaning of a message from an adversary. Covert communication (or deniable communication) raises the stakes. Here, the goal is to hide the very existence of the transmission. The transmitter wants to communicate with a receiver in such a way that a watchful adversary—often called a warden—cannot statistically distinguish between the channel's normal background state and the state when a message is being sent.
In standard communications, we are used to the concept of a transmission rate—a constant number of bits sent per channel use, meaning the total information scales linearly ($O(n)$) with the blocklength $n$. However, a foundational body of research shows that for covert communications, a fundamental mathematical barrier emerges: the Square Root Law. Under most standard channel conditions, the maximum amount of information that can be transmitted covertly scales only with the square root of the blocklength ($O(\sqrt{n})$).
As the duration of the communication increases, the effective rate per channel use ($\sqrt{n}/n = 1/\sqrt{n}$) inevitably vanishes to zero. Understanding why this law arises, where it applies, and how it can occasionally be bypassed is central to modern information hiding.
Why the Square Root Law Emerges
To understand why the square root limit exists, we must look at how a warden detects a signal using statistical hypothesis testing.
Imagine a baseline channel that is completely silent, outputting only background noise (such as Additive White Gaussian Noise). When the transmitter is inactive, the warden observes $n$ samples from an "innocent" noise distribution, $P_0$. When the transmitter sends a message, it injects a small amount of signal power, shifting or altering the distribution to $P_1$.
The warden's goal is to decide whether the collected samples came from $P_0$ or $P_1$. The fundamental metric governing the warden's detection error is the statistical distance—specifically the Kullback-Leibler (KL) divergence—between the two multi-sample distributions, denoted as $D(P_1^n \parallel P_0^n)$. For $n$ independent channel uses, the total statistical divergence accumulates linearly with the number of samples:
$$D(P_1^n \parallel P_0^n) = n \cdot D(P_1 \parallel P_0)$$
For a small signal with power $P$, the divergence per single channel use $D(P_1 \parallel P_0)$ scales quadratically with the power, behaving as $O(P^2)$. This is because the warden is looking at changes in the variance or mean of the noise, where small deviations are masked by the background distribution. Substituting this back into the total divergence formula gives:
$$\text{Total Divergence} \approx n \cdot O(P^2)$$
To remain covert, the transmitter must ensure that the warden cannot reliably distinguish between the two states, which requires keeping the total divergence bounded by a small constant. If the total divergence grows arbitrarily large, the warden will eventually detect the transmission with near-perfect certainty. To keep $n \cdot P^2 \le \text{constant}$, the allowed signal power per channel use must scale down as the blocklength grows:
$$P = O\left(\frac{1}{\sqrt{n}}\right)$$
At very low signal-to-noise ratios (SNR), Shannon's channel capacity scales linearly with the signal power $P$. Therefore, the number of bits that can be reliably transmitted per channel use is also proportional to $P$, or $O(1/\sqrt{n})$.
Finally, to find the total amount of information that can be sent over the entire transmission, we multiply the bits per channel use by the total number of channel uses $n$:
$$\text{Total Covert Bits} = n \cdot O\left(\frac{1}{\sqrt{n}}\right) = O(\sqrt{n})$$
This is the intuition behind the fundamental limits established by Wornell et al.. Attempting to transmit at a constant linear rate eventually provides enough statistical evidence for an adversary to detect the transmission.
Universality Across Information Hiding
The Square Root Law is not an artifact of Gaussian noise channels; it is a universal statistical constraint that manifests across diverse communication mediums and problem formulations.
- Digital Steganography: In multimedia security, steganography involves hiding data inside carrier files like digital images. As reviewed by Bas et al., the theoretical capacity for secure data embedding is strictly governed by the square root law. The safe payload size can only scale with the square root of the host content's size (e.g., the number of pixels), because larger images give steganalysis algorithms more samples to detect statistical anomalies.
- Network Packet Streams: Instead of physical signals, covert data can be embedded into network traffic. Soltani et al. demonstrated that if a covert sender attempts to hide information by altering packet sizes within a stream of $n$ packets, the maximum volume of hidden data is restricted to $O(\sqrt{n})$ bits. Pushing past this limit alters the aggregate packet size distribution enough for a monitoring warden to detect the channel.
- Multi-User Networks: The constraint persists when moving from point-to-point links to multi-user networks. For instance, Tan et al. proved that the square root scaling law dictates the fundamental limit for covert communication over broadcast channels. Similarly, Zhang et al. showed that when multiple parties attempt to generate shared secret keys covertly over a multiple-access channel, the total number of secret bits can only grow as $O(\sqrt{n})$.
- State Masking: The law even applies when the goal is not to transmit a message, but to hide environmental changes. In state-masking communication, a transmitter tries to send data over a compound channel while preventing an adversary from figuring out the channel's underlying state. Salehkalaibar et al. proved that the total information transmitted while successfully masking the state is strictly bound to a square-root scaling law relative to the number of channel uses.
Engineering Within the Law
Because the square root law forces the transmission rate to zero asymptotically, practical system design focuses on two fronts: constructing efficient codes that hit this upper bound, and optimizing physical-layer parameters to maximize the constant factor in front of the $\sqrt{n}$.
To address the coding challenge, Zhang et al. developed the first computationally efficient, polynomial-time coding scheme for deniable communication. They utilized a concatenated coding structure—combining systematic Reed-Solomon outer codes with low-weight random inner codes—to achieve the optimal $O(\sqrt{n})$ scaling for message length while keeping encoding and decoding mathematically tractable.
At the physical layer, researchers use multi-antenna systems to maximize throughput within the square-root envelope. Ma et al. designed robust beamforming strategies that leverage a legitimate "cover" user's traffic to shield the covert signal, optimizing the transmission power even when the warden's channel state information is imperfect.
Going further into electromagnetic environments, Liu et al. demonstrated that extremely large-scale reconfigurable intelligent surfaces (XL-RIS) can exploit near-field spherical-wave propagation. By leveraging unique beam diffraction patterns, they showed how to maximize the covert payload delivered to a receiver even when a warden is positioned directly in the line of sight.
Breaking the Square Root Barrier
Is it ever possible to escape the square root law and achieve a positive, constant communication rate ($O(n)$) covertly? The answer is yes, but it requires changing the baseline assumptions about what the warden observes.
+-------------------------------------------------------------------------+
| BASELINE CONDITIONS |
+----------------------------------+--------------------------------------+
| Standard / Silent Baseline | Dynamic / Uncertain Baseline |
| (Warden expects static noise) | (CSI, Packet Timing, Jammers) |
+----------------------------------+--------------------------------------+
| Statistical evidence accumulates | Signal hides inside the natural |
| linearly with blocklength n. | fluctuations or existing structures. |
+----------------------------------+--------------------------------------+
| Result: O(sqrt(n)) Capacity | Result: O(n) Linear Capacity |
+----------------------------------+--------------------------------------+
Exploiting Channel-State Information (CSI)
The square root law assumes the background noise distribution is static and perfectly known to the warden. Wang et al. demonstrated that if the transmitter possesses prior knowledge of fluctuating channel states (such as time-varying fading or environmental noise), it can opportunistically hide its signal inside these natural variations. Because the warden cannot distinguish whether an increase in energy is due to a transmission or a natural channel fluctuation, the transmitter can achieve a constant, positive transmission rate without increasing the probability of detection.
Timing Manipulation vs. Packet Insertion
In network traffic channels, the method of modulation dictates the scaling law. As noted earlier, inserting new packets into a stream alters the total packet count distribution, subjecting the channel to the $O(\sqrt{n})$ limit. However, Soltani et al. proved that if the transmitter instead manipulates the timing of existing packets in a renewal packet stream, it can achieve a linear transmission rate ($O(n)$). Because the total number of packets remains identical to the innocent traffic, the statistical footprint is significantly smaller, allowing more data to pass undetected.
Stealth vs. Covert Communication
Finally, the fundamental definition of the baseline state matters. Song et al. drew a distinction between "covert" communication (where the baseline state is silence) and "stealthy" communication (where the baseline state is an active, non-zero distribution, such as a network experiencing adversarial jamming). When the environment is already noisy and dynamic, the transmitter does not have to worry about waking a silent channel; it merely has to blend into the ongoing disruption, unlocking linear throughput scaling.
Key Foundational Work
Fundamental Limits of Communication with Low Probability of Detection (2015) — contributed 3 concept elements to this direction.
Covert communications on renewal packet channels (2016) — contributed 2 concept elements to this direction.
Computationally Efficient Deniable Communication (2016) — contributed 1 concept elements to this direction.