We consider the problem of covert communication with random slot selection over binary-input Discrete Memoryless Channels (DMCs) and Additive White Gaussian Noise (AWGN) channels, in which a transmitter attempts to reliably communicate with a legitimate receiver while simultaneously maintaining covertness with respect to (w.r.t.) an eavesdropper. Covertness refers to the inability of the eavesdropper to distinguish the transmission of a message from the absence of communication, modeled by the transmission of a fixed channel input. Random slot selection refers to the transmitter’s ability to send a codeword in a time slot with known boundaries selected uniformly at random among a predetermined number of slots. Our main contribution is to develop bounds for the information-theoretic limit of communication in this model, called the covert capacity, when the number of time slots scales sub-exponentially with the codeword length. Our upper and lower bounds for the covert capacity are within a multiplicative factor of$\sqrt {2}$independent of the channel. This result partially fills a characterization gap between the covert capacity without random slot selection and the covert capacity with random selection among an exponential number of slots in the codeword length. Our key technical contributions consist of 1) a tight upper bound for the relative entropy characterizing the effect of random slot selection on the covertness constraint in our achievability proof; 2) a careful converse analysis to characterize the maximum allowable weight or power of codewords to meet the covertness constraint. Our results suggest that, unlike the case without random slot selection, the choice of covertness metric does not change the covert capacity in the presence of random slot selection.

We analyze a two-receiver binary-input discrete memoryless broadcast channel, in which the transmitter communicates a common message simultaneously to both receivers and a covert message to only one of them. The unintended recipient of the covert message is treated as an adversary who attempts to detect the covert transmission. This model captures the problem of embedding covert messages in an innocent codebook and generalizes previous covert communication models in which innocent behavior corresponds to the absence of communication between legitimate users. We identify the exact asymptotic behavior of the number of covert bits that can be transmitted when the rate of the innocent codebook is close to the capacity of the channel to the adversary. Our results also identify the dependence of the number of covert bits on the channel parameters and the characteristics of the innocent codebook.

We consider a scenario in which K transmitters attempt to communicate covert messages reliably to a legitimate receiver over a discrete memoryless multiple-access channel (MAC) while simultaneously escaping detection from an adversary who observes their communication through another discrete memoryless MAC. We assume that each transmitter may use a secret key that is shared only between itself and the legitimate receiver. We show that each of the K transmitters can transmit on the order of √n reliable and covert bits per n channel uses, exceeding which, the warden will be able to detect the communication. We identify the optimal pre-constants of the scaling, which leads to a complete characterization of the covert capacity region of the K-user binary-input MAC. We show that, asymptotically, all sum-rate constraints are inactive unlike the traditional MAC capacity region. We also characterize the channel conditions that have to be satisfied for the transmitters to operate without a secret key.

We analyze a physically degraded relay channel, in which the transmitter sends a covert message to the legitimate receiver with the help of a relay. Two wardens, who do not collude with each other, monitor communication from the transmitter and the relay, respectively, through two Discrete Memoryless Channels (DMCs) to detect the presence of a covert message. The objective of the transmitter is to deliver the covert message successfully to the receiver without exceeding the covertness threshold of either warden. We identify the optimal asymptotic scaling of message and key bits and the dependence of the covert throughput on the two covertness thresholds.

We analyze a two-receiver binary-input discrete memoryless broadcast channel, in which the transmitter communicates a common message simultaneously to both users and a covert message to only one of them while treating the other as an adversary. This model captures the problem of embedding covert messages in an innocuous codebook and generalizes previous models in which the innocent behavior corresponds to the absence of communication between legitimate users. We identify the exact asymptotic behavior of the number of reliable and covert bits when the rate of the innocuous codebook is close to the channel capacity of the adversary. In particular, our results characterize the dependence of the number of covert bits on the channel parameters and the characteristics of the innocent codebook.

We consider a scenario in which two legitimate transmitters attempt to communicate with a legitimate receiver over a discrete memoryless Multiple-Access Channel (MAC), while escaping detection from an adversary who observes their communication through another discrete memoryless MAC. If the MAC to the legitimate receiver is “better” than the one to the adversary, in a sense that we make precise, then the legitimate users can reliably communicate on the order of √n bits per n channel uses with arbitrarily Low Probability of Detection (LPD) without using a secret key. We also identify the pre-constants of the scaling, which leads to a characterization of the covert capacity region.

We consider a scenario in which Alice asynchronously communicates with Bob over a Discrete Memoryless Channel (DMC) while escaping detection from an adversary who observes their communication through another DMC. Specifically, Alice transmits codewords of length n and chooses the transmission epoch T uniformly at random among N available time epochs, where N ≫ n. This deliberate symbol level-asynchronism forces the adversary to monitor a window of size N' much larger than the codeword length n, and results in an increased covert throughput compared to the scenario without asynchronism. Our result generalizes a previous work in which asynchronism was introduced at the codeword level, i.e., having Alice choose a transmission window among non-overlapping windows of length n.