A Formal Study of Differential Privacy in Complex and Correlated Data

Differential privacy (DP) has emerged as the standard for privacy-preserving data analyses, offering formal protection that can be monitored over time thanks to its composability properties. DP has proven to be highly effective for classical tabular data and simple queries; however, its deployment in modern data types---such as trajectories, time series, graphs, and other complex high-dimensional data---is not yet fully understood. These complex data types are characterized by rich semantics, strong correlations, and non-trivial structures, all of which deviate from the underlying assumptions of classical DP analyses and complicate the interpretation of privacy guarantees in practice.

In this thesis, we investigate the limitations of DP in complex data and develop new theoretical and practical tools to improve the adoption of DP in these new scenarios.
We begin by systematizing the challenges that arise when DP is applied beyond its original tabular context, using trajectory data as a representative and practically relevant case study. This analysis reveals four core issues, which we then study throughout this dissertation: (i) The widespread formal errors in the design and implementation of DP mechanisms for complex domains, (ii) the issues in extending key DP properties like composability, (iii) the limited interpretability of DP parameters under realistic attack models, and (iv) the failure of classical DP guarantees in the presence of correlated data.
... mehr



First, we address the challenge of composition in complex data domains. To provide general composition results applicable to the growing landscape of DP variations, we adopt the general metric privacy framework.
Within this framework, we develop a unified composition theory that yields tighter privacy loss bounds by explicitly accounting for amplification and attenuation effects induced by preprocessing. As a result, we obtain tighter bounds that apply consistently across any domain and DP variation.
Additionally, we extend our composition analysis to Gaussian DP, enabling a more interpretable characterization of the composition privacy loss over general data domains.


Second, we investigate the parameter interpretation and attack resilience of DP through a formal and empirical study on the risk incurred by individuals whose data are processed by DP mechanisms. Understanding this risk is essential for principled noise calibration: If the privacy parameters are set too loosely, sensitive information may be exposed; while if they are set too conservatively, utility is unnecessarily degraded.
We analyze reconstruction attacks and demonstrate that existing adversarial metrics---such as reconstruction robustness (ReRo)---systematically overestimate the privacy risk by conflating statistical imputation and auxiliary knowledge with genuine participation leakage. To address this issue, we introduce reconstruction advantage (RAD), a novel advantage-based metric that explicitly incorporates auxiliary information.
We establish worst-case and auxiliary-dependent tight bounds that link DP guarantees to RAD, providing a sharper and more interpretable characterization than previous approaches.
Our theoretical and empirical evaluation demonstrates both the robustness of RAD as a risk measure and the practical impact of our analysis. In particular, our bounds enable improved noise calibration, yielding better utility without sacrificing meaningful privacy guarantees. Moreover, we develop a RAD-based auditing framework that improves both efficiency and accuracy, especially for high-dimensional categorical data, and broadens the scope with respect to existing auditing tools. This framework enables earlier detection of formal errors and implementation flaws, ensuring that individuals’ privacy guarantees are effectively enforced.


Finally, we study the vulnerability of DP to correlation-based inference attacks.
Correlations---such as temporal dependencies in trajectories or social dependencies in networks---can substantially amplify an attacker’s information gain, effectively shrinking DP privacy guarantees.
To address this challenge, we investigate whether accurate inference guarantees can be achieved under Bayesian differential privacy (BDP), an enhanced DP notion that explicitly protects against correlation-based attacks.
Particularly, we derive novel leakage bounds for BDP under arbitrary correlations, as well as tighter, correlation-specific bounds for Gaussian and Markov distributions. These results provide a systematic methodology for constructing accurate BDP mechanisms tailored to realistic correlation structures, a principled first step towards understanding when BDP guarantees and improved utility are simultaneously attainable.


Overall, this thesis demonstrates that privacy risk in complex data analysis depends critically on the data structure, correlations, and mechanism design---not solely on the DP parameters. By providing new theoretical foundations, tighter bounds, and practical auditing tools, our work advances the field towards reliable and interpretable deployments of DP in complex and correlated data.