In traditional cryptography, we focus on hiding the content of a message from an eavesdropper. However, in many sensitive scenarios, the mere fact that a communication is taking place can be incriminating. Covert communication, or communication with Low Probability of Detection (LPD), aims to hide the very existence of the transmission from a watchful adversary, often called a "warden."
The Square Root Law of Covert Capacity
The central discovery in this field is that covert communication is fundamentally more restricted than standard communication. In a normal channel, you can send a number of bits that grows linearly with the number of channel uses ($n$). But if you must remain undetectable to a warden, you are typically limited by the Square Root Law.
As established by Gregory Wornell, Ligong Wang, and Lizhong Zheng in Fundamental Limits of Communication with Low Probability of Detection, the maximum amount of information that can be sent covertly scales with $\sqrt{n}$.
The intuition is rooted in statistical hypothesis testing. A warden monitors the channel for any deviation from "background noise." To stay hidden, the sender must keep the signal power so low that the total energy of the transmission is indistinguishable from the natural fluctuations (the variance) of the noise. Because noise fluctuations grow with the square root of the number of samples, the signal power must be spread thinner and thinner as the transmission length increases, leading to the $\sqrt{n}$ scaling. This principle holds even in continuous-time settings with regulatory constraints, where Qiaosheng Zhang and Matthieu R. Bloch showed that bits scale with the square root of the product of bandwidth and time ($O(\sqrt{WT})$) in Undetectable Radios: Covert Communication under Spectral Mask Constraints.
The Secret Key Bottleneck
For a receiver to extract a signal that is buried deep within noise, they usually need to know exactly what to look for. This typically requires a pre-shared secret key between the sender and receiver to synchronize their codebooks.
Vincent Y. F. Tan and Si-Hyeon Lee demonstrated in Time-Division Transmission is Optimal for Covert Communication over Broadcast Channels that there is a strict trade-off: the amount of secret key material required scales proportionally with the message size. Without this shared randomness, the sender cannot generate a signal that looks like noise to the warden but remains decodable to the receiver. In multi-user broadcast scenarios, this creates a significant resource allocation problem, as the "cost" of covertness is paid in the consumption of these finite secret keys.
Overcoming the Square Root Limit
Is it ever possible to communicate covertly at a positive rate (linear scaling) rather than being trapped by the square root law? Research suggests two primary "loopholes":
- Channel Asymmetry: If the warden’s channel is significantly noisier than the legitimate receiver’s channel, the requirement for a pre-shared key can be relaxed or eliminated. Ashish Khisti and Si-Hyeon Lee found that when the adversary is at a disadvantage, covertness can be achieved more efficiently, as the warden cannot distinguish the signal from their own high levels of thermal noise.
- Channel-State Information (CSI): In Covert Communication With Channel-State Information at the Transmitter, Ligong Wang and Gregory W. Wornell showed that if the transmitter knows the exact state of the background noise or interference, it can "mold" the signal to hide within those specific fluctuations. This allows for a positive communication rate, effectively breaking the square root barrier by leveraging environmental uncertainty.
Public-Key Steganography
The logistical burden of pre-sharing secret keys is the "Achilles' heel" of covert systems. To address this, researchers like Kejiang Chen and Weiming Zhang have moved toward public-key steganography.
In Provably Secure Public-Key Steganography Based on Admissible Encoding, they propose using mathematical structures like elliptic curves to hide data within generative media (such as AI-generated text or images). By using "admissible encoding," they ensure that the resulting transmission is computationally indistinguishable from legitimate, non-covert traffic. This allows two parties to establish a covert channel without ever having met previously to exchange a key, shifting the problem from information-theoretic limits to computational complexity.