Fundamental Limits of Covert Communication

Traditional security (e.g., encryption) prevents unauthorized access to message content; however, detection of the mere presence of a message can have significant negative impact on the privacy of the communicating parties. Unlike these standard methods, covert or low probability of detection (LPD) communication not only protects the information contained in a transmission from unauthorized decoding, but also prevents the detection of a transmission in the first place. In this thesis we investigate the fundamental laws of covert communication. We first study covert communication over additive white Gaussian noise (AWGN) channels, a standard model for radio-frequency (RF) communication. We present a square root limit on the amount of information transmitted covertly and reliably over such channels. Specifically, we prove that if the transmitter has the channels to the intended receiver and the warden that are both AWGN, then O(\sqrt{n}) covert bits can be reliably transmitted to the receiver in n uses of the channel. Conversely, attempting to transmit more than O(\sqrt{n}) bits either results in detection by the warden with probability one or a non-zero probability of decoding error at the receiver as n--\u3e\infty. Next we study the impact of warden\u27s ignorance of the communication attempt time. We prove that if the channels from the transmitter to the intended receiver and the warden are both AWGN, and if a single n-symbol period slot out of T(n) such slots is selected secretly (forcing the warden to monitor all T(n) slots), then O(\min{\sqrt{n\log T(n)},n}) covert bits can be transmitted reliably using this slot. Conversely, attempting to transmit more than O(\sqrt{n\log T(n)}) bits either results in detection with probability one or a non-zero probability of decoding error at the receiver. We then study covert optical communication and characterize the ultimate limit of covert communication that is secure against the most powerful physically-permissible adversary. We show that, although covert communication is impossible when a channel injects the minimum noise allowed by quantum mechanics, it is attainable in the presence of any noise excess of this minimum (such as the thermal background). In this case, O(\sqrt{n}) covert bits can be transmitted reliably in n optical channel uses using standard optical communication equipment. The all-powerful adversary may intercept all transmitted photons not received by the intended receiver, and employ arbitrary quantum memory and measurements. Conversely, we show that this square root scaling cannot be circumvented. Finally, we corroborate our theory in a proof-of-concept experiment on an optical testbed