Measuring Information Leakage in Non-stochastic Brute-Force Guessing

Farhad Farokhi, Ni Ding

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.

Introduction

Traditional privacy frameworks, such as Differential Privacy and Information-Theoretic Privacy, are fundamentally rooted in probability theory. They evaluate risk by measuring how an observation shifts a probability distribution over sensitive data. However, these models often falter in real-world scenarios where probability distributions are unknown, data samples are too small for statistical inference, or system policies are strictly deterministic (common in auditing or fraud detection).

This paper introduces a formal framework for measuring information leakage in "non-stochastic" environments. By shifting the focus from probability to set-based uncertainty, the authors provide a robust metric for privacy that accounts for an adversary employing brute-force trial-and-error tactics.

The Framework of Uncertain Variables

The foundation of this work lies in Uncertain Variables (uvs). While a random variable is defined by its probability distribution, an uncertain variable is defined by its range—the set of possible values it can take. In this context, an adversary’s knowledge is represented not by a posterior distribution, but by a "realization set" of all values compatible with the observed output. This is particularly useful for small datasets or unpredictable systems where statistics cannot be reliably captured.

Operationalizing Brute-Force Guessing

The core contribution is an operational measure of leakage based on brute-force guessing complexity. In a non-stochastic setting, the difficulty of uncovering a secret is determined by the maximum number of attempts required to check every possibility.

The proposed leakage metric is defined as the ratio between:

  1. The maximum number of guesses needed without any observation.
  2. The maximum number of guesses needed after observing an output.

This ratio captures the precise reduction in an adversary's workload. If an observation reduces the set of possible values from 100 to 10, the adversary's guessing complexity has decreased significantly, representing a measurable leak of private information.

Key Theoretical Results

The authors derive a closed-form expression for the maximal leakage ($L_\star$):

$$L_\star(X \to Y) = \log_2(|X| - \min_y |X|y| + 1)$$

where $|X|$ is the size of the initial uncertainty set and $|X|y|$ represents the size of the set of possible values for $X$ given an observation $y$. This formula allows researchers to calculate the worst-case privacy risk simply by looking at the sizes of the possible data sets.

Axiomatic Validation

To ensure the metric's validity, the authors demonstrate that it satisfies several "gold standard" properties of information theory:

  • Data Processing Inequality (DPI): Processing data further cannot increase the information leaked about the original secret.
  • Additivity: Leakage from independent sources adds up predictably.
  • Hartley Connection: The metric is intrinsically linked to Hartley entropy (the log of the size of a set), confirming that in non-stochastic settings, the cardinality of uncertainty sets is the primary driver of risk.

Privacy Budgeting and Identifiability

The paper introduces the concept of $\epsilon$-identifiability, a non-stochastic analogue to the privacy budgets found in differential privacy. This allows system designers to set a "privacy knob" ($\epsilon$) that strictly bounds the maximal leakage. Specifically, the authors prove that for an $\epsilon$-identifiable system, the leakage is bounded by:

$$\log_2(|X|(1 - 2^{-\epsilon}) + 1)$$

This provides a concrete mathematical guarantee for defenders, even when they cannot rely on probabilistic assumptions. It ensures robustness; if a system is safe under this metric, it remains safe even if the defender's assumptions about underlying probability distributions are incorrect.

One-Shot vs. Brute-Force

A significant distinction made in the paper is the difference between "one-shot" guessing (where an adversary has only one attempt) and "brute-force" guessing. While existing metrics like maximin information address the former, this new metric is the first to formally operationalize the latter in a non-stochastic context, providing a more realistic assessment of risk against persistent attackers who can try repeatedly until they succeed.

Conclusion and Future Work

By moving away from probabilistic requirements, this research offers a robust alternative for privacy preservation in small-data or deterministic environments. While currently focused on static, one-off data releases, the authors suggest that the framework could be extended to dynamic systems involving continual observations, such as IoT devices or streaming sensors where uncertainty evolves over time.

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