Multi-user Pufferfish Privacy

1. Problem Statement

The paper addresses the challenge of achieving individual indistinguishability in a multi-user system where users report data that is inherently random (stochastic) rather than deterministic.

• Context: Traditional Differential Privacy (DP) assumes that data records are deterministic. However, in many modern scenarios (e.g., federated learning, local privacy, sensitive surveys), a user's data is a realization of a random variable.
• The Gap: While the Pufferfish Privacy framework was designed to handle probabilistic data and adversary priors, existing literature has focused heavily on mechanism design and theoretical analysis. There is a lack of concrete methods on how to calibrate noise (specifically Laplace noise) to prevent membership inference or distinguish between specific user behaviors (value changes, presence/absence, or distribution changes) in a multi-user aggregated query setting.
• Goal: The authors aim to derive sufficient conditions for adding Laplace noise to an aggregated query answer such that an adversary cannot distinguish between specific "secret" scenarios regarding a user's data, even when the user's presence is probabilistic.

2. Methodology

The authors adopt the Pufferfish Privacy framework combined with the Kantorovich (1-Wasserstein) metric for noise calibration.

System Model

• Multi-User Setting: A system with a set of users $\mathcal{V}$. Each user $i$ reports a random variable $D_i$.
• Aggregated Query: The system computes a sum query $X = \sum D_i$.
• Presence Probability: Each user $i$ has a probability $\zeta_i$ of being present in the system. If absent, they contribute nothing (effectively 0).
• Mechanism: The mechanism adds Laplace noise $N_\theta$ to the query result $Y = X + N_\theta$. The goal is to determine the scale parameter $\theta$.

Secret Pairs

The paper defines four distinct sets of secret pairs ($\mathbb{S}$) to test indistinguishability:

1. $\mathbb{S}_{a,b}$: Distinguishing between a user reporting value $a$ vs. value $b$.
2. $\mathbb{S}_{a,\perp}$: Distinguishing between a user reporting value $a$ vs. being absent ($\perp$).
3. $\mathbb{S}_{P,\perp}$: Distinguishing between a user being present with data following distribution $P$ vs. being absent.
4. $\mathbb{S}_{P,Q}$: Distinguishing between a user following distribution $P$ vs. distribution $Q$.

The Kantorovich Approach

Instead of using the computationally expensive $\infty$-Wasserstein distance, the authors utilize the 1-Wasserstein distance (Kantorovich metric).

• They define the noise scale $\theta$ based on the optimal transport plan $\pi^*$ between the probability distributions of the query answers under two different secrets.
• The core condition for Pufferfish privacy is derived from the inequality:
  $$P_{Y|S}(y|s_i) \leq e^\epsilon P_{Y|S}(y|s_j)$$
• Using the properties of the Laplace distribution and the triangle inequality, they derive that a sufficient condition is:
  $$\theta \geq \frac{1}{\epsilon} \sup_{(x, x') \in \text{supp}(\pi^*)} |x - x'|$$
  Essentially, the noise scale must be proportional to the maximum distance between points in the support of the optimal transport coupling.

3. Key Contributions

The paper provides rigorous sufficient conditions for calibrating Laplace noise for the four secret pair scenarios defined above.

A. Deterministic Value Changes ($\mathbb{S}_{a,b}$ and $\mathbb{S}_{a,\perp}$)

• Result: For distinguishing between two specific values $a$ and $b$, the noise scale is $\theta = \frac{|a - b|}{\epsilon}$.
• Significance: This mirrors the standard $\ell_1$-sensitivity in DP. Crucially, the authors prove that this condition is independent of the user's presence probability ($\zeta_i$) and the statistics of other users. The "absence" case is mathematically equivalent to reporting a value of 0.

B. Distributional Changes ($\mathbb{S}_{P,\perp}$ and $\mathbb{S}_{P,Q}$)

This is the novel contribution where data is probabilistic.

• $\mathbb{S}_{P,\perp}$ (Presence vs. Absence with Distribution $P$):
  • The sufficient condition is derived as $\mathbb{E}_{D_i \sim P} [e^{|D_i|/\theta}] = e^\epsilon$.
  • A simplified, conservative bound is $\theta = \frac{\max |t|}{\epsilon}$ (where $t$ is in the support of $P$).
  • Relaxation: For binary (Bernoulli) variables, the authors derive a closed-form solution that is strictly less than the conservative bound, allowing for reduced noise.
• $\mathbb{S}_{P,Q}$ (Distribution $P$ vs. Distribution $Q$):
  • The authors define a metric $\Delta^*(t)$ based on the cumulative distribution functions (CDFs) of $P$ and $Q$.
  • The noise scale is $\theta = \frac{1}{\epsilon} \sup \Delta^*(t)$.
  • Relaxation: For binary variables, a "relaxed sufficient condition" is proposed (Lemma 2). This condition utilizes the specific statistics of the other users in the system to calculate a tighter bound on $\theta$, significantly reducing the required noise compared to the worst-case bound.

C. Independence of System Statistics

A major theoretical finding is that for individual indistinguishability, the derived sufficient conditions depend only on the statistics of the specific user $i$ being analyzed. They do not depend on the presence probabilities or data distributions of the other users in the system (except for the relaxed binary case where other user stats help optimize the noise).

4. Experimental Results

The authors validated their theoretical findings on three real-world UCI datasets: Adult, Bank Marketing, and Student Performance.

• Noise Reduction: In experiments comparing the standard conservative bounds (Theorem 3, Eq 14) against the relaxed bounds (Theorem 3, Eq 13 using Brent's method, and Lemma 2), the relaxed conditions consistently required a smaller noise scale ($\theta$).
• Data Utility: A smaller $\theta$ implies less noise added to the query, resulting in higher data utility while maintaining the same privacy budget $\epsilon$.
• Binary Case: The experiments on binary features (e.g., marital status, loan status) showed significant noise reduction when using the relaxed sufficient condition (Lemma 2) compared to the standard $\theta = 1/\epsilon$ approach, particularly at lower privacy budgets.

5. Significance and Impact

1. Bridging Theory and Practice: The paper moves Pufferfish Privacy from a theoretical framework to a practical mechanism for multi-user systems with stochastic data. It provides explicit formulas for noise calibration.
2. Handling Intrinsic Randomness: It addresses a critical limitation of standard DP by formally handling scenarios where user data is a random variable (e.g., local differential privacy mechanisms or natural variability).
3. Optimization of Utility: By deriving "relaxed sufficient conditions" (especially for binary data), the paper demonstrates that one can achieve the same privacy guarantees with significantly less noise, thereby improving the accuracy of aggregated queries.
4. Modularity: The finding that privacy conditions for an individual are largely independent of the rest of the system simplifies the deployment of privacy mechanisms in dynamic, multi-user environments where user populations change frequently.

In summary, this paper establishes a robust mathematical foundation for applying Pufferfish Privacy to multi-user aggregated queries, offering specific, optimized noise calibration strategies that enhance data utility without compromising privacy guarantees.