An Operational Approach to Information Leakage via Generalized Gain Functions

Abstract

We introduce a gain function viewpoint of information leakage by proposing maximal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> -leakage, a rich class of operationally meaningful leakage measures that subsumes recently introduced leakage measures — maximal leakage and maximal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula> -leakage. In maximal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> -leakage, the gain of an adversary in guessing an unknown random variable is measured using a gain function applied to the probability of correctly guessing. In particular, maximal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> -leakage captures the multiplicative increase, upon observing <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$Y$ </tex-math></inline-formula> , in the expected gain of an adversary in guessing a randomized function of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$X$ </tex-math></inline-formula> , maximized over all such randomized functions. We also consider the scenario where an adversary can make multiple attempts to guess the randomized function of interest. We show that maximal leakage is an upper bound on maximal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> -leakage under multiple guesses, for any non-negative gain function <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> . We obtain a closed-form expression for maximal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> -leakage under multiple guesses for a class of concave gain functions. We also study maximal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> -leakage measure for a specific class of gain functions related to the <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula> -loss, that interpolates log-loss ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha =1$ </tex-math></inline-formula> ) and (soft) 0–1 loss ( <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha =\infty $ </tex-math></inline-formula> ). In particular, we first completely characterize the minimal expected <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula> -loss under multiple guesses and analyze how the corresponding leakage measure is affected with the number of guesses. We show that a new measure of divergence that belongs to the class of Bregman divergences captures the relative performance of an arbitrary adversarial strategy with respect to an optimal strategy in minimizing the expected <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$\alpha $ </tex-math></inline-formula> -loss. Finally, we study two variants of maximal <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"> <tex-math notation="LaTeX">$g$ </tex-math></inline-formula> -leakage depending on the type of adversary and obtain closed-form expressions for them, which do not depend on the particular gain function considered as long as it satisfies some mild regularity conditions. We do this by developing a variational characterization for the Rényi divergence of order infinity which naturally generalizes the definition of pointwise maximal leakage to incorporate arbitrary gain functions.

Topics & Concepts