In standard information theory, we focus on how much data can be sent reliably over a noisy channel. But in covert communication, the goal is more ambitious: the transmitter (Alice) must send a message to a receiver (Bob) such that a watchful adversary (Willie the Warden) cannot even detect that a transmission is taking place.
This requirement introduces a fundamental bottleneck known as the Square Root Law. While standard communication allows for a constant rate of information (linear scaling with time), covert communication is typically restricted to sending only $O(\sqrt{n})$ bits over $n$ channel uses.
The Statistical Barrier to Secrecy
To understand why covert communication is so much harder than encrypted communication, we must look at the problem from the perspective of the Warden. Willie is performing a statistical hypothesis test: is the observed signal just background noise, or is it noise plus a message?
As established by Gregory Wornell, Ligong Wang, and Lizhong Zheng in Fundamental Limits of Communication with Low Probability of Detection, if Alice sends at a constant power, Willie’s ability to distinguish the signal from the noise improves as he collects more samples. Eventually, the statistical evidence becomes overwhelming, and Willie can detect the transmission with near-certainty.
To remain undetected, Alice must ensure that the "distance" between the distribution of pure noise and the distribution of her signal-plus-noise remains small. Mathematically, this is often measured using Total Variation Distance (TVD) or Relative Entropy. As Xinchun Yu and Shuangqin Wei demonstrate in their finite blocklength analysis, maintaining covertness requires the signal power to scale inversely with the square root of the blocklength ($1/\sqrt{n}$). This ensures that as Willie gets more samples to analyze, the signal he is looking for becomes proportionally weaker, keeping him in a state of statistical uncertainty.
The Square Root Law
The consequence of this vanishing power is the Square Root Law (SRL). If the power per symbol is $O(1/\sqrt{n})$, then the total energy Alice can expend over $n$ symbols is $O(\sqrt{n})$. Since the capacity of a channel at low signal-to-noise ratios is proportional to the signal power, the total number of bits that can be reliably transmitted also scales as $O(\sqrt{n})$.
This law is remarkably robust across different media:
- Wireless Channels: In AWGN channels, the limit is $O(\sqrt{n})$ bits. Sadaf Salehkalaibar and Vincent Y. F. Tan showed this scaling even applies to hiding the state of the channel itself.
- Network Traffic: When inserting packets into a stream, Ramin Soltani and Don Towsley found that the number of covert packets is limited to the square root of the total legitimate packets.
- Steganography: In digital media, the safe payload for hidden data grows only with the square root of the host content's size.
Breaking the Square Root Barrier
While the SRL seems like a hard ceiling, researchers have identified specific conditions where Alice can achieve linear scaling ($O(n)$ bits), effectively communicating at a constant positive rate without detection.
The most common way to "break" the law is by exploiting the Warden's uncertainty. If Willie does not perfectly know the background noise level or the channel state, Alice can hide her signal within that uncertainty. Ligong Wang and Ashish Khisti proved that if Alice has Channel-State Information (CSI), she can modulate her power to "fill in" gaps in the background noise, achieving a positive rate.
Another approach involves timing. In Covert communications on Poisson packet channels, Ramin Soltani showed that while inserting packets is limited by the SRL, delaying or reordering existing packets can allow for linear covert capacity. By manipulating the timing of legitimate traffic, Alice isn't adding new energy to the system that Willie can detect; she is simply changing its shape.
Practical Constraints and Refinements
In real-world scenarios, we rarely have infinite time ($n \to \infty$). This has led to a focus on the non-asymptotic regime. Xinchun Yu has refined the SRL by identifying second-order terms, such as $O(n^{1/4})$, which become significant for short-duration transmissions. These refinements are crucial for engineering practical systems, such as multi-antenna covert radios or spectral-mask constrained transmissions, where the exact number of bits matters more than the asymptotic scaling.
Ultimately, covert communication is a game of statistical shadows. Whether through the use of Intelligent Reflecting Surfaces to confuse Willie's phase measurements or by modulating application payloads in transit, the goal remains the same: staying just beneath the threshold where the Warden's observations turn into evidence.