Source-linked AI summary
Fundamental Limits of Communication with Low Probability of Detection
Ligong Wang, Gregory Wornell, Lizhong Zheng
TL;DR
The paper studies communication that remains difficult for an output-observing adversary to detect, formalized through a relative-entropy constraint. It develops DMC and AWGN analyses and shows square-root scaling in the nonredundant DMC case, with exact scaling constants.
Problem
The problem is to communicate while preventing an adversary from determining whether transmission is occurring, rather than merely hiding message content.
Source: §I · p. 1Method
The paper analyzes randomized secret-key communication under a relative-entropy detectability constraint for DMCs and AWGN channels.
Source: §I · p. 1Results
For DMCs with a nonredundant off symbol, the maximum transmitted information scales like √n, and the paper derives exact scaling constants.
Source: §I · p. 1, B. Case 2: input symbol 0 is not… · p. 3, §III · p. 4Takeaways & Limitations
The results characterize the information-growth limit for covert communication over the studied memoryless channels.
Source: §I · p. 1The conclusions are scoped to memoryless channels; the paper notes that channel memory or unknown noise conditions may enable positive-rate LPD communication.
Source: §VI · p. 10
Abstract
from arXiv · showhide
This paper considers the problem of communication over a discrete memoryless channel (DMC) or an additive white Gaussian noise (AWGN) channel subject to the constraint that the probability that an adversary who observes the channel outputs can detect the communication is low. Specifically, the relative entropy between the output distributions when a codeword is transmitted and when no input is provided to the channel must be sufficiently small. For a DMC whose output distribution induced by the "off" input symbol is not a mixture of the output distributions induced by other input symbols, it is shown that the maximum amount of information that can be transmitted under this criterion scales like the square root of the blocklength. The same is true for the AWGN channel. Exact expressions for the scaling constant are also derived.
I. INTRODUCTION
The paper studies covert communication, where an adversary should not know whether communication is occurring, and establishes square-root scaling for broad DMCs with exact scaling constants.
Motivation
- The paper studies LPD communication, requiring the adversary to remain uncertain whether the legitimate parties are communicating at all.This differs from secrecy, which hides message content but not necessarily communication activity.Source: §I · p. 1
Contributions
Model assumptions
- The setting uses a DMC with an off symbol, a sufficiently long shared secret key, and an adversary observing the same outputs as the receiver.The LPD criterion bounds relative entropy between outputs under transmission and no input.Source: §I · pp. 1–2
Related problems
- LPD communication differs from steganography because LPD adds noise after codeword selection, whereas steganography embeds messages into an already generated data file.Although both settings exhibit square-root behavior, they require different analyses.Source: §I · p. 2
Paper organization
- The paper analyzes DMCs with redundant and nonredundant off symbols before deriving general DMC expressions, a simpler special-case formula, and AWGN results.The paper concludes with remarks on future directions.Source: §I · p. 2
II. PROBLEM FORMULATION FOR DMCS
The formulation defines covert communication over a DMC using an off symbol, randomized secret-key codebooks, an error constraint, and a relative-entropy detectability constraint.
Channel model
- The DMC has finite input and output alphabets, with input symbol 0 designated as the off symbol used whenever no message is sent.The channel transition law is denoted W(·|·).Source: §II · p. 2
Random coding
- The transmitter and receiver use a secret-key-selected random codebook, while the adversary knows its selection distribution but not the realized code.Because the adversary observes the same outputs as the receiver, deterministic codes cannot provide LPD communication.Source: §II · p. 2
LPD constraint
- The formulation requires the induced output distribution to remain close in relative entropy to the n-fold output distribution produced by the off symbol.This criterion limits the adversary’s ability to distinguish transmission from silence.Source: §II · p. 2
Support reduction
- Input symbols whose output support is not contained in the off-output support must be excluded because they make the relative entropy infinite.The channel can therefore be reduced by removing those inputs and unsupported output symbols.Source: §II · p. 2
Problem objective
- The goal is to maximize log |M| for a length-n random code satisfying the LPD constraint and average error probability at most ϵ, denoted K_n(δ, ϵ).The error requirement is later taken to be arbitrarily small.Source: §II · p. 2
Regimes
- The maximum information can scale linearly with n when the off symbol is redundant, or like √n when it is not redundant.Channels that cannot satisfy the paper’s standing condition, such as the binary erasure channel, permit no nontrivial LPD communication.Source: §II · p. 2
A. Case 1: input symbol 0 is redundant
When the off symbol is redundant, a positive communication rate is achievable under the LPD constraint, reaching the channel’s unconstrained capacity in the binary symmetric example.
A. Case 1: input symbol 0 is redundant
- The case is characterized by a positive-rate regime in which the square-root scaling constant L is infinite.All logarithms are natural, so information is measured in nats.Source: A. Case 1: input symbol 0 is redundant · p. 2
- Positive communication rate is achievable when a distribution satisfying (5) exists, with the rate determined by the mutual information maximized over such distributions.The input distribution must assign zero probability to the off symbol and induce the off-output distribution.Source: A. Case 1: input symbol 0 is redundant · p. 2
- An IID codebook satisfying the output-matching condition achieves vanishing relative entropy and reliable communication below I(P, W).Violating the output-matching condition makes the relative entropy grow linearly with blocklength, while assigning mass to the off symbol is suboptimal.Source: A. Case 1: input symbol 0 is redundant · p. 3
- For the binary symmetric channel with an off symbol, the uniform input distribution on {−1, 1} achieves capacity 1 − Hb(p), unchanged by the LPD constraint.The off symbol induces a uniform output distribution, making it redundant in this example.Source: A. Case 1: input symbol 0 is redundant · p. 3, Figure 1 · p. 3
B. Case 2: input symbol 0 is not redundant
When the off symbol is not redundant, positive communication rates are impossible under the LPD constraint, and the maximum transmitted information instead grows on the order of √n.
B. Case 2: input symbol 0 is not redundant
- When no distribution satisfies the output-matching condition, the achievable information Kn grows like √n rather than linearly with blocklength.The corresponding scaling constant L is finite and positive under the stated DMC conditions.Source: B. Case 2: input symbol 0 is not… · p. 3
- The square-root scaling constant L has units of √nat and, by definition, may be infinite, as it is in Case 1.Source: B. Case 2: input symbol 0 is not… · p. 3
- A positive rate would require a nonvanishing fraction of non-off symbols, which changes the average output distribution and makes the relative entropy diverge.Because the off-output distribution cannot be represented as a mixture of nonzero-input output distributions, the LPD constraint is violated.Source: B. Case 2: input symbol 0 is not… · p. 3
III. GENERAL EXPRESSIONS FOR L FOR ALL DMCS
The section derives general expressions for the LPD scaling constant L for DMCs, including a single-letter characterization and a computable formula when the off symbol is nonredundant. It also gives achievability and converse arguments and evaluates the formula for a binary symmetric channel.
General characterization
- Theorem 1 provides a general characterization of L for any DMC, supported by converse and achievability arguments.The achievability proof uses randomly generated IID codebooks, joint-typicality decoding, and a zero-rate information-spectrum argument.Source: §III · pp. 3–5
Channel cases
- When the off symbol is redundant, L is infinite; otherwise, the analysis focuses on the nonredundant case.The paper notes that channels not satisfying the standing condition, including the binary erasure channel, cannot support nontrivial LPD communication.Source: §III · p. 3
Computable expression
- For a DMC satisfying the regularity condition with a nonredundant off symbol, L is positive, finite, and given by a computable single-letter expression.The expression maximizes a ratio involving divergence from the off-output distribution and the induced output-distribution deviation.Source: §III · p. 5
Binary symmetric channel
- For the binary symmetric channel, L is approximately 0.94 √nat at p = 0.083, while it approaches zero as p approaches either 0 or 0.5.At small p, the LPD constraint forces the non-off input to be used sparsely because the two input symbols are easy to distinguish; at p near 0.5, channel capacity also vanishes.Source: §III · p. 5, Figure 3 · p. 5
Proof strategy
- The proof constructs input distributions that mix the off symbol with a vanishing probability of non-off symbols, yielding the square-root scaling regime.The induced relative entropy is approximated through Fisher information, while mutual information is dominated by the first-order term in the mixing probability.Source: §III · pp. 5–6
Limit characterization
- The limit inferior in the definition of L can be replaced by an ordinary limit, producing a more convenient equivalent expression.This follows from the existence argument established through the proof of Theorem 2.Source: §III · p. 6
IV. A SIMPLER BUT LESS GENERAL EXPRESSION FOR L
Under Condition 1, the paper derives an upper bound on L for DMCs and gives a sufficient geometric condition making that bound exact, while showing symmetry alone need not suffice.
Theorem 3
- Theorem 3 gives a formula for L for a DMC satisfying Condition 1, in terms of Q0, Q∗, and the variance under Q0.The equality condition in the supporting lemma depends on the support of a candidate input distribution being contained in that of a capacity-achieving distribution.Source: §IV · p. 6
Upper bound
- The upper bound is tight for many channels, including the binary symmetric channel, but requires an additional condition for general DMCs.The paper introduces this condition after stating that the bound is tight for many channels.Source: §IV · pp. 6–7
Sufficient condition
- If Condition 1 holds and the linear system (55) has a nonnegative solution, Theorem 4 makes the bound in (40) exact.The solution condition means the tangent vector s lies in the convex cone generated by the non-off conditional output distributions relative to Q0.Source: §IV · p. 7
- The condition constructs a valid nearby output distribution, so both the upper-bound expression and the corresponding lower-bound expression hold with equality.The proof chooses a nonnegative solution to construct an input distribution and evaluates the resulting output distribution in the lower bound.Source: §IV · pp. 7–8
Example 3
- For the k-array uniform-error channel, the relevant solution is nonnegative and Theorem 4 supplies the resulting expression for L.The channel’s capacity-achieving output distribution is uniform; the displayed result gives (1 − p) log(1/(1 − p)) + p log((k − 1)/p).Source: §IV · p. 8
Example 4
- For the ternary symmetric channel, the bound gives 0.66 whereas the actual value is L = 0.62 because the required exponential-family segment leaves the feasible output-distribution set.The same obstruction is described geometrically as s not lying in the relevant convex cone; Fig. 4 depicts this departure.Source: §IV · p. 8, Figure 4 · p. 8
A. Converse for Theorem 5
The AWGN converse bounds reliable covert communication by relating mutual information to input second moment and the relative-entropy constraint, forcing vanishing input power.
Converse setup
- The AWGN converse applies the DMC converse argument to continuous distributions whose output marginals satisfy the LPD constraint.The maximization is over input-output distributions induced by the AWGN law and constrained through the output marginal Qn.Source: A. Converse for Theorem 5 · p. 8
Converse bound
- A zero-mean Gaussian input maximizes mutual information at fixed second moment, while the output second moment equals the input second moment plus σ2.These facts convert the information bound into one expressed through the input second moment ρn.Source: A. Converse for Theorem 5 · p. 8
Converse conclusion
- The LPD constraint forces the input second moment ρn to tend to zero and yields the converse bound on the achievable information scaling.The argument uses the Gaussian maximum-entropy property to relate D(Qn∥Q0) to the second moment and then combines the resulting inequalities.Source: A. Converse for Theorem 5 · p. 9
- The derivation concludes the converse part of Theorem 5 for the AWGN channel.The converse establishes the upper limit later matched by the Gaussian achievability construction.Source: A. Converse for Theorem 5 · p. 9
B. Achievability for Theorem 5
The AWGN achievability proof uses Gaussian inputs and verifies both the LPD constraint and reliable decoding at the target information scaling.
Achievability strategy
- Because the finite-alphabet achievability proof does not extend generally to continuous channels, the AWGN proof restricts attention to Gaussian input distributions.This restriction makes the achievability argument simpler for the AWGN channel.Source: B. Achievability for Theorem 5 · p. 9
Code construction
- The construction uses an IID Gaussian codebook with variance ρn and joint-typicality decoding.Each codeword is generated independently, and the decoder uses joint typicality.Source: B. Achievability for Theorem 5 · p. 9
LPD verification
- The Gaussian code construction is checked against the LPD condition by analyzing the induced output distribution.The proof begins by verifying that the output sequence satisfies the required relative-entropy constraint.Source: B. Achievability for Theorem 5 · p. 9
Reliability
- Reliable transmission follows by evaluating the information-density ratio and showing that the resulting sequence of message sizes is achievable under the AWGN constraint.The proof analyzes the mean and variance of the relevant information-density expression.Source: B. Achievability for Theorem 5 · p. 9
Achievability conclusion
- The variance calculation and Chebyshev argument establish the required concentration, completing the achievability proof of Theorem 5.Expanding the square shows that every summand’s expectation tends to zero, which establishes the intermediate concentration statements.Source: B. Achievability for Theorem 5 · pp. 9–10
VI. CONCLUDING REMARKS
The concluding remarks connect the results to practical LPD systems and emphasize that channel memory or discretization choices can materially affect covert communication.
Discretization
- The results suggest that the optimal discretization of a continuous-alphabet channel may depend heavily on whether an LPD requirement is imposed.The paper notes that a DMC can represent a discretization of a continuous-alphabet channel, including AWGN examples.Source: §VI · p. 10
Practical scope
- Positive-rate LPD systems can work in practice even when an idealized memoryless channel model appears not to permit positive rates.The paper attributes this possibility to realistic channels having memory and to the adversary’s ignorance of a fixed, unknown noise parameter.Source: §VI · p. 10