An Operational Approach to Information Leakage via Generalized Gain Functions

Gowtham R. Kurri, Lalitha Sankar, Oliver KosutIEEE Trans. Information Theory 2022 · OpenReview

TL;DR

This paper introduces "maximal g-leakage," a flexible framework for quantifying information leakage that generalizes existing measures. It provides operational guarantees for privacy mechanisms and offers new insights into how adversaries can learn information, especially when allowed multiple guesses.

What Problem Does This Paper Address?

In privacy and security, a fundamental question is how much sensitive information (represented by a random variable X) can be inferred by an adversary observing some data (represented by a random variable Y). Existing measures of information leakage, like maximal leakage and maximal $\alpha$-leakage, provide valuable insights but are often tied to specific adversary models or guessing strategies. This paper aims to create a more general and operationally meaningful framework by allowing the adversary's success to be measured by an arbitrary "gain function" applied to their probability of correctly guessing. This generalization is crucial for understanding leakage in more realistic scenarios and for designing privacy mechanisms that offer robust guarantees against a wider range of adversaries.

Methods

The core of this work is the introduction of maximal g-leakage, where 'g' represents an arbitrary non-negative gain function. This function quantifies the adversary's success based on their probability of correctly guessing a randomized function of the secret data X. The paper then extends this to scenarios with multiple guesses, where an adversary can attempt to guess the secret multiple times.

Key techniques include:

  • Variational characterizations: The authors develop new variational characterizations for Rényi divergence of order infinity. This transforms abstract divergence measures into optimization problems, making them easier to analyze and compute.
  • Duality in linear programming: A technique is used to transform complex optimization problems involving multiple random variables into simpler ones involving a single variable.
  • Analysis of specific gain functions: The paper focuses on gain functions related to $\alpha$-loss, which interpolate between log-loss and 0-1 loss, providing a tunable measure of leakage.
  • Exploiting convexity and concavity: Properties of gain functions (concavity) and loss functions (convexity) are leveraged to derive closed-form expressions and establish bounds.

Datasets

Not discussed in the paper. The paper focuses on theoretical analysis of random variables and probability distributions, not on empirical evaluation with specific datasets.

Key Insights and Ideas

  • Flexibility of Gain Functions: By allowing arbitrary gain functions, the framework captures a broader spectrum of adversary capabilities and success metrics, moving beyond fixed loss functions.
  • Multiple Guesses Matter: The paper demonstrates that the number of guesses an adversary has significantly impacts leakage, and it provides methods to quantify this impact.
  • Connection to Information-Theoretic Measures: The work establishes strong links between maximal g-leakage and established information-theoretic quantities like Sibson mutual information and Rényi divergence, providing a unified perspective.
  • Robustness of Leakage Measures: For certain variants of g-leakage (opportunistic and maximal realizable), the leakage measures are shown to be independent of the specific gain function, as long as it satisfies mild regularity conditions. This is a powerful result for practical applications.
  • Bregman Divergences for Performance: A new divergence measure based on Bregman divergences is introduced, which effectively captures the relative performance of different adversarial strategies.

Key Results

  • Upper Bound: Maximal leakage is shown to be an upper bound on maximal g-leakage under multiple guesses for any non-negative gain function.
  • Closed-Form Expressions: Closed-form expressions for maximal g-leakage under multiple guesses are derived for classes of concave gain functions and for a specific gain function $g(t) = 1+t$ in the binary case.
  • $\alpha$-Loss Analysis: The paper fully characterizes minimal expected $\alpha$-loss under multiple guesses and analyzes its behavior with the number of guesses.
  • Variational Characterization: A new variational characterization for $\infty$-Rényi divergence is developed, which naturally extends pointwise maximal leakage and leads to closed-form expressions for variants of maximal g-leakage.
  • Robustness Result: Opportunistic and maximal realizable g-leakages are shown to be independent of the gain function (under mild conditions), simplifying their application.

Limitations and Future Work

  • Non-negative Gain Functions: While the paper studies a particular non-positive gain function (log-loss), the primary focus is on non-negative gain functions. Characterizing maximal g-leakage for general classes of gain functions remains an open area.
  • Reverse Direction of Bounds: The paper shows that maximal a-leakage under k guesses is at least that of a single guess. Proving the reverse direction (i.e., maximal a-leakage under k guesses is at most that of a single guess) is an open question.
  • Generalization of Pointwise Leakage: The work generalizes pointwise maximal leakage to arbitrary gain functions, but further exploration of its properties (like composition and data-processing) is suggested.
  • Practical Applications: While the theoretical framework is robust, applying these generalized leakage measures to specific real-world privacy-utility trade-off problems and designing optimal privacy mechanisms based on these insights is a promising direction.

Summary updated

Abstract

We introduce a \emph{gain function} viewpoint of information leakage by proposing \emph{maximal $g$-leakage}, a rich class of operationally meaningful leakage measures that subsumes recently introduced leakage measures -- {maximal leakage} and {maximal $\alpha$-leakage}. In maximal $g$-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 $g$-leakage captures the multiplicative increase, upon observing $Y$, in the expected gain of an adversary in guessing a randomized function of $X$, 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 $g$-leakage under multiple guesses, for any non-negative gain function $g$. We obtain a closed-form expression for maximal $g$-leakage under multiple guesses for a class of concave gain functions. We also study maximal $g$-leakage measure for a specific class of gain functions related to the $\alpha$-loss. In particular, we first completely characterize the minimal expected $\alpha$-loss under multiple guesses and analyze how the corresponding leakage measure is affected with the number of guesses. Finally, we study two variants of maximal $g$-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\'{e}nyi divergence of order infinity which naturally generalizes the definition of pointwise maximal leakage to incorporate arbitrary gain functions.
BibTeX
@article{kurri2022operational,
  author = {Gowtham R. Kurri and Lalitha Sankar and Oliver Kosut},
  title = {{An Operational Approach to Information Leakage via Generalized Gain Functions}},
  journal = {IEEE Trans. Information Theory},
  year = {2022},
  url = {https://openreview.net/forum?id=4gKNYgctcx},
}

Loading related content...

Figure