Measuring Information Leakage in Non-stochastic Brute-Force Guessing

Farhad Farokhi, Ni Ding

TL;DR

This paper introduces a new way to measure privacy risks when we don't know the underlying probability distributions of data. By modeling an adversary who uses brute-force guessing to uncover sensitive information, the authors define "non-stochastic leakage" as the reduction in the number of guesses required once an adversary sees an anonymized report.

What Problem Does This Paper Address?

Most modern privacy frameworks, like Differential Privacy or Information-Theoretic Privacy, rely heavily on statistics. They assume we know the probability distributions of the data or the noise being added. However, in the real world, distributions might be unknown, change unpredictably over time, or be impossible to estimate from small datasets.

Furthermore, some applications (like financial auditing or fraud detection) cannot tolerate the "untruthfulness" introduced by randomized privacy mechanisms. There is a growing need for a non-stochastic framework—one that works with sets of possibilities rather than probabilities—to quantify how much information "leaks" from a system when an adversary is determined to guess a secret.

Methods

The authors build their framework using Uncertain Variables (uvs), which are the non-probabilistic cousins of random variables. Instead of asking "What is the probability $X$ takes value $x$?", we simply define a range of possible values $[X]$ that $X$ could take.

The core of their approach is the Brute-Force Guessing Model:

  1. The Setup: An adversary wants to guess a sensitive attribute $U$ (derived from data $X$) by looking at a released output $Y$.
  2. The Guessing Game: The adversary has an "oracle" they can ask if a guess is correct. They systematically check every possible value in the set of possibilities until they find the true one.
  3. The Metric: Leakage is defined as the ratio of the maximum number of guesses needed without the output $Y$ versus the maximum number of guesses needed with $Y$.

Mathematically, they define the leakage from $U$ to $Y$ as: $$\mathcal{L}(U \to Y) = \max_{y} \log_2 \frac{|[U]|}{|[U|y]|}$$ This represents the "guessing gain"—how much the search space for the secret attribute shrinks after seeing the public report.

Datasets

Not discussed in the paper. As a theoretical work in information theory, the authors focus on proving mathematical properties and establishing definitions rather than benchmarking against specific empirical datasets.

Key Insights and Ideas

  • Operational Meaning: Unlike abstract entropy measures, this metric has a direct physical interpretation: it tells you exactly how much easier you've made a brute-force attack.
  • The "Maximal" Perspective: The authors introduce Maximal Non-stochastic Leakage, which considers the "worst-case" scenario where we don't know exactly what attribute the adversary is targeting. They prove a surprisingly simple closed-form formula for this: it depends only on the size of the total range of $X$ and the size of the smallest possible conditional range.
  • Axiomatic Validity: The authors demonstrate that their measure satisfies the "gold standard" requirements for any leakage metric, including the Data Processing Inequality (post-processing data cannot increase leakage) and Additivity (leakage from independent sources adds up).
  • Bridging the Gap: The paper connects this new set-based measure to established concepts like Maximin Information (which relates to one-shot "lucky" guessing) and Hartley Entropy.

Key Results

  • Closed-form Expression: They proved that the maximal leakage $\mathcal{L}_\star(X \to Y)$ is equal to $\log_2(|[X]| - \min_y |[X|y]| + 1)$. This makes it computationally easy to evaluate for discrete systems.
  • Non-Stochastic Identifiability: The authors proposed a new privacy definition called $\epsilon$-identifiability. If a system is $\epsilon$-identifiable, the maximal leakage is bounded by a function of the privacy budget $\epsilon$.
  • Relationship to Stochastic Leakage: They showed that this non-stochastic measure acts as a "robust" counterpart to stochastic maximal leakage. Specifically, the non-stochastic leakage provides an upper bound on what an adversary could learn even if the underlying probabilities were known.

Limitations and Future Work

The current framework is primarily designed for one-shot releases of discrete data. The authors acknowledge two main areas for future exploration:

  1. Continuous Variables: While the paper hints at extensions to infinite sets, the primary proofs focus on discrete alphabets.
  2. Dynamic Systems: The most significant next step is extending this to a "dynamic framework" where an adversary makes continual observations over time (e.g., tracking a user's location or monitoring a sensor stream).

This work provides a foundational tool for engineers who need to guarantee privacy in systems where probabilistic assumptions are either too risky or simply unavailable.

Summary updated

Abstract

We propose an operational measure of information leakage in a non-stochastic setting to formalize privacy against a brute-force guessing adversary. We use uncertain variables, non-probabilistic counterparts of random variables, to construct a guessing framework in which an adversary is interested in determining private information based on uncertain reports. We consider brute-force trial-and-error guessing in which an adversary can potentially check all the possibilities of the private information that are compatible with the available outputs to find the actual private realization. The ratio of the worst-case number of guesses for the adversary in the presence of the output and in the absence of it captures the reduction in the adversary's guessing complexity and is thus used as a measure of private information leakage. We investigate the relationship between the newly-developed measure of information leakage with the existing non-stochastic maximin information and stochastic maximal leakage that are shown arise in one-shot guessing.
BibTeX
@inproceedings{farokhi2020measuring,
  author = {Farhad Farokhi and Ni Ding},
  title = {{Measuring Information Leakage in Non-stochastic Brute-Force Guessing}},
  booktitle = {Itw},
  year = {2020},
  doi = {10.1109/itw46852.2021.9457602},
}
Figure