Source-linked AI summary
Bounds on the Posterior-to-Prior Ratios for Inclusion Belief under Bounded Differential Privacy
Jan Reiter Sørensen, Heidi Søgaard Christensen, Rasmus Rask Kragh Jørgensen, Martin Bøgsted
TL;DR
Differential privacy gives strong formal guarantees, but how a release changes an adversary’s belief that an individual is included remains difficult to interpret. The paper derives posterior-to-prior inclusion-belief bounds under bounded probabilistic and approximate differential privacy, then studies Gaussian-mechanism failure probabilities. Across the parameter sweeps, the theoretical upper limit is substantially above the estimated failure probability, making it conservative in practice.
Problem
The practical disclosure-risk interpretation of differential privacy, particularly changes in inclusion beliefs after observing a protected release, remains unclear.
Method
The paper derives posterior-to-prior inclusion-belief bounds under bounded probabilistic and approximate differential privacy and analyzes Gaussian-mechanism failure regions and probabilities.
Results
The theoretical failure-probability upper limit lies substantially above the estimated failure probability throughout the parameter sweeps considered.
Takeaways & Limitations
For the Gaussian mechanism, calibrating parameters to keep the theoretical failure-probability limit below an acceptable level provides a conservative privacy guarantee.
Takeaways & Limitations
The analysis uses n = 100 because larger n values impose high computational demands, although the authors state that the analytical points should apply for n > 100.
Abstract
from arXiv · showhide
Differential privacy has become the standard for generating privacy-protected data releases. However, differential privacy does not translate intuitively to disclosure risk. In particular, it remains unclear how much an adversary's belief about an individual's inclusion in a dataset can change after observing a protected release. To address this question, we derive upper and lower bounds on the posterior-to-prior ratios of inclusion beliefs under bounded probabilistic and approximate differential privacy. By assuming a worst-case adversary with all-but-one auxiliary information, i.e., knowledge of all except for one of the participants in a dataset, we obtain bounds that apply to any adversary. Because these bounds may fail with non-zero probability, we study the corresponding failure probability for the Gaussian mechanism. We derive a theoretical upper limit on this probability and compare it with Monte Carlo estimates across a wide range of parameter settings. The observed failure rate is several orders of magnitude smaller than its theoretical upper limit, indicating that the latter is highly conservative. These findings suggest that the inferential privacy guarantees provided by differentially private mechanisms may be substantially stronger in practice than what is implied by the theoretical upper limit.
1 Introduction
Differential privacy offers strong theoretical disclosure guarantees, but their practical meaning for disclosure risk and inclusion beliefs remains difficult to interpret. This paper derives bounded-privacy posterior-to-prior bounds and evaluates how conservatively their Gaussian-mechanism failure limits behave.
- Motivation: Differential privacy is widely used for privacy-preserving data sharing, but selecting an intuitively appropriate privacy budget remains challenging.Its applications include statistical databases, browser telemetry, and large-language-model training.
- Prior work: Posterior-to-prior differences and ratios provide measures for quantifying changes in beliefs after observing protected data releases.Prior work derived deterministic or probabilistic inferential bounds under several differential-privacy settings.
- Prior work: Existing bounds address important inference risks, but broader disclosure risks include re-identification, data reconstruction, and other forms of inference.General Bayesian inferential bounds cover arbitrary Bayesian inference on differentially private releases.
- Contribution: The paper derives probabilistic bounds for inclusion-belief posterior-to-prior ratios under bounded approximate differential privacy and characterizes their Gaussian-mechanism failure regions.It also derives an upper failure-probability limit and evaluates its tightness with Monte Carlo simulations.
- Contribution: The Gaussian-mechanism failure-probability upper limit is highly conservative in practice according to the paper’s Monte Carlo evaluation.The paper’s sections develop the framework, privacy relations, bounds, failure limit, and simulation study.
2 Notation and Preliminaries
The paper formalizes datasets as points in an extended metric space and data releases as measurable mappings with associated output distributions. It then states approximate and probabilistic privacy concepts for generic neighboring relations and illustrates bounded approximate privacy with the Gaussian mechanism.
- Data universe: A data universe is an extended metric space whose points represent possible datasets and whose metric determines neighboring datasets.Datasets may be collections of records sampled from a common domain.
- Data universe: The metric assigns distance zero to identical datasets, shortest-path distance to connected datasets, and infinite distance to disconnected datasets.Datasets are neighbors when their distance equals one.
- Data-release mechanisms: A data-release mechanism is a measurable mapping that transforms datasets into publicly released outputs, with a probability measure associated with each dataset.Mechanisms may be randomized or deterministic and can release statistics, synthetic datasets, or other products.
- Privacy definitions: Approximate differential privacy bounds output probabilities for neighboring datasets using ε and δ, with δ = 0 recovering pure ε-differential privacy.A value δ ≥ 1 makes the approximate-privacy promise vacuous.
- Privacy definitions: Bounded privacy uses replace-one neighbors with equal-sized datasets, whereas unbounded privacy uses add/remove-one neighbors.The neighbor relation affects query sensitivity and the noise required for a target privacy level.
- Gaussian mechanism: The Gaussian mechanism privatizes a query by adding normally distributed noise, and Hamming-distance neighbors make the example satisfy bounded approximate differential privacy.Using symmetric difference instead would produce an unbounded privacy setting.
3 Probabilistic Differential Privacy
This section relates probabilistic and approximate differential privacy through measurable bad regions where likelihood-ratio bounds can fail. It establishes minimal bad regions, parameter translations, and their Gaussian-mechanism geometry and probability calculations.
- Definition and relations: Probabilistic differential privacy permits pure ε-differential-privacy inequalities to fail on a set whose probability is at most δ.It therefore relaxes pure differential privacy through a failure-probability interpretation rather than an additive δ term.
- Definition and relations: Probabilistic differential privacy implies approximate differential privacy with the same (ε, δ)-parameters.The converse requires constructing an appropriate measurable bad region.
- Bad regions: Lemma 1 identifies a minimal bad region for each neighboring dataset pair by comparing their output densities.Its construction yields the smallest probability under one dataset among sets satisfying the required likelihood-ratio inequalities.
- Definition and relations: Approximate differential privacy implies probabilistic differential privacy with ε′ > ε and a closed-form δ′ determined by the original parameters.The inverse characterization instead allows δ′ within a suitable interval and gives ε′ in closed form.
- Gaussian mechanism: For the Gaussian mechanism, bad regions are characterized geometrically and their probability mass can be calculated exactly for neighboring datasets.The regions are formed from open half-spaces determined by the query-output displacement and noise scale.
- Gaussian mechanism: The Gaussian mechanism satisfies approximate differential privacy and consequently probabilistic differential privacy under the established implication.The analysis applies when the query output lies in a bounded subset of Rq.
4 Posterior-to-Prior-Ratio of Inclusion Belief
The paper bounds how a Bayesian adversary’s inclusion belief can change after a differentially private release. Under all-but-one auxiliary information, it derives posterior-to-prior ratio bounds for bounded probabilistic and approximate differential privacy, with failure controlled by conservative regions.
- Motivation: Posterior-to-prior ratios quantify how much a release changes an adversary’s inclusion belief relative to the prior.The paper treats this change as more informative for disclosure risk than the posterior belief alone.
- Adversary model: The adversary is assumed to know m −1 participants in the observed dataset, yielding an all-but-one auxiliary-information setting.Bounds for this worst-case setting also constrain adversaries with less auxiliary information.
- Failure regions: The identified failure region is conservative: the ratio bounds hold outside it, but they may also hold inside it.Consequently, the probability of bound failure is at most the probability mass of the conservative region.
- Prior dependence: The bounds can also be compared with prior-independent bounds, whose wider interval has no greater probability of being violated.This follows because widening the interval cannot increase the event that R(t) falls outside it.
5 The Risk of Failing the Ratio Bounds under the Gaussian Mechanism
For the Gaussian mechanism, the paper characterizes the probability that outputs fall in the conservative failure regions. It reduces the calculation to multivariate normal probabilities and obtains an exact expression that serves as an upper limit on actual bound failures.
- Gaussian representation: The analysis represents Gaussian outputs through standardized normal variables and their covariance structure.The relevant summands are probabilities under a zero-mean multivariate normal distribution.
- Covariance calculation: The covariance matrices encode correlations among the standardized variables used to evaluate the multivariate normal probabilities.The derivation uses covariance matrices for the joint distribution of the variables.
- Failure-region probability: The Gaussian mechanism’s conservative failure-region probability is expressed exactly using the mechanism’s output distribution.The expression is obtained after decomposing the failure region into disjoint sets.
- Interpretation: The resulting expression provides only an upper limit on the failure probability of the posterior-to-prior ratio bounds.Because the conservative region can contain outputs where the bounds still hold, its probability can exceed the actual failure probability.
6 The Empirical Failure Rate
Monte Carlo experiments compare empirical failure probabilities with conservative theoretical upper limits across ε, m, and δ. The empirical rates are generally far below the limits, although failure rises sharply as δ approaches one and the analysis is computationally bounded.
- Simulation design: The two-level simulation calibrates Gaussian-mechanism noise, samples datasets, and estimates failure as the proportion of posterior-to-prior ratios violating the bounds.The outer loop samples N1 datasets, while the inner loop applies the mechanism N2 times per dataset.
- Monte Carlo estimator properties: As N2 increases, F consistently estimates the realization-specific failure probability but not the unconditional probability; as N1 →∞, F converges to the unconditional probability ρ.The estimator is unbiased and consistent for ρ when the number of outer-loop datasets grows.
- Effect of ε: Approximately two orders of magnitude separate T and F across ε ∈[0.2, 2.0], with mean T = 1.49 × 10−2 and mean difference T − F = 1.48 × 10−2.F decreases as ε increases, while T remains near 1.5 × 10−2 over the plotted range.
- Effect of m: As m approaches 99, T decreases, F increases, and both coincide at m = 99 because the candidate set contains only the held-out individual.The decline in T becomes markedly steeper after approximately m = 70, producing a hockey-stick shape.
- Effect of δ: For δ ∈[10−1.1, 1], T exceeds F throughout, while F increases from 0.007% to 18% below δ = 0.95 and from 18% to 100% over δ ∈[0.95, 1].The rapid increase near δ = 1 is associated with larger bad regions; estimates below 10−1.1 were not obtained because rare-event simulation was computationally prohibitive.
- Overall findings: Across ε, m, and δ, the theoretical upper limit is highly conservative, with realistic settings potentially yielding failure probabilities several orders of magnitude smaller.The limit remains useful as a conservative bound when privacy parameters sufficiently constrain the posterior-to-prior ratio.
7 Conclusion
The paper unifies probabilistic and approximate differential privacy, derives inclusion-belief posterior-to-prior bounds, and evaluates their failure probability for the Gaussian mechanism. Simulations show the theoretical failure-probability upper limit is conservative, supporting its use for privacy-risk calibration while leaving important scope limitations.
- A unified measure-theoretic framework rederives the implications between probabilistic and approximate differential privacy, including modified (ε, δ)-parameters for the converse.
- The paper derives upper and lower inclusion-belief posterior-to-prior ratio bounds and an exact Gaussian-mechanism expression for the mass of their potential failure regions.Because violations are not guaranteed within those regions, the expression is an upper limit on failure probability.
- Across the parameter sweeps, the theoretical upper limit lies substantially above the estimated failure probability, indicating that it is conservative.
- The bounds can support privacy-parameter selection against an acceptable privacy-risk level, while calibrating the Gaussian mechanism to the upper limit yields a conservative guarantee.
- The results assume a finite, known population, cover inclusion events rather than all inference types, and offer analytically tractable failure limits only for the Gaussian mechanism.