Bayesian Differential Privacy on Correlated Data

Bin Yang, Issei Sato, Hiroshi Nakagawa2015 · DOI

TL;DR

This paper introduces "Bayesian Differential Privacy" (BDP), a new privacy definition that extends differential privacy to handle correlated data and adversaries with incomplete knowledge. BDP provides a more robust privacy guarantee by explicitly modeling data correlations and adversary beliefs, addressing a key vulnerability of standard differential privacy.

What Problem Does This Paper Address?

Differential privacy (DP) is a gold standard for privacy-preserving data analysis, ensuring that the output of a query doesn't reveal whether an individual's data was included. However, DP's guarantees can break down when the data itself is correlated. Imagine a social network where friends' health statuses are likely similar; knowing one person's status might reveal information about their friends, even with DP. Furthermore, DP assumes an adversary with "arbitrary" knowledge, which is often too strong an assumption. This paper tackles the problem of ensuring privacy when data is correlated and adversaries have partial, rather than complete, knowledge.

Methods

The authors propose Bayesian Differential Privacy (BDP), a new privacy definition that extends DP by incorporating Bayesian reasoning. BDP models the adversary's beliefs about unknown data points using prior distributions and accounts for data correlations.

Key techniques include:

  • Bayesian Differential Privacy (BDP) Definition: This formalizes privacy leakage as the difference in posterior probabilities of a target tuple, given the query output and the adversary's background knowledge, considering data correlations.
  • Gaussian Correlation Model: To handle complex data correlations, they introduce a model based on Gaussian Markov Random Fields. This allows for efficient analysis of correlations and privacy leakage.
  • Hierarchical Structure for Adversaries: To manage the complexity of analyzing privacy against numerous adversaries with varying knowledge, they propose a hierarchical structure that helps identify the "most dangerous" adversaries.
  • Laplacian and Geometric Mechanisms: They analyze the privacy guarantees of standard perturbation mechanisms (Laplacian for continuous data, Geometric for discrete data) under their new BDP framework.
  • Extension with Prior Knowledge: To further enhance utility and model more realistic scenarios, they extend the Gaussian model to incorporate uncertain prior knowledge about specific attributes.

Datasets

  • Artificial Network Data: Generated networks with varying vertex numbers and degrees to test the Gaussian correlation model and privacy leakage.
  • Real Social Network Data: A dataset from Facebook (Stanford Large Network Dataset Collection) was used to evaluate the model's performance on real-world correlated data.

Key Insights and Ideas

  • Correlated Data Weakens Standard DP: The core insight is that data correlations, especially when combined with an adversary who doesn't know all other data points, can significantly undermine standard differential privacy guarantees.
  • Weakest Adversary Can Be Most Dangerous: Counter-intuitively, the paper shows that adversaries with the least background knowledge can sometimes pose the biggest privacy threat in correlated datasets, as their uncertainty amplifies the impact of data correlations on query results.
  • BDP as a More Rigorous Standard: BDP is presented as a more robust privacy definition that explicitly accounts for data correlations and adversary knowledge, making it strictly stronger than DP in these scenarios.
  • Prior Knowledge Enhances Utility: By modeling uncertain prior knowledge (e.g., a salary range), BDP can achieve better utility (less noise) while maintaining privacy, compared to assuming complete ignorance about certain attributes.

Key Results

  • Demonstrated Vulnerability: Through examples and analysis, the paper clearly shows how standard DP can fail on correlated data against adversaries with partial knowledge.
  • BDP Formalization: A new privacy definition, Bayesian Differential Privacy, is formally introduced and analyzed.
  • Gaussian Correlation Model: A practical model for analyzing privacy on correlated data is proposed and shown to be computationally tractable.
  • Algorithm for Noise Calibration: An efficient algorithm is presented to determine the appropriate noise level for Laplacian mechanisms to satisfy BDP.
  • Experimental Validation: Experiments on artificial and real-world social network data confirm that privacy leakage increases with data correlation and decreases with prior knowledge, aligning with theoretical predictions.

Limitations and Future Work

  • Computational Intractability: While BDP is more robust, its full analysis can be computationally intractable for large datasets and complex correlation structures. The paper proposes efficient algorithms and models (like the Gaussian correlation model) to mitigate this.
  • Focus on Sum Queries: Much of the analysis is focused on sum queries, though the authors note that other queries (counting, histogram) can be derived.
  • Model Assumptions: The Gaussian correlation model, while flexible, still makes assumptions about the data distribution. Extending to more general correlation models is a potential future direction.
  • Uncertainty in Prior Knowledge: The paper explores uncertain prior knowledge but acknowledges that precisely defining and quantifying this uncertainty remains an area for further research.

Summary updated

Abstract

Differential privacy provides a rigorous standard for evaluating the privacy of perturbation algorithms. It has widely been regarded that differential privacy is a universal definition that deals with both independent and correlated data and a differentially private algorithm can protect privacy against arbitrary adversaries. However, recent research indicates that differential privacy may not guarantee privacy against arbitrary adversaries if the data are correlated.
BibTeX
@misc{yang2015bayesian,
  author = {Bin Yang and Issei Sato and Hiroshi Nakagawa},
  title = {{Bayesian Differential Privacy on Correlated Data}},
  year = {2015},
  doi = {10.1145/2723372.2747643},
}
Figure