An Adaptive Composition Theorem for Maximal Leakage for Binary Inputs
Ibrahim Issa, Aaron B. Wagner · 2022 IEEE International Symposium on Information Theory (ISIT) · 2022
Given a binary random variable X representing sensitive information and n noisy observations Y1, Y2, … , Ynavailable to an adversary, we analyze the maximal leakage $\mathcal{L}\left( {X \to {Y^n}} \right)$ in the following setting modeling adaptive attacks. At each stage i, the adversary may choose an action to interact with the system containing X to obtain Yi. The action may depend on previous realizations of the observations, but the leakage at each stage is limited. We derive an adaptive composition theorem wherein $\mathcal{L}\left( {X \to {Y^n}} \right)$ is bounded in terms of the leakage of each stage. Furthermore, we show that the bound is achieved for $\mathcal{L}\left( {X \to {Z^n}} \right)$ where (Z1, Z2, … , Zn) are conditionally independent given X and each Zicorresponds to the output of a binary erasure channel with the appropriate parameter; moreover, X −Zn−Yncan be coupled as a Markov chain for any feasible Yn. As a corollary of this result and the asymptotic analysis of composition by Wu et al., we show that the binary erasure channel maximizes the Chernoff information between the "rows" of binary-input channels given a maximal leakage constraint. On the other hand, we show that the binary symmetric channel minimizes the Chernoff information for a given maximal leakage constraint.