We investigate covert communication over general memoryless classical-quantum channels with fixed finite-size input alphabets. We show that the square root law (SRL) governs covert communication in this setting when product a ofninput states is used:$L_{\mathrm { SRL}}\sqrt {n}+o(\sqrt {n})$covert bits (but no more) can be reliably transmitted innuses of classical-quantum channel, where$L_{\mathrm { SRL}}\gt 0$is a channel-dependent constant that we callcovert capacity. We also show that ensuring covertness requires$J_{\mathrm { SRL}}\sqrt {n}+o(\sqrt {n})$bits secret key shared by the communicating parties prior to transmission, where$J_{\mathrm { SRL}}\geq 0$is a channel-dependent constant. We assume a quantum-powerful adversary that can perform an arbitrary joint (entangling) measurement on allnchannel uses. We determine the single-letter expressions for$L_{\mathrm { SRL}}$and$J_{\mathrm { SRL}}$, and establish conditions when$J_{\mathrm { SRL}}=0$(i.e., no pre-shared secret key is needed). Finally, we evaluate scenarios where covert communication is not governed by the SRL.

The approximate stabilizer rank of a quantum state is the minimum number of terms in any approximate decomposition of that state into stabilizer states. Bravyi and Gosset showed that the approximate stabilizer rank of a so-called “magic” state like |T⟩⊗ n, up to polynomial factors, is an upper bound on the number of classical operations required to simulate an arbitrary quantum circuit with Clifford gates and n number of T gates. As a result, an exponential lower bound on this quantity seems inevitable. Despite this intuition, several attempts using various techniques could not lead to a better than a linear lower bound on the “exact” rank of |T⟩⊗ n, meaning the minimal size of a decomposition that exactly produces the state. For the “approximate” rank, which is more realistically related to the cost of simulating quantum circuits, no lower bound better than Ω(√n) has been known. In this paper, we improve the lower bound on the approximate rank to Ω(n2) for a wide range of the approximation parameters. An immediate corollary of our result is the existence of polynomial time computable functions which require a super-linear number of terms in any decomposition into exponentials of quadratic forms over F2, resolving a question by Williams. Our approach is based on a strong lower bound on the approximate rank of a quantum state sampled from the Haar measure, a step-by-step analysis of the approximate rank of a magic-state teleportation protocol to sample from the Haar measure, and a result about trading Clifford operations with T gates.

Motivated by application to quantum radar and the known benefits of quantum illumination in the high-noise low-reflectance regime, we study the design of signaling schemes for covertly probing a distant target over a lossy and noisy bosonic channel. Specifically, we analyze the performance of diffuse and sparse signaling schemes, which achieve covertness by spreading a constant number of photons in many modes or in a few modes, respectively. We benchmark the performance against a converse bound that holds for arbitrary covert quantum illumination schemes. Numerical results suggest the superior performance of the diffuse signaling scheme, which we conjecture outperforms any other covert quantum illumination scheme.

We formalize the problem of active covert sensing, in which a legitimate user wants to not only sense an unknown parameter but also remain undetectable from an adversary by actively controlling the actions that generate observations. We characterize the optimal achievable error exponent when the actions of the legitimate user do not depend on the past observations. When the actions are allowed to depend on the past observations, we provide an example showing the benefits of adaptivity.

We investigate the problem of covert and secret key generation over a state-dependent discrete memoryless channel with one-way public discussion in which an adversary, the warden, may arbitrarily choose the channel state. We develop an adaptive protocol that, under conditions that we explicitly specify, not only allows the transmitter and the legitimate receiver to exchange a secret key but also conceals from the active warden whether the protocol is being run. When specialized to passive adversaries that do not control the channel state, we partially characterize the covert secret key capacity. In particular, the covert secret key capacity is sometimes equal to the covert capacity of the channel, so that secrecy comes “for free.”

We consider the problem of coding to ensure covert communication, which involves ensuring reliable communication between two legitimate parties while simultaneously guaranteeing a low probability of detection by an eavesdropper. Specifically, we develop an optimal low-complexity coding scheme that achieves the information-theoretic limits of covert communications over binary-input discrete memoryless channels (BI-DMCs). To justify our design, we first consider a regime in which information theory proves the possibility of covert communication without shared secret key and show the impossibility of achieving information-theoretic limits using linear codes without secret key. We then circumvent this impossibility by introducing non-linearity into the coding scheme through the use of pulse position modulation (PPM) and multilevel coding (MLC). This MLC-PPM scheme exhibits several appealing properties; in particular, for an appropriate decoder, the channel at a given level is independent of the total number of levels and the codeword length. We exploit these properties to show how one can use families of channel capacity- and channel resolvability-achieving codes to concretely instantiate a covert communication scheme.

We consider an enhanced measure of security for a quantum key distribution protocol, in which we require that the adversary not only obtains no information about the key but also remains unaware that a key generation protocol has been executed. When the adversary applies the same quantum channel independently to each transmitted quantum state, akin to a collective attack in the quantum key distribution literature, we propose a protocol that achieves covert and secret key expansion under mild restrictions. A crucial component of the protocol is a covert estimation stage, which is then combined with universal channel coding for reliability and resolvability in the covert regime.

Secure communication over a wiretap channel is investigated, in which an active adversary modifies the state of the channel and the legitimate transmitter has the opportunity to sense and learn the adversary's actions. The adversary has the ability to switch the channel state and observe the corresponding output at every channel use while the encoder has causal access to observations that depend on the adversary's actions. A joint learning/transmission scheme is developed in which the legitimate users learn and adapt to the adversary's actions. For some channel models, it is shown that the achievable rates, defined precisely for the problem, are arbitrarily close to those obtained with hindsight, had the transmitter known the actions ahead of time. This initial study suggests that there is much to exploit and gain in physical-layer security by learning the adversary, e.g., monitoring the environment.

The covert capacity is characterized for a non-coherent fast Rayleigh-fading wireless channel, in which a legitimate user wishes to communicate reliably with a legitimate receiver while escaping detection from a warden. It is shown that the covert capacity is achieved with an amplitude-constrained input distribution that consists of a finite number of mass points including one at zero and numerically tractable bounds are provided. It is also conjectured that distributions with two mass points in fixed locations are optimal.

We propose a coding scheme for covert communication over additive white Gaussian noise channels, which extends a previous construction for discrete memoryless channels. We first show how sparse signaling with On-Off keying fails to achieve the covert capacity but that a modification allowing the use of binary phase-shift keying for "on" symbols recovers the loss. We then construct a modified pulse-position modulation scheme that, combined with multilevel coding, can achieve the covert capacity with low-complexity error-control codes. The main contribution of this work is to reconcile the tension between diffuse and sparse signaling suggested by earlier information-theoretic results.

We propose a model of secure communication over wireless channels in which the legitimate parties leverage Radio Tomographic Imaging (RTI) to learn the adversary. Specifically, we model the results of RTI as an "in band" sensing channel that provides causal information about the eavesdropper's path-loss to the transmitter. This ability to learn the path-loss is exploited to achieve secrecy, even in presence of an eavesdropper that moves to optimize its path-loss and improves its eavesdropping. We show that the secrecy rates achieved are the same as those that would have been obtained with hindsight, had the transmitter known the average path-loss ahead of time.

We study the first- and second-order asymptotics of covert communication over binary-input discrete memoryless channels for three different covertness metrics and under maximum probability of error constraint. When covertness is measured in terms of the relative entropy between the channel output distributions induced with and without communication, we characterize the exact first- and second-order asymptotics of the number of bits that can be reliably transmitted with a maximum probability of error less than E and a relative entropy less than δ. When covertness is measured in terms of the variational distance between the channel output distributions or in terms of the probability of missed detection for fixed probability of false alarm, we establish the exact first-order asymptotics and bound the second-order asymptotics. Pulse position modulation achieves the optimal first-order asymptotics for all three metrics, as well as the optimal second-order asymptotics for relative entropy. The main conceptual contribution of this paper is to clarify how the choice of a covertness metric impacts the information-theoretic limits of covert communications. The main technical contribution underlying our results is a detailed expurgation argument to show the existence of a code satisfying the reliability and covertness criteria.

We develop a low-complexity coding scheme to achieve covert communications over binary symmetric channels. We circumvent the impossibility of covert communication with linear codes by introducing non-linearity through the use of pulse-position modulation (PPM) and multilevel coding (MLC). We show that the MLC-PPM scheme exhibits many appealing properties, in particular, the channel at a given index level remains the same as the number of level increases, which allows one to use families of capacity- and resolvability-achieving codes to concretely instantiate the covert communication scheme.

We analyze the problem of secure communication over a wiretap channel with an active adversary, in which the legitimate transmitter has the opportunity to sense and learn the adversary's actions. Specifically, the adversary has the ability to switch between two channels and to observe the corresponding output at every channel use; the encoder, however, has causal access to observations impacted by adversary's actions. We develop a joint learning/transmission scheme in which the legitimate users learn and adapt to the adversary's actions. For some channel models, we show that the achievable rates, which we define precisely, are arbitrarily close to those obtained with hindsight, had the transmitter known the actions ahead of time. This suggests that there is much to exploit and gain in physical-layer security by monitoring the environment.

We define and study the error exponent of covert communications over binary-input Discrete Memoryless Channels (DMCs). Our main result consists of upper and lower bounds for the exponent, which match in a regime that we explicitly characterize. While our proofs follow standard techniques, the vanishing rate regime inherent to covert communications and the low-weight of codewords introduces specific technical challenges. In particular, the lower bound of the error exponent follows from a non-standard constant-composition ensemble instead of an independent and identically distributed (i.i.d.) ensemble, and the upper bound requires a careful treatment that does not appear in the traditional analysis of error exponent.

We consider the problem of covert communication over noisy binary input Discrete Memoryless Channels (DMCs). Covertness is measured with respect to an adversary in terms of the divergence between the channel output distribution induced with and without communication. We characterize the exact second order asymptotics of the number of bits that can be reliably transmitted with a probability of error less than ∈ and a divergence less than δ. The main technical contribution of this paper is a detailed analysis of how to expurgate a random code while maintaining its channel resolvability properties.

In this paper we define critical graphs as minimal graphs that support a given set of rates for the index coding problem, and study them for both the one-shot and asymptotic setups. For the case of equal rates, we find the critical graph with minimum number of edges for both one-shot and asymptotic cases. For the general case of possibly distinct rates, we show that for one-shot and asymptotic linear index coding, as well as asymptotic non-linear index coding, each critical graph is a union of disjoint strongly connected subgraphs (USCS). On the other hand, we identify a non-USCS critical graph for a one-shot non-linear index coding problem. In addition, we show that the capacity region of the index coding associated with a given graph can be obtained by time-sharing over valid index codes for its strongly connected components.