Covert Identification Over Binary-Input Discrete Memoryless Channels

Qiaosheng Zhang, Vincent TanOpenReview 2023 · OpenReview

TL;DR

This paper introduces and solves the "covert identification" problem: how to reliably send an identification message to receivers while simultaneously hiding the fact that communication is happening from a warden. The authors establish a "square-root law" for this problem, showing that the message size grows as exp(exp(Θ(√n))) over n channel uses, and crucially, this can be achieved without any shared secret key between sender and receivers.

What Problem Does This Paper Address?

Imagine a scenario where a government needs to inform a group of people about a potential health risk, but also wants to keep this communication secret from foreign adversaries. Each person needs to know if the message is specifically for them (identification), but the overall fact of communication must remain hidden. This is the essence of the covert identification problem. It combines the challenges of reliable communication (getting the message through a noisy channel) with the security requirement of covertness (hiding the communication from an eavesdropper, or "warden"). While previous work has addressed covert communication (hiding the content of a message) and standard identification (reliably sending an ID), this paper tackles the intersection: reliably sending an ID covertly. A key challenge is that traditional methods for achieving high identification rates often require shared keys, which might not be available in all covert scenarios.

Methods

The authors employ a two-stage approach for their achievability proof:

  1. Weak Covert Identification Code: They first construct a "weak" code using a random coding argument combined with Pulse-Position Modulation (PPM). PPM is chosen for its favorable properties in ensuring covertness. This stage guarantees covertness and vanishing average error probabilities for the third kind of error (mistaking no communication for a message), but only vanishing maximum error probabilities for the first two kinds (misidentifying the correct message or identifying the wrong message).
  2. Code Refinement: A second stage refines the weak code. This process is crucial for ensuring that the maximum error probabilities for all three types of errors vanish, while maintaining the covertness and the message rate. This refinement is non-standard, as it preserves the channel output distribution induced by the original code, which is essential for covertness.

For the converse proof (showing the limits of what's possible), they leverage results from channel resolvability, adapting them to handle the stringent input constraints imposed by the covertness requirement. This involves an expurgation argument to remove problematic codewords.

Datasets

Not discussed in the paper. The paper focuses on theoretical limits and achievability using abstract channel models.

Key Insights and Ideas

  • The Square-Root Law for Covert Identification: The most striking result is the "square-root law" for covert identification. Unlike standard identification where message size scales exponentially with blocklength ($exp(exp(O(n)))$), covert identification is limited by a square root in the exponent ($exp(exp(Θ(√n)))$). This highlights how covertness significantly constrains communication capabilities.
  • Keyless Covert Identification: Surprisingly, the paper shows that the optimal covert identification capacity can be achieved without any pre-shared secret key between the sender and receivers. This is a significant departure from some prior work on covert communication, where keys were sometimes necessary.
  • PPM's Dual Role: Pulse-Position Modulation (PPM) is shown to be effective for both achieving the desired identification rates and satisfying the covertness constraints, making it a powerful tool for this problem.
  • Non-Standard Refinement: The code refinement technique used is novel because it preserves the channel output distribution, a critical property for maintaining covertness, unlike traditional expurgation methods that might alter it.

Key Results

  • Covert Identification Capacity: The paper characterizes the covert identification capacity, denoted $C_s$, for binary-input discrete memoryless channels. This capacity is given by $C_s = \frac{1}{\sqrt{2\chi^2(Q_1||Q_0)D(P_1||P_0)}}$, where $P$ and $Q$ represent channel transition probabilities for the receiver and warden, respectively.
  • Achievability of $C_s$: The authors demonstrate that a message size of $exp(exp(Θ(√n)))$ can be reliably and covertly transmitted over $n$ channel uses, achieving the derived capacity $C_s$.
  • Keyless Achievability: This capacity is achieved without any shared secret key.
  • Converse Bound: A converse bound is established, showing that no scheme can exceed this capacity.

Limitations and Future Work

  • Weak Converse: The paper mentions that the converse proof is a "weak converse," meaning error probabilities are allowed to vanish. A "strong converse" would be more desirable, and the authors suggest that developing a more general channel resolvability result for stringent input constraints might be key to achieving this.
  • Error Exponent: The paper focuses on the first-order asymptotics (the capacity). Deriving the error exponent (how quickly the error probability decays with blocklength) for covert identification is suggested as future work. This would require adapting techniques from standard identification problems while accounting for covertness constraints.
  • Alternative Covertness Metrics: The work primarily uses KL-divergence for covertness. Exploring other metrics like variational distance or probability of missed detection is proposed for future research.

Summary updated

Abstract

This paper considers the covert identification problem in which a sender aims to reliably convey an identification (ID) message to a set of receivers via a binary-input discrete memoryless channel (BDMC), and simultaneously to guarantee that the communication is covert with respect to a warden who monitors the communication via another independent BDMC. We prove a square-root law for the covert identification problem. This states that an ID message of size exp(exp(Θ(√{ n})) can be transmitted over n channel uses. We then characterize the exact pre-constant in the Θ(·) notation. This constant is referred to as the covert identification capacity. We show that it equals the recently developed covert capacity in the standard covert communication problem, and somewhat surprisingly, the covert identification capacity can be achieved without any shared key between the sender and receivers. The achievability proof relies on a random coding argument with pulse-position modulation (PPM), coupled with a second stage which performs code refinements. The converse proof relies on an expurgation argument as well as results for channel resolvability with stringent input constraints.
BibTeX
@misc{zhang2023covert,
  author = {Qiaosheng Zhang and Vincent Tan},
  title = {{Covert Identification Over Binary-Input Discrete Memoryless Channels}},
  year = {2023},
  url = {https://openreview.net/forum?id=pOCOv-RFhc9},
  howpublished = {OpenReview},
}
Figure