Fundamental Limits of Covert Communication

30 Oct
Thursday, 10/30/2014 11:00am to 1:00pm
Ph.D. Thesis Defense

Boulat Bash

Lederle Graduate Research Center, Room A311

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, if the transmitter has the channels to the intended receiver and the warden that are both AWGN, we prove that 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-->\infty.

Next we study the impact of warden's 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 it is impossible when a channel injects the minimum noise allowed by quantum mechanics, covert communication 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.

We believe that our findings will both motivate further theoretical inquiries into the rich area of covert communications as well as enable practical realizations of covert communication and sensing. While the results of this thesis have been confined to point-to-point links, we view this as the first step in the construction of the "shadow networks" that will enable groups of people to exchange messages in a completely hidden fashion, allowing communication where it is not permitted.

Advisor: Donald Towsley