Source-linked AI summary
Limits of Reliable Communication with Low Probability of Detection on AWGN Channels
Boulat A. Bash, Dennis Goeckel, Don Towsley
TL;DR
The paper addresses previously unexplored information-theoretic limits for low-probability-of-detection communication. It proves a square-root law: reliable LPD communication is limited to O(√n) bits in n channel uses, with detection-error constraints and converse consequences.
Problem
The information-theoretic limits and performance requirements for achieving LPD communication had not been explored or analyzed prior to this work.
Method
The paper quantifies conditions for the existence and maintenance of an LPD channel by proving a square-root-law theorem for communication between Alice, Bob, and Willie.
Results
O(√n) information bits can be transmitted in n channel uses under LPD constraints, while exceeding this scale causes detection by Willie with probability one or a non-zero decoding-error probability.
Takeaways & Limitations
LPD communication over the considered channels is fundamentally subject to a square-root limit on the number of transmissible bits.
Abstract
from arXiv · showhide
We present a square root limit on the amount of information transmitted reliably and with low probability of detection (LPD) over additive white Gaussian noise (AWGN) channels. Specifically, if the transmitter has AWGN channels to an intended receiver and a warden, both with non-zero noise power, we prove that $o(\sqrt{n})$ bits can be sent from the transmitter to the receiver in $n$ channel uses while lower-bounding $α+β\geq1-ε$ for any $ε>0$, where $α$ and $β$ respectively denote the warden's probabilities of a false alarm when the sender is not transmitting and a missed detection when the sender is transmitting. Moreover, in most practical scenarios, a lower bound on the noise power on the channel between the transmitter and the warden is known and $O(\sqrt{n})$ bits can be sent in $n$ LPD channel uses. Conversely, attempting to transmit more than $O(\sqrt{n})$ bits either results in detection by the warden with probability one or a non-zero probability of decoding error at the receiver as $n\rightarrow\infty$.
I. INTRODUCTION
The paper establishes information-theoretic limits for low-probability-of-detection communication over AWGN channels, where Alice communicates with Bob while Willie detects transmissions. Its main result is a square-root scaling law governing reliably transmissible information under low detection probability.
- Channel model and motivation: The paper develops fundamental bounds for LPD communication over wireless AWGN channels between Alice, Bob, and passive warden Willie.Alice transmits low-power signals to Bob while Willie attempts to classify them as noise or communication.
- Main result: O(√n) bits can be transmitted reliably in n channel uses while maintaining a low probability of detection when Willie’s channel has non-zero noise power.Alice and Bob require a sufficiently long shared secret, and the warden’s detection-error sum can be lower-bounded by 1 − ε.
- Main result: o(√n) information bits can be sent while ensuring α + β ≥ 1 − ε for any ε > 0, where α is false alarm probability and β is missed-detection probability.The theorem assumes non-zero AWGN powers on both Alice–Bob and Alice–Willie channels.
- Main result: If a positive lower bound on Willie’s noise power is known, Alice can maintain the same detection-error lower bound while transmitting O(√n) bits.This is the practical scenario identified by the theorem’s achievability result.
- Converse: Transmitting ω(√n) bits forces either arbitrarily reliable detection by Willie or a nonzero probability of decoding error at Bob as n grows.This converse holds regardless of the shared-secret length.
- Interpretation: The LPD channel has zero information-theoretic capacity in bits per channel use, despite permitting a significant number of bits across n channel uses.The paper therefore studies total information transmitted over n uses rather than a constant rate.
II. PREREQUISITES
The paper models LPD communication over discrete-time real-valued AWGN channels, with Bob decoding Alice’s message while Willie tests whether transmission occurred. It bounds Willie’s detection errors using total variation and relative entropy, then establishes square-root-scale achievability results.
- Channel and hypotheses: Alice transmits n real-valued symbols over an AWGN channel to Bob, while Willie applies statistical hypothesis testing to his observations.The null hypothesis is no transmission; the alternative is transmission of Alice’s noisy codeword.
- Channel and hypotheses: α denotes Willie’s false-alarm probability, while β denotes his missed-detection probability.The sum α + β captures the trade-off between the two detection errors.
- Detection analysis: Pinsker’s inequality and product relative entropy convert the total-variation objective into an upper bound on divergence across n observations.The analysis uses relative entropy’s connection to Neyman–Pearson testing and bounds it through Taylor expansion.
- Achievability: Theorem 1.1 achieves α + β ≥ 1 − ε for any ε > 0 while transmitting the stated square-root-scale message size when Willie’s noise power has a known positive lower bound.The theorem assumes sufficient shared secret length and positive AWGN power on Willie’s channel.
- Detection analysis: The optimal detector satisfies α + β = 1 − VT(P0, P1), so limiting total variation limits Willie’s detection performance.P0 describes noise-only observations and P1 describes Alice’s transmitted codeword corrupted by noise.
- Achievability: Under the peak-power theorem, Bob’s decoding error probability averaged over codebooks decays exponentially to zero while the transmitted message remains below the square-root scale.The result is paired with a corresponding lower bound on Willie’s summed detection errors.
2. As in the proof
The achievability proof constructs low-power random codewords and analyzes Willie’s divergence and Bob’s decoding error as the symbol amplitude decreases with blocklength. It also addresses public codebooks and the secret needed to preserve Willie’s i.i.d. observation model.
- Willie’s detector: Taylor expansion of the divergence bounds Willie’s detector performance when Alice’s symbol power decreases with n.The proof uses the fourth-order term after lower-order terms vanish, with symbol power a^2 = Pf.
- Bob’s decoder: Bob’s hard-decision front end creates a binary symmetric channel with crossover probability pe = Q(a/σb).An ML decoder then yields an averaged error bound involving nR and the binary entropy H(pe).
- Bob’s decoder: For a constant ρ < 1, Bob’s averaged decoding error decays exponentially to zero while he obtains nR = o(√n) bits.This establishes reliable communication below the square-root scale under the proof’s low-power construction.
- Codebook secrecy: Selecting a specific good codebook can violate the i.i.d. codeword condition required to limit Willie’s detection capability.The proof therefore begins with performance averaged over codebooks rather than directly selecting one uniformly good codebook.
- Codebook secrecy: A public codebook can support O(√n) reliable bits, but Willie may exploit that codebook by performing the same decoding as Bob.The paper proposes protecting communication with a shared random binary vector rather than revealing the full codebook.
2. Alice XORs k and the binary representation
The paper connects LPD communication to steganographic square-root laws and explains how secret-key masking preserves the distributional conditions used in the proof. It identifies secret length relative to message length as an open research boundary.
- Secret masking: XORing a shared binary vector with the hard-decision output lets Bob recover the masked bits before ML decoding.The shared vector is kept secret and is not reused, preserving the i.i.d. observation assumption used for Willie’s analysis.
- Secret length: The square-root law implies that the shared O(n)-bit secret is quadratic in the message length M = O(√n).An alternative construction uses an O(n log n)-bit secret in the appendix.
- Open problem: Developing LPD communication with a shared secret linear or sublinear in message size remains an open theoretical research problem.The paper identifies secret efficiency as a key direction for future work.
- Relation to steganography: LPD communication and steganography share a square-root form because relative entropy is locally quadratic.The paper relates this behavior to Fisher information for nearby distributions in the same parametric family.
- Relation to steganography: Finite-alphabet steganography can modify O(√n) covertext symbols and embed O(√n log n) bits, whereas noisy LPD channels allow only O(√n) bits in n uses.The additional channel noise creates a need for error correction in the LPD setting.
IV. CONVERSE
The converse shows that transmitting more than O(√n) bits forces either reliable detection by Willie or a non-zero decoding error at Bob. The proof uses a power detector and relates Willie’s detectability to codeword power, then bounds Bob’s decoding performance.
- Detection test: Willie’s simple power detector observes all n channel uses and compares the summed squared observations with a threshold.The detector’s error probabilities are bounded using the statistic’s means, variances, and Chebyshev’s inequality.
- Converse theorem: ω(√n) transmitted bits imply either Willie can detect Alice with arbitrarily low α + β or Bob cannot decode with arbitrarily low error.This is the section’s main converse conclusion as n →∞.
- Power constraint: Codewords with average symbol power ω(1/√n) are detectable with arbitrarily low error probability, whereas O(1/√n) power prevents the missed-detection bound from vanishing.Maintaining a nontrivial lower bound on Willie’s total error therefore requires a positive fraction of low-power codewords.
- Goodput consequence: Because only low-power messages can remain sufficiently undetectable, the probability of successfully decoding such messages at Bob limits the overall goodput.The argument defines goodput through messages that have a non-zero probability of remaining undetected and bounds their contribution to decoding performance.
A. Relationship to Previous Work in Communications
The paper distinguishes LPD communication from secrecy, anonymous communication, spread spectrum, and cognitive radio. Its setting concerns preventing a warden from detecting transmission, without requiring the receiver’s channel to be better than the adversary’s.
- Spread spectrum: Spread spectrum systems reduce power spectral density by transmitting over bandwidth Ws much wider than WM, but they remain limited by the square root law.The paper’s narrowband analysis translates to wideband channels, including spread spectrum systems.
- Distinction from prior work: LPD communication studies fundamental limits on information that can be transmitted while keeping detection probability low.The paper frames this as distinct from prior communication problems focused on decoding secrecy or traffic analysis.
- Information-theoretic secrecy: Unlike information-theoretic secrecy, the LPD setting targets the adversary’s ability to detect transmissions and does not require Bob’s channel to be better than Willie’s.The secrecy literature instead considers secure communication when the legitimate receiver has a better channel.
- Anonymous communication: Unlike network traffic analysis, the LPD scenario prevents Willie from detecting Alice’s transmission with high probability before any network-layer analysis.The settings and approaches therefore differ despite related objectives.
- Cognitive radio: The paper notes that cognitive-radio interference constraints differ fundamentally from the properties of an undetectable signal.It reports no cognitive-radio work addressing the latter issue.
B. Impact of Adversary’s a priori Knowledge of the Transmission State on Achievability
The achievability results remain asymptotically valid when Willie has a nontrivial prior distribution over whether Alice transmits. Additional prior information helps Willie, but the square root law still holds.
- Prior transmission knowledge: A nontrivial prior distribution on Alice’s transmission state does not impact the asymptotic results.The analysis considers prior probabilities π0 and π1 for no transmission and transmission.
- Generalized error bound: With prior probabilities π0 and π1, Willie’s average hypothesis-testing error satisfies Pe ≥ min(π0, π1) − max(π0, π1)VT(P0, P1).P0 and P1 denote Willie’s observation distributions under the two transmission hypotheses.
- Effect on achievability: Additional information about the likelihood of Alice transmitting helps Willie, but bounds on total variation distance preserve the square root law.The result therefore does not depend asymptotically on assuming a particular nontrivial prior.
C. Mapping to a Continuous-time Channel
The discrete-time LPD model maps to a continuous-time channel by pulse shaping and sampling. Ideal sinc signaling yields the standard Nyquist representation, while practical pulse shapes motivate higher-rate sampling and future cyclostationary-detection analysis.
- Discrete-to-continuous mapping: Sampling the continuous-time signaling band at 2W samples per second leads directly to the paper’s discrete-time model.This supports the demonstration of Alice’s fundamental LPD channel limits.
- Ideal pulse shaping: With ideal sinc pulse shaping and Ts = 1/2W, the system has no intersymbol interference and Willie and Bob can extract all signaling information.The construction follows the Nyquist sampling criterion under a bandwidth constraint of W Hz.
- Practical sampling: Practical raised-cosine pulses with excess bandwidth can make sampling above 2W useful for signal detection even when the Nyquist ISI criterion is satisfied.The paper identifies cyclostationary detection in this setting as a promising direction for future work.
VI. CONCLUSION
The paper establishes a square-root law for LPD communication and identifies open questions involving secret length, practical network dynamics, and channel imperfections.
- The authors quantify conditions for the existence and maintenance of an LPD channel.
- The number of LPD bits transmitted in n channel uses is bounded by O(√n).
- LPD communication using a secret linear in message length remains an open theoretical research problem.
- Future work should analyze LPD packet transmission under delay constraints and examine network dynamism.
- More realistic scenarios should include fading and interference from other nodes, while friendly jamming may improve LPD communication.
- A fundamental future question is whether a shadow wireless network can be established and maintained with active and passive wardens.
APPENDIX
The appendix supports the paper’s achievability and detector analyses, including a randomized binary coding construction and continuity arguments for the proof’s integral expressions.
- The proof verifies continuity and integrability conditions for K(x,a) and its derivatives using dominating functions and Gaussian absolute moments.
- Rearrangement and dominated convergence establish the continuity condition required by Lemma 1.
- The coding scheme randomly selects symbol periods using biased coin flips, then applies a binary code to the selected periods.The expected number of selected periods is τn.
- The scheme uses shared secret randomness, including selected symbol locations and a random binary vector.Representing selected locations requires O(√n log n) secret bits in the described construction.
- Choosing τa^2 at most a quantity proportional to 1/√n limits the performance of Willie’s detector.The product τa^2 is the average symbol power used by Alice.
- The construction enables Alice to reliably transmit O(√n) bits in n LPD channel uses.
C. Proof of the generalized version of Fact 1
The proof formulates Willie’s decision problem through conditional densities and derives an error bound for the optimal hypothesis test using posterior probabilities and L1 inequalities.
- Willie’s test selects between null and alternate hypotheses represented by conditional densities p0(x) and p1(x).
- The optimal test uses the maximum a posteriori rule to maximize the probability of a correct decision.
- The proof lower-bounds the test error probability using triangle inequalities for the L1 norm, with a tighter bound when π1 exceeds π0.
- Combining the resulting inequalities completes the generalized Fact 1 proof.