Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

Covert Identification over Binary-Input Memoryless Channels.

Qiaosheng Eric Zhang, Vincent Y. F. Tan

Published Jul 27, 2020• 2 citations
OpenAlex

Abstract

This paper considers the covert identification problem in which a sender aims to reliably convey an identification (ID) message to a set of receivers via a binary-input memoryless channel (BMC), and simultaneously to guarantee that the communication is covert with respect to a warden who monitors the communication via another independent BMC. We prove a square-root law for the covert identification problem. This states that an ID message of size \exp(\exp(\Theta(\sqrt{n}))) can be transmitted over n channel uses. We then characterize the exact pre-constant in the \Theta(.) notation. This constant is referred to as the covert identification capacity. We show that it equals the recently developed covert capacity in the standard covert communication problem, and somewhat surprisingly, the covert identification capacity can be achieved without any shared key between the sender and receivers. The achievability proof relies on a random coding argument with pulse-position modulation (PPM), coupled with a second stage which performs code refinements. The converse proof relies on an expurgation argument as well as results for channel resolvability with stringent input constraints.

Related papers

Covert Identification Over Binary-Input Discrete Memoryless Channels

Qiaosheng Eric Zhang, Vincent Y. F. Tan

This paper considers the covert identification problem in which a sender aims to reliably convey an identification (ID) message to a set of receivers via a binary-input discrete memoryless channel (BDMC), and simultaneously to guarantee that the communication is covert with respect to a warden who monitors the communication via another independent BDMC. We prove a square-root law for the covert identification problem. This states that an ID message of size exp(exp(Θ(√{ n})) can be transmitted over n channel uses. We then characterize the exact pre-constant in the Θ(·) notation. This constant is referred to as the covert identification capacity. We show that it equals the recently developed covert capacity in the standard covert communication problem, and somewhat surprisingly, the covert identification capacity can be achieved without any shared key between the sender and receivers. The achievability proof relies on a random coding argument with pulse-position modulation (PPM), coupled with a second stage which performs code refinements. The converse proof relies on an expurgation argument as well as results for channel resolvability with stringent input constraints.

arXiv:2007.13333•IEEE Transactions on Information Theory•Jun 14, 2021•8 citations

Covert Communication Over Noisy Channels: A Resolvability Perspective

Matthieu R. Bloch

We consider the situation in which a transmitter attempts to communicate reliably over a discrete memoryless channel, while simultaneously ensuring covertness (low probability of detection) with respect to a warden, who observes the signals through another discrete memoryless channel. We develop a coding scheme based on the principle of channel resolvability, which generalizes and extends prior work in several directions. First, it shows that irrespective of the quality of the channels, it is possible to communicate on the order of √n reliable and covert bits over n channel uses if the transmitter and the receiver share on the order of √n key bits. This improves upon earlier results requiring on the order of √n log n key bits. Second, it proves that if the receiver's channel is better than the warden's channel in a sense that we make precise, it is possible to communicate on the order of √n reliable and covert bits over n channel uses without a secret key. This generalizes earlier results established for binary symmetric channels. We also identify the fundamental limits of covert and secret communications in terms of the optimal asymptotic scaling of the message size and key size, and we extend the analysis to Gaussian channels. The main technical problem that we address is how to develop concentration inequalities for low-weight sequences. The crux of our approach is to define suitably modified typical sets that are amenable to concentration inequalities.

arXiv:1503.08778•IEEE Transactions on Information Theory•Feb 15, 2016•435 citations

Covert Communication Over a KKK -User Multiple-Access Channel

Keerthi Suria Kumar Arumugam, Matthieu R. Bloch

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.

arXiv:1803.06007•IEEE Transactions on Information Theory•Jul 22, 2019•100 citations

Bounds on Covert Capacity With Sub-Exponential Random Slot Selection

Shi-Yuan Wang, Keerthi Suria Kumar Arumugam, Matthieu R. Bloch

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.

arXiv:2409.07777•IEEE Transactions on Information Theory•Jul 16, 2025•1 citation

Covert Capacity-Key Tradeoff Over Discrete Memoryless Networks

Abdelaziz Bounhar, Mireille Sarkiss, Michèle Wigger

This paper characterizes the covert capacity-key tradeoffs for discrete memoryless channels (DMC) and discrete memoryless multiple-access channels (DMMAC). The focus is on channels where communication rates are measured as the number of transmitted bits divided by the square-root of the blocklength and by the square-root of the covertness constraint. Previous results had determined the largest achievable covert rates for these channels, as well as the minimum key rates required to achieve these largest covert rates. In this work, we additionally determine the minimum key rates required at reduced covert rates. Stated differently, we determine the set of all covert rates that are achievable for a given set of key rates. This is termed thecovert capacity-key tradeoff. Our results on the covert capacity-key tradeoffs over DMCs and DMMACs show that for small key rates and when the adversary observes the inputs through a better channel than the legitimate receiver, binary signalling at all transmitters is optimal even for larger input alphabets and the capacity-key tradeoff grows linearly. Moreover, in this regime the covert capacity-key tradeoff of DMMACs is square implying that each of the transmitters can simultaneously achieve its own largest covert rate depending only on its own available key rate, irrespective of the other transmitter. For larger key rates or when the adversary is not uniformly stronger than the legitimate receiver over all inputs, the covert capacity-key tradeoff region of DMMACs is non-square and a tradeoff arises between the rates of the various transmitters.

IEEE Journal on Selected Areas in Information Theory•Jan 1, 2026•0 citations

Capacity-Key Tradeoff in Covert Communication

Abdelaziz Bounhar, Mireille Sarkiss, Michèle Wigger

This paper explores the tradeoff between covert communication capacity and secret key requirements over discrete memoryless channels (DMCs). We focus on settings where under a covertness constraint both communication and key rates are measured as the number of bits per square root of the block-length. While previous work has identified the maximum covert communication rates and the corresponding minimum key rates needed to achieve them, our study characterizes the minimum key rates necessary for all of desired covert communication rates. In equivalent terms, we determine, for any given key rate, the set of achievable covert rates. This relationship defines what we call the covert capacity-key tradeoff.Our analysis reveals several new insights. In scenarios where only small key rates are available and the adversary has a stronger channel than the intended receiver, binary signaling is optimal—regardless of the specific channel characteristics or input alphabets. In these cases, the covert capacity increases linearly with the available key rate. In other cases and for larger key rates, the covert capacity-key tradeoff grows sublinearly.We also extend our findings to multi-access channels (MACs) with binary inputs.

IEEE Information Theory Workshop (ITW)•Sep 29, 2025•0 citations
This paper considers the covert identification problem in which a sender aims to reliably convey an identification (ID) message to a set of receivers via a binary-input memoryless channel (BMC), and simultaneously to guarantee that the communication is covert with respect to a warden who monitors the communication via another independent BMC. We prove a square-root law for the covert identification problem. This states that an ID message of size \exp(\exp(\Theta(\sqrt{n}))) can be transmitted over n channel uses. We then characterize the exact pre-constant in the \Theta(.) notation. This constant is referred to as the covert identification capacity. We show that it equals the recently developed covert capacity in the standard covert communication problem, and somewhat surprisingly, the covert identification capacity can be achieved without any shared key between the sender and receivers. The achievability proof relies on a random coding argument with pulse-position modulation (PPM), coupled with a second stage which performs code refinements. The converse proof relies on an expurgation argument as well as results for channel resolvability with stringent input constraints.
This paper considers the covert identification problem in which a sender aims to reliably convey an identification (ID) message to a set of receivers via a binary-input discrete memoryless channel (BDMC), and simultaneously to guarantee that the communication is covert with respect to a warden who monitors the communication via another independent BDMC. We prove a square-root law for the covert identification problem. This states that an ID message of size exp(exp(Θ(√{ n})) can be transmitted over n channel uses. We then characterize the exact pre-constant in the Θ(·) notation. This constant is referred to as the covert identification capacity. We show that it equals the recently developed covert capacity in the standard covert communication problem, and somewhat surprisingly, the covert identification capacity can be achieved without any shared key between the sender and receivers. The achievability proof relies on a random coding argument with pulse-position modulation (PPM), coupled with a second stage which performs code refinements. The converse proof relies on an expurgation argument as well as results for channel resolvability with stringent input constraints.
We consider the situation in which a transmitter attempts to communicate reliably over a discrete memoryless channel, while simultaneously ensuring covertness (low probability of detection) with respect to a warden, who observes the signals through another discrete memoryless channel. We develop a coding scheme based on the principle of channel resolvability, which generalizes and extends prior work in several directions. First, it shows that irrespective of the quality of the channels, it is possible to communicate on the order of √n reliable and covert bits over n channel uses if the transmitter and the receiver share on the order of √n key bits. This improves upon earlier results requiring on the order of √n log n key bits. Second, it proves that if the receiver's channel is better than the warden's channel in a sense that we make precise, it is possible to communicate on the order of √n reliable and covert bits over n channel uses without a secret key. This generalizes earlier results established for binary symmetric channels. We also identify the fundamental limits of covert and secret communications in terms of the optimal asymptotic scaling of the message size and key size, and we extend the analysis to Gaussian channels. The main technical problem that we address is how to develop concentration inequalities for low-weight sequences. The crux of our approach is to define suitably modified typical sets that are amenable to concentration inequalities.
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 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 of2\sqrt {2}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.
This paper characterizes the covert capacity-key tradeoffs for discrete memoryless channels (DMC) and discrete memoryless multiple-access channels (DMMAC). The focus is on channels where communication rates are measured as the number of transmitted bits divided by the square-root of the blocklength and by the square-root of the covertness constraint. Previous results had determined the largest achievable covert rates for these channels, as well as the minimum key rates required to achieve these largest covert rates. In this work, we additionally determine the minimum key rates required at reduced covert rates. Stated differently, we determine the set of all covert rates that are achievable for a given set of key rates. This is termed thecovert capacity-key tradeoff. Our results on the covert capacity-key tradeoffs over DMCs and DMMACs show that for small key rates and when the adversary observes the inputs through a better channel than the legitimate receiver, binary signalling at all transmitters is optimal even for larger input alphabets and the capacity-key tradeoff grows linearly. Moreover, in this regime the covert capacity-key tradeoff of DMMACs is square implying that each of the transmitters can simultaneously achieve its own largest covert rate depending only on its own available key rate, irrespective of the other transmitter. For larger key rates or when the adversary is not uniformly stronger than the legitimate receiver over all inputs, the covert capacity-key tradeoff region of DMMACs is non-square and a tradeoff arises between the rates of the various transmitters.
This paper explores the tradeoff between covert communication capacity and secret key requirements over discrete memoryless channels (DMCs). We focus on settings where under a covertness constraint both communication and key rates are measured as the number of bits per square root of the block-length. While previous work has identified the maximum covert communication rates and the corresponding minimum key rates needed to achieve them, our study characterizes the minimum key rates necessary for all of desired covert communication rates. In equivalent terms, we determine, for any given key rate, the set of achievable covert rates. This relationship defines what we call the covert capacity-key tradeoff.Our analysis reveals several new insights. In scenarios where only small key rates are available and the adversary has a stronger channel than the intended receiver, binary signaling is optimal—regardless of the specific channel characteristics or input alphabets. In these cases, the covert capacity increases linearly with the available key rate. In other cases and for larger key rates, the covert capacity-key tradeoff grows sublinearly.We also extend our findings to multi-access channels (MACs) with binary inputs.