PaperlayerView exact revision on arXiv

Source-linked AI summary

Covert Communication over Noisy Channels: A Resolvability Perspective

Matthieu R. Bloch

arXiv:1503.08778v3cs.IT

TL;DR

The paper asks how to communicate reliably over a noisy channel while remaining covert to a warden observing another channel. It develops a channel-resolvability coding scheme and shows square-root message scaling with reduced or no secret-key requirements under specified channel conditions, while establishing asymptotic limits and extensions.

  • Problem

    The problem is reliable communication over a discrete memoryless channel while keeping transmission covert from a warden observing a second channel.

  • Method

    The paper uses channel resolvability, with modified typical sets to obtain concentration results for low-weight codewords.

  • Results

    The scheme supports O(√n) reliable covert bits over n uses with O(√n) key bits, and needs no key when the legitimate channel is sufficiently better than the warden’s; message and key scalings are asymptotically optimal for DMCs.

  • Takeaways & Limitations

    Channel resolvability reduces the key required for square-root-law covert communication and extends the analysis to secrecy constraints and AWGN channels.

Abstract

from arXiv · show

We consider the situation in which a transmitter attempts to communicate reliably over a discrete memoryless channel while simultaneously ensuring covertness (low probability of detection) with respect to a warden, who observes the signals through another discrete memoryless channel. We develop a coding scheme based on the principle of channel resolvability, which generalizes and extends prior work in several directions. First, it shows that, irrespective of the quality of the channels, it is possible to communicate on the order of $\sqrt{n}$ reliable and covert bits over $n$ channel uses if the transmitter and the receiver share on the order of $\sqrt{n}$ key bits; this improves upon earlier results requiring on the order of $\sqrt{n}\log n$ key bits. Second, it proves that, if the receiver's channel is "better" than the warden's channel in a sense that we make precise, it is possible to communicate on the order of $\sqrt{n}$ reliable and covert bits over $n$ channel uses without a secret key; this generalizes earlier results established for binary symmetric channels. We also identify the fundamental limits of covert and secret communications in terms of the optimal asymptotic scaling of the message size and key size, and we extend the analysis to Gaussian channels. The main technical problem that we address is how to develop concentration inequalities for "low-weight" sequences; the crux of our approach is to define suitably modified typical sets that are amenable to concentration inequalities.

I. INTRODUCTION

The paper revisits covert communication over noisy channels through channel resolvability, reducing secret-key requirements while characterizing optimal message and key scalings. It also extends the framework to secrecy constraints, continuous channels, and AWGN channels.

  • Approach: Channel resolvability reframes covert communication as simulating a warden output process that is difficult to distinguish from no communication.The technical challenge is concentration for low-weight codewords, addressed through modified typical sets.
  • Contributions: O(√n) reliable and covert bits can be communicated over n channel uses with O(√n log n) secret-key bits in a universal scheme.This revisits earlier coding results with a technical refinement and a maximum-key-size guarantee.
  • Contributions: O(√n) reliable and covert bits can be communicated with O(√n) secret-key bits when the warden’s channel statistics are known.If the legitimate user’s channel is sufficiently better than the warden’s channel, no secret key is needed; this extends the result to DMCs.
  • Contributions: The message size and key size achieved by the proposed scheme are asymptotically optimal for DMCs.The converse adapts and extends prior converse results to establish optimality of both scalings.
  • Extensions: The paper extends the covert communication scheme to secrecy constraints and partially to continuous channels, including AWGN channels.The AWGN extension appears as Theorem 6, while secrecy constraints are treated separately.
  • Problem setting: The model uses a DMC for Alice and Bob and another DMC for Willie, who tests whether communication occurred from his observed sequence.An innocent input symbol represents no communication, while absolute-continuity assumptions exclude trivial channel cases.

B. Technical digression: concentration inequalities with low-weight sequences

The analysis explains why standard concentration bounds fail for low-weight sequences and introduces modified typical sets to recover useful concentration results. It also describes the source-resolvability scheme that spreads a secret key and modulates its non-innocent positions to transmit covert information.

  • Concentration challenge: The low-weight input sequence contains only O(ω_n√n) non-innocent symbols, so standard concentration bounds do not yield vanishing error terms.The difficulty arises because only a sublinear number of symbols contribute materially to the relevant sums.
  • Concentration challenge: The proposed remedy is to define modified typical sets that are amenable to concentration inequalities.The paper notes that stronger inequalities such as Bernstein’s or Bennett’s could also help, but it uses suitably modified typical sets.
  • Source-resolvability scheme: The scheme revisits earlier spreading-based covert communication while retaining a secret-key requirement on the order of √n log n bits.The key serves as a seed for generating a spreading sequence, rather than directly indexing transmission positions.
  • Source-resolvability scheme: Theorem 1 analyzes this scheme for DMCs under absolute-continuity conditions and establishes a covert communication construction with parameters determined by the main-channel law.The scheme’s existence statement uses P1 ≪ P0, Q1 ≪ Q0, and Q1 ≠ Q0, with constants depending on the legitimate receiver’s channel but not the warden’s channel.
  • Source-resolvability scheme: The source-resolvability architecture encodes a secret key into a low-weight spreading sequence whose non-innocent positions are modulated by the message.The spreading sequence distribution is designed to approximate the target covert stochastic process at the channel input.

V. CHANNEL-RESOLVABILITY BASED COVERT COMMUNICATION

The channel-resolvability scheme uses a secret key to select among codebooks, balancing reliability within each codebook against warden confusion across all codewords. It reduces the key requirement, can operate without a key when the legitimate channel is sufficiently better, and has asymptotically optimal message and key scalings for DMCs.

  • Architecture and scaling: Channel resolvability replaces source resolvability to reduce the secret-key size to the order of √n bits while preserving covert communication.The key directly helps simulate the covert process at the channel output.
  • Architecture and scaling: The key S selects one of K codebooks, each containing M message codewords; each codebook supports reliability while the aggregate codewords confuse the warden.This architecture separates the reliability and covertness roles across codebook size and total codeword diversity.
  • Keyless operation: No secret key is needed when D(P1∥P0) > D(Q1∥Q0), whereas a key is required when D(P1∥P0) ≤ D(Q1∥Q0).In the keyless case, a single codebook K = 1 achieves both channel resolvability and reliability.
  • Analysis: The random-codebook analysis combines channel reliability and channel resolvability using typical-set arguments adapted to low-weight codewords.The decoder uses the shared key and an information-density-based typicality test to identify a unique message or declare no communication.
  • Optimality and extensions: The extension to continuous channels requires concentration conditions such as sub-Gaussian information-density behavior, and the paper discusses the AWGN case separately.The stated absolute-continuity requirements restrict the class of channels considered, although they include AWGN channels.
  • Optimality and extensions: The message and key-size scalings of the proposed DMC scheme are asymptotically optimal.The paper states that converse results establish optimality for both quantities.

VI. CONVERSE RESULT FOR DMCS

The converse establishes that the message and key-size scalings achieved by the covert communication scheme are asymptotically optimal for DMCs.

  • The converse proof adapts results from prior converse analyses to establish optimality of the asymptotic limits in Corollary 2.The proof specifically adapts the converse technique of, [5], and.
  • For reliable communication, the converse upper-bounds log M using mutual information between the transmitted variables and the receiver’s observations.The bound includes the decoding error term Hb(ϵn) and the error-weighted message-size term ϵn log M.
  • The warden-channel divergence scales as D(Qµn∥Q0) ≈ µn^2χ2(Q1∥Q0)/2, with matching bounds up to factors 1 ± √µn.
  • Vanishing covertness divergence and diverging message size require √nµn → 0 and nµn → ∞.
  • The converse also derives bounds on the combined quantity log M + log K, including equality cases associated with the achievable scheme.These bounds are obtained by combining the receiver and warden information inequalities.

VII. EXTENSIONS AND APPLICATIONS

The extensions summarize optimal message and key-size scalings for covert communication and indicate that the proposed scheme’s scalings are optimal.

  • The optimal scaling of log M is summarized in Table II under the condition that the warden’s relative entropy divergence vanishes asymptotically.
  • The optimal scaling of log K is summarized in Table III under the same asymptotic covertness condition.

B. Multiple symbols

The multiple-symbol extension assigns low activation probabilities to several non-innocent symbols and characterizes the resulting optimal covert communication scalings.

  • Multiple symbols: The analysis extends to multiple symbols {xi} by assigning each non-innocent symbol xi probability piαn, with the probabilities satisfying Σpi = 1.
  • Multiple symbols: Theorem 4 applies when Q0 is not a mixture of the warden distributions {Qi}, while each Qi and Pi is absolutely continuous with respect to Q0 and P0.
  • Multiple symbols: With αn = ωn√n, where ωn ∈ o(1) ∩ ω(1/√n), the construction provides a covert communication scheme for sufficiently large n.
  • Multiple symbols: The extension characterizes the asymptotic scaling and establishes optimality by adapting the proof of Theorem 3.

C. Covert and secret communication

The paper separates covertness from secrecy and shows how secret keys support both, while a sufficiently better legitimate channel can provide semantic secrecy without an additional key.

  • Covert and secret communication: Undetectability alone does not prevent the warden from extracting information about the transmitted message, motivating an additional semantic-secrecy constraint.
  • Covert and secret communication: When D(P1∥P0) > D(Q1∥Q0), semantic secrecy may be obtained without an extra key by using a wiretap-channel code.
  • Covert and secret communication: The architecture in Section IV already provides secrecy through a one-time pad using key bits bS.
  • Covert and secret communication: Theorem 5 constructs covert communication schemes across the two divergence regimes, using resolvability and one-time padding for the relevant message components.
  • Covert and secret communication: The regimes are illustrated by scaling message and key bits by √n as a function of D(P1∥P0) for fixed D(Q1∥Q0).
  • Covert and secret communication: For D(P1∥P0) ≤ D(Q1∥Q0), secret keys are required for both covertness and secrecy; when D(P1∥P0) > D(Q1∥Q0), keys are required only for added secrecy.

D. Gaussian channels

The Gaussian-channel analysis extends the covert-communication framework to continuous channels, with a weaker total-variation result because a key lemma does not apply when the innocent symbol is zero. As in the discrete-memoryless case, no key is required when D(P1∥P0) > D(Q1∥Q0).

  • Gaussian channels: Gaussian channels are analyzed with innocent symbol x0 = 0, extending the framework to a practically relevant continuous setting.The Gaussian-channel discussion specifies this setting and introduces AWGN distributions Pi ∼ N(xi, σ).
  • Gaussian channels: The continuous-channel extension retains one lemma but not another because the condition µ0 = 0 prevents applying Lemma 4.The resulting analysis uses a slightly weaker result in terms of total variation.
  • Gaussian channels: Covertness in the Gaussian setting is established through total variation, whose vanishing ensures covert communication.The proof uses the relation α + β ⩾ 1 − V and the triangle inequality.
  • Gaussian channels: The continuous-memoryless theorem assumes P1 ≪ P0, Q1 ≪ Q0, and Q1 ≠ Q0, with additional conditions on the likelihood-ratio random variables.The theorem introduces αn ≜ ωn√n with ωn ∈ o(1) ∩ ω(1/√n).
  • Gaussian channels: No secret key is required when D(P1∥P0) > D(Q1∥Q0), as in the discrete-memoryless case.This condition is stated explicitly for the AWGN analysis.

APPENDIX A KULLBACK-LEIBLER (KL) DIVERGENCE AND HYPOTHESIS TESTING

This appendix interprets KL divergence through the warden’s hypothesis test even when the covert distribution is not i.i.d. It relates test effectiveness to Jensen–Shannon divergence and uses KL minimization as a sufficient route to ineffective detection.

  • Hypothesis-testing interpretation: The usual i.i.d. interpretation of KL-divergence error exponents does not apply because bQn is not i.i.d.The appendix instead develops an operational interpretation tailored to this testing setting.
  • Hypothesis-testing interpretation: The warden’s test is modeled as a Bernoulli output with parameter α under H0 and 1−β under H1.The rejection region determines the Type I error α and Type II error β.
  • Hypothesis-testing interpretation: J(Bα, B1−β) measures test effectiveness, ranging from 0 exactly when α + β = 1 to 1 exactly when α = β = 0.Thus, the divergence distinguishes ineffective testing from perfect discrimination.
  • Hypothesis-testing interpretation: Covert communication requires making J(Bα, B1−β) small, for which minimizing D is sufficient by the log-sum inequality.The appendix connects the operational testing criterion to the KL-divergence analysis.
  • KL expansion: The KL expansion includes terms proportional to αn^2, αn^3, and αn^4 with χ2, χ3, and χ4 divergences, respectively.The displayed expansion is part of the derivation combined to obtain the desired results.

APPENDIX D PROOF OF LEMMA 3

The proof of Lemma 3 bounds decoding failure by separating three error events and controlling each with typicality and averaging arguments. Combining these bounds yields the claimed result for sufficiently large n.

  • Error analysis: Three decoding error events are considered: transmitted-codeword atypicality, confusion with another codeword, and false decoding when no communication occurs.A union bound reduces the proof to bounding these three terms.
  • Error analysis: The first error event occurs when the transmitted codeword and received sequence are outside the typical set Anγ.This term is analyzed as the first component of the union-bound expression.
  • Error analysis: The second event is decoding confusion caused by another codeword satisfying the same typicality condition with the received sequence.The proof analyzes this term for competing message-codeword indices.
  • Error analysis: The third event is a false decoding in which the decoder finds a typical codeword despite no communication.This term is bounded similarly for each message index.
  • Bounding technique: Jensen’s inequality and expectations over the remaining random codewords support the bounds for the analyzed terms.The proof applies these averaging steps to both single-index and message-key codeword ensembles.
  • Conclusion: For n large enough that 1 − αn ⩾ 1/2, the combined bounds establish the desired result.The conclusion follows after combining the intermediate bounds.

APPENDIX G SPECIAL CASES OF CHANNELS

The appendix discusses channel cases excluded from the main assumptions P1 ≪ P0, Q1 ≪ Q0, and Q1 ≠ Q0.

  • Special cases: Special channel cases excluded by the main assumptions are discussed separately.The excluded conditions are P1 ≪ P0, Q1 ≪ Q0, and Q1 ≠ Q0.

A. Q1 is not absolutely continuous w.r.t. Q0 or Q1 = Q0

The section contrasts regimes where the warden cannot distinguish transmissions with regimes where the receiver channel has output symbols that reveal x1 unambiguously. These conditions determine whether covert communication is impossible, can use keyless schemes, or supports linear message scaling.

  • Q1 not absolutely continuous w.r.t. Q0: If Q1 is not absolutely continuous with respect to Q0, then D(Q1∥Q0) is infinite, and the section states that covert bits cannot be transmitted.This contrasts with the Q1 = Q0 case, where message size can scale as Θ(n).
  • Q1 = Q0: When Q1 = Q0, the warden’s observations are independent of transmitted signals, allowing standard reliability coding and Θ(n) message scaling.The achievable rate can approach the main-channel capacity.
  • P1 not absolutely continuous w.r.t. P0: When P1 is not absolutely continuous with respect to P0, the set S identifies x1 without ambiguity with probability κ at the channel output.Here S consists of outputs having positive probability under P1 and zero probability under P0.
  • P1 not absolutely continuous w.r.t. P0: Theorem 7 states that, under P1 not absolutely continuous w.r.t. P0, Q1 absolutely continuous with respect to Q0, and Q1 ≠ Q0, covert schemes exist with αn = ωn√n.The scaling satisfies ωn ∈ o(1) ∩ ω(1/√n).
  • P1 not absolutely continuous w.r.t. P0: Under P1 not absolutely continuous w.r.t. P0, the decoder uses positions whose outputs lie in S and accepts a codeword whose x1-symbols match all such positions.Otherwise, it declares an error; the reliability analysis considers insufficient identifying positions and competing matching codewords.
  • Keyless covert communication: The corresponding construction can operate without a secret key, and Corollary 4 identifies its asymptotic scaling constant while noting dependence on the choice of ωn.Theorem 8 provides a converse whose scaling is asymptotically tight relative to the achievable regime.
Loading 1503.08778v3…