PaperlayerView exact revision on arXiv

Source-linked AI summary

Covert Communication Gains from Adversary's Ignorance of Transmission Time

Boulat A. Bash, Dennis Goeckel, Don Towsley

arXiv:1403.1013v5cs.IT

TL;DR

The paper asks whether covert communication can exceed the square root law when Willie does not know the transmission time. It analyzes a slotted AWGN channel with secret single-slot selection and shows that Alice can reliably transmit O(min{√(n log T(n)), n}) bits while keeping Willie’s detector ineffective, without Bob knowing the slot when T(n)<2^(c_T n).

  • Problem

    The paper addresses whether secretly hiding Alice’s transmission slot improves on the O(√n) covert-bit limit that assumes Willie knows when transmission occurs.

  • Method

    The paper models T(n) AWGN slots of n symbol periods and has Alice randomly select one slot secretly before transmission.

  • Results

    O(min{√(n log T(n)), n}) covert bits can be transmitted reliably while Willie’s detector becomes arbitrarily close to ineffective.

  • Takeaways & Limitations

    The covert-bit gain does not require Bob to know the transmission slot when T(n)<2^(c_T n).

Abstract

from arXiv · show

The recent square root law (SRL) for covert communication demonstrates that Alice can reliably transmit $\mathcal{O}(\sqrt{n})$ bits to Bob in $n$ uses of an additive white Gaussian noise (AWGN) channel while keeping ineffective any detector employed by the adversary; conversely, exceeding this limit either results in detection by the adversary with high probability or non-zero decoding error probability at Bob. This SRL is under the assumption that the adversary knows when Alice transmits (if she transmits); however, in many operational scenarios he does not know this. Hence, here we study the impact of the adversary's ignorance of the time of the communication attempt. We employ a slotted AWGN channel model with $T(n)$ slots each containing $n$ symbol periods, where Alice may use a single slot out of $T(n)$. Provided that Alice's slot selection is secret, the adversary needs to monitor all $T(n)$ slots for possible transmission. We show that this allows Alice to reliably transmit $\mathcal{O}(\min\{\sqrt{n\log T(n)},n\})$ bits to Bob (but no more) while keeping the adversary's detector ineffective. To achieve this gain over SRL, Bob does not have to know the time of transmission provided $T(n)<2^{c_{\rm T}n}$, $c_{\rm T}=\mathcal{O}(1)$.

I. INTRODUCTION

The paper studies covert communication when Willie does not know which slot Alice will use. In a slotted AWGN channel, secretly selecting one of T(n) slots increases the reliably transmissible covert-bit scale while keeping Willie’s detector ineffective.

  • Motivation: The square root law permits O(√n) covert bits in n AWGN channel uses, while exceeding this scale causes detection or nonzero decoding error.
  • Model: Alice is restricted to one secretly selected slot among T(n) slots, each containing n symbol periods.Willie must consider every slot when searching for Alice’s transmission.
  • Converse: Transmitting more than O(√(n log T(n))) bits using n consecutive symbol periods leads to detection with high probability or unreliable decoding.
  • Mechanism: Willie’s detector uses the maximum observed slot power, whose higher noise-only baseline forces a higher threshold than when the transmission slot is known.This threshold increase enables additional covert information.
  • Main result: Secret slot selection allows Alice to transmit O(min{√(n log T(n)), n}) covert bits while maintaining arbitrarily low detection probability.The result assumes random selection among T(n)=ω(1) slots under the stated AWGN and power constraints.
  • Receiver knowledge: Bob need not know the transmission slot when T(n)<2^(c_T n), whereas larger T(n) requires at most log T(n) additional secret bits to identify it.Here c_T is a positive constant.

II. PREREQUISITES

The model gives Willie the task of distinguishing Alice’s transmission from noise across multiple slots, without knowing which slot was selected. Covertness is defined through the false-alarm and missed-detection trade-off, requiring Willie’s test to be only slightly better than guessing.

  • Channel model: Alice selects one slot uniformly at random from T(n) slots, each containing n symbol periods, before transmission.
  • Hypothesis testing: Willie does not know the transmission slot and tests his entire observation set to distinguish noise-only operation from transmission.
  • Hypotheses: Under H0, Alice does not transmit and Willie observes i.i.d. AWGN samples; under H1, one slot has a different distribution.
  • Detection criterion: The false-alarm and missed-detection probabilities characterize the trade-off in Willie’s hypothesis test.
  • Detection criterion: PFA + PMD ≥ 1 − ϵ ensures that Willie’s detector is ineffective for any ϵ > 0.

III. ACHIEVABILITY

The achievability analysis transforms Willie’s likelihood-ratio statistic and proves that its behavior under the two hypotheses makes detection ineffective. A coding scheme then supports reliable covert transmission while the transmission-dependent slot contribution vanishes asymptotically.

  • Proof strategy: The paper explicitly analyzes Willie’s optimal detector rather than relying only on relative-entropy bounds used in earlier achievability proofs.
  • Construction: Alice and Bob secretly choose a transmission slot and use a secret shared before the potential transmission.
  • Adversary knowledge: Willie knows Alice’s channel-input and noise distributions and the slot boundaries, but not the selected slot or codebook.
  • Test statistic: A one-to-one rescaling converts the likelihood-ratio statistic into a weighted sum across T(n) independent slot variables.
  • Covertness proof: If the slot-dependent term converges to zero in probability while the remaining sum satisfies central-limit conditions, PFA + PMD ≥ 1 − ϵ.
  • Reliability: The random coding argument extends prior reliability proofs after the covertness condition is established.

B. Average Power Constraint

Under an average power constraint, Alice uses random codebooks embedded in a secretly selected slot, while Willie’s likelihood ratio aggregates evidence across all slots. The construction supports reliable covert transmission with a rate governed by n and T(n), and Bob can decode without the slot index below an exponential slot-count threshold.

  • Model and construction: Alice and Bob use a slotted AWGN channel with T(n) = ω(1) slots, each containing n symbol periods, under a finite average power constraint.
  • Code construction: Alice secretly selects one slot and encodes the message using a random Gaussian codebook associated with that slot.
  • Willie’s detector: Willie’s likelihood ratio combines the slot statistics through a LogSumExp expression because he does not know which slot was selected.
  • Covertness: PFA + PMD ≥ 1 − ϵ follows when the relevant likelihood-ratio bound converges to zero for any ϵ > 0.
  • Bob’s decoding: Bob does not need to know the selected slot when T(n) < 2^(c_T n), because decoding error probability then decays to zero.
  • Achievable throughput: O(min{√(n log T(n)), n}) covert bits can be transmitted reliably in a randomly selected n-symbol slot.

C. Peak Power Constraint

Under a peak power constraint, the paper constructs covert communication over one secretly selected slot and analyzes Willie’s detection and Bob’s decoding. The construction supports a rate governed by n log T(n), while Bob need not know the transmission slot when T(n)<2^{c_T n}.

  • The construction reduces the required pre-shared secret to O(n) bits when T(n)<2^{c_T n}.
  • Theorem 1.2 considers a slotted AWGN channel with T(n)=ω(1) slots of n symbols under a finite peak power constraint P_max.
  • Alice secretly selects one slot, encodes messages into length-n binary codewords, and keeps the codebook unknown to Willie.The symbols are drawn from {−a,a}, with a^2<P_max; the codebook is secretly shared by Alice and Bob.
  • Willie’s observation model averages over the unknown transmission slot and unknown codebook, producing a likelihood-ratio analysis for detection.The analysis evaluates the likelihood under no transmission and transmission hypotheses using the slot uncertainty.
  • P_FA+P_MD≥1−ε for any ε>0, so Willie’s detector is ineffective under the construction.
  • Bob’s decoding error probability decays to zero when Alice transmits the supported number of bits in the selected slot.Knowledge of the selected slot ensures reliable decoding, and the paper also shows that this knowledge is unnecessary when T(n)<2^{c_T n}.

IV. CONVERSE

The converse bounds covert communication when Alice’s transmission location is unknown to Willie. It shows that exceeding the paper’s scaling forces either reliable detection by Willie or a non-vanishing decoding error at Bob.

  • The achievability result is summarized as n log T(n) covert bits reliably transmitted using one of the available slots.
  • Theorem 2 considers transmission over n consecutive symbol periods placed arbitrarily within nT(n) observations.
  • If Alice exceeds the supported covert scaling, then Willie detects her with high probability or Bob cannot decode with arbitrarily low error probability.
  • For log T(n)=ω(n), an average power constraint limits reliable communication to O(n) bits in n channel uses.
  • Willie partitions his observations into T(n) non-overlapping subsequences of n observations and thresholds the maximum subsequence power.
  • A constant threshold can make the false-alarm probability arbitrarily small for sufficiently large n when log T(n)=O(n).

V. DISCUSSION

The discussion section situates the paper within prior covert-communication studies. The supplied passages provide only a pointer to an overview of the area.

  • The paper relates its results to other studies of covert communication and points readers to an overview in.

A. Relationship with Steganography

The paper connects timing-based covert communication to steganography through shared square-root-law behavior and a batch-covertext interpretation. The analogy has limits because standard communication systems cannot generally replace part of the noise source.

  • Steganography hides information by altering fixed-size finite-alphabet covertext objects, such as images.
  • Steganographic systems can safely modify O(√n) symbols in an n-symbol covertext to hide an O(√n log n)-bit message.
  • The square-root laws in covert communication and steganography arise from the mathematics of statistical hypothesis testing.
  • The extra log n factor in the steganographic scaling is attributed to the absence of noise in that setting.
  • Timing-based covert communication is equivalent to using one of T(n) covertext objects of size n to embed a message, with Willie examining all objects because he does not know which was used.
  • The authors are not aware of work on this particular batch-steganography problem, though they suggest their result could likely be extended to it.
  • The paper notes that an empirical covertext model can permit O(n) embedded bits, but this relies on replacing part of the covertext.
  • Replacing part of the covertext cannot be done in standard communication systems unless Alice controls Willie’s noise source.

B. Related Work in Physical Layer Covert Communication

Physical-layer covert communication builds on spread-spectrum techniques, while recent SRL work formalizes covert-bit limits and extends them across assumptions about Willie’s knowledge. This paper improves on the SRL by exploiting Willie’s ignorance of transmission timing.

  • Spread-spectrum systems suppress signal power spectral density below the noise floor, providing covertness and resistance to jamming, fading, and interference.
  • The fundamental SRL for covert communication was derived recently, renewing the field and motivating follow-on work on pre-shared-secret size.
  • Related work extends the SRL to quantum channels and characterizes the optimal constant hidden by its big-O notation.
  • Other studies show that incomplete knowledge of Willie’s noise variance can permit O(n) covert bits and even positive-rate covert communication.
  • This paper improves on the SRL by exploiting Willie’s ignorance of transmission timing rather than uncertainty about channel parameters.
  • Prior work also analyzes covert communication when Willie knows slot boundaries, with later results removing that requirement.

VI. CONCLUSION AND FUTURE WORK

The paper secretly assigns Alice one n-symbol slot among T(n) slots, increasing covert throughput while keeping Willie’s detector ineffective. The gain does not require Bob to know the transmission slot below an exponential T(n) threshold, and larger slot sets require additional secret bits.

  • Secretly pre-arranging one n-symbol slot among T(n) slots enables Alice to transmit O(min{n, n log T(n)}) bits reliably on an AWGN channel while keeping Willie’s detector arbitrarily close to ineffective.
  • The multiplicative information increase over the standard SRL is obtained without requiring Bob to know which slot contains the transmission when T(n) < 2^c_Tn.
  • When T(n) ≥ 2^c_Tn, achieving the gain requires only an additional log T(n) pre-shared secret bits.
  • The authors identify combining these results with jammer-assisted covert communication to enable covert networks as future work.

APPENDIX A

Appendix A establishes a lower bound on Willie’s combined false-alarm and missed-detection probabilities for arbitrary thresholds by partitioning the threshold line into three regions. The argument uses pointwise Gaussian convergence and yields P_FA + P_MD ≥ 1 − ϵ for sufficiently large n.

  • The analysis partitions the real number line into three threshold regions for studying the event P(E_C(τ(n), δ)).
  • Region 1: For thresholds below G, pointwise convergence of F_S(n)(z) to Φ(z) supplies a lower bound on the detection-error event for sufficiently large n.
  • Region 3: For thresholds above H, the analogous Gaussian-convergence argument lower-bounds the missed-detection probability for sufficiently large n.
  • Region 2: For G ≤ τ(n) ≤ H, a δ-spaced sequence and monotonicity of F_S(n)(z) extend the lower bound to every intermediate threshold.
  • Combining the relevant error events with DeMorgan’s Law and the union bound gives P_FA + P_MD ≥ 1 − ϵ for all sufficiently large n.
  • The lemma remains valid for any limiting distribution with a continuous density, although that generality is unnecessary here.

APPENDIX B

Appendix B analyzes Bob’s decoding error under known transmission time and binary modulation, using random Gaussian codebooks and Euclidean-distance error events. It concludes that reliable throughput scales as O(n) under constant amplitude and as O(na^2) when the amplitude vanishes.

  • The appendix analyzes Bob’s decoding error when the transmission time is known and Alice uses binary modulation satisfying a peak-power constraint.
  • The appendix presents an alternative analysis adapted for Theorem 1.2, whose earlier proof contains minor technical errors that do not change the main results.
  • The proof uses independently generated Gaussian codewords, Euclidean-distance error events, and a union bound over competing codewords.
  • For codewords differing in j locations, their squared Euclidean distance is 4ja^2, which supports the averaged error analysis.
  • When the modulation amplitude squared is O(1), Bob’s decoding error probability decays to zero and M = O(n) bits are achievable.
Loading 1403.1013v5…