Differential Privacy Beyond the Independence Assumption

467 concepts245 papers

Standard Differential Privacy (DP) guarantees that an adversary cannot reliably determine whether any single individual's record was included in a dataset. This mathematical shield relies on a foundational, often unstated assumption: data records are independent and identically distributed (i.i.d.). In their seminal work, Calibrating Noise to Sensitivity in Private Data Analysis, McSherry et al. established this framework by calibrating noise to the maximum impact a single independent record can have on a query output.

But what happens when records are deeply intertwined? As Humbert argues in When Others Impinge upon Your Privacy - Interdependent Risks and Protection in a Connected World, privacy in a connected world behaves less like an individual right and more like a shared resource. If your data is highly correlated with your neighbor's—whether through social ties, family medical histories, or shared IoT environments—deleting your record does not erase your information. It remains mirrored in the data of those around you, violating the core promise of traditional privacy models.

The Sensitivity Explosion

To understand why correlation breaks standard DP, we must look at global sensitivity—the metric that determines how much noise must be added to obscure an individual's presence. When data points are independent, changing one record alters the dataset's summary statistics by a strictly bounded amount.

However, in relational or networked data, a single change triggers a cascade:

  • Network and Graph Structures: In graph neural networks, Daigavane et al. point out in Node-Level Differentially Private Graph Neural Networks that a node's features are aggregated across its neighborhood. Consequently, removing one individual alters multiple interconnected data points, causing sensitivity to skyrocket.
  • Pairwise Relationships: In distance metric learning, Li et al. demonstrate in Secure Metric Learning via Differential Pairwise Privacy that because one individual participates in multiple pairs, the presence of a single person creates inherent correlations that attackers can exploit.
  • Social Contagion: When attributes spread through interpersonal connections (such as habits or opinions), Gao shows in On Privacy of Socially Contagious Attributes that attackers can leverage known social network structures to bypass noise-based protections, effectively deflating the nominal privacy budget.
  • Data Augmentation: Even in standard machine learning pipelines, techniques like Mixup create artificial dependencies. As noted by Bao et al. in DP-Mix: Mixup-based Data Augmentation for Differentially Private Learning, mixing private images spreads an individual's influence across multiple training points, complicating standard privacy accounting.

Feature-Level and Cross-Column Leakage

The independence assumption does not just fail between different records; it also fails within individual records. Real-world datasets feature high correlation between attributes, creating indirect channels for information leakage.

In The Tao of Inference in Privacy-Protected Databases, Grubbs demonstrates that hybrid encryption strategies—which strongly encrypt sensitive columns but leave non-sensitive columns partially exposed—fail because cross-column correlations allow attackers to reconstruct redacted data. This proxy effect means that simply hiding a sensitive variable is insufficient.

For instance, Cundy et al. show in Privacy-Constrained Policies via Mutual Information Regularized Policy Gradients that an autonomous agent's behavior can still expose protected information if its observable actions remain correlated with hidden, sensitive variables. Similarly, Ma et al. demonstrate in Locally Private Estimation with Public Features that high correlation between public metadata and private features allows adversaries to infer sensitive information, undermining Local Differential Privacy (LDP) mechanisms.

This challenge is particularly acute in high-dimensional domains like genomics. As Jiang explains in Answering Count Queries for Genomic Data with Perfect Privacy, the tight statistical dependencies between neighboring genetic markers mean that releasing seemingly benign aggregate counts can act as a proxy that reconstructs private individual records.

Evolving the Privacy Framework

To address these vulnerabilities, researchers have shifted toward frameworks that explicitly model data dependencies rather than ignoring them.

Bayesian Differential Privacy

One prominent solution is Bayesian Differential Privacy (BDP). As detailed by Triastcyn et al. in Bayesian Differential Privacy for Machine Learning, BDP incorporates the data distribution and the adversary's prior beliefs directly into the privacy analysis. By moving away from worst-case scenarios that assume independent data, BDP provides tighter, more realistic privacy bounds for typical users. Zhao et al. extend this framework in Adaptive Statistical Learning with Bayesian Differential Privacy, proving that BDP maintains statistical validity and generalization guarantees even when data points like social media profiles or genetic markers are highly correlated.

Active Correlation Reduction

Instead of merely accounting for correlation, some methods actively reduce it. In Correlated Differential Privacy: Feature Selection in Machine Learning, Zhang et al. introduce a feature selection scheme (CR-FS) that filters out highly interdependent features before noise injection, preventing the inflation of query sensitivity. For fine-grained control, Aliakbarpour et al. propose Enhancing Feature-Specific Data Protection via Bayesian Coordinate Differential Privacy, which allows for coordinate-specific privacy levels while rigorously accounting for inter-feature correlations to block indirect leakage channels.

Shifting Privacy Granularity

When data is sequentially or temporally correlated, changing the unit of privacy can restore protection. For example, in natural language processing, treating individual sentences as independent fails because conversational context links them together. In Granularity is crucial when applying differential privacy to text: An investigation for neural machine translation, the authors demonstrate that shifting the privacy boundary from sentence-level to document-level granularity successfully mitigates membership inference attacks in dialogues by capturing inter-sequence dependencies.

The Circularity Catch-22

While these advanced frameworks offer a mathematically rigorous path forward, they introduce a fundamental paradox. To calibrate the correct amount of noise for a correlated dataset, a mechanism must know the underlying correlation structure (such as a Markov blanket or a covariance matrix).

However, as Zhao et al. and Aliakbarpour et al. note, estimating these statistical priors accurately without violating individual privacy creates a circular dependency: you need privacy-preserving estimation to discover the correlation parameters required to protect the data in the first place. Resolving this tension—and finding ways to learn correlation structures safely—remains one of the most critical frontiers in modern privacy research.

History & citationVersion 2 · 2026-10-04

Current · Permanent link

  1. Version 2 (latest) · 2026-10-04 · 249 papers
  2. Version 1 · 2026-10-04 · 202 papers
Cite this direction

Latest version (a living page):

@misc{lacuna_correlated_data_privacy_94681641,
  title = {correlated data privacy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/correlated-data-privacy/rdr_946816415d1448d1aeebc82b2b9b26e4},
  note = {Latest version of a living research direction; cite a version for a fixed text. Accessed 2026-11-19},
}

This exact version (version 2, frozen text):

@misc{lacuna_correlated_data_privacy_94681641_v2,
  title = {correlated data privacy},
  author = {{Lacuna}},
  howpublished = {Lacuna research direction},
  year = {2026},
  url = {https://lacuna.tiptreesystems.com/direction/correlated-data-privacy/rdr_946816415d1448d1aeebc82b2b9b26e4/v/2},
  note = {Version 2, frozen 2026-10-04. Accessed 2026-11-19},
}
About

These directions overlap with this one through shared papers.

See something wrong? Report a mistake