Technical Summary: Composition for Pufferfish Privacy

Problem Statement

Differential Privacy (DP) is the gold standard for privacy protection, widely deployed by major organizations due to its rigorous guarantees and, crucially, its composition properties. Composition allows the privacy loss of a complex system to be calculated as the sum of the losses of its constituent mechanisms, enabling the construction of large-scale privacy-preserving systems from smaller components.

However, for datasets with strong correlations (e.g., medical records where one person's infection status affects others), standard DP semantics can be overly restrictive or meaningless. Pufferfish privacy, an inferential/posterior-based definition, addresses this by allowing data curators to specify a set of prior distributions and secret pairs, ensuring that a Bayesian adversary learns little about specific secrets. Despite its semantic advantages for correlated data, Pufferfish is rarely used in practice because it lacks composition guarantees.

The paper identifies a critical flaw: it is possible to design Pufferfish mechanisms that have zero privacy leakage when run once but reveal the entire dataset when run multiple times (a phenomenon termed privacy collapse). This lack of composition makes the design of complex, multi-query platforms based on Pufferfish intractable, as every new mechanism requires a tedious, manual joint analysis of how it interacts with all other supported mechanisms.

Methodology

The authors investigate the necessary and sufficient conditions required to ensure linear composition for Pufferfish mechanisms. Their approach involves three main theoretical pillars:

1. Demonstration of Privacy Collapse

The paper constructs specific counterexamples (Theorems 1, 2, and 3) showing that posterior-based definitions, including Pufferfish, do not inherently defend against privacy leakage via composition.

• Single-secret/prior: A mechanism can return a tuple where the components depend on the secret in a way that, when run twice, allows an attacker to deduce the true dataset with high probability, despite having zero leakage in a single run.
• Multiple secrets/priors: Even with expanded sets of secrets or priors, mechanisms can be designed to satisfy Pufferfish privacy for a single run but fail catastrophically upon composition.

2. Necessary Conditions (NfC Constraints)

The authors prove that for a set of Pufferfish mechanisms to compose linearly, they must satisfy a class of constraints called NfC (Necessary-for-Composition) constraints.

• These constraints take the form of inequalities involving convex combinations of log-probabilities of mechanism outputs across different datasets.
• Crucially, the paper proves that for these constraints to also be post-processing invariant (a key property for practical utility), the constraints must reduce to standard Differential Privacy (DP) inequalities.
• Key Insight: To achieve linear composition in Pufferfish, mechanisms must essentially satisfy a form of differential privacy. The Pufferfish privacy parameter $\epsilon_{puffer}$ cannot be guaranteed to compose linearly without adopting DP-style constraints.

3. Sufficient Conditions and the $a(b)$-Influence Curve

To bridge the gap between DP and Pufferfish, the authors introduce the $a(b)$-influence curve.

• Definition: This curve characterizes the worst-case information leakage through a "low-influence" set of data entries ($L$) when a "high-influence" set ($H$) of size $b$ is allowed to vary. It quantifies how much a secret can influence the rest of the dataset beyond a specific group size $b$.
• Translation: The paper establishes a translation formula: if a mechanism satisfies per-entry $\epsilon_{DP}$-differential privacy, it satisfies $\epsilon_{puffer}$-Pufferfish privacy where:
  $$\epsilon_{puffer} = b \cdot \epsilon_{DP} + a(b)$$
  Here, $b \cdot \epsilon_{DP}$ accounts for the group privacy of $b$ entries, and $a(b)$ is the penalty for correlations extending beyond that group.
• Composition: The authors prove that if mechanisms are constructed using this translation, their Pufferfish parameters compose linearly (specifically, sub-additively). The "penalty" $a(b)$ is paid only once, not per mechanism, allowing for better utility than simple addition.

Key Contributions

1. Proof of Privacy Collapse: The paper rigorously demonstrates that posterior-based privacy definitions (like Pufferfish) are not robust to composition without additional constraints, showing mechanisms that are secure in isolation but fail completely when composed.
2. Necessary and Sufficient Conditions: The authors prove that linear composition in Pufferfish necessitates the inclusion of differential privacy-style inequalities (NfC constraints). They show that only DP-style constraints are post-processing invariant within this framework.
3. The $a(b)$-Influence Curve Framework: They introduce a general framework to translate any existing per-entry DP mechanism into a composable Pufferfish mechanism. This generalizes previous work (e.g., Song et al.'s Markov Quilt Mechanism) which was limited to Laplace noise and specific Markov network priors.
4. Robustness to Prior Uncertainty: The framework includes methods to handle mis-specified priors, allowing curators to compute upper bounds on the influence curve even when the true data distribution is uncertain (e.g., within a 20% error margin).

Experimental Results

The authors evaluate their framework (termed Ours-Exp) against the state-of-the-art Markov Quilt Mechanism (MQM) on two real-world datasets with strong temporal correlations:

• Foursquare Check-in Dataset: Location data with high user correlation.
• Capture24 Dataset: 24-hour activity monitoring data.

Findings:

• Superior Utility: The proposed framework significantly outperforms MQM across all privacy parameters ($\epsilon_{puffer}$) and metrics (Accuracy@k, Hit Rate, NDCG, $\ell_1$ Count Error).
• Mechanism Flexibility: The improvement stems from the framework's ability to adapt the Exponential Mechanism (which is optimal for Top-$k$ queries) to the Pufferfish setting. MQM is restricted to the Laplace mechanism, which is less suitable for ranking queries.
• Robustness: Incorporating 20% prior uncertainty into the influence curve calculation resulted in only a modest decrease in utility, demonstrating the framework's practical viability even with imperfect prior knowledge.

Significance and Claims

The paper claims to resolve a major bottleneck hindering the development of Pufferfish-based query-answering platforms. By proving that composable Pufferfish mechanisms must inherently satisfy differential privacy constraints, the authors argue that the path forward is not to invent new, complex Pufferfish-specific mechanisms, but to leverage the vast library of existing DP mechanisms.

The significance of this work lies in:

• Unification: It formally links Pufferfish and Differential Privacy, showing that achieving interpretable semantics for correlated data and composition benefits requires adopting DP mechanisms.
• Practicality: It provides a "recipe" for system designers: compute the $a(b)$-influence curve for their specific data and secrets, and then simply rescale the privacy budget of any existing DP algorithm to achieve a composable Pufferfish guarantee.
• Generalization: It moves beyond the limitations of previous work (which was restricted to Laplace noise and Markov networks) to support general tabular datasets and arbitrary priors.

The authors conclude that their theoretical results imply that designing new mechanisms for Pufferfish should be done by building upon existing DP platforms, effectively making the adaptation of DP to Pufferfish an inevitable and systematic process rather than a heuristic one.