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:
- 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).
- 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