PaperlayerView exact revision on arXiv

Source-linked AI summary

Fundamental Limits of Communication with Low Probability of Detection

Ligong Wang, Gregory Wornell, Lizhong Zheng

arXiv:1506.03236v3cs.IT

TL;DR

The paper studies communication that remains difficult for an adversary to detect, especially when the transmitter must be off when not communicating. It establishes square-root scaling for broad DMCs and AWGN channels and derives exact scaling constants, while noting a limitation concerning channels with memory.

  • Problem

    LPD communication requires preventing an adversary from learning whether legitimate parties are communicating, including settings where the transmitter must be switched off when idle.

  • Method

    The paper analyzes LPD communication over DMCs and AWGN channels, proving square-root-law results and deriving exact scaling constants.

  • Results

    The maximum information scales like √n for a broad class of DMCs and for AWGN channels; for the binary symmetric channel, the maximum scaling constant is approximately 0.94 √nat at p = 0.083.

  • Takeaways & Limitations

    When the off-symbol output is not a mixture of nonzero-input outputs, positive communication rates are unavailable, and repeated use of square-root-case codes increases detection probability.

  • Takeaways & Limitations

    The paper notes that communication exploiting an unknown, fixed channel parameter and long-lived channel memory remains ongoing research.

Abstract

from arXiv · show

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 communication that conceals whether transmission occurs, using relative entropy to constrain detection by an adversary observing the same outputs as the receiver. It establishes square-root scaling for broad DMCs and derives exact scaling constants for DMCs and AWGN channels.

  • LPD communication hides whether legitimate parties are communicating, not merely the message content, from an adversary.
  • The square-root law holds for a broad class of DMCs, with exact scaling constants also characterized for DMCs and AWGN channels.
  • Unlike wiretap formulations, the adversary and intended receiver observe the same channel outputs, and a sufficiently long shared secret key is assumed.
  • The receiver is assumed to know when transmission begins, supported by secret-key synchronization before message transmission.
  • The paper considers an always-off transmitter baseline and constrains relative entropy between transmitted-codeword and no-input output distributions.
  • For the nonredundant case, the paper develops general DMC characterizations, simpler formulas for some DMCs, and an AWGN formulation.

II. PROBLEM FORMULATION FOR DMCS

The DMC formulation uses an off input symbol, shared randomness, and an output-distribution relative-entropy constraint. The maximum log-message-set size is governed by whether the off symbol is redundant.

  • The DMC has finite input and output alphabets, with input symbol 0 designated as the off symbol transmitted when no message is sent.
  • The transmitter and receiver select a random code using a sufficiently long shared secret key, while the adversary knows the selection distribution but not the realized code.
  • The induced output distribution must have sufficiently small relative entropy from the n-fold off-output distribution Q0^n.
  • Symbols whose output support is not contained in the off-output support are excluded because using them would make the relative entropy infinite.
  • The objective is to maximize log |M| subject to the LPD constraint and average error at most ϵ, defining the maximum as K_n(δ, ϵ).
  • If the off symbol is redundant, K_n can grow linearly with n; otherwise, it grows like √n.

A. Case 1: input symbol 0 is redundant

When the off symbol is redundant, positive communication rates remain achievable under the LPD constraint, including for the binary symmetric channel with an off symbol.

  • A. Case 1: input symbol 0 is redundant: A distribution P satisfying (5) enables positive communication rates under the LPD constraint.The proposition applies when the off input is redundant, with the maximum rate taken over distributions satisfying (5).
  • A. Case 1: input symbol 0 is redundant: Random IID codebooks satisfying (5) have zero relative entropy divergence, while rates below I(P, W) permit arbitrarily small decoding error as n grows.Codebooks whose empirical input distribution violates (5b) instead produce divergence that grows linearly with n.
  • A. Case 1: input symbol 0 is redundant: Any distribution satisfying (5b) but assigning positive probability to the off symbol is suboptimal, because conditioning on nonzero inputs preserves (5b) and increases mutual information.Thus an optimal distribution can be chosen with P(0)=0.
  • A. Case 1: input symbol 0 is redundant: For the binary symmetric channel with an off symbol, the optimal LPD input is uniform on {−1, 1}.The off symbol induces a uniform output distribution, while the channel has cross-over probability p.
  • A. Case 1: input symbol 0 is redundant: The LPD-constrained capacity of this channel equals its unconstrained capacity, 1 −Hb(p).The channel is illustrated as a binary symmetric channel with an additional off input symbol.

B. Case 2: input symbol 0 is not redundant

When the off symbol is not redundant, positive communication rates are unavailable under the LPD constraint, and the maximum information grows on the square-root scale.

  • B. Case 2: input symbol 0 is not redundant: No distribution P satisfying (5) exists when the off symbol is not redundant.This case is the focus of the paper’s next sections.
  • B. Case 2: input symbol 0 is not redundant: √n is the growth scale of the maximum transmitted information K_n in this case.The paper defines the corresponding normalized limit inferior L and notes that it has units of √nat.
  • B. Case 2: input symbol 0 is not redundant: The scaling constant L can be infinite in Case 1, but is characterized for the nonredundant case in the following sections.Its value is introduced through a limit inferior involving K_n(δ, ϵ).
  • B. Case 2: input symbol 0 is not redundant: A positive rate would require a nonvanishing fraction of non-off symbols, making the average output distribution differ from the off-output distribution.Because the off-output distribution cannot be represented as a mixture of nonzero-input output distributions, the resulting divergence is positive.
  • B. Case 2: input symbol 0 is not redundant: The resulting relative entropy divergence grows without bound with n, violating the LPD constraint.This explains why positive communication rates cannot be achieved in this case.

III. GENERAL EXPRESSIONS FOR L FOR ALL DMCS

The section develops general single-letter and computable expressions for the LPD scaling constant L for DMCs, proving converse and achievability results. It also characterizes how L is optimized and illustrates its behavior on the binary symmetric channel.

  • General characterization: Theorem 1 gives a general characterization of the maximum codebook logarithm under the LPD constraint for any DMC.The proof combines Fano’s inequality and information-quantity bounds for the converse with random coding and joint-typicality decoding for achievability.
  • Achievability: Achievability follows when IID-generated codebooks have size below the theorem’s bound, with decoding error tending arbitrarily small as blocklength grows.The argument uses a zero-rate achievability analysis rather than the standard asymptotic equipartition property.
  • Computable expression: Theorem 2 states that, for qualifying nonredundant-off DMCs, L is positive and finite and has a computable single-letter expression.The expression uses an output distribution induced by an input distribution supported away from the off symbol.
  • Binary symmetric channel: For the binary symmetric channel, L approaches zero both as p approaches 0.5 and as p approaches zero, attaining approximately 0.94 √nat at p = 0.083.At small p, the LPD constraint forces the non-off input to be used sparsely despite capacity approaching 1 bit per use.
  • Optimization: The optimizing input distribution concentrates asymptotically on the distribution maximizing the leading term in the mutual-information expansion.This follows because the first term in the expansion dominates as n tends to infinity.

IV. A SIMPLER BUT LESS GENERAL EXPRESSION FOR L

Under Condition 1, the paper derives a simpler upper bound for L and gives a sufficient geometric condition for equality. Examples show the bound is tight for some channels but can fail even for symmetric channels.

  • Condition 1 requires a capacity-achieving input distribution that uses all input symbols.
  • Theorem 3 characterizes L using the capacity-achieving output distribution Q∗ and the variance under the off-output distribution Q0.
  • The upper bound is obtained by minimizing divergence over the exponential family connecting Q0 and Q∗, temporarily dropping the feasible-output constraint.
  • If the linear system in (55) has a nonnegative solution, the upper bound holds with equality because the relevant tangent lies in the generated convex cone.
  • For the k-ary uniform-error channel, the capacity-achieving output distribution is uniform and the linear system has a nonnegative solution.
  • For the ternary symmetric channel, the bound gives 0.66 while the actual value is L = 0.62 because the exponential-family direction is infeasible.

V. AWGN CHANNELS

The paper extends the LPD communication problem to the AWGN channel with the off input set to zero. It states an exact expression for the AWGN scaling constant, independent of the noise power.

  • The AWGN model has real input and output, Gaussian noise of variance σ2, and zero as the off input symbol.
  • The encoder and decoder use a random code subject to the LPD constraint, without imposing average- or peak-power constraints.
  • Theorem 5 gives the AWGN scaling constant, which is independent of the noise power σ2.

A. Converse for Theorem 5

The converse proof bounds AWGN communication under the LPD constraint by relating input second moment, output divergence, and mutual information. Gaussian distributions provide the extremal comparison needed for the bound.

  • The AWGN converse remains valid from the earlier converse argument, with optimization over input-induced output distributions satisfying the LPD condition.
  • A zero-mean Gaussian input maximizes mutual information among input distributions with the same second moment.
  • The output second moment equals the input second moment plus σ2 because the input and noise are independent.
  • For the output divergence from Q0 to vanish asymptotically, the input second moment must tend to zero.

B. Achievability for Theorem 5

The achievability proof uses Gaussian random codebooks rather than the finite-alphabet argument used for DMCs. It verifies both low detectability and reliable transmission for the AWGN channel.

  • The finite-alphabet achievability proof does not apply directly to AWGN channels, so the paper proves achievability specifically for Gaussian inputs.
  • The random codebook uses independent codewords whose symbols are IID N(0, ρn).
  • The proof first verifies that the Gaussian codebook satisfies the LPD condition.
  • The achievable number of transmitted nats is established by evaluating the likelihood ratio and proving the required concentration properties.
  • The variance calculation and asymptotic vanishing of each summand complete the achievability proof.

VI. CONCLUDING REMARKS

The concluding remarks connect LPD communication to practical channel discretization and positive-rate systems, while identifying channel memory as an important setting for further study.

  • LPD requirements may substantially change which discretization of a continuous-alphabet channel is optimal.Different discretizations of the same AWGN channel can lead to different implications under an LPD requirement.
  • Positive-rate LPD systems may be practical when transmitted signals have wide spectra and resemble white noise.
  • Channel memory may enable undetected communication by exploiting an adversary’s ignorance of a fixed, unknown noise parameter.A representative scenario has noise varying over a coherence time longer than the codeword length; further study is ongoing.
Loading 1506.03236v3…