Bounds on the Posterior-to-Prior Ratios for Inclusion Belief under Bounded Differential Privacy

Bounds on the Posterior-to-Prior Ratios for Inclusion Belief under Bounded Differential Privacy Jan Reiter Sørensen1,† , Heidi Søgaard Christensen1 , Rasmus Rask Kragh Jørgensen1,2 , and Martin Bøgsted1 1

arXiv:2608.30473v1 [math.ST] 31 Aug 2026

2

Center for Clinical Data Science, Aalborg University, Aalborg, Denmark Department of Hematology, Aalborg University Hospital, Aalborg, Denmark † Corresponding author: janrs@dcm.aau.dk September 1, 2026 Abstract

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, first introduced by Dwork et al. (2006b), has become a widely accepted standard for privacy-preserving data sharing. It has been adopted across a broad range of applications, including statistical databases (Christ et al., 2022), web-browser telemetry collection (Erlingsson et al., 2014), and the training of large language models (McKenna et al., 2025). By limiting the information that can be learned about an individual, differential privacy provides strong theoretical guarantees regarding disclosure risk and inference attacks. However, the practical interpretation of these guarantees remains elusive. In practice, users must select a privacy budget, yet determining an appropriate value remains challenging because privacy budgets lack a direct and intuitive interpretation in terms of privacy risk (Dwork et al., 2019). Consequently, researchers have often turned to Bayesian adversarial frameworks to assess privacy risk (Wagner and Eckhoff, 2018). Within these frameworks, privacy risk is characterised through an adversary’s posterior beliefs after observing a differentially private release. McClure and Reiter (2012) argue that posterior probabilities of disclosure risk and inference attacks alone are insufficient for assessing privacy risk, as they do not account for the adversary’s prior knowledge. Rather, the change in posterior relative to prior beliefs provides a more informative metric, as it reflects the information gained from the release of differentially private data. Therefore, characterising posterior-to-prior changes is fundamental to understanding the privacy risk under differential privacy. Such changes can be quantified using posterior-to-prior differences and ratios (Jarmin et al., 2023). Using these measures, Kazan and Reiter (2024) derive deterministic upper and lower bounds on attribute and membership inference under unbounded pure differential privacy. Kazan (2025) extends these results to unbounded approximate differential privacy, obtaining probabilistic bounds that may fail with non-zero probability. Complementing this work, Bailie and Gong (2024) establish general Bayesian inferential limits under pure differential privacy, yielding direct bounds on posterior-to-prior ratios for arbitrary 1

inferences drawn from the observed data. The bounds derived by Kazan and Reiter (2024) for attribute and membership inference cover two important classes of disclosure risks. Nevertheless, adversarial inferences are not limited to these settings and also include risks such as re-identification (Jarmin et al., 2023), data reconstruction (Guerra-Balboa et al., 2026), and other forms of inference (Pilgram et al., 2025). The general inferential bound of Bailie and Gong (2024) encompasses this broader spectrum of disclosure risks by applying to arbitrary Bayesian inference on differentially private releases. However, the methods of Kazan and Reiter (2024) and Bailie and Gong (2024) are limited to pure differential privacy, a notion known to exhibit a steep privacyutility trade-off, where even marginal increases in privacy budget can substantially degrade statistical accuracy of a differentially private release (Canonne et al., 2020). Consequently, pure differential privacy is often replaced with more relaxed definitions, such as approximate differential privacy. Kazan (2025) subsequently extended the attribute and membership inference bounds to the unbounded approximate differential privacy setting. Despite the widespread adoption of bounded differential privacy in practice (Erlingsson et al., 2014; Christ et al., 2022; Hayes et al., 2023), no corresponding posterior-to-prior bounds have been established for bounded approximate differential privacy. In this paper, we partially fill this gap by deriving bounds on the posterior-to-prior ratios for inclusion beliefs under bounded approximate differential privacy. Similar to Kazan (2025), our bounds are probabilistic and may therefore fail with non-zero probability. For the Gaussian mechanism, we characterise the regions of the output space where the bounds are not guaranteed to hold. This characterisation enables closed-form expressions for the probability mass of these regions, providing an upper limit on the probability that the proposed guarantees fail. Finally, we use Monte Carlo simulations to evaluate the tightness of this upper limit and find that it is highly conservative in practice. The paper is organised as follows. Section 2 introduces the mathematical framework and relevant privacy definitions. Section 3 covers the relation between probabilistic and approximate differential privacy and derives the shape and mass of the failure regions for the Gaussian mechanism. Section 4 establishes the posterior-to-prior ratio bounds under bounded probabilistic and bounded approximate differential privacy, while Section 5 derives a closed-form expression for an upper limit on their failure probability for the Gaussian mechanism. Section 6 presents a Monte Carlo study evaluating the tightness of this limit. Finally, Section 7 discusses the findings, addresses limitations, and outlines directions for future research.

2

Notation and Preliminaries

Our notation and terminology largely follow Bailie and Gong (2024). The following definition of a data universe is adapted from their framework. Definition 1. (Data universe) Let X be a set and G := (X , E) an undirected graph with unit-length edges. A data universe is an extended metric space (X , d), where the metric d : X × X → [0, ∞] is given by  0, if x = x′ ,    k, if x ̸= x′ are connected in G and k is the length of the d(x, x′ ) :=  shortest path between them,    ∞, if x, x′ are not connected in G, for x, x′ ∈ X . Intuitively, X represents the set of all datasets that may be drawn from a given population. A dataset x ∈ X is typically a set of records sampled from a common domain D, that is, x = {ri }ni=1 with ri ∈ D for all i = 1, 2, . . . , n. As an example, D = R2≥0 may represent height and weight measurements of the population. Note for notational simplicity the graph G is omitted from the data universe notation, as it is typically redundant when d is given. The metric d determines the notion of neighbouring datasets, with x and x′ being neighbours whenever d(x, x′ ) = 1. Common examples used in differential privacy include the Hamming distance and the symmetric difference, which induce different neighbour relations. The following definition introduces data-release mechanisms, which are randomised mappings that transform datasets into into publicly released outputs, such as statistics, synthetic datasets, or other privacyprotected data products. 2

Definition 2. (Data-release mechanism) Let (X , d) be a data universe and (T , F ) a standard Borel space. The map M : X × [0, 1] → T is called a data-release mechanism if M (x, ·) is B[0, 1]-F -measurable for all x ∈ X . Additionally, we define a family of probability measures {Px }x∈X on (T , F ), where Px (S) := λ ({u ∈ [0, 1] | M (x, u) ∈ S})

(1)

for x ∈ X and S ∈ F , and where λ denotes the Lebesgue measure. The notion of data-release mechanisms encompasses both randomised and deterministic mechanisms. Examples of deterministic outputs include summary statistics such as sample means, regression coefficients, or p-values computed from a dataset. Randomised mechanisms incorporate an additional source of randomness, so that repeated applications to the same dataset may produce different outputs. The Gaussian mechanism, introduced below, provides an example. Differential privacy is a property that quantifies the level of privacy a data-release mechanism guarantees. The following definition is adapted from Dwork et al. (2006a). Definition 3. (Approximate differential privacy) Let (X , d) be a data universe and M : X × [0, 1] → T a data-release mechanism. For ε, δ ∈ R≥0 , the data-release mechanism is said to satisfy (ε, δ)-approximate differential privacy if Px (S) ≤ eε Px′ (S) + δ

(2)

for x, x′ ∈ X with d(x, x′ ) = 1 and S ∈ F . When δ = 0, M is said to satisfy pure ε-differential privacy. Two commonly used notions are unbounded (or add/remove-one) differential privacy, where neighbouring datasets differ by the presence of a single individual, and bounded (or replace-one) differential privacy, where neighbouring datasets have the same size and differ in the record of a single individual. The choice of neighbour relation affects the sensitivity of statistical queries and consequently the amount of noise required to achieve a given privacy level. To accommodate both settings, the definition above is stated with respect to a generic neighbour relation d. Under pure differential privacy, symmetry of the neighbour relation implies that e−ε Px′ (S) ≤ Px (S) ≤ eε Px′ (S), meaning that the output distributions of the data-release mechanism differ by at most a factor of eε . The δ parameter of approximate differential privacy relaxes these bounds by allowing that eε Px′ (S) < Px (S) ≤ eε Px′ (S) + δ, as long as δ > 0. Note that δ ≥ 1 would render the privacy promise of approximate differential privacy vacuous. Example: The Gaussian mechanism To illustrate the preceding definitions, we present a simple example based on the Gaussian mechanism. Consider datasets consisting of m records, where each record is a point in R2 representing, for instance, height and weight measurements. We then define X = 2R

2

(3) m

as the collection of all datasets of size m. We equip X with the Hamming distance, X d(x, x′ ) := 1i∈x / ′,

(4)

i∈x

for x, x′ ∈ X . Since all datasets in X have cardinality m, every pair of datasets is connected. With the above, we have now specified a data universe (X , d). Suppose we observe a dataset x ∈ X and wish to publish the output f (x) of a deterministic query f : X → A, where A is a bounded subset of R2 . For instance, f (x) could be the bivariate sample 3

mean of height and weight measurements. Releasing f (x) may reveal sensitive information, and we are therefore interested in publishing it through a privacy-protecting data-release mechanism. The Gaussian mechanism proposed by Dwork and Roth (2014) privatises the output of a query by adding normally distributed noise, that is, M (x, u) := f (x) + σΦ−1 (u),

(5)

where the entries of Φ−1 : [0, 1] → R2 are the inverse standard normal distribution function. According to Dwork and Roth (2014), this mechanism satisfies (ε, δ)-approximate differential privacy if p ∆2 f 2 log(1.25/δ) , (6) σ> ε where ε, δ ∈]0, 1[ and ∆2 f ∈ R≥0 is the ℓ2 -sensitivity of f defined by ∆2 f :=

sup ∥f (x) − f (x′ )∥2 .

x,x′ ∈X d(x,x′ )=1

Since the Hamming distance was used to define neighbouring datasets, the Gaussian mechanism satisfies bounded (ε, δ)-approximate differential privacy. If we had used the symmetric difference instead, the mechanism would satisfy unbounded (ε, δ)-approximate differential privacy. Note, for this example we considered the classical Gaussian mechanism, however, other versions of the Gaussian mechanism have been proposed by, for instance, Balle and Wang (2018) and Ji and Li (2024).

3

Probabilistic Differential Privacy

To derive bounds on the posterior-to-prior ratio under bounded approximate differential privacy, we we adapt the approach of Kazan (2025), who considered the unbounded setting. Specifically, we first derive bounds under bounded probabilistic differential privacy and then transfer these results to bounded approximate differential privacy using the implication from approximate differential privacy to probabilistic differential privacy. In this section, we restate probabilistic differential privacy and its relation to approximate differential privacy within our mathematical framework. Probabilistic differential privacy is a variant of differential privacy that relaxes the strictness of pure ε-differential privacy (Machanavajjhala et al., 2008). Instead of adding a δ, as approximate differential privacy does in (2), probabilistic differential privacy is defined as pure ε-differential privacy that breaks with probability at most δ. The following definition is adapted from Meiser (2018). Definition 4. (Probabilistic differential privacy) Let (X , d) be a data universe and M : X × [0, 1] → T a data-release mechanism. For ε, δ ∈ R≥0 , the data-release mechanism M is said to satisfy (ε, δ)-probabilistic differential privacy if, for x, x′ ∈ X with δ δ d(x, x′ ) = 1, there exists a set Sx,x ′ ∈ F with Px (Sx,x′ ) ≤ δ, such that δ δ ε δ e−ε Px′ (S \ Sx,x ′ ) ≤ Px (S \ Sx,x′ ) ≤ e Px′ (S \ Sx,x′ )

(7)

δ for S ∈ F . All such sets Sx,x ′ are called bad regions.

Similarly to approximate differential privacy, a value of δ ≥ 1 renders Definition 4 vacuous as the privacy condition is then allowed to fail with probability one. The following theorem, adapted from Zhao et al. (2019), establishes that probabilistic differential privacy directly implies approximate differential privacy. Theorem 1. For any ε, δ ∈ R≥0 , if a data-release mechanism satisfies (ε, δ)-probabilistic differential privacy it also satisfies (ε, δ)-approximate differential privacy. Proof. Let (X , d) be a data universe and M : X × [0, 1] → T a data-release mechanism satisfying (ε, δ)probabilistic differential privacy. Further, let x, x′ ∈ X with d(x, x′ ) = 1 and a set S ∈ F be given. By δ δ assumption, there exists a set Sx,x ′ ∈ F , such that Px (Sx,x′ ) ≤ δ and (7) hold. Consequently, we obtain δ δ Px (S) = Px (S \ Sx,x ′ ) + Px (S ∩ Sx,x′ )

4

δ δ ≤ eε Px′ (S \ Sx,x ′ ) + Px (Sx,x′ )

≤ eε Px′ (S) + δ, establishing (2). The converse relation is not immediate. In particular, it requires proving the existence of a measurable δ δ set Sx,x ′ ∈ F satisfying (7) and determining an upper bound on Px (Sx,x′ ). We have therefore formulated the following lemma that states the existence of such a set and serves as a key ingredient in the proof for the converse of Theorem 1. Lemma 1. Let (X , d) be a data universe, M : X × [0, 1] → T a data-release mechanism, and ε ∈ R≥0 . For all x, x′ ∈ X , there exists a set Sx,x′ ∈ F , such that e−ε Px′ (S \ Sx,x′ ) ≤ Px (S \ Sx,x′ ) ≤ eε Px′ (S \ Sx,x′ )

(8)

′ ′ for S ∈ F , and for any set Sx,x ′ ∈ F satisfying (8) in the place of Sx,x′ , we have Px (Sx,x′ ) ≤ Px (Sx,x′ ).

Proof. Let x, x′ ∈ X be given and let µ be any σ-finite measure such that µ ≫ Px and µ ≫ Px′ . Such a measure always exists, for instance by taking µ = Px + Px′ . Regardless of how µ is constructed, the corresponding densities p :=

dPx′ dPx and q := dµ dµ

are well defined. Define Sx,x′ := Ax,x′ ∪ Bx,x′ , where the disjoint subsets Ax,x′ and Bx,x′ are given by  Ax,x′ := v ∈ T | e−ε q(v) > p(v) , (9) Bx,x′ := {v ∈ T | p(v) > eε q(v)} . Since p and q are measurable, both Ax,x′ and Bx,x′ belong to F . Hence, so does Sx,x′ . By construction e−ε q(v) ≤ p(v) ≤ eε q(v) for all v ∈ / Sx,x′ . Therefore, for S ∈ F , Z Z ε ′ Px (S \ Sx,x ) = p(v)dµ(v) ≤ e q(v)dµ(v) = eε Px′ (S \ Sx,x′ ), S\Sx,x′

S\Sx,x′

Z Px (S \ Sx,x′ ) =

p(v)dµ(v) ≥ e

−ε

Z

S\Sx,x′

q(v)dµ(v) = e−ε Px′ (S \ Sx,x′ ).

S\Sx,x′

This proves the existence of a set Sx,x′ satisfying (8). It remains to show that Sx,x′ minimises Px (·) among ′ ′ all such sets. To this end, let Sx,x ′ ∈ F be any other set satisfying (8), and define D := Sx,x′ \ Sx,x′ . Then ′ ′ Px (D) = Px (Ax,x′ \ Sx,x ′ ) + Px (Bx,x′ \ Sx,x′ ). ′ ′ It holds that Ax,x′ \ Sx,x ′ and Bx,x′ \ Sx,x′ are µ-zero sets, since Z ′ −ε ′ Px (Ax,x′ \ Sx,x′ ) ≥ e Px′ (Ax,x′ \ Sx,x′ ) ⇔

p(v) − e−ε q(v) dµ(v) ≥ 0,

′ Ax,x′ \Sx,x ′

′ ε ′ Px (Bx,x′ \ Sx,x ′ ) ≤ e Px′ (Bx,x′ \ Sx,x′ )

Z ⇔

(p(v) − eε q(v)) dµ(v) ≤ 0,

′ Bx,x′ \Sx,x ′

and the integrands p(v) − e−ε q(v) and p(v) − eε q(v) are, respectively, strictly negative and positive. Consequently, D is a µ-zero set and therefore also a Px -zero set. Hence, ′ ′ ′ ′ Px (Sx,x′ ) = Px (Sx,x′ ∩ Sx,x ′ ) + Px (Sx,x′ \ Sx,x′ ) = Px (Sx,x′ ∩ Sx,x′ ) ≤ Px (Sx,x′ ).

This proves that Sx,x′ has minimal Px -measure among all sets satisfying (8). In essence, Lemma 1 identifies a minimal bad region for each neighbouring pair of datasets. Using this result, we can prove the following theorem, which states the converse relation of Theorem 1. A proof for this result is given by Zhao et al. (2019), however, we provide an alternative proof. 5

Theorem 2. Let ε ∈ R≥0 and δ ∈ [0, 1). If a mechanism satisfies (ε, δ)-approximate differential privacy, it also satisfies (ε′ , δ ′ )-probabilistic differential privacy for any ε′ > ε and ′

δ(1 + e−ε ) . δ = 1 − eε−ε′ ′

Proof. δ′ Let x, x′ ∈ X with d(x, x′ ) = 1 be given. We need to show that there exists a set Sx,x ′ ∈ F , such that (7) holds and ′

′

δ ′ Px (Sx,x ′ ) ≤ δ :=

δ(1 + e−ε ) . 1 − eε−ε′

(10)

The existence of a set satisfying (7) for ε′ is concluded by Lemma 1, so it remains to show (10). We will δ′ ′ assume that Sx,x ′ is the smallest set satisfying (7) for a given ε > ε. As in the proof of Lemma 1, let µ be a σ-finite measure for which µ ≫ Px and µ ≫ Px′ , and define the densities p :=

dPx , dµ

q :=

dPx′ . dµ

Let Ax,x′ and Bx,x′ be given as in (9). Then, under (ε, δ)-approximate differential privacy, we have Px (Bx,x′ ) ≤ eε Px′ (Bx,x′ ) + δ Z ε =e q(v)dµ(v) + δ Bx,x′ ′

≤ eε−ε

Z p(v)dµ(v) + δ Bx,x′

′

= eε−ε Px (Bx,x′ ) + δ, which implies that Px (Bx,x′ ) ≤

δ . 1 − eε−ε′

′

(11)

Consider now the set Sxδ ′ ,x ∈ F obtained by exchanging x and x′ in Definition 4 and Lemma 1. Proceed′ ing analogously to the construction above, we decompose Sxδ ′ ,x into Ax′ ,x , Bx′ ,x ∈ F . By construction, Ax,x′ = Bx′ ,x and Bx,x′ = Ax′ ,x . Since (11) holds for arbitrary x ∈ X , we must also have Px′ (Bx′ ,x ) ≤

δ . 1 − eε−ε′

This gives the following upper bound: Z Px (Ax,x′ ) =

p(v)dµ(v) Ax,x′ −ε′

Z

≤e

q(v)dµ(v) Ax,x′

′

= e−ε Px′ (Ax,x′ ) ′

= e−ε Px′ (Bx′ ,x ) ′ δ . ≤ e−ε 1 − eε−ε′ Consequently, ′

δ Px (Sx,x ′ ) = Px (Ax,x′ ) + Px (Bx,x′ ) ′ δ δ ≤ e−ε + 1 − eε−ε′ 1 − eε−ε′ ′ δ(1 + e−ε ) = , 1 − eε−ε′

which was to be shown. 6

Theorem 2 shows how the (ε, δ)-parameters of approximate differential privacy translates into corresponding parameters ε′ and δ ′ for probabilistic differential privacy. Specifically, ε′ may be chosen arbitrarily larger than ε, after which δ ′ can be calculated in closed form. The following corollary, adapted from Kazan (2025), provides the inverse characterisation: δ ′ may be chosen arbitrarily within a suitable interval, and the corresponding value of ε′ is then given in closed form. Corollary 1. A data-release mechanism satisfying (ε, δ)-approximate differential privacy for ε ∈ R≥0 and δ ∈ [0, 1) also satisfies (ε′ , δ ′ )-probabilistic differential privacy for any δ ′ ∈ (δ, 1] and   ′ ε δ e +δ . ε′ = log δ′ − δ Proof. Let δ ′ ∈ (δ, 1] be given. Solving ′

δ(1 + e−ε ) δ = 1 − eε−ε′ ′

for ε′ yields  ′ ε  δ e +δ ε = log , δ′ − δ ′

which was to be shown. The Geometry of the bad regions under the Gaussian mechanism δ In this section we investigate the shape and size of the bad regions Sx,x ′ for the Gaussian mechanism. As stated in Section 2, the Gaussian mechanism satisfies approximate differential privacy. By Theorem 2 it also satisfies probabilistic differential privacy.

Let (X , d) be a data universe, and consider again the Gaussian mechanism given by (5), but where f : X → A and A is a bounded subset of Rq . In Section 2 we specified the data universe by (3) and (4), however, the Gaussian mechanism satisfies approximate differential privacy regardless of the data δ q universe. According to Definition 4 there exists a set Sx,x ′ ∈ B(R ), such that δ Px (Sx,x ′) ≤ δ

and (7) holds for any S ∈ B(Rq ). Under the Gaussian mechanism,     Z Z 1 v − f (x) 1 v − f (x′ ) Px (S) = q ϕ dv and Px′ (S) = q ϕ dv σ S σ σ S σ for all S ∈ B(Rq ), where ϕ denotes density of the q-dimensional standard normal distribution. Hence, the measures Px and Px′ admit the densities p and q given by     1 v − f (x) 1 v − f (x′ ) p(v) := q ϕ and q(v) := q ϕ . σ σ σ σ Since the support of ϕ is Rq , we have  δ Sx,x v ∈ Rq | p(v) < e−ε q(v) ∨ eε q(v) < p(v) ′ =     p(v) q = v ∈ R | log >ε , q(v) where  log

p(v) q(v)

 = log =

! exp − 2σ1 2 ∥v − f (x)∥22
exp − 2σ1 2 ∥v − f (x′ )∥22

1 ∥v − f (x′ )∥22 − ∥v − f (x)∥22 2 2σ 7

(12)

δ ′ with ∥·∥2 denoting the Euclidean norm. When f (x) = f (x′ ), we get Sx,x ′ = ∅. For f (x) ̸= f (x ), define ′

(x ) ∆f ′ . Thus, f (x) = m + ∆f ∆f := f (x) − f (x′ ) and m := f (x)+f 2 2 and f (x ) = m − 2 , and we can now rewrite ∆f 2 ∆f 2 ∥v − f (x′ )∥22 − ∥v − f (x)∥22 = ∥v − m + ∥2 − ∥v − m − ∥ 2 2 2     ∆f ∆f ∆f ∆f ,v − m + − v−m− ,v − m − = v−m+ 2 2 2 2

= 2 ⟨v − m, ∆f ⟩ . Combining the above yields  log

p(v) q(v)

 =

⟨v − m, ũ⟩ ∆ ⟨v − m, ∆f ⟩ = , 2 σ σ2

where ∆ := ∥∆f ∥2 and ũ := ∆f /∆. Substituting this into (12), we obtain   ⟨v − m, ũ⟩ ∆ δ q Sx,x′ = v ∈ R | >ε σ2   εσ 2 = v ∈ Rq | ⟨v, ũ⟩ − ⟨m, ũ⟩ > . ∆

(13) 2

εσ δ Thus, Sx,x ′ is the union of the two open half-spaces defined by the inequalities ⟨v, ũ⟩ > ∆ + ⟨m, ũ⟩ and 2 εσ ⟨v, ũ⟩ < − ∆ + ⟨m, ũ⟩. Let V (u) := M (x, u). Using (13), we can rewrite   εσ 2 δ q Px (Sx,x′ ) = Px v ∈ R | ⟨v, ũ⟩ − ⟨m, ũ⟩ > ∆   εσ 2 =λ u ∈ [0, 1] | ⟨V (u), ũ⟩ − ⟨m, ũ⟩ > ∆   2 εσ = λ ⟨V, ũ⟩ − ⟨m, ũ⟩ > ∆     εσ 2 εσ 2 = λ ⟨V, ũ⟩ − ⟨m, ũ⟩ > + λ ⟨V, ũ⟩ − ⟨m, ũ⟩ < − . (14) ∆ ∆

Since V (u) = M (x, u), we have by the construction of the Gaussian mechanism in (5), ⟨V (u), ũ⟩ = f (x) + σΦ−1 (u), ũ = ⟨f (x), ũ⟩ + σ Φ−1 (u), ũ   ∆f = m+ , ũ + σ Φ−1 (u), ũ 2   ∆ · ũ = m+ , ũ + σ Φ−1 (u), ũ 2 ∆ + σ Φ−1 (u), ũ . 2 Then, defining N (u) := Φ−1 (u), ũ , which is standard normally distributed, (14) becomes     ∆ εσ 2 ∆ εσ 2 δ Px (Sx,x′ ) = λ ⟨m, ũ⟩ + + σN − ⟨m, ũ⟩ > + λ ⟨m, ũ⟩ + + σN − ⟨m, ũ⟩ < − 2 ∆ 2 ∆     2 2 ∆ εσ ∆ εσ =λ + σN > +λ + σN < − 2 ∆ 2 ∆     εσ ∆ εσ ∆ = λ −N < − + +λ N <− − ∆ 2σ ∆ 2σ     εσ ∆ εσ ∆ =Φ − + +Φ − − . (15) ∆ 2σ ∆ 2σ = ⟨m, ũ⟩ +

This can be used to exactly calculate the size of the bad region for any choice of x, x′ ∈ X with d(x, x′ ) = 1. 8

4

Posterior-to-Prior-Ratio of Inclusion Belief

In this section, we quantify the inferential capabilities of a Bayesian adversary under differential privacy. We focus on inclusion belief, defined as the adversary’s subjective probability that a specific individual is contained in the underlying dataset. The adversary begins with a prior belief about inclusion, which is updated to a posterior belief upon observing information about the dataset. A natural decision rule is then to infer inclusion based on this posterior probability. However, it has been argued that posterior beliefs alone do not fully capture privacy risk (Hotz et al., 2024). Recent works such as Kazan and Reiter (2024) and Bailie and Gong (2024) have opted for posterior-to-prior ratios and differences instead. Individually, these measures do not convey the exact risk of disclosure but how much the belief of an adversary changes due to the release of dataset information. For a data holder deciding whether to release information about a dataset, the implied posterior-to-prior change is more informative than the posterior belief itself; if the change is negligible, then so is the additional privacy risk induced by the release, and vice versa. Posterior beliefs are conditioned on the outputs of a data-release mechanism, and since these outputs may follow a continuous distribution, we set up a probability theoretic framework for defining probability measures conditioned on realisations of continuous random variables. Defining the posterior-to-prior ratio We assume for the rest of this paper that an observed dataset consists of a sample drawn from a finite population. Specifically, let P := {1, 2, . . . , n} denote a population of n ∈ N individuals, and let m ∈ {1, . . . , n} denote the fixed sample size. Define X := 2P m , the collection of all possible datasets of size m that can be observed from the population. For the rest of this paper, we will equip X with the Hamming distance d defined in (4), such that (X , d) forms a data universe. Hence, any data-release mechanism satisfying Definition 3 satisfies bounded approximate differential privacy from now on. Let M be a data-release mechanism as in Definition 2, and assume that the family of probability measures {Px }x∈X on (T , F ) given by (1) is dominated by a σ-finite measure ν. In this setup, a dataset x ∈ X is represented as a subset of the population indices P . In practice, however, each individual is associated with a record of attributes taking values in some domain D, and the data-release mechanism M operates on these attribute values rather than on the indices themselves. As in Kazan (2025), we assume that each individual in P can be uniquely identified by its attribute record, that is, there exists a bijection between P and D that is embedded in M . Consequently, we may represent a dataset by the set of individual identifiers, while M internally maps these identifiers to their corresponding attribute values when producing a release. This representation is applicable regardless of whether we consider cancer registries, blood panel databases, or other collections of independent static records, provided that no two records are exactly identical. From the perspective of a Bayesian adversary, the observed dataset is random. Hence, on some probability space (Ω, A , P), we define a random variable X : Ω → X for which a realisation represents an observed dataset. Since Px ≪ ν for all x ∈ X , each measure Px admits a density px with respect to ν. Using these densities, we define the intensity measure as Z PM,X (t, I) := pX(ω) (t)dP(ω), (16) I

where t ∈ T and I ∈ A . Formally, (16) requires the map (x, t) 7→ px (t) to be measurable. This follows from assuming that M is (A ⊗ B[0, 1])-F measurable, in addition to the assumptions of Definition 2. Define the conditional density of the data-release mechanism by PM |X (t | I) :=

PM,X (t, I) , P(I)

where t ∈ T , I ∈ A , and P(I) > 0. Finally, we define the conditional probability measure of X given an approximate differentially private mechanism output t ∈ T and a set of auxiliary information A ∈ A by PX|M (I | t, A) :=

9

PM,X (t, I ∩ A) , PM,X (t, A)

(17)

where PM,X (t, A) > 0. This conditional probability measure reflects the probability that the observed dataset x is sampled from X(I) given a mechanism output t ∈ T and some auxiliary information about the observed dataset, represented by A. Assuming that the adversary has auxiliary information is, as noted by Guerra-Balboa et al. (2026), crucial as bounding the capabilities of such an adversary will also bound the capabilities of adversaries with less information. For inclusion inference, we consider the event Ii := {ω ∈ Ω | i ∈ X(ω)}

(18)

for i ∈ P , which contains all realisations of the data-generating process for which individual i is in the observed dataset. For the auxiliary information, we adopt an all-but-one framework and assume that the adversary knows m − 1 individuals in the observed dataset, i.e.  A := ω ∈ Ω | x− ⊂ X(ω) (19) for some fixed x− ⊂ P \{i} of length m−1. Our goal is to assess upper and lower bounds to the following posterior-to-prior ratio under bounded approximate differential privacy R(t) :=

PX|M (Ii | t, A) . P(Ii | A)

(20)

Posterior-to-prior ratio bounds under bounded differential privacy Before deriving the bounds, we need the following two results. The first states that probabilistic differential privacy has a pointwise equivalent version. Theorem 3. Let M be a data-release mechanism, and assume that its family of probability measures {Px }x∈X defined by (1) is dominated by a σ-finite measure ν. Let px and px′ denote the densities of Px and Px′ , respectively, with respect to ν. Then M satisfies (ε, δ)-probabilistic differential privacy for ε, δ ∈ R≥0 if and δ δ only if, for any x, x′ ∈ X with d(x, x′ ) = 1 there exists a set Sx,x ′ ∈ F with Px (Sx,x′ ) ≤ δ, where e−ε px′ ≤ px ≤ eε px′

(21)

δ ν-almost everywhere on T \ Sx,x ′.

Proof. We first prove that probabilistic differential privacy implies (21). Assume that M satisfies (ε, δ)probabilistic differential privacy, and let x, x′ ∈ X be given with d(x, x′ ) = 1, where (X , d) is our δ data universe. By the definition of probabilistic differential privacy, there exists a set Sx,x ′ ∈ F with δ Px (Sx,x′ ) ≤ δ such that (7) holds for any S ∈ F . Then Z Z δ ε δ px (t)dν(t) = Px (S \ Sx,x eε px′ (t)dν(t), ′ ) ≤ e Px′ (S \ Sx,x′ ) = δ S\Sx,x ′

δ S\Sx,x ′

where px and px′ are densities of Px and Px′ , respectively, with respect to ν. Since this inequality holds δ for arbitrary S ∈ F , px (t) ≤ eε px′ (t) for ν-almost every t ∈ T \ Sx,x ′ . The converse inequality can be derived analogously. This proves the first implication. To prove the reverse implication, let x, x′ ∈ X with d(x, x′ ) = 1, and assume that there exists some set δ δ δ Sx,x ′ ∈ F with Px (Sx,x′ ) ≤ δ such that (21) holds for ν-almost every t ∈ T \ Sx,x′ . Then, for S ∈ F , Z Z δ δ Px (S \ Sx,x px (t)dν(t) ≤ eε px′ (t)dν(t) = eε Px′ (S \ Sx,x ′) = ′ ). δ S\Sx,x ′

δ S\Sx,x ′

δ −ε δ It can similarly be shown that Px (S \ Sx,x Px′ (S \ Sx,x ′) ≥ e ′ ), which proves (ε, δ)-probabilistic differential privacy of M .

Theorem 3 shows that probabilistic differential privacy can be characterised pointwise whenever the family of probability measures defined by the data-release mechanism is dominated by a common σfinite measure. Assuming that a mechanism satisfies the conditions of Theorem 3, then there exists δ by Lemma 1 a tight smallest set Sx,x ′ ∈ F constructed through (9) for which the inequality (21) 10

δ fails everywhere on Sx,x ′ and holds everywhere on its complement. Hence, we can understand the bad δ region Sx,x′ as the exact region in which the data-release mechanism violates pure ε-differential privacy. δ Releasing an output in T \ Sx,x ′ is therefore a necessary and sufficient condition for (21) to hold.

Using Theorem 3, we establish the following lemma, which forms the basis for deriving upper and lower bounds on R under probabilistic differential privacy. Lemma 2. Let Ii and A denote the inclusion and auxiliary-information events defined in (18) and (19), respectively, and assume that P(Iic ∩ A) > 0. Let M be a data-release mechanism satisfying (ε, δ)-probabilistic differential privacy for ε, δ ∈ R≥0 , and assume that its family of probability measures {Px }x∈X given by (1) is dominated by a σ-finite measure ν. If x ∈ X(Ii ∩ A), then e−ε ≤

PM |X (t | Iic ∩ A) ≤ eε px (t)

(22)

for ν-almost every t ∈ T \ Sxδ , where [

Sxδ :=

δ Sx,x ′.

x′ ∈X(Iic ∩A)

Proof. Rewriting the numerator, we obtain that PM,X (t, Iic ∩ A) P(Iic ∩ A) Z 1 pX(ω) (t)dP(ω) = P(Iic ∩ A) Iic ∩A Z † 1 ≤ eε px (t)dP(ω) ν-almost every t ∈ T \ Sxδ P(Iic ∩ A) Iic ∩A

PM |X (t | Iic ∩ A) =

= eε px (t), where † follows from the fact that every realisation X(ω) is a neighbour of x for ω ∈ Iic ∩ A, and thus Theorem 3 applies. This establishes the right-hand inequality in (22); the left-hand inequality follows analogously. In Lemma 2, the condition t ∈ T \Sxδ is sufficient, but not necessary, for (22) to hold. To see this, consider the integrals on the left- and right-hand sides of the inequality marked † in the proof of Lemma 2. Since X(Iic ∩ A) is a finite set, we may write X(Iic ∩ A) = {x1 , x2 , . . . , xq }, for some xj ∈ X , j = 1, . . . , q. The integrals can then be expressed as Z pX(ω) (t)dP(ω) =

q X

Iic ∩A

j=1

Z

q X

eε px (t)dP(ω) =

Iic ∩A

pxj (t)(P ◦ X −1 )({xj }), eε px (t)(P ◦ X −1 )({xj }).

j=1

Assuming a uniform prior on X(Iic ∩ A), we have (P ◦ X −1 )({xj }) =

P(Iic ∩ A) , q

j = 1, . . . , q.

It follows that PM |X (t | Iic ∩ A) =

q X 1 px (t)(P ◦ X −1 )({xj }) P(Iic ∩ A) j=1 j

11

q

1X px (t). = q j=1 j Consequently, the upper bound in (22) is equivalent to q X

pxj (t) ≤ qeε px (t).

(23)

j=1

Now suppose that t ∈ Sxδ and, more specifically, that t belongs to exactly one of the bad regions, say Sq−1 δ δ t ∈ Sx,x and t ∈ / j=1 Sx,x . For j = 1, . . . , q − 1, Theorem 3 gives q j e−ε px (t) ≤ pxj (t) ≤ eε px (t) for ν-almost every such t. In particular, q−1 X

pxj (t) ≤ (q − 1)eε px (t).

j=1

Consider the case in which pxq (t) > eε px (t). Although the pointwise upper bound is then violated for xq , the corresponding bound for the mixture continues to hold if this excess is compensated by the slack contributed by the remaining terms, that is, if pxq (t) − eε px (t) ≤ (q − 1)eε px (t) −

q−1 X

pxj (t).

j=1

Indeed, this condition is equivalent to (23) and therefore establishes the upper bound in (22). The lower bound also holds in this case. For j = 1, . . . , q − 1, Theorem 3 gives pxj (t) ≥ e−ε px (t), while pxq (t) > eε px (t) ≥ e−ε px (t). It follows that q X

pxj (t) ≥ qe−ε px (t),

j=1

which establishes the lower bound in (22). Thus, (22) may hold even when t ∈ Sxδ and the pointwise upper bound is violated for xq . At the same time, Lemma 2 guarantees that (22) holds for ν-almost every t ∈ T \ Sxδ . Hence, up to a ν-null set, the actual failure region is contained in Sxδ , and Px ({t ∈ T | (22) fails at t}) ≤ Px (Sxδ ). Thus, Sxδ is a conservative failure region. We now use Lemma 2 to establish bounds on the posterior-to-prior ratio R under bounded probabilistic differential privacy. Theorem 4. Assume that P(Ii ∩ A) > 0 and P(Iic ∩ A) > 0, where Ii and A are given by (18) and (19), respectively. Let M be a data-release mechanism satisfying (ε, δ)-probabilistic differential privacy for ε, δ ∈ R≥0 , and assume that its family of probability measures {Px }x∈X given by (1) is dominated by a σ-finite measure ν. If x ∈ X(Ii ∩ A), then 1 1 ≤ R(t) ≤ ε P(Ii | A) + (1 − P(Ii | A))e P(Ii | A) + (1 − P(Ii | A))e−ε for ν-almost every t ∈ T \ Sxδ , where Sxδ :=

[ x′ ∈X(Iic ∩A)

12

δ Sx,x ′.

(24)

Proof. First note that Z

Z

PM,X (t, Ii ∩ A) =

px (t)dP(ω) = px (t)P(Ii ∩ A),

pX(ω) (t)dP(ω) = Ii ∩A

Ii ∩A

since X(ω) = x for all ω ∈ Ii ∩ A. Hence, PM |X (Ii | t, A) =

PM,X (t, Ii ∩ A) PM,X (t, A)

=

PM,X (t, Ii ∩ A) PM,X (t, Ii ∩ A) + PM,X (t, Iic ∩ A)

=

px (t)P(Ii ∩ A) px (t)P(Ii ∩ A) + PM |X (t | Iic ∩ A)P(Iic ∩ A)

=

≤

P(Ii | A) (t|I c ∩A)

P

P(Ii | A) + P(Iic | A) M |Xpx (t)i

P(Ii | A) , P(Ii | A) + (1 − P(Ii | A))e−ε

for ν-almost every t ∈ T \ Sxδ , where the final inequality follows from Lemma 2. The lower bound in (24) is obtained analogously.

As discussed following Lemma 2, the condition t ∈ T \ Sxδ is sufficient, but not necessary, for the bounds in (24) to hold. Indeed, these bounds are derived from (22), which is guaranteed to hold outside Sxδ but may also hold within this region. Consequently, Sxδ is a conservative failure region for (24), and the probability that these bounds fail is at most Px (Sxδ ). Using Theorem 2, we can reformulate Theorem 4 to hold for approximately differentially private mechanisms. Corollary 2. Assume that P(Ii ∩A) > 0 and P(Iic ∩A) > 0, where Ii and A are given by (18) and (19), respectively. Let M be a data-release mechanism satisfying (ε′ , δ ′ )-approximate differential privacy for ε′ , δ ′ ∈ R≥0 , and assume that its family of probability measures {Px }x∈X given by (1) is dominated by a σ-finite measure ν. If x ∈ X(Ii ∩ A), then 1 1 ≤ R(t) ≤ , P(Ii | A) + (1 − P(Ii | A))eε P(Ii | A) + (1 − P(Ii | A))e−ε

(25)

for ν-almost every t ∈ T \ Sxδ , where [

Sxδ :=

δ Sx,x ′,

x′ ∈X(Iic ∩A)

δ ∈ [δ ′ , 1), and ′

ε = log

δeε + δ ′ δ − δ′

! .

Proof. The corollary follows immediately from Corollary 1 and Theorem 4. The upper and lower bounds in (24) and (25) depend on the prior probability P(Ii | A) adopted by the Bayesian adversary. However, Kazan (2025) show that the posterior-to-prior ratio also satisfies the prior-independent bounds e−ε ≤ R(t) ≤ eε ,

13

(26)

for ν-almost every t ∈ T \ Sxδ . As these bounds define a wider interval, the probability that R(t) falls outside them is not greater than for the corresponding prior-dependent bounds. Quantifying when the posterior-to-prior ratio bounds fail is important when assessing whether the release of differentially private data poses an unacceptable disclosure risk. Finding a general expression for Px (Sxδ ) is elusive. However, an upper limit can be obtained by exploiting the subadditivity of Px , namely,   X [ δ δ  Px (Sx,x Px (Sxδ ) = Px  Sx,x ≤ ′ ) = qδ, ′ x′ ∈X(Iic ∩A)

x′ ∈X(Iic ∩A)

where q = |X(Iic ∩ A)|. In our setting, q = n − m may be very large, rendering the upper limit vacuous. δ δ ′ c As the sets Sx,x ′ , x ∈ X(Ii ∩ A), may overlap, Px (Sx ) can be significantly smaller than qδ. Nevertheless, for the Gaussian mechanism an exact expression for Px (Sxδ ) can be derived, as shown in the following section.

5

The Risk of Failing the Ratio Bounds under the Gaussian Mechanism

To quantify the probability of violating the bounds in (24) and (25), it remains to characterise Px (Sxδ ). δ Since a closed-form expression for Px (Sx,x ′ ) was derived for the Gaussian mechanism in Section 3, we δ can now use it to characterise Px (Sx ). Recall that [ δ Sxδ = Sx,x ′, x′ ∈X(Iic ∩A)

where Ii is given by (18), A is given by (19), and x ∈ X(Ii ∩ A). Note that X(Ii ∩ A) = {x− ∪ {i}}, while X(Iic ∩ A) contains p := n − m + 1 elements, say {x1 , x2 , . . . , xp }. Then    ! p p i−1 [ [ [ δ δ δ  , Px (Sxδ ) = Px Sx,x = Px  Sx,x \ Sx,x i i j i=1

with the convention that of Px implies that  Px 

i=1

j=1

S0

δ j=1 Sx,xj = ∅. Since the outer union is taken over disjoint sets, the additivity

p [

 δ Sx,x \ i

i−1 [

 δ  = Sx,x j

j=1

i=1

p X

 δ Px Sx,x \ i

i=1

=

p X

T0

j=1



δ Sx,x j

c

 δ  Sx,x j

j=1

 δ Px Sx,x ∩ i

i=1

where, by convention,

i−1 [

i−1 \

 δ Sx,x j

c

,

(27)

j=1

=T.

To facilitate the analysis of the summands above, we first introduce some notation. Recall the Gaussian mechanism M described by M (x, u) := f (x) + σΦ−1 (u), where f : X → A ⊂ Rq is a deterministic function and the entries of Φ−1 : [0, 1] → Rq are inverse standard normal distribution functions. Define mj := 12 (f (x) + f (xj )), ∆fj := f (x) − f (xj ), ∆j := ∥∆fj ∥2 , and δ ũj := ∆fj /∆j for each j = 1, 2, . . . , p with f (x) ̸= f (xj ). Note, for f (x) = f (xj ), we have Sx,x = ∅ as j shown in Section 3. Using this notation, we have from (13) that   εσ 2 δ q Sx,x = v ∈ R |⟨v − m , ũ ⟩| > . j j j ∆j

14

Define the random variables V (u) := M (x, u) and Wj (u) := ⟨V (u) − mj , ũj ⟩, j = 1, 2, . . . , p. For U ∼ Unif[0, 1], we have that V (U ) ∼ N (f (x), σ 2 Iq ), and in turn E [Wj ] = E [⟨V − mj , ũj ⟩] = ⟨f (x) − mj , ũj ⟩ =

∆j , 2

Var [Wj ] = Var [⟨V − mj , ũj ⟩] = σ 2 . We can then define the standardised version of Wj , Nj :=

Wj − ∆j /2 . σ

δ ) in terms of the Lebesgue measure, Combining the above, we can reexpress Px (Sx,x j   εσ 2 δ q Px (Sx,xj ) = Px v ∈ R |⟨v − mj , ũj ⟩| > ∆j   εσ 2 =λ u ∈ [0, 1] |⟨V (u) − mj , ũj ⟩| > ∆j   εσ 2 =λ |⟨V − mj , ũj ⟩| > ∆j   εσ 2 ∆j + σNj > . =λ 2 ∆j

Using this representation, consider now the summand in (27),       i−1   i−1 c 2 2 \ \ εσ  ∆j δ δ  =λ  ∆i + σNi > εσ Px Sx,x ∩ Sx,x + σNj ≤ ∩ i j 2 ∆ 2 ∆j i j=1 j=1     i−1   2 2 2 \ εσ εσ ∆ εσ ∆ i j  =λ  + σNi < − + σNj ≤ ∩ − ≤ 2 ∆i ∆ 2 ∆j j j=1     i−1   2 2 2 \ εσ εσ ∆ ∆ εσ i j  + λ + σNi > + σNj ≤ ∩ ≤ − 2 ∆i ∆ 2 ∆j j j=1    i−1    \ εσ εσ ∆ ∆ ∆ εσ i j j  ∩ − ≤ Nj ≤ =λ  Ni < − − − − ∆i 2σ ∆ 2σ ∆ 2σ j j j=1     i−1  \  εσ εσ εσ ∆ ∆ ∆ i j j . + λ  Ni > ∩ − ≤ Nj ≤ − − − ∆i 2σ ∆ 2σ ∆ 2σ j j j=1 For j = 1, 2, . . . , p, define (1)

tj

:= −

εσ ∆j − , ∆j 2σ

(2)

tj

:=

εσ ∆j − . ∆j 2σ

We then obtain the simplified expression     i−1 c n o i−1 n o \ \ (1) (2) δ δ  = λ  Ni < t(1) Sx,x ∩ tj ≤ Nj ≤ tj  Px Sx,x ∩ i i

j

j=1

j=1

  n o i−1 n o \ (2) (1) (2) + λ  Ni > ti ∩ tj ≤ Nj ≤ tj  .

(28)

j=1

Each of the two summands in (28) is a probability under the joint distribution of (N1 , N2 , . . . , Ni ), which is a zero-mean multivariate normal distribution. Evaluating these probabilities therefore reduces to determining the corresponding covariance matrix. For i, j = 1, 2, . . . , p, define ρi,j := Cov [Ni , Nj ] =

1 1 † Cov [Wi , Wj ] = 2 Cov [⟨V, ũi ⟩, ⟨V, ũj ⟩] = ⟨ũi , ũj ⟩. σ2 σ 15

(1)

⊤ where † follows from ⟨V, ũi ⟩ = ũ⊤ denote the i × i covariance matrix of i V and ⟨V, ũj ⟩ = ũj V . Let Σi (N1 , . . . , Ni ), i.e.,   1 ρ1,2 · · · ρ1,i ρ2,1 1 · · · ρ2,i    (1) Σi :=  . . ..  . .. ..  .. . . 

ρi,1

ρi,2

···

1

Now the first term on the right hand side in (28) can be rewritten:   n o i−1 n o h i h i h i  \ (1) (1) (2) (1) (2) (1) (2) (1) (2) (1) (1) λ  Ni < ti ∩ tj ≤ Nj ≤ tj  = Φ t1 , t1 , t2 , t2 , . . . , ti−1 , ti−1 , ti ; Σi , j=1 (1)

where Φ(·, . . . , ·; Σi ) denotes the cumulative distribution function of the zero-mean multivariate normal (1) distribution with covariance matrix Σi . For the second term of the right hand side in (28), we exploit that n o n o (2) (2) λ Ni > ti = λ Ni < −ti , and obtain a similar expression:   n o i−1 o \ n (1) (2) (2) λ  Ni > ti ∩ tj ≤ Nj ≤ tj  j=1

h i h i h i  (1) (2) (1) (2) (1) (2) (2) (2) = Φ t1 , t1 , t2 , t2 , . . . , ti−1 , ti−1 , −ti ; Σi , where 

1

 ρ2,1  ..  . ρi−1,1 −ρi,1

 (2) Σi := 

ρ1,2 1 .. .

··· ··· .. .

ρ1,i−1 ρ2,i−1 .. .

ρi−1,2 −ρi,2

··· ···

1 −ρi,i−1

 −ρ1,i −ρ2,i   ..  . .   −ρi−1,i  1

Substituting these expressions into (28) yields   i−1 2 h i h i h i  c \ X (1) (2) (1) (2) (1) (2) (j) δ δ j−1 (j)  Px Sx,x ∩ S = Φ t , t , t , t , . . . , t , t , (−1) t ; Σ . x,xj 1 1 2 2 i−1 i−1 i i i j=1

j=1

Combining this with (27), we obtain the following exact expression for the probability that the Gaussian mechanism produces an output in the Sxδ : Px (Sxδ ) =

p X 2 X

Φ

h

(1)

(2)

t1 , t1

i h i  i h (1) (2) (1) (2) (j) (j) . , t2 , t2 , . . . , ti−1 , ti−1 , (−1)j−1 ti ; Σi

(29)

i=1 j=1

Again, since Sxδ is a conservative failure region, this expression provides only an upper limit to the failure probability of the posterior-to-prior ratio bounds (24) and (25).

6

The Empirical Failure Rate

Although Px (Sxδ ) provides a conservative upper limit on the probability that R violates the bounds in (24) and (25), the tightness of this limit is not immediately clear. For the Gaussian mechanism, (29) gives an exact expression for Px (Sxδ ), which we compare with the empirical failure probability obtained via Monte Carlo simulation. This comparison allows us to assess how conservative the limit is in practice. We focus on the failure probability under probabilistic differential privacy, as the corresponding analysis 16

under approximate differential privacy differs only in the choice of (ε, δ)-parameters by the results in Section 3. To carry out this comparison, we first calibrate the Gaussian mechanism to satisfy a prescribed (ε, δ)probabilistic differential privacy guarantee. This requires selecting the noise parameter σ such that the probability mass of the bad region is approximately δ. Recall from (15) that for any x, x′ ∈ X with d(x, x′ ) = 1,     εσ ∆ εσ ∆ δ ) = Φ − + + Φ − − . Px (Sx,x ′ ∆ 2σ ∆ 2σ Hence, to obtain exactly (ε, δ)-probabilistic differential privacy, we choose σ > 0 by minimising     εσ ∆ εσ ∆ L(σ) := Φ − + +Φ − − −δ . ∆ 2σ ∆ 2σ

(30)

This calibration is similar to the approach of Balle and Wang (2018), except that their minimisation yields the optimal noise parameter for approximate differential privacy. Simulation setup To assess the tightness of the theoretical bound, we consider the following two-level simulation setup. In the outer loop, we simulate N1 datasets of size m from a population P = {1, 2, . . . , n} of size n > m. For each sampled dataset, we calculate the theoretical upper bound Px (Sxδ ). In the inner loop, we independently apply the Gaussian mechanism with probabilistic differential privacy N2 times to each dataset, taking f (x) to be the vector of attribute values of the individuals in x. This generates a total of N1 N2 noisy datasets. For each realisation, we calculate the posterior-to-prior ratio and record whether it violates the bounds in (24). The empirical failure probability, denoted F , is then estimated as the proportion of the N1 N2 posterior-to-prior ratios outside these bounds. Since the theoretical upper limit depends on the specific dataset realisation, we compare its mean across the N1 datasets, denoted T , with F. For each dataset x = {x1 , . . . , xm } sampled in the outer loop from the population P , we treat x− = x \ {xm } as auxiliary information available to the adversary. The adversary therefore knows all but one member of the dataset and seeks to infer the identity of the remaining individual from among the individuals in P not contained in x− . Accordingly, the candidate set is C = P \ x− , and the true remaining individual is xm ∈ C. After observing the noisy output of the Gaussian mechanism, the adversary updates the prior inclusion probability of xm . The resulting posterior-to-prior ratio is used to determine whether the bounds in (24) are violated. The following procedure outlines the simulation framework used to compute T and F .

17

Procedure: Monte Carlo estimation of failure probability 1: Input: Privacy parameters: ε > 0, δ ∈]0, 1]; simulation parameters n, m, N1 , N2 ∈ N 2: Set population P ← {1, 2, . . . , n} 3: Compute σ ← arg minσ̃>0 L(σ̃) 4: Initialise N1 × N2 matrix F 5: Initialise size N1 vector T 6: 7: for j = 1, 2, . . . , N1 do 8: 9: 10: 11: 12: 13:

(j)

Sample attributes ϕi ∼ Unif[0, 1] independently for all i ∈ P Sample dataset x ⊂ P uniformly without replacement with |x| = m Enumerate the elements of x as x = {x1 , . . . , xm } Define the set of auxiliary information x− = x \ {xm } Compute Tj ← Px (Sxδ ) using (29)

for k = 1, 2, . . . , N2 do (j) Generate noisy dataset t, where tℓ ← ϕxℓ + N (0, σ 2 ) for ℓ = 1, . . . , m 16: Compute R(t) according to (32) for Ii , where i = xm , and A = {ω ∈ Ω | x− ⊂ X(ω)} 17: if R(t) satisfies (24) then 18: Fj,k ← 0 19: else 20: Fj,k ← 1 21: end if 22: end for 23: end for

14: 15:

24: 25: return T := N1

1

PN1

j=1 Tj ;

F := N11N2

PN1 PN2 j=1

k=1 Fj,k

The posterior-to-prior ratio in Line 16 of the simulation procedure is obtained by first deriving the posterior probability in (20). Applying Bayes’ rule yields PX|M (Ii | t, A) ∝ PM |X (t | Ii ∩ A)P(Ii ∩ A) ∝ PM |X (t | Ii ∩ A)P(Ii | A) ∝ PM |X (t | Ii ∩ A). The last proportionality follows from the fact that the prior inclusion probability P(Ii | A) is uniform over the set of candidates C. In particular, P(Ii | A) = 1/|C|. Since the Gaussian mechanism at Line 15 adds independent N (0, σ 2 ) noise to each attribute, the conditional density of t given a candidate i ∈ C is !!  2 m−1 2 X 1 (j) PM |X (t | Ii ∩ A) ∝ exp − 2 tm − ϕ i tℓ − ϕ(j) + =: γ(i). (31) xℓ 2σ ℓ=1

Since γ(i) is proportional to the posterior probability PX|M (Ii | t, A) for all i ∈ C, normalising over C gives γ(i) . PX|M (Ii | t, A) = P q∈C γ(q) Finally, dividing by the prior, we get the posterior-to-prior ratio R(t) =

PX|M (Ii | t, A) γ(i) =P |C|. P(Ii | A) q∈C γ(q)

(32)

Properties of the Monte Carlo estimators Before presenting the simulation results, we investigate the theoretical properties of the Monte Carlo estimator. Let Zj denote all randomness generated in the jth iteration of the outer loop, including 18

the attribute vector ϕ(j) and the sampled dataset x(j) . We assume that Z1 , . . . , ZN1 are i.i.d. For j = 1, . . . , N1 and k = 1, . . . , N2 , let Fj,k indicate whether the posterior-to-prior ratio obtained in the kth inner-loop iteration violates the bounds in (24). Conditional on Zj , we assume that Fj,1 , . . . , Fj,N2 are independent and satisfy Fj,k | Zj ∼ Bernoulli(ρ(Zj )) , where ρ(Zj ) denotes the conditional failure probability associated with the jth outer-loop realisation. The corresponding unconditional failure probability is ρ := E[ρ(Zj )] . Define N

F j :=

2 1 X Fj,k N2

N

and

F :=

k=1

1 1 X F j. N1 j=1

By the law of total expectation,   E[F j ] = E E[F j | Zj ] " # N2 1 X =E E[Fj,k | Zj ] N2 k=1

= E[ρ(Zj )] = ρ. Consequently, N

E[F ] =

1 1 X E[F j ] = ρ. N1 j=1

Hence, both F j and F are unbiased estimators of ρ. For a fixed outer-loop realisation, however, the conditional law of large numbers gives N

Fj =

2 1 X Fj,k → ρ(Zj ) N2

a.s. as N2 → ∞.

k=1

Thus, increasing N2 makes F j consistent for the realisation-specific failure probability ρ(Zj ), but not for the unconditional failure probability ρ, since Var[ρ(Zj )] > 0. By contrast, averaging over independent outer-loop realisations yields a consistent estimator of ρ. Since F 1 , . . . , F N1 are i.i.d.,   N1 X 1 Var[F ] = Var  F j N1 j=1 =

Var[F j ] →0 N1

as N1 → ∞.

Together with the unbiasedness of F , this implies that F converges to ρ in probability. Therefore, F is a consistent estimator of the unconditional failure probability as N1 → ∞. Results Source code and plots are available at https://github.com/janreiter793/ratio bounds failure rate. We investigate the behaviour of the Monte Carlo estimators through parameter sweeps over ε, m, and δ, while fixing n = 100, N1 = 1, 000, and N2 = 1, 000, 000. We have limited the analysis to a population 19

size of n = 100 due to high computational demands for larger n; however, the points of the analysis should still apply to n > 100. The ranges are given in the following table Variable ε m δ

Range [0.2, 2.0] {10, . . . , 99} [10−1.1 , 1]

The resulting estimates are displayed in Figure 1, Figure 2, and Figure 3.

Value

10-2

10-3 F T

10-4

0.2

0.4

0.6

0.8

1.0

1.2

1.4

1.6

1.8

2.0

ε

Figure 1: Empirical estimates and standard deviations of the failure probability F (blue) and the corresponding mean theoretical upper limit T (red) for 40 equidistant values of ε in the interval [0.2, 2.0]. Results are shown for n = 100, m = 90, and δ = 10−1.1 . Estimates are based on N1 = 1, 000 attribute samples and N2 = 1, 000, 000 simulations per attribute sample. As shown in Figure 1, the average theoretical upper limit T consistently exceeds the empirical failure probability F by approximately two orders of magnitude throughout the interval ε ∈ [0.2, 2.0]. While F decreases noticeably as ε increases, T remains visibly constant around 1.5 × 10−2 . The standard deviations of F and T are within the ranges of [5.82 · 10−12 , 1.51 · 10−11 ] and [5.16 · 10−4 , 6.22 · 10−4 ], respectively, and are therefore negligible on the scale of Figure 1. Averaged over the chosen values of ε, the mean difference between T and F is 1.48 × 10−2 , while the mean value of T is 1.49 × 10−2 . This suggests that the theoretical upper bound is highly conservative in practice, with the empirical failure probability contributing only a small fraction of the bound across the entire range of ε considered. Although T is not visibly decreasing in Figure 1, a linear regression of T on ε yields a negative slope of −1.83 · 10−3 (p-value = 5.22 · 10−10 ). Hence, both F and T exhibit a decreasing trend over the considered values of ε. The decrease in F indicates that the posterior-to-prior ratio R satisfies the bounds (24) more often as the privacy budget increases. This is consistent with the widening of the admissible interval as ε increases. Indeed, considering (24), we see that the bounds expand with ε:     1 1 1 → 0, , , P(Ii | A) + (1 − P(Ii | A))eε P(Ii | A) + (1 − P(Ii | A))e−ε P(Ii | A) as ε → ∞. Importantly, the limiting interval remains finite. At the same time, increasing ε weakens the privacy guarantee and results in less perturbed data. Consequently, the posterior distribution may deviate more substantially from the prior distribution, potentially increasing the variability of the ratio R. The asymptotic behaviour of F thus depends on the interaction between the widening of the admissible interval and the changing distribution of R. Although the simulations cover only a finite range of ε and 20

therefore do not determine this asymptotic behaviour, we conjecture that F may converge to a strictly positive limit or eventually exhibit qualitatively different behaviour if the increasing variability of R outweighs the widening of the admissible interval. Figure 2 shows T and F for observed dataset sizes from m = 10 to m = 99. We limit the range to m = 99, since m = n would result in the candidate set C containing only xm . Consequently, P(Ii | A) = 1 for i ∈ C and, likewise, PX|M (Ii | t, A) = 1, resulting in R(t) = 1. Since R(t) = 1 always satisfies (24), the empirical failure probability would be zero. There are two key observations from Figure 2. First, for most values of m there is a substantial gap between F and T . As m increases towards 99, T tends to decrease while F tends to increase, with the two quantities coinciding at m = 99. The downward trend of T is explained by the decreasing number of neighbours of x. Specifically, since [ δ Sx,x Sxδ = ′, x′ ∈X(Iic ∩A) δ the set Sxδ is formed from a union of fewer and fewer sets Sx,x ′ as m approaches n − 1. As a result, the δ δ size of Sx decreases, causing Px (Sx ) to decrease, which is reflected in the downward trend of T . The second observation concerns the shape of this downward trend. In particular, T steadily decreases until approximately m = 70, after which the decline becomes markedly steeper, resulting in the hockey-stick shape of the curve. As m increases, the number of neighbours to the observed dataset x decreases, reducing the number of bad regions contributing to Sxδ . The non-linear shape of T further suggests that δ the regions Sx,x ′ are overlapping or differing in size. Although these observations are based on n = 100, we hypothesise that the trends hold for any population size n. Further, the standard deviations for T and F in Figure 2 are within [2.96 · 10−4 , 7.44 · 10−4 ] and [6.03 · 10−12 , 5.64 · 10−11 ], respectively, and are therefore negligible in the scale of the figure.

10-1

Value

10-2

10-3

F T

10-4

10-5 10

20

30

40

50

60

70

80

90

100

m

Figure 2: Empirical estimates and standard deviations of the failure probability F (blue) and the corresponding mean theoretical upper limit T (red) for 40 equally distributed integer values of m from m = 10 to m = 99. Results are shown for n = 100, ε = 1, and δ = 10−1.1 . Estimates are based on N1 = 1, 000 attribute samples and N2 = 1, 000, 000 simulations per attribute sample. Figure 3 shows T and F across 40 equidistant δ ∈ [10−1.1 , 1]. The estimates remain separated throughout the interval, with T > F for all considered values of δ, and both approach 1 as δ tends to 1. The monotonic increase in F is due to the role of δ in determining the size of the bad regions. Recall that the Gaussian δ noise level is calibrated by minimising (30), thereby enforcing Px (Sx,x ′ ) ≈ δ. Consequently, larger values of δ correspond to larger bad regions, which in turn increase both Px (Sxδ ) and the mean theoretical upper limit T . While T increases steadily across the entire range, most of the increase in F occurs in the interval δ ∈ [0.95, 1]. Specifically, F grows from 18% to 100% over δ ∈ [0.95, 1], compared with an increase from 21

0.007% to 18% over δ ∈ [10−1.1 , 0.95]. In practice, δ is typically chosen considerably smaller than 10−1.1 (Dwork et al., 2006a). Consequently, practical applications of posterior-to-prior ratio bounds are unlikely to operate in the regime of the rapid failure probability increase observed for δ close to one. We have not obtained estimates for δ < 10−1.1 , as the computational requirements of the corresponding rare-event simulations would be prohibitive. The standard deviations of T and F are within [1.11·10−19 , 4.33·10−3 ] and [8.44 · 10−12 , 4.25 · 10−10 ], respectively, and are therefore negligible on the scale of Figure 3. 100

10-1

Value

10-2 F T

-3

10

10-4

10-5 0.0

0.1

0.2

0.3

0.4

0.5

0.6

0.7

0.8

0.9

1.0

δ

Figure 3: Empirical estimates and standard deviations of the failure probability F (blue) and the corresponding mean theoretical upper limits T (red) for 40 equidistant values of δ in the interval [10−1.1 , 1]. Results are shown for n = 100, m = 90, and ε = 1. Estimates are based on N1 = 1, 000 attribute samples and N2 = 1, 000, 000 simulations per attribute sample. In summary, Monte Carlo simulations across a range of values of ε, m, and δ indicate that the theoretical upper limit Px (Sxδ ) is highly conservative compared to the true failure probability. In realistic settings, the privacy budget ε is likely to be moderate, the population size n substantially larger than the sample size m, and δ negligibly small. Consquently, the true failure probability may be several orders of magnitude below its theoretical upper limit. The principal implication is that if privacy parameters can be chosen such the posterior-to-prior ratio is sufficiently constrained by (24), then Px (Sxδ ) provides a useful conservative limit on the probability that the privacy guarantee is violated.

7

Conclusion

In this paper, we considered data universes, data-release mechanisms, approximate differential privacy, and probabilistic differential privacy within a common measure-theoretic framework. With this unified formulation, we rederived the well-known result that probabilistic differential privacy implies approximate differential privacy, as well as the converse implication with modified (ε, δ)-parameters. Using the implication from approximate differential privacy to probabilistic differential privacy, we derived upper and lower bounds for posterior-to-prior ratios of inclusion beliefs for data-release mechanisms satisfying bounded probabilistic or approximate differential privacy. These bounds quantify the extent to which observing a mechanism output can alter prior beliefs about inclusion events. Since the bounds are only guaranteed when the mechanism output falls outside certain regions of the output space, we further studied the probability that an output lies within such regions. Using a geometric approach, we derived an exact expression for this probability for the Gaussian mechanism. However, as violations of the bounds are not guaranteed within these regions, this probability constitutes an upper limit on the failure probability. To investigate the potential gap between the failure probability and its theoretical upper limit, we conducted a Monte Carlo study. The simulation results indicate that the theoretical upper limit is conservative, lying substantially above the estimated failure probability throughout the

22

parameter sweeps considered in the study. These findings aid in the assessment of privacy risks associated with the release of differentially private data. The posterior-to-prior ratio bounds can help a data holder select privacy parameters that are consistent with a predetermined acceptable level of privacy risk. For the Gaussian mechanism, the theoretical upper limit on the failure probability can be calculated using the formula derived in this paper. Since this upper limit appears to be considerably larger than the actual failure probability, calibrating the mechanism to keep the limit below an acceptable level provides a conservative privacy guarantee. Although our framework provides rigorous results, several limitations remain. First, our derivations of the posterior-to-prior ratio bounds and the theoretical upper limit on the failure probability rely on the assumption that the underlying population is finite and known. Extending these results to settings with unknown, infinite, or uncountable populations would therefore be a valuable direction for future research. Second, while we only consider the posterior-to-prior ratios for inclusion events, adverse inferences encompass a broader range of inference types, including attribute inference and data reconstruction attacks. Extending the bounds to a wider class of inference problems would be an important direction for future research. Finally, the true failure probability of the posterior-to-prior ratio bounds may depend strongly on the specific data-release mechanism. While the theoretical upper limit was analytically tractable for the Gaussian mechanism, analogous derivations may be intractable for more general mechanisms. Investigating practical methods for estimating failure probabilities under arbitrary data-release mechanisms is therefore a highly relevant avenue for future work.

References James Bailie and Ruobin Gong. General inferential limits under differential and Pufferfish privacy. International Journal of Approximate Reasoning, 172, 2024. Borja Balle and Yu-Xiang Wang. Improving the Gaussian mechanism for differential privacy: Analytical calibration and optimal denoising. In International Conference on Machine Learning, pages 394–403. PMLR, 2018. Clément L Canonne, Gautam Kamath, and Thomas Steinke. The discrete Gaussian for differential privacy. In Advances in Neural Information Processing Systems, volume 33, pages 15676–15688, 2020. Miranda Christ, Sarah Radway, and Steven M Bellovin. Differential privacy and swapping: Examining de-identification’s impact on minority representation and privacy preservation in the U.S. census. In 2022 IEEE Symposium on Security and Privacy (SP), pages 457–472. IEEE, 2022. Cynthia Dwork and Aaron Roth. The algorithmic foundations of differential privacy. Foundations and Trends® in Theoretical Computer Science, 9(3–4):211–407, 2014. Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. Our data, ourselves: Privacy via distributed noise generation. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 486–503. Springer, 2006a. Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Theory of Cryptography Conference, pages 265–284. Springer, 2006b. Cynthia Dwork, Nitin Kohli, and Deirdre Mulligan. Differential privacy in practice: Expose your epsilons! Journal of Privacy and Confidentiality, 9(2), 2019. Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized aggregatable privacypreserving ordinal response. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pages 1054–1067, 2014. Patricia Guerra-Balboa, Annika Sauer, Héber H Arcolezi, and Thorsten Strufe. Understanding disclosure risk in differential privacy with applications to noise calibration and auditing (extended version). arXiv preprint arXiv:2603.12142, 2026. Jamie Hayes, Borja Balle, and Saeed Mahloujifar. Bounding training data reconstruction in DP-SGD. In Advances in Neural Information Processing Systems, volume 36, pages 78696–78722, 2023.

23

V Joseph Hotz, Christopher R Bollinger, Tatiana Komarova, Charles F Manski, Robert A Moffitt, Denis Nekipelov, Aaron Sojourner, and Bruce D Spencer. The key role of absolute risk in the disclosure risk assessment of public data releases. Proceedings of the National Academy of Sciences, 121(11): e2321882121, 2024. Ron S Jarmin, John M Abowd, Robert Ashmead, Ryan Cumings-Menon, Nathan Goldschlag, Michael B Hawes, Sallie Ann Keller, Daniel Kifer, Philip Leclerc, Jerome P Reiter, et al. An in-depth examination of requirements for disclosure risk assessment. Proceedings of the National Academy of Sciences, 120 (43):e2220558120, 2023. Tianxi Ji and Pan Li. Less is more: Revisiting the Gaussian mechanism for differential privacy. In 33rd USENIX Security Symposium (USENIX Security 24), pages 937–954, 2024. Zeki Kazan and Jerome P Reiter. Prior-itizing privacy: A Bayesian approach to setting the privacy budget in differential privacy. In Advances in Neural Information Processing Systems, volume 37, pages 90384–90430, 2024. Zekican Kazan. Bayesian Strategies for Differential Privacy and Risk Assessment. PhD thesis, Duke University, 2025. Ashwin Machanavajjhala, Daniel Kifer, John Abowd, Johannes Gehrke, and Lars Vilhuber. Privacy: Theory meets practice on the map. In 2008 IEEE 24th International Conference on Data Engineering, pages 277–286. IEEE, 2008. David McClure and Jerome P Reiter. Differential privacy and statistical disclosure risk measures: An investigation with binary synthetic data. Transactions on Data Privacy, 5(3):535–552, 2012. Ryan McKenna, Yangsibo Huang, Amer Sinha, Borja Balle, Zachary Charles, Christopher A ChoquetteChoo, Badih Ghazi, George Kaissis, Ravi Kumar, Ruibo Liu, et al. Scaling laws for differentially private language models. arXiv preprint arXiv:2501.18914, 2025. Sebastian Meiser. Approximate and probabilistic differential privacy definitions. Cryptology ePrint Archive, 2018. URL https://eprint.iacr.org/2018/277.pdf. Lisa Pilgram, Fida Kamal Dankar, Jörg Drechsler, Mark Elliot, Josep Domingo-Ferrer, Paul Francis, Murat Kantarcioglu, Linglong Kong, Bradley Malin, Krishnamurty Muralidhar, et al. A consensus privacy metrics framework for synthetic data. Patterns, 6(10), 2025. Isabel Wagner and David Eckhoff. Technical privacy metrics: a systematic survey. ACM Computing Surveys (Csur), 51(3):1–38, 2018. Jun Zhao, Teng Wang, Tao Bai, Kwok-Yan Lam, Xuebin Ren, Xinyu Yang, Shuyu Shi, Yang Liu, and Han Yu. Reviewing and improving the Gaussian mechanism for differential privacy. arXiv preprint arXiv:1911.12060, 2019.

24

Related documents

• Bounds on the Posterior-to-Prior Ratios for Inclusion Belief under Bounded Differential Privacy#799674
• Privacy Amplification Without Independence: How Far Negative Dependence Carries the Guarantees of Poisson Subsampling#632789
• A Privacy Study of Sparse Collaborative Inference#620642
• A Privacy Study of Sparse Collaborative Inference#618963
• A MODEL REGIME OF PRIVACY PROTECTION#465593