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

IEEE Information Theory Workshop (ITW)

Covert Communication over Asynchronous Channels with Timing Advantage

Vidyalaxmi Dani, Venkatesh Ramaiyan, Devendra Jalihal

Published Oct 17, 2021• 6 citations
Publisher

Abstract

We study a problem of covert communication over binary symmetric channels (BSC) in an asynchronous setup. Here, Alice seeks to communicate to Bob over a BSC while trying to be covert with respect to Willie, who observes any communication through possibly a different BSC. When Alice communicates, she transmits a message (using a codeword of length n) at a random time uniformly distributed in a window of size Awslots. We assume that Bob has side information about the time of transmission leading to a reduced uncertainty of Abslots for Bob, where $A_{b}\lt A_{w}$. In this setup, we seek to characterize the limits of covert communication as a function of the timing advantage. When Awis increasing exponentially in n, we characterize the covert capacity as a function of Awand Ab. When Awis increasing sub-exponentially in n, we characterize lower and upper bounds on achievable covert bits and show that positive covert rates are not feasible irrespective of timing advantage. Using numerical work, we illustrate our results for different network scenarios, and also highlight a tradeoff between timing advantage and channel advantage (between Bob and Willie).

DOI
10.1109/itw48936.2021.9611511

Related papers

Keyless asynchronous covert communication

Keerthi Suria Kumar Arumugam, Matthieu R. Bloch

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.

IEEE Information Theory Workshop (ITW)•Sep 1, 2016•21 citations

Covert communications on Poisson packet channels

Ramin Soltani, Dennis Goeckel, Don Towsley +1 more

Consider a channel where authorized transmitter Jack sends packets to authorized receiver Steve according to a Poisson process with rate λ packets per second for a time period T. Suppose that covert transmitter Alice wishes to communicate information to covert receiver Bob on the same channel without being detected by a watchful adversary Willie. We consider two scenarios. In the first scenario, we assume that warden Willie cannot look at packet contents but rather can only observe packet timings, and Alice must send information by inserting her own packets into the channel. We show that the number of packets that Alice can covertly transmit to Bob is on the order of the square root of the number of packets that Jack transmits to Steve; conversely, if Alice transmits more than that, she will be detected by Willie with high probability. In the second scenario, we assume that Willie can look at packet contents but that Alice can communicate across an M/M/1 queue to Bob by altering the timings of the packets going from Jack to Steve. First, Alice builds a codebook, with each codeword consisting of a sequence of packet timings to be employed for conveying the information associated with that codeword. However, to successfully employ this codebook, Alice must always have a packet to send at the appropriate time. Hence, leveraging our result from the first scenario, we propose a construction where Alice covertly slows down the packet stream so as to buffer packets to use during a succeeding codeword transmission phase. Using this approach, Alice can covertly and reliably transmit O(λT) covert bits to Bob in time period T over an M/M/1 queue with service rate μ > e · λ.

arXiv:1610.00381•Allerton Conference on Communication, Control, and Computing•Sep 1, 2015•19 citations

Covert Communications Under Environmental Uncertainty on a Continuous-Time Channel

Amna Gillani, Tamara V. Sobers, Don Towsley +1 more

Covert communication is achieved when a transmitter Al-ice can successfully transmit a message to a receiver Bob without being detected by an attentive and capable adversary Willie. Early results demonstrated the difficulty of the covert communications problem: with AWGN discrete-time channels between all parties, only$O(\sqrt{n})$bits can be sent in$n$channel uses. But it was soon recognized that uncertainty about the environment at Willie, for example, uncertainty in his own noise statistics, could allow for a positive rate:$O(n)$bits can be sent covertly in$n$channel uses. However, most covert communication results, including this promising positive rate result, have been obtained for a discrete-time communications channel. Here, we demonstrate that the assumption of a discrete-time channel is problematic when trying to exploit Willie's noise uncertainty. In particular, we demonstrate that if Alice transmits$\omega(\sqrt{T})$bits in a length$T$interval to Bob on a continuous-time channel, then there exists a detector at Willie that can detect her transmission, as the probability of false alarm and missed detection$P_{MD}+P_{FA}\rightarrow 0$as$T\rightarrow\infty$. In other words, the communication is not covert, unlike the case of a discrete-time channel.

Asilomar Conference on Signals, Systems and Computers (ACSSC)•Oct 29, 2023•1 citation

FUNDAMENTAL LIMITS OF COVERT COMMUNICATION IN PACKET CHANNELS

Ramin Soltani

This dissertation focuses on covert communication in channels where the communication takes place by the transmission of packets. Consider a channel where authorized transmitter Jack sends packets to authorized receiver Steve according to a Poisson process with rate $\lambda$ packets per second for a time period $T$. Jack's transmitted packet visit Alice, Willie, Bob and Steve, respectively. Suppose that covert transmitter Alice wishes to communicate information to covert receiver Bob without being detected by a watchful adversary Willie. We consider three sets of assumptions for this channel. For each set of assumptions, we present a technique for establishing covert communication and analyze its fundamental limits: (1) if Willie cannot verify the sources of the packets but he is aware of the channel's packet rate $\lambda$, Alice can insert packets of her own in the channel covertly and Bob can successfully extract them (packet insertion); (2) if Willie can verify the sources of the packets but Alice and Bob can share a codebook and Bob receives the packets after they pass through an $M/M/1$ queue, Alice can establish covert communication with Bob by embedding information in packet arrival timings (timing channel); and (3) if packets have available space and Willie knows the probability density function (pdf) of the packet sizes, Alice can insert her own bits in the packets covertly and Bob can extract them successfully (bit insertion). We discuss the extensions of the first and second techniques to packet channels whose packet timings are governed by a renewal process. Finally, we consider the use of timing channels for network fingerprinting which is a traffic analysis method applicable to breaking the anonymity of networks. Assume Alice and Bob have access to the input and the output links of a network, respectively, where the timings of the flows are governed by independent Poisson point processes. The connections between the input and output links are hidden. We show the degree to which Alice can use flow identifiers (fingerprints) and transmit them via a timing channel to Bob to reveal the input-output connections without being detected by Willie who protects the network. We model the network as parallel $M/M/1$ queues where each queue is shared by a flow from Alice to Bob and other flows independent of the flow from Alice to Bob.

•Apr 13, 2021•1 citation

Covert communications on renewal packet channels

Ramin Soltani, Dennis Goeckel, Don Towsley +1 more

In recent years, the information theory of covert communications, where the very presence of the communication is undetectable to a watchful adversary Willie, has been of great interest. Our recent work introduced the information-theoretic limits for communication by covert users Alice and Bob, over packet channels where the packet timings of legitimate users Jack and Steve are governed by a Poisson point process. Here we consider the extension to timing channels characterized by more general renewal processes of rate λ. We consider two scenarios. In the first scenario, the source of the packets on the channel cannot be authenticated by Willie, and therefore Alice can insert packets into the channel. We show that if the total number of transmitted packets by Jack is N, Alice can covertly insert O(√N)packets and, if she transmits more, she will be detected by Willie. In the second scenario, packets are authenticated by Willie but we assume that Alice and Bob share a secret key; hence, Alice alters the timings of the packets according to a pre-shared codebook with Bob to send information to him over a G/M/1 queue with service rate μ > λ. We show that Alice can covertly and reliably transmit O(N) bits to Bob when the total number of packets sent from Jack to Steve is N.

arXiv:1610.00368•Allerton Conference on Communication, Control, and Computing•Sep 1, 2016•15 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
We study a problem of covert communication over binary symmetric channels (BSC) in an asynchronous setup. Here, Alice seeks to communicate to Bob over a BSC while trying to be covert with respect to Willie, who observes any communication through possibly a different BSC. When Alice communicates, she transmits a message (using a codeword of length n) at a random time uniformly distributed in a window of size Awslots. We assume that Bob has side information about the time of transmission leading to a reduced uncertainty of Abslots for Bob, where Ab<AwA_{b}\lt A_{w}Ab​<Aw​. In this setup, we seek to characterize the limits of covert communication as a function of the timing advantage. When Awis increasing exponentially in n, we characterize the covert capacity as a function of Awand Ab. When Awis increasing sub-exponentially in n, we characterize lower and upper bounds on achievable covert bits and show that positive covert rates are not feasible irrespective of timing advantage. Using numerical work, we illustrate our results for different network scenarios, and also highlight a tradeoff between timing advantage and channel advantage (between Bob and Willie).
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.
Consider a channel where authorized transmitter Jack sends packets to authorized receiver Steve according to a Poisson process with rate λ packets per second for a time period T. Suppose that covert transmitter Alice wishes to communicate information to covert receiver Bob on the same channel without being detected by a watchful adversary Willie. We consider two scenarios. In the first scenario, we assume that warden Willie cannot look at packet contents but rather can only observe packet timings, and Alice must send information by inserting her own packets into the channel. We show that the number of packets that Alice can covertly transmit to Bob is on the order of the square root of the number of packets that Jack transmits to Steve; conversely, if Alice transmits more than that, she will be detected by Willie with high probability. In the second scenario, we assume that Willie can look at packet contents but that Alice can communicate across an M/M/1 queue to Bob by altering the timings of the packets going from Jack to Steve. First, Alice builds a codebook, with each codeword consisting of a sequence of packet timings to be employed for conveying the information associated with that codeword. However, to successfully employ this codebook, Alice must always have a packet to send at the appropriate time. Hence, leveraging our result from the first scenario, we propose a construction where Alice covertly slows down the packet stream so as to buffer packets to use during a succeeding codeword transmission phase. Using this approach, Alice can covertly and reliably transmit O(λT) covert bits to Bob in time period T over an M/M/1 queue with service rate μ > e · λ.
Covert communication is achieved when a transmitter Al-ice can successfully transmit a message to a receiver Bob without being detected by an attentive and capable adversary Willie. Early results demonstrated the difficulty of the covert communications problem: with AWGN discrete-time channels between all parties, onlyO(n)O(\sqrt{n})O(n​)bits can be sent innnnchannel uses. But it was soon recognized that uncertainty about the environment at Willie, for example, uncertainty in his own noise statistics, could allow for a positive rate:O(n)O(n)O(n)bits can be sent covertly innnnchannel uses. However, most covert communication results, including this promising positive rate result, have been obtained for a discrete-time communications channel. Here, we demonstrate that the assumption of a discrete-time channel is problematic when trying to exploit Willie's noise uncertainty. In particular, we demonstrate that if Alice transmitsω(T)\omega(\sqrt{T})ω(T​)bits in a lengthTTTinterval to Bob on a continuous-time channel, then there exists a detector at Willie that can detect her transmission, as the probability of false alarm and missed detectionPMD+PFA→0P_{MD}+P_{FA}\rightarrow 0PMD​+PFA​→0asT→∞T\rightarrow\inftyT→∞. In other words, the communication is not covert, unlike the case of a discrete-time channel.
This dissertation focuses on covert communication in channels where the communication takes place by the transmission of packets. Consider a channel where authorized transmitter Jack sends packets to authorized receiver Steve according to a Poisson process with rate λ\lambdaλ packets per second for a time period TTT. Jack's transmitted packet visit Alice, Willie, Bob and Steve, respectively. Suppose that covert transmitter Alice wishes to communicate information to covert receiver Bob without being detected by a watchful adversary Willie. We consider three sets of assumptions for this channel. For each set of assumptions, we present a technique for establishing covert communication and analyze its fundamental limits: (1) if Willie cannot verify the sources of the packets but he is aware of the channel's packet rate λ\lambdaλ, Alice can insert packets of her own in the channel covertly and Bob can successfully extract them (packet insertion); (2) if Willie can verify the sources of the packets but Alice and Bob can share a codebook and Bob receives the packets after they pass through an M/M/1M/M/1M/M/1 queue, Alice can establish covert communication with Bob by embedding information in packet arrival timings (timing channel); and (3) if packets have available space and Willie knows the probability density function (pdf) of the packet sizes, Alice can insert her own bits in the packets covertly and Bob can extract them successfully (bit insertion). We discuss the extensions of the first and second techniques to packet channels whose packet timings are governed by a renewal process. Finally, we consider the use of timing channels for network fingerprinting which is a traffic analysis method applicable to breaking the anonymity of networks. Assume Alice and Bob have access to the input and the output links of a network, respectively, where the timings of the flows are governed by independent Poisson point processes. The connections between the input and output links are hidden. We show the degree to which Alice can use flow identifiers (fingerprints) and transmit them via a timing channel to Bob to reveal the input-output connections without being detected by Willie who protects the network. We model the network as parallel M/M/1M/M/1M/M/1 queues where each queue is shared by a flow from Alice to Bob and other flows independent of the flow from Alice to Bob.
In recent years, the information theory of covert communications, where the very presence of the communication is undetectable to a watchful adversary Willie, has been of great interest. Our recent work introduced the information-theoretic limits for communication by covert users Alice and Bob, over packet channels where the packet timings of legitimate users Jack and Steve are governed by a Poisson point process. Here we consider the extension to timing channels characterized by more general renewal processes of rate λ. We consider two scenarios. In the first scenario, the source of the packets on the channel cannot be authenticated by Willie, and therefore Alice can insert packets into the channel. We show that if the total number of transmitted packets by Jack is N, Alice can covertly insert O(√N)packets and, if she transmits more, she will be detected by Willie. In the second scenario, packets are authenticated by Willie but we assume that Alice and Bob share a secret key; hence, Alice alters the timings of the packets according to a pre-shared codebook with Bob to send information to him over a G/M/1 queue with service rate μ > λ. We show that Alice can covertly and reliably transmit O(N) bits to Bob when the total number of packets sent from Jack to Steve is N.
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.