Information Leakage in Zero-Error Source Coding: A Graph-Theoretic Perspective
This work provides theoretical insights into information leakage in zero-error source coding for researchers in information theory and coding.
This paper investigates information leakage in zero-error source coding, where the source coding problem is defined by a confusion graph. The authors provide a single-letter characterization of the optimal normalized leakage under a basic adversarial model and observe that it equals the optimal compression rate with fixed-length codes, both achievable by deterministic schemes. They also derive single-letter lower and upper bounds for generalized adversarial models.
We study the information leakage to a guessing adversary in zero-error source coding. The source coding problem is defined by a confusion graph capturing the distinguishability between source symbols. The information leakage is measured by the ratio of the adversary's successful guessing probability after and before eavesdropping the codeword, maximized over all possible source distributions. Such measurement under the basic adversarial model where the adversary makes a single guess and allows no distortion between its estimator and the true sequence is known as the maximum min-entropy leakage or the maximal leakage in the literature. We develop a single-letter characterization of the optimal normalized leakage under the basic adversarial model, together with an optimum-achieving scalar stochastic mapping scheme. An interesting observation is that the optimal normalized leakage is equal to the optimal compression rate with fixed-length source codes, both of which can be simultaneously achieved by some deterministic coding schemes. We then extend the leakage measurement to generalized adversarial models where the adversary makes multiple guesses and allows certain level of distortion, for which we derive single-letter lower and upper bounds.