Unifying Re-Identification, Attribute Inference, and Data Reconstruction Risks in Differential Privacy
Authors: Bogdan Kulynych
Juan Felipe Gomez
Georgios Kaissis
Jamie Hayes
Borja Balle
Flavio Calmon
Jean Louis Raisaro
Venue: NeurIPS 2025 poster ()
Keywords: differential privacy
privacy risk
re-identification
singling out
attribute inference
data reconstruction
machine learning
Primary area: social_and_economic_aspects_of_machine_learning
TL;DR: Easy-to-interpret, unified, tunable bounds on major operational attack risks in privacy-preserving ML and statistical releases that are more accurate than prior methods, using f-DP

Abstract: Differentially private (DP) mechanisms are difficult to interpret and calibrate because existing methods for mapping standard privacy parameters to concrete privacy risks—re-identification, attribute inference, and data reconstruction—are both overly pessimistic and inconsistent. In this work, we use the hypothesis-testing interpretation of DP ($f$-DP), and determine that bounds on attack success can take the same unified form across re-identification, attribute inference, and data reconstruction risks. Our unified bounds are (1) consistent across a multitude of attack settings, and (2) tunable, enabling practitioners to evaluate risk with respect to arbitrary, including worst-case, levels of baseline risk. Empirically, our results are tighter than prior methods using $\varepsilon$-DP, R\'enyi DP, and concentrated DP. As a result, calibrating noise using our bounds can reduce the required noise by 20% at the same risk level, which yields, e.g., an accuracy increase from 52% to 70% in a text classification task. Overall, this unifying perspective provides a principled framework for interpreting and calibrating the degree of protection in DP against specific levels of re-identification, attribute inference, or data reconstruction risk.

Unifying Re-Identification, Attribute Inference, and Data Reconstruction Risks in Differential Privacy
Bogdan Kulynych Lausanne University Hospital
Juan Felipe Gomez Harvard University
Georgios Kaissis Google DeepMind
Jamie Hayes Google DeepMind
Borja Balle
Flavio P. Calmon Harvard University
Google DeepMind
Jean Louis Raisaro Lausanne University Hospital University of Lausanne
Abstract
Differentially private (DP) mechanisms are difficult to interpret and calibrate because existing methods for mapping standard privacy parameters concrete privacy risks-re-identificatin attribute inference, and data reconstruction-arr both overly pessimistic and inconsistent. In this work, use the hypothesis- testing interpretation of DP (f-DP), and determine that bounds on attack success can take the same unified form across re-identification, attribute inference, and data reconstruction risks. Our unified bounds are (1) consistent across a multitude of attack settings, and (2) tunable, enabling practitioners evaluate risk with respect to arbitrary, including worst-case, levels of baseline risk. Empirically, our results are tighter than prior methods using c-DP, Rényi DP, and concentrated DP. As a result, calibrating noise using our bounds can reduce the required noise by 20% at the same risk level, which yields, e.g., an accuracy increase from 52% to 70% text classification task. Overall, this unifying perspective provides a principled framework for interpreting and calibrating the degree of protection DP against specific levels of re-identification, attribute inference, data reconstruction risk.
1 Introduction
Releases of models and statistics derived from personal data-such as de-identified and synthetic data releases, outcomes of statistical analyses, and machine-learuing models can reveal information about individuals in the data. These releases can be classified into record-level (releasing de-identified obfuscated records) and aggregate (releasing statistical properties and models) (Gadotti al., 2024). The disclosure of such information incurs different types privacy risks, which are legislated differently across jurisdictions and regulatory frameworks.
In record-level releases, information leakage can occur via singling out of an individual (Cohen and Nissim, 2020), e.g., determining that there is only one Colombian woman fluent in Mandarin the age of 60 in the dataset. When combined with external information, singling out can result in person's 's re- re-identification Re-identification is harmful when it enables inference of previously unknown personal attributes by an attacker, e.g., disease status or voting record (Sweeney. 2002). Although in aggregate releases there no one-to-one mapping between the released information and individuals, sensitive information can still be inferred via attribute inference or data reconstruction attacks (Fredrikson al., 2015; Yeom al., 2018; Balle et al., 2022), in which the adversary could,
39th Conference on Neural Information Processing Systems (NcurIPS 2025).

---

Attack success Po successtul
re identifiction
after observing mech. output
Attack success
0.75
Baseling Pr
successfull
data reconstruction
prior to observing mech. output
0.5
0.25
Prior bound re-identilicatio (Cohen and Nissim (2020), (t.6)-DP)
Prior bound on reconstruction attribbte interence (Balia et al. (2022), via Rény: DP)
Unilying bound: Success S (Basellne) (ours, via DP)
0.25
03.5
0.75
Baseline
Noise
Better Utility
Tunability
0.30
0.30
0.2
Risk (Succes - -Boeline)
0.23
0.4
0.3
0.20
0.15
0.15
0.00
DU65 0.70
0.75
35
70 0.00 0.25
0.50
0.70
1.00
Noise
accuracy
Baseline
Figure 1: Our results offer unified and more precise way to interpret and calibrate DP mechanisms in terms of re-identification, attribute inference, and data reconstruction risks. Top: The success of all these attacks cannot be higher than the power of the worst-case membership inference attack, which we immediately obtain from the f function in the decision-theorete characterization of privacy mechanisms-f-DDe Bottom left: Our results enable to add A 20% less noise at any given level of risk compared to using prior methods (see Section 4 for details). Bottom middle: Less noise translates into 18pp improved task accuracy (shown: DP-SGD for sentiment classification with GPT-2). Bottom right: The unifying risk measure is tunable-we can either estimate post-release risk for any given level of baseline risk, or measure the worst-case risk (shown: US 2020 Census state-level data).
e.g., inspect the confidence outputs of predictive model to infer one or more unknown attributes of an individual. These notions of risk are interpretable and appear data-protection guidelines such as ISO standards (ISO/IEC 27559:2022), or guidelines from the European Medicines Agency (European Medicines Agency, 2018).
Differential privacy (DP) (Dwork et al., 2014) is standard tool for controlling information leakage in record-level and aggregate data disclosures. The goal of DP mechanisms mask the contribution of each individual in the release via noise injection and randomization. One of the core challenges in applying DP in practice is its interpretation (Franzen et al., 2022; Nanayakkara et al., 2023), as DP parameters do not trivially bound concrete risks such as re-identification, attribute inference, and data reconstruction. In the standard practice, information leakage in DP quantified by two parameters: with values closer to zero meaning better privacy, and 6, which should be kept cryptographically small (Vadhan, 2017).
There are few established guidelines for selecting DP parameters (e, 8), and often contradictory standards are adopted in practice. For example, heuristics such < 10 are common in deep learning (Ponomareva et al., 2023). When translated to concrete privacy risks, such choices can result theory,
10 can yield a more than 99% worst-case attribute inference accuracy.' This poor performance is not due to inherent limitations of DP -nelf--nsttad, it a reflection of the imprecise nature of existing methods that convert between DP guarantees and notions of privacy risk. In fact, empirical evidence shows that even E > 10 still prevents practical reconstruction attacks (Ziller al., 2024; Hayes al., 2024).
in vacuous privacy guarantees:
In this paper, we use the Decision-theorete characterization of DP known as f-DP (Dong et al., 2022) unify and improve existing conversion bounds between DP and different notions of privacy risk. We work under the strong- andengaadvrrrryyy threat model, in which the adversary has access to the entire dataset
Attack accuracy is bounded by
5+ +1
(Kairouz et al., 2015; Humphries et al., 2023; Salem al., 2023).

---

except for one element, and has a certain prior distribution over the remaining element. Inspired by Cohen and Nissim (2020), we characterize the attack success probability of the adversary after observing the output of DP mechanism as a function of the attack's s baseline probability without the DP output. Surprisingly, we find that under the strong threat model, we can simultaneously bound the success probability of re-identification, attribute inference, and reconstruction attacks at once, using the same expression. Importantly, we find that not only this is a convenient way to analyze multiple kinds of risk at once, but also it provides a significantly tighter bound than prior methods, due to our usage of f-D.. See Fig. for an illustration of these properties, with more details in Section 4.
As concrete example, consider the release of all state-level US 2020 Census data, which satisfies DP with E 10.6 at å 10- 10 A standard risk analysis (Salem et al., 2023) indicates that the maximum difference between success and baseline probabilities of an attribute inference attack is > 99 percentage points (pp), a more involved numeric analysis (Balle et al., 2022) based on the notion of Rényi DP (Mironov, 2017) yields 73pp, whereas our worst-case bound yields 52pp- Moreover, if we assume an adversary with a specific goal and background knowledge, e.g., inferring disease status with in 10,000 prevalence in the population, our bound yields < 0.001pp. This corroborates and generalizes prior observations (Ziller et al., 2024; Hayes et al., 2024) that even e 10 attains meaningful privacy guarantees in certain regimes, to arbitrary f-DP mechanisms.
To summarize, our contributions are:
A unifying framework for analyzing re- re-identification attribute inference, and data recon- struction risks in the strong threat model of DP. This includes new formalization of re-identification risk as a variant of the notion of predicate singling out (Cohen and Nissim, 2020), adapted to the standard threat model of DP.
Demonstration that our bounds offer tighter estimates of risk compared to prior ap- proaches (Cohen and Nissim, 2020; Balle et al., 2022).
Case studies demonstrating that our results provide a more precise and comprehensive interpretation of privacy risk for the US 2020 Census than prior methods, and enable noise reduction in DP mechanisms by approximately 20%. yielding utility improvements in deep learning with DP-SGD of up to 18pp in test accuracy when calibrating noise to a given level of privacy risk (Kulynych et al., 2024).
Novel bounds on generalization and memorization under f-DP as corollaries of our results.
We release the code as part of the Python package:
https: /gi thub. www.etttt......e.eeeeeeeeeee
Overall, our unifying perspective provides a principled and easy-to-use framework for interpreting and calibrating the degree of privacy protection in DP mechanisms against specific levels of privacy risks that are relevant in practice.
2 Background
This section sets up the notation and provides a concise overview of relevant background. We defer a more extensive overview of relevant background to Appendix A.
Suppose that we have sensitive dataset, e.g., patient healthcare records, S 2D, where B is the data record space. We want to run a randomized algorithm M (S), e.g., statistical analysis, or train a machine learning model, and release its output. We also call (-) mechanism. We denote the space of its outputs as θ and a specific output, e.g., model, as 0 E O. We say that two datasets S, S" are neighbouring they belong to a neighborhood relation denoted as S S'. To capture meaningful notion of training data privacy, this relation must correspond to adding, removing, or replacing all of the data that contains information of a single privacy unit, e.g., individual or secret. In the rest of the paper, we follow the standard practice and assume that the privacy unit corresponds to a single record. We consider two standard neighbourhood relations: the hud-remove relation in which either S = S" U {z} or S' = S U {z) for some E D. and the replace-one relation in which both S and S have the same size, but differ by one record.
Differential privacy. An algorithm M 22 + θ satisfies (DP if for any measurable E C θ and S ~ S", we have Pr[M(S) E Fl S ef Pr[M((') E F. + 8 (Dwork et al., 2014). We also make use of the notion of 17-total vatiaai-v (TV) privacy, which is equivalent to satisfying (0, DDP
3

---

Strong-adversang membership inference. DP can be completely characterised via constraint on the success rate of strong membership inference attacks (SMIA), which aim to determine whether a given record was part of the input dataset S based on the output of M Formally, given a sensitive record E D, and a partial dataset S E D= let P = M(5) and Q M($ (z)). SMIA can be seen as a hypothesis test:
Ho : ~ P. and H1 8 1 Q.
(I)
For given decision Φ θ + {0, } to reject the null hypothesis, we can quantify the adversary's success by characterizing its error rates (Wasserman and Zhou, 2010; Kairouz et al., 2015; Dong et al., 2022): Og - Ep (b), Bg _ Eg [o)] where og and 3gg are the false positive rate (FPR) and false negative rate (FNR) respectively. For any desired FPR level a E [0. 1]. the Neyman-Pearson lemma guarantees that there exists an optimal test o² which achieves the lowest possible FNR B. We can thus characterize the SMIA by trade-off curve, a function which shows the lowest FNR achieved by the most powerful test for any level of FPR a: T(P, Q)(a) & inf e- as S aa..
This trade-off curve forms the basis of more general version of DP called f-DP: mechanism M(- satisfies f-DP if for any S = 5" and a E [0. 1] we have that (S), (a)) 2 f(a). This formulation more general than DP: a mechanism M()) is (s, O)PP) iff it satisfies f-DP with:
f(a) max - 8 a e e a-)).
(2)
Notably, f-DP is closed under prst-processing: if (.) satisfies f-DP, then so does g M for any deterministic or randomized mapping 9(-). We make use of a lesser known representation of f-DP:
Lemma 2.1. An algorithm M: : 2D + O satisfies f-DP iff for any measurable C θ and S S':
(S) E EJ < - J(Pr[M(S') E E)).
(3)
This form also appears in Kifer et al. (2022), and we provide self-contained proof in Appendix C. Another property of f-DP that is relevant to our work is that it implies 17- r--TV privacy with = max (1 f(a) - a) (Kaissis et al., 2024). As result, even though TV privacy its own is
weak notion of privacy (Vadhan, 2017), any f-DP algorithm implies TV privacy for some 17 2 O.
3 Bounding Operational Privacy Risks
Next, we introduce formalizations of standard notions of risk in crivacy-preserving statistics and learning: singling out, attribute inference, and data reconstruction. Our main results enable the analysis of these risks under a unifying framework given by f-DP.
3.1 Threat Model
We focus on the risk within the strong threat model (see, e.g., Balle et al., 2022) in which the adversary has access to the workings of the
algorithm M(.), has access to the partial dataset S except for one target record x, and has side information about the remaining record in the form of a prior distribution & ~ P. Note that this threat model is slightly different from the standard threat model of SMIA (see Section 2) in that exactly. To quantify the adversary's 's success rate, we consider expectations over the prior distribution P as well as over the randomness of the algorithm, as we detail next.
do not assume that the adversary knows the target record
Although this might seem like an overly strong model, providing security in this setting is desirable because it represents the worst-case scenario for attacks against privacy of individuals. In particular, as the adversary knows the partial dataset, it captures even the case when the adversary can poison the data (Leemann et al., 2024). By bounding the success of the strong adversary, we also bound the success of attacks against the considered privacy unit under other threat models that are weaker or more realistic for specific application.
In addition, we discuss existing risk notions which assume that the adversary does not have access to the partial dataset, but knows the data distribution S ~ Pa, The success is then evaluated over pR, We call this the average-datasel threat model. We summarize the difference between these threat models in Table I in Appendix H.

---

3.2 Notions of Risk
Singling-out risk. We introduce formalizations of singling out risk based on the notion of predicate singling out (PSO) (Cohen and Nissim, 2020). For the purpose of our work, we use singling-out risk and re-identification risk interchangeably for brevity, although singling out is only necessary condition for re-identification, and other approaches to defining re-identi addentffication (e.g.. also capturing inference) exist (Article 29 Data Protection Working Party, 2014).
Definition 3.1 (PSO security). For a given n. > 1, mechanism M 1D - G, data distribution P over B, weight E [0, 1/m), and adversary A,, O Qp which oulputs predicate that aims to single out one record in the training dataset from the set of admissible predicates 1p _ {p p ID {0, 1), P.Epppp] S w), define the PSO success rate as follows:
Σ Σx(z)=1 = LEES
succrso M, P. A,
Pr
(4)
S pt An Pau (M())
and the baseline success as! baserso [n, P. w) & sup
Σ p(z) -1 -((2)=1 = sup Eplpp -(ppp)))-
Pr pEpr, S Pm
(5)
pEQr
LESS
Observe that PSO security does not assume that the adversary has access to the dataset beyond its distribution S ~ P", thus assumes the average-datase threat model. As we are interested in notion of PSO security where assume that the
the strong-ad arong-adversary model, we introduce adversary has knowledge of the entire dataset except for one element:
Definition 3.2 (SPSO security). For a given n. > 1, k 2 2, mechanism M 20 - θ, partial dataset S E m²-1, data distribution P over a candidate set W S Il with [W] = k, weight E [o, 1], and adversary AM.S,P P,w. ( - P,w which outputs predicate that aims to single out the unknown record in the training dataset from the set of predicates D5,r.a S {p
D +
{0, E*. p(z') O, Eplp] < w/. we define the strong PSO (SPSO) success rate as follows:
succsrso (Mr 5, P. A) A
Pr
[p(=) = 1],
(6)
zPPP
p+- A...B.P..
and the baseline success as: basespso (S, P. P, sup Pr [p(2)= = 1]= PEOs.P.w zmp
sup
Eplp] < w.
(7)
pEOs.P,.
Unlike PSO, in which the adversary aims to single out any record in an unknown dataset, in SPSO, the adversary aims to find predicate that matches only one record from a prior set of candidates. We provide additional background on PSO in Appendix A.2.
Attribute inference and reconstruction attacks. Following Balle et al. (2022), we formalize attribute inference and data reconstruction attacks using the notion of reconstruction robustness: Definition 3.3 (SRR security). For a given n 2 1, mechanism M 2 - θ, data distribution P over D. partial dataset 5 D= loss function Ê D R, threshold y E R. and reconstruction attack AM,S,D θ + D, we define the strong reconstruction robustness (SRR) success rate as follows:
SUCCSRR [M, P:A.,) A
Pr ZNP
[e(2, 2) I s>
(8)
and the baseline success as basesıR (P; 7) supsen Pro-p [0(2, S 7
Robustness against attribute inference attacks can be seen as special case of SRR:
Definition 3.4 (SAI security). For given n > 1, mechanism M 2 + θ, set of attributes A = (I..., k.. mapping from records to attributes a - Pa, data distribution over B, partial
dataset S E D and attribute inference attack A.S,P O P., the strong attribute inference (SAI) success rate is defined as:
succs (M,
Pr a (.A....(M((SU(E)
[a(z)=
a), a
(9)
and the baseline success basesar(P.d) supaea Pre- (a(z) ā].
We review the prior methods to bound these notions of risk under DP in Appendix A.3.
5

---

3.3 Main Results: Unifying Bounds
Our core contribution a unifying relationship between the hypothesis testing interpretation of DP via f-DP and the operational notions of privacy risk in the strong adversary model defined in Section 3.2. We achieve this via a general result that connects the expectation an attack-specific query function q(2, 0) over the randomness of f M (S)(z)) and P to the maximum "baseline" expectation of the same function over only 2 ~ P:
Lemma 3.1. Suppose that M : 20 - θ satisfies f-DP w.r.. either add-remove or replace-one relation. Then, for any bounded function q D + [0, 1], any partial dataset D= with 2 1, and any probability distribution P over D, we have:
Ez-P E la(=;0)) s - (sup EZp Ezup (a(=](((;) 01).
(10)
laee
Intuitively, the function g(=; ()) be seen as indicating the degree of success of some attack against the privacy of the record = given the knowledge of model 0, on a scale from 0 to 1. We provide a proof of this statement, as well of all the following results, in Appendix C. Technically, the core steps of the proof involve the usage of the representation of f-DP in Lemma 2.1, and an application of Jensen's ' inequality push the expectation over z P inside of (a))
We recover the notions of risk in Section 3.2 by taking relevant instantiations of g(2; 8), e.g.. the indicator of successful reconstruction event, q(2; f) 1 S 71, in the case of reconstruction attacks. As a result, we get a unifying bound on attack success:
Theorem 3.1 (Informal). Suppose that (-) satisfies f-DP w.r.f. either add-remove or replace-one relation. For SPSO, SRR, and SAI, it holds that:
succisPso, SRR, SAI I 1 - [base sPSO. SRR. SAB)
(11)
We provide precise statement including the missing arguments for each risk notion in Appendix C.
Normalized success. Multiple prior works have observed that privacy analyses based on attack success alone can be misleading (Guerra-Balbe Balboa et al., 2023; Salem et al., 2023; Cohen et al., 2025). Thus, for all notions of risk, we consider an additional representation of risk in terms of success normalized by the baseline via additive advantage: adv - succ - base, where we drop the arguments for brevity. As a consequence of Theorem 3.1, we obtain:
Theorem 3.2 (Informal). Suppose that (() satisfies f-DP w.r.t. either add-remove or replace-one relation. For SPSO, SRR, and SAI, it holds that:
advispso, sRR. SAI $ f SRR. SAn) base SRR, SAT)
(12)
Theorem 3.2 trivially extends to other ways to normalize attack success, such as succ base (see, e.g., 1-base
1-suce Guo et al., 2023) or base (see, e.g., Chatzikokolakis et al., 2023). In the rest of the paper, we use additive advantage to express risk.
Daseline-independenn guarantees. We can also obtain a bound on advantage that is independent of the baseline by just taking the maximum over all baselines. For this, we use the notion of TV-TV privacy, which any f-DP algorithm satisfies for some 17 (see Section 2).
Theorem 3.3 (Informal). Suppose that the algorithm M()) satisfies 1--V privacy w.r.l. either the add-remove or replace-one relation. Then, the advantage of SPSO, SRR, and SAI is bounded:
adviseso. SRR. SAI
5-
(13)
This result useful as (1) it enables to measure and communicate the worst-case risk across all buselines using single number, and (2) we can use standard software tools for analyzing privacy in common algorithms such as DP-SGD (Abadi et al., 2016) by evaluating the DP guarantee for (e 0,8 = DDP without the need to instantiate the full ff curve. We detail on these properties next.

---

3.4 Discussion of the Theoretical Results
Computing the bounds in practice. Effective usage of our baseline- baseline-specific bounds in Theo- rems 3.1 and 3.2 requires an analysis of a privacy-preservnng algorithm in terms of f-DP. Although different variants of DP imply f-DP, e.g., via Eq. (2) for a single pair of (E, guarantees, such conver- sions are loose (Kulynych et al., 2024). For simple mechanisms such as Gaussian or Laplace (Dwork et al., 2014), exact trade-off curves are known (Dong et al., 2022). For more complex algorithms such as DP-SGD (Abadi et al., 2016), there are two ways for obtaining the corresponding curve.
First, we can estimate it using Eq. (2) from the privacy profile of the algorithm (Balle et al., 2018), i.e., the set of all attainable (s, 6)-P pairs. This method has been used for privacy auditing pre- viously (Nasr et al., 2023). Second, it is possible to analyze DP-SGD or other algorithms that are compositions of (subsampled) Gaussian and Laplace mechanisms using direct method (Kulynych et al., 2024). Both upproaches provide tight analyses when using state-of-ther of-the-art accounting tools as a backbone, such as the Connect-the the- -oeeots accountant (Doroshenko et al., 2022). In particular, prior work (Nasr et al., 2023) has shown that the upper bounds on privacy leakage obtained with the modern accounting techniques can be nearly reached by empirical attacks in the SMIA threat model.
Tunability. Our bound advantage in Theorem 3.2 enables practitioners to tune the baseline risk. In certain data release scenarios, it might be useful to simulate relevant re-identification or attribute inference attacks, estimate their plausible baseline risk, and consider the risk of the release with respect to such a baseline, i.e., adv S 1 (base) - base. As an example, consider releasing outputs of a mechanism trained on tabular medical data which contains a column corresponding to a patient's 's HIV status. In this case, we might want to evaluate the risk of an adversary inferring the HIV status under standard threat models considered when releasing medical data (El Emam, 2010) such as "marketer" or "journalist". For instance, the baseline risk of a "marketer" adversary- who does not target any specific individual could be modeled as guessing based on the prevalence of HIV in the general population. The baseline risk of a "journalist" adversary whho is assumed to be able to obtain side information on the target from public sources- could be modeled as guessing based on target patient's 's demographics. We leave the derivation of application-speccfii procedures and guidelines for modeling baseline risk to future work.
In high-risk scenarios, c.g., public model releases, it might be more desirable to ensure security against the worst-case attacks. In this case, it more appropriate to use the baseline-inde -eneinee-ndeeeedeent bound of adv < maXbare [1 fbass) - base) S 17 from Theorem 3.3.
On tightness of the bounds. Our bounds never vacuous, and are saturated for perfectly private and blatantly non- non-private mechanisms. However, they can be significantly tightened under additional assumptions the adversary's 's threat model. In particular, in Appendix D for an important case of binary altribute inference with a non-uniform prior, and empirically show that it provides tighter bounds in this setting than prior work (Guo al., 2023). Although there exist cases under which the unified bound can be tightened, we conjecture that it is tight in the most general case, i.c., there exist non-trivial settings under which Theorem 3.1 holds with equality. We leave the verification of this conjecture, and the identification of settings under which equality is achieved case it true, to future work.
show example of such strengthening
Beyond privacy. Our results extend to statistical learning theory. Concretely, in Appendix E, we show that our derivations can be extended to new kind of generalization bound. Informally, we show that for the on-average train set error err, and on-average generalization error errist (Shalev-Shwartz al., 2010) of learning algorithm satisfying f-DP, it holds that err I 1 f(err.). Moreover, in Appendix F. we show that our derivations imply a bound on memorization (Feldman, 2019; Zhang et al., 2023). We believe these results are of independent interest.
4 Experimental Evaluation
4.1 Bounds Comparison
Singling-out risk. We compare prior bounds on singling-out risk in the average-dataset threat model from Cohen and Nissim (2020) (detailed Appendix B) to our bound on SPSO in Theorem 3.2, which operates under a different threat model. To provide apples-to-apples comparison, we fix
7

---

500
1000
5000
Rovk (ahrentag)
0.5
0.5
PSO (Coken and Novin, 6. Unitynn (.DP)
04
0.4
0.2
35
60
10 32 50 30
20 43
Figure 2: Our bound on predicate singling out the strong threat model (SPSO) is always non- vacuous, and, surprisingly, shows significantly lower risk than bounds in the PSO threat model. The risk is adv = succ base with fixed given base for Gaussian mechanism with e calculated for 10
5
Raselne
Raseline
Rok (advantag))
4.8
Method
SRR (Balk ei du RDP feed on)]
0.4
Unifrr (sle /-DP)
0.0
10
31 30 10 20
Figure 3: Our bound on reconstruction robustness shows lower risk than prior bounds. We show risk as adv succ base for three different baseline values for Gaussian mechanism with calculated for 10-5
the weight w for both threat models. The baseline probability for PSO base = n w (1 w)--1 whereas is base for SPSO. We use standard Laplace and Gaussian mechanisms (Dwork et al., 2014) with varying noise levels, and simulate different dataset sizes n E (500, 1000, 5000} with a fixed weight 1/5000. We use ō 10-5 derive for the Gaussian mechanism, and analyze DP under replace-one relation.
We show the results for the Gaussian mechanism in Fig. 2 (the results for Laplace mechanism similar, shown in Appendix H). Unlike the PSO bounds, our bounds provide meaningful guarantees even in the 8 [10, 20] regime, and saturate only around & 35. Note that our SPSO bound based on f fDP and the strong adversary threat model shows lower risk than the PSO bound in the average-dataee dataset threat model based on (D-P. In Appendix F, we derive novel PSO guarantee based on f-DP, but we observe no meaningful difference from the (e, 6)- bound in Fig. (see Appendix H). We hypothesize that both phenomena are due the looseness in the derivations of the average-dataset PSO results that are not present in the SPSO derivation. We leave the derivation of tighter PSO bounds future work.
Reconstruction robustness. Next, we compare prior bounds on SRR from Balle et al. (2022) that based Rényi DP (RDP) (Mironov, 2017) and zero-concentrated DP (zCDP) (Dwork and Rothblum, 2016; Bun and Steinke, 2016), detailed in Appendix A.3, to our unifying bounds in Theorem 3.2. We use the Gaussian mechanism, analyzed under the add-one relation. We vary the noise parameter σ, and compute æ at = 10-5 For the SRR bounds, we evaluate separately the bound for a single RDP guarantee e) with Fig. 3 demonstrates that our bound always shows lower risk than prior approaches.
and the bound for the tighter zCDP guarantee.
4.2
Case Studies
We present two case studies which showcase how our results can be used interpret and calibrate realistic DP mechanisms. Additionally, in Appendix G, we discuss another application of our results DP statistical-query answering system (Gaboardi et al., 2020).
Calibrating noise to reconstruction risk in deep learning. It is possible partially reconstruct training-date records from observing outputs or weights of classification models (Balle al., 2022) and language models (Carlini et al., 2022). In this case study, assume the modeler fine-tunes

---

Rikk (atramaage
0.44
0.50
.0.37 -0.37
Method Undkjng (Ax (-00)
0.31
0:25
0.2
County
Group
Group
Level
Figure 4: Our method shows up to 33% lower worst-case reconstruction risk in the US 2020 Census release than the prior method. x axis shows granularity levels of the release, y axis shows risk of attacks succ base for the worst-case baseline.
language model for text sentiment classification the SST-2 dataset (Socher et al., 2013). order to limit the privacy risk to given threshold, e.g., ensure at most 0.15 increase in the probability of successful reconstruction under the worst-case baseline, the modeler runs DP-SGD with attack-aware noise calibration (Kulynych et al., 2024). To simulate this, we fine-tune multiple GPT-2 (small) models (Radford al., 2019) using DP version of LoRA (Yu et al., 2021) (we provide technical details in Appendix G). We obtain the f curve under the add-remove relation for each model using the direct method (Kulynych et al., 2024), and apply Theorem 3.2 measure risk. We compare this to the RDP-based analysis from Balle et al. (2022), where we optimize RDP over grid (see Appendix A.3).
Fig. shows that if we calibrate the noise scale to given level of maximum attack risk, our unifying bound enables one to choose lower noise scale at the same level of risk, which, turn, results in better classification accuracy. Fig. I (left) shows the risk as a function of noise scale, and Fig. (middle) shows the corresponding accuracy when training using that noise scale. The figure demonstrates that for the worst-case risk target of 0. 0.15, we can increase the accuracy from 52% to 70% using our analysis, as opposed an RDP-based one. Notably, the increase accuracy due to a more precise privacy calculation alone, thus does not come with additional costs. In Appendix F, we detail on variant of this case study with CIFAR- 10 (Krizhevsky al., 2009).
Analyzing risk in US Census release. The US Census bureau has released the 2020 Census data using DP (Abowd al., 2022). this case study, we aim analyze this release in terms of operational privacy risks using our bounds, leveraging recent analysis of the Census algorithm in terms of f-DP (Su et al., 2024). The Census data consists of eight different levels of granularity, ranging from the US-wide level to block-level, with different privacy guarantees at each level. The standard analysis uses zCDP, thus we compare Theorem 3.2 the analysis of data reconstruction risk via zCDP, as in our previous experiments in Section 4.1.
In Fig. 4, we present the results for each granularity level under the worst-case baseline, which show that our unifying bound indicates up to 33% less risk. The results for other baselines are similar, shown in Fig. 9, Appendix H. Moreover, in Fig. 1 (right) we show the risk as a function of baseline for the state-level release as an illustration for analyzing risk at different baselines.
5 Related Work
Prior work has extensively studied bounds on attack risks in DP. Balle et al. (2022) introduced a formalization of robustness to reconstruction attacks and provided bounds using (s. D)-P, RDP and zCDP. Compared to these, our bounds are tighter, as we demonstrate in Section 4. Under specialized threat models, these bounds were subsequently improved by Guo et al. (2023), and by Guerra-Bail et al. (2023) for the case of (s, O)-DP. We study the bounds by Guo et al. (2023), which specifically assume discrete prior P. in Appendix D. Cherubin al. (2024) provided closed-fom ffrmd bounds on data reconstruction and membership inference advantage for DP-SGD using an approximate analysis. Our results do not rely approximations and instead the tight privacy analysis in terms of f-DP based on the of SPD accountants, as detailed in Section 3.4.
Hayes et al. (2024) used decision-theoretic view of DP via approximations to provide bound on reconstruction robustness. There are several core differences compared to our results: (1) they provide a Monte-Carlo sampling-be based method rather than provable bound, (2) their method is

---

specific to DP-SGD, and (3) it only covers reconstruction attacks. In contrast, our work focuses on the fundamental connection between different standard types of risks and the f-DP framework, as opposed to providing method to evaluate specific type of privacy risk in DP-SGD. Our approach enables us to obtain provable bounds on risks for general DP mechanisms. Even though the theoretical underpinnings of our approaches are different, the outputs of the algorithm from Hayes et al. (2024) will converge in the limit of infinite Monte-Carlo samples to our f-DP bound in the setting of reconstruction risk in DP-SGD.
In Appendix B, we provide an additional overview of the alternative Bayesian approaches to interpret DP and other approaches to unify privacy risks.
Bibliographic note. This paper subsumes the results from a prior workshop paper (Kaissis et al., 2023a) presented at the 2023 Theory and Practice of Differential Privacy (TPDP) workshop.
6 Concluding Remarks
This paper presents a unifying framework for analyzing re-identification, attribute inference, and data reconstruction risks-realistic privacy threats facing the releases of statistics, models, de- identified data-using f-differential privacy, a decision-theoretic approach to differential privacy. We demonstrated that our unifying framework is applicable to privacy-preservie algorithms such as DP-SGD, and statistical applications such as the US Census data release.
machine-learning
Impact. We have shown that the existing approaches mapping DP parameters to risk are imprecise. As a result, in settings where ensuring a certain maximum level of operational risk is required as opposed to ensuring target value of practitiioness would need to add more noise than is necessary. Not only does this hurt overall utility, but has negative effects on fairness (Bagdasaryan et al., 2019) and prediction consistency (Kulynych al., 2023). Our approach provides more precise way to estimate maximum risk, enabling practitioners to obtain better utility at the same level of target risk.
f-DP for analyzing operational risks. Our empirical and theoretical results demonstrated that the decision-theoreth view of DP via the f-DP framework is a useful tool for analyzing privacy- preserving algorithms in terms of operational risks. As have shown, it enables both substantially tighter characterizations of operational risk compared to other standard approaches such as Rényi DP or Concentrated DP, and easy-to-use unified analyses of various types of risk.
Optimality, Although our bounds outperform prior methods to measure risk in DP, as we show in Appendix D, they can be significantly strengthened under additional assumptions on the adversarial model, e.g., by assuming the setting of binary attribute inference. We leave finding other practically relevant settings in which the bounds can be further tightened-eithee under specific attack configura- tions and priors like in Appendix D or under relaxed threat models (see, e.g., Kaissis et al., 2023b; Swanberg et al., 2025) future work.
Importance of the privacy unit. Our privacy risk bounds have to be interpreted in terms of the underlying privacy unit. For instance, when training language models on open internet data, it is often practically infeasible to define a neighborhood relation that protects the privacy of individuals, as an individual's sensitive data can appear in various forms across multiple documents (Brown et al., 2022). In such settings, a more feasible privacy unit is single document (Sinha et al., 2025). Thus, our bounds in this context would quantify the risk single document rather than an individual.
The need for transparent processes to prevent baseline gaming. Our methods provide way to adjust the level of risk to given adversarial setting by modeling the baseline risk. This is strength as it enables to measure the risk of relevant threats, but also could facilitate privacy theater (Smart et al., 2022) if the communicated or calibrated risk is specific to a baseline that is too low. In this case, the risk estimate could appear lower than it actually is. Trustworthy usage of our baseline-specific bounds requires ensuring that the baseline is well-justified and representative of realistic threats.
10

---

Acknowledgments
The authors would like thank Thanh-Long Tran for spotting the missing A(0) case original version of the proof of Lemma 2.1 in Appendix C. This project is supported by the U.S. Department of Energy, Office of Science, Office Advanced Scientific Computing Research, Department of Energy Computational Scienee Graduate Fellowship under Award Number DE DE-SC0022158, by Swiss National Science Foundation under Award Numbers 10003518 and 237378, and is part of the SYNTHIA project. SYNTHIA (Synthetic Data Generation framework for integrated validation of the Innovative Health Initiative Joint Undertaking (IHI JU) under grant agreement No. 101 1728722 Thus, the project is partially funded by the European Union, the private memhers, and those contrihuting partners of the IHI JU. Views and opinions expressed are however those of the authors only and do not necessarily reflect those of the aforementioned parties. Neither of the aforementioned parties can be held responsible for them.
and Al healthcare applications) is supported by
References
Aloni Cohen and Kobbi Nissim. Towards formalizing the GDPR's notion of singling out. Proceedings of the National Academy of Sciences, 117(15):8344-83) 2020.
Borja Balle, Giovanni Cherubin, and Jamie Hayes. Reconstructing training data with informed adversaries. In 2022 IEEE Symposium on Security and Privacy (SP). IEEE, 2022.
Andrea Gadotti, Luc Rocher, Florimond Houssiau, Ana-Maria Cretu, and Ylex-Alex De Mon- tjoye. Anonymization: The imperfect science of using data while preserving privacy. Science Advances, 10(29):eadn7053, 2024.
Latanya Sweeney. k-anonymity: A model for protecting privacy. International journal of uncertainty, fuzziness and knowledge-based systems, 10(05):557-570, 2002.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the ACM SIGSAC conference on computer and communications security, 2015.
Samuel Yeom, Irene Giacomelli, Matt Fredrikson, and Somesh Jha. Privacy risk in machine learning: Analyzing the connection to overfitting. In Computer Security Foundations Symposium (CSF).
IEEE, 2018.
ISO/EC 27559:2022. Privacy enhancing data de-identification framework, 2022. Available at: http::/wwww..ioooooggstaaaddd///
GT European Medicines Agency. External guidance on the implementation of the european medicines agency policy on the publication of clinical data for medicinal products for human use, 2018.
Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 2014.
Daniel Franzen, Saskia Nuñez von Voigt, Peter Sörries, Florian Tschorsch, and Claudia Müller-Bing Am private and if so, how many? communicating privacy guarantees of differential privacy with risk communication formats. In Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security, 2022.
Priyanka Nanayakkara, Mary Anne Smart, Rachel Cummings, Gabriel Kaptchuk, and Elissa M Redmiles. What are the chances? Explaining the epsilon parameter in differential privacy. In 32nd USENIX Security Symposium (USENIX Security 23), 2023.
Salil Vadhan. The complexity of differential privacy. Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, pages 347-450, 2017.
Natalia Ponomareva, Hussein Hazimeh, Alex Kurakin, Zheng Xu, Carson Denison, H Brendan McMahan, Sergei Vassilvitskii, Steve Chien, and Abhradeep Guha Thakurta. How to DP-fy MI. practical guide to machine learning with differential privacy. Journal of Artificial Intelligence Research, 77: 17:1113-122 2023.

---

Peter Kairouz, Sewoong Oh, and Pramod Viswanath. The composition theorem for differential privacy. In International conference on machine learning. PMLR, 2015.
Thomas Humphries, Simon Oya, Lindsey Tulloch, Matthew Rafuse, Ian Goldberg, Urs Hengartner, and Florian Kerschbaum. Investigating membership inference attacks under data dependencies. In Computer Security Foundations Symposium (CSF), 2023.
Ahmed Salem, Giovanni Cherubin, David Evans, Boris Köpf, Andrew Paverd, Anshuman Suri, Shruti Tople, and Santiago Zanella-Bégee Béguelin. SoK: Let the privacy games begin! A unified treatment of data inference privacy in machine learning. In 2023 IEEE Symposium on Security and Privacy (SP), 2023.
Alexander Ziller, Tamara T Mueller, Simon Stieger, Leonhard Feiner. Johannes Brandt, Rickmer Braren, Daniel Rueckert, and Georgios Kaissis. Reconciling privacy and accuracy in ai for medical imaging. Nature Machine Intelligence, 6(7):764-774, 2024.
Jamie Hayes, Borja Balle, and Saeed Mahloujifar. Bounding training data reconstruction in DP-SGD. Advances in Neural Information Processing Systems (NeurIPS), 2024.
Jinshuo Dong, Aaron Roth, and Weijie Su. Gaussian differential privacy. Journal of the Royal Statistical Society Series Statistical Methodology. 2022.
Ilya Mironov. Rényi differential privacy. In Computer Security Foundations Symposium (CSF). IEEE, 2017.
Bogdan Kulynych, Juan Felipe Gomez, Georgios Kaissis, Flavio du Pin Calmon, and Carmela Troncoso. Attack-aware noise calibration for differential privacy. Advances in Neural Information Processing Systems (NeurIPS), 2024.
Larry Wasserman and Shuheng Zhou, A statistical framework for differential privacy. Journal of the American Statistical Association, 2010.
Daniel Kifer, John M Abowd, Robert Ashmead, Ryan Cumings-Menon, Philip Leclerc, Ashwin Machanavajjhala, William Sexton, and Pavel Zhuravlev. Bayesian and frequentist semantics for common variations of differential privacy: Applications to the 2020 census. arXiv preprint arXiv:2209.0333 03,10, 2022.
Georgios Kaissis, Stefan Kolek, Borja Balle, Jamie Hayes, and Daniel Rueckert. Beyond the calibration point: Mechanism comparison in differential privacy. In International Conference on Machine Learning, pages 22840-22860. PMLR, 2024.
Tobias Leemann, Martin Pawelczyk, and Gjergji Kasneci. Gaussian membership inference privacy. Advances in Neural Information Processing Systems (NeurIPS), 2024.
Article 29 Data Protection Working Party. Opinion 05/2014 on anonymisation techniques. Technical Report WP216, Article 29 Data Protection Working Party, 2014.
Patricia Guerra Barraa,albba,,,, Annika Sauer, and Thorsten Strufe. Analysis and measurement of attack resilience of differential privacy. In Workshop on Privacy in the Electronic Society, 2023.
Edith Cohen, Haim Kaplan, Yishay Mansour, Shay Moran, Kobbi Nissim, Uri Stemmer, and Eliad Tsfadia. Data reconstruction: When you see it and when you don't. In 16th Innovations in Theoretical Computer Science Conference (ITCS 2025). pages 39-1. Schloss Dagstuhl- Leibniz- Zentrum für Informatik, 2025.
Chuan Guo, Alexandre Sablayrolles, and Maziar Sanjabi. Analyzing privacy leakage in machine learning via multiple hypothesis testing: A lesson from fano. In International Conference on Machine Learning. PMLR, 2023.
Konstantinos Chatzikokolakis, Giovanni Cherubin, Catuscia Palamidessi, and Carmela Troncoso. Bayes security: A not so average metric. Computer Security Foundations Symposium (CSF), 2023.
12

---

Martin Abadi, Andy Chu, lan Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. ACM SIGSAC conference on computer and communications security, 2016.
Borja Balle, Gilles Barthe, and Marco Gaboardi. Privacy amplification by subsampling: Tight analyses via couplings and divergences. Advances in Neural Information Processing Systems (NeurIPS), 2018.
Milad Nasr, Jamie Hayes, Thomas Steinke, Borja Balle, Florian Tramèr, Matthew Jagiclski, Nicholas Carlini, and Andreas Terzis. Tight auditing of differentially private machine learning. 32nd USENIX Security Symposium (USENIX Security 23), 2023.
Vadym Doroshenko, Badih Ghazi, Pritish Kamath, Ravi Kumar, and Pasin Manurangsi. Connect the dots: Tighter discrete approximations of privacy loss distributions. Proceedings Privacy Enhancing Technologies, 2022.
Khaled El Emam. Risk-based de de-identificattin of health data. IEEE Security Privacy, 2010.
Shai Shalev-Shwartz, Ohad Shamir, Nathan Srebro, and Karthik Sridharan. Learnability, stability and uniform convergence. The Journal of Machine Learning Research, 11:2635-2670, 2010.
Vitaly Feldman. Does learning require memorization? a short tale about a long tail. corr abs/1906.0 05271 (2019). arXiv preprint arXiv: 05271, 2019.
Chiyuan Zhang, Daphne Ippolito, Katherine Lee, Matthew Jagielski, Florian Tramèr, and Nicholas Carlini. Counterfactual memorization in neural language models. Advances in Neural Information Processing Systems (NeurIPS), 2023.
Cynthia Dwork and Guy N Rothblum.
Concentrated differential privacy. arXiv preprint
1r3.v:1603.01887, 2016.
Mark Bun and Thomas Steinke. Concentrated differential privacy: Simplifications, extensions, and lower bounds. In Theory of cryptography conference, 2016.
Marco Gaboardi, Michael Hay, and Salil Vadhan. A programming framework for opendp. Manuscript, May, 2020.
Nicholas Carlini, Daphne Ippolito, Matthew Jagielski, Katherine Lee, Florian Tramer, and Chiyuan Zhang. Quantifying memorization across neural language models. arXiv preprint 1.Xiv:2202.076466 2022.
Richard Socher, Alex Perelygin, Jean Wu, Jason Chuang, Christopher D. Manning, Andrew Ng, and Christopher Potts. Recursive deep models for semantic compositionality over a sentiment treebank. In Proceedings of the 2013 Conference on Empirical Methods in Natural Language Processing, 2013.
Alec Radford, Jeffrey Wu, Rewon Child, David Luan, Dario Amodei, Ilya Sutskever, et al. Language models are unsupervised multitask learners. OpenAl blog, 2019.
Da Yu, Saurabh Naik, Arturs Backurs, Sivakanth Gopi, Huseyin A Inan, Gautam Kamath, Janardhan Kulkarni, Yin Tat Lee, Andre Manoel, Lukas Wutschitz, et al. Differentially private fine-tuning of language models. In International Conference on Learning Representations, 2021.
Alex Krizhevsky, Geoffrey Hinton, et al. Learning multiple layers of features from tiny images. Technical report, 2009.
John M Abowd, Robert Ashmead, Ryan Cumings- Simson Garfinkel, Micah Heineck, Chris- tine Heiss, Robert Johns, Daniel Kifer, Philip Leclere, Ashwin Machanavajjhala, et al. The 2020 census disclosure avoidance system topdown algorithm. Harvard Data Science Review, 2, 2022.
Buxin Su, Weijie Su, and Chendi Wang. The 2020 United States Decennial Census more private than you (might) think. arXiv preprint arXiv:2410.09296 2024.
13

---

Giovanni Cherubin, Boris Köpf, Andrew Paverd, Shruti Tople. Lukas Wutschitz, and Santiago Zanella-Bégus Closed-form bounds for DP-SGD against record-level inference attacks. In 33rd USENIX Security Symposium (USENIX Security 24), pages 4819-4836, 2024.
Georgios Kaissis, Jamie Hayes, Alexander Ziller, and Daniel Rueckert. Bounding data recon- struction attacks with the hypothesis testing interpretation of differential privacy. arXiv preprint arXiv:2307.03928, 2023a.
Eugene Bagdasaryan, Omid Poursaeed, and Vitaly Shmatikov. Differential privacy has disparate impact on model accuracy. Advances in Neural Information Processing Systems (NeurIPS), 2019.
Bogdan Kulynych, Hsiang Hsu, Carmela Troncoso, and Flavio P Calmon. Arbitrary decisions are hidden cost of differentially private training. In Proceedings of the 2023 ACM Conference Fairness, Accountability, and Transparency, 2023.
Georgios Kaissis, Alexander Ziller, Stefan Kolek, Anneliese Riess, and Daniel Rueckert, Optimal privacy guarantees for relaxed threat model: Addressing sub-optimal adversaries in differentially private machine learning. Advances in Neural Information Processing Systems (NeurIPS), 2023b.
Marika Swanberg, Meenatchi Sundaram Muthu Selva Annamalai, Jamie Hayes, Borja Balle, and Adam Smith. Beyond the worst case: Extending differential privacy guarantees realistic adversaries. arXiv preprint arXiv:2507.08158 2025.
Hannah Brown, Katherine Lee, Fatemehsadat Mireshghallah, Reza Shokri, and Florian Tramèr. What does mean for a language model to preserve privacy? In ACM conference on fairness, accountability, and Iranspurency, 2022.
Amer Sinha, Thomas Mesnard, Ryan McKenna, Daogao Liu, Christopher A. Choquette- Yangsibo Huang, Da Yu, George Kaissis, Zachary Charles, Ruibo Liu, Lynn Chua, Pritish Kamath, Pasin Manurangsi, Steve He, Chiyuan Zhang, Badih Ghazi, Borja De Balle Pigem, Prem Eruvbetine, Tris Warkentin, Armand Joulin, and Ravi Kumar. VaultGemma: A differentially private Gemma model, 2025.
Mary Anne Smart, Dhruv Sood, and Kristen Vaccaro. Understanding risks of privacy theater with differential privacy. Proceedings of the ACM on l'lmaan-Copputr Interaction, 6(CSCW2):1-24, 2022.
Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. Calibrating noise to sensitivity in private data analysis. In Proceedings of the Theory of Cryptography Conference, 2006.
Milad Nasr, Shuang Songi, Abhradeep Thakurta, Nicolas Papernot, and Nicholas Carlini. Adversary instantiation: Lower bounds for differentially private machine learning. In IEEE Symposium on security and privacy (SP), 2021.
Weijie J Su. A statistical viewpoint on differential privacy: Hypothesis testing, representation, and blackwell's theorem. Anmual Review of Statistics and Its Application, 12, 2024.
Quan Geng and Pramod Viswanath. Optimal noise adding mechanisms for approximate differential privacy. IEEE Transactions Information Theory, 2015.
Raef Bassily, Kobbi Nissim, Adam Smith, Thomas Steinke, Uri Stemmer, and Jonathan Ullman. Algorithmic stability for adaptive data analysis. In Proceedings of the annual ACM symposium on Theory of Computing, 2016.
Bogdan Kulynych, Mohammad Yaghini, Giovanni Cherubin, Michael Veale, and Carmela Troncoso. Disparate vulnerability to membership inference attacks. Proceedings on Privacy Enhancing Technologies, 2022a.
Elena Ghazi and Ibrahim Issa. Total variation with differential privacy: Tighter composition and asymptotic bounds. In IEEE International Symposium on Information Theory (ISIT), 2023.
Rachel Cummings, Shlomi Hod, Jayshree Sarathy, and Marika Swanberg. Attaxonomy: Unpacking differential privacy guarantees against practical adversaries. arXiv preprint arXivv2405.017166 2024.
14

---

Alexandra Wood, Micah Altman, Aaron Bembenek, Mark Bun, Marco Gaboardi, James Honaker, Kobbi Nissim, David R O'Brien, Thomas Steinke, and Salil Vadhan. Differential privacy; A primer for non-technical audience. Vand. J. Ent. & Tech. I.,, 2018.
Zeki Kazan and Jerome Reiter. Prior-itizing privacy: A bayesian approach to setting the privacy budget in differential privacy. Advances in Neural Information Processing Systems (NeurIPS), 2024.
Bargav Jayaraman, Lingxiao Wang, Katherine Knipmeyer, Quanquan Gu, and David Evans. Re- visiting membership inference under realistic assumptions. Proceedings on Privacy Enhancing Technologies, 2021.
Igal Sason and Sergio Verdú. f-divergence inequalities. IEEE Transactions on Information Theory, 62(11):5573-660) 2016.
Bogdan Kulynych, Yao- Yuan Yang, Yaodong Yu, Jaroslaw Blasiok, and Preetum Nakkiran. What you see what you get: Principled deep learning via distributional generalization, Advances in Neural Information Processing Systems (NeurIPS), 2022b.
Jean Louis Raisaro, Gwangbac Choi, Sylvain Pradervand, Raphael Colsenet, Nathalic Jacquemont, Nicolas Rosat, Vincent Mooser, and Jean-Pierre Hubaux. Protecting privacy and security of ge- nomic data in i2h2 with homomorphic encryption and differential privacy. IEEE/ACM transactions on computational biology and bioinformatics, 1555):1433144 2018.
Florian Tramer and Dan Boneh. Differentially private learning needs better features (or much more data). In International Conference on Learning Representations, 2021.
Edward J Hu, Phillip Wallis, Zeyuan Allen-Zhur Yuanzhi Li, Shean Wang, Lu Wang. Weizhu Chen, et al. Lora: Low-rank adaptation of large language models. In International Conference Learning Representations, 2021.
Alex Wang, Amanpreet Singh, Julian Michael, Felix Hill, Omer Levy, and Samuel Bowman. Glue: A multi-task benchmark and analysis platform for natural language understanding. In Proceedings of the 2018 EMNLP Workshop BlackboxNLP: Analyzing and Interpreting Neural Networks for NLP, 2018
Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. Pytorch: An imperative style, high-performance deep learning library. In Advances in Neural Information Processing Systems (NeurIPS), 2019.
Ashkan Yousefpour, Igor Shilov, Alexandre Sablayrolles, Davide Testuggine, Karthik Prasad, Mani Malek, John Nguyen, Sayan Ghosh, Akash Bharadwaj. Jessica Zhao, Graham Cormode, and Ilya Mironov. Opacus: User-friendly differential privacy library in PyTorch. arXiv preprint arXiv:2109. 12298, 2021.
Charles R. Harris, K. Jarrod Millman, Stéfan J. van der Walt, Ralf Gommers, Pauli Virtanen, David Coumapeau, Eric Wieser, Julian Taylor, Sebastian Berg, Nathaniel J. Smith, Robert Kern, Matti Picus, Stephan Hoyer, Marten H. van Kerkwijk, Matthew Brett, Allan Haldane, Jaime Fernández del Río, Mark Wiebe, Pearu Peterson, Pierre Sérard-Marchart Kevin Sheppard, Tyler Reddy, Warren Weckesser, Hameer Abbasi, Christoph Gohlke, and Travis F. Oliphant. Array programming with NumPy. Nature, 2020.
The pandas development team. pandas-dev/pandas: Pandas, 2020.
Thomas Kluyver, Benjamin Ragan-Kelley, Fernando Pérez, Brian Granger, Matthias Bussonnier, Jonathan Frederic. Kyle Kelley, Jessica Hamrick, Jason Grout, Sylvain Corlay, Paul Ivanov, Damián Avila, Saña Abdalla, Carol Willing, and Jupyter development team. Jupyter notebooks a publishing format for reproducible computational workflows. In Positioning and Power in Academic Publishing: Players, Agents and Agendas. IOS Press, 2016.
Michael L. Waskom. seaborn: statistical data visualization. Journal of Open Source Software, 6(60), 2021. doi: 10.21 10.21105/joss.00000 03021. URL http://oo.....0/0///1101 jossos/.o..ooooooe.ese/./sesosss 03021..
15

---

A Extended Background
This section presents a more extensive overview of the background.
A.1 Differential Privacy and its Variants
Classical differential privacy. Differential privacy (DP) is a formal notion of privacy applicable to releases of statistical information or machine learning models:
Definition A.1 (Dwork al., 2006). A mechanism M 2 + θ satisfies (e, 6D- for any S = S we have E.e (P Il Q) & 6, where P and Q are the respective probability distributions of (S) and MS'), and the hockey-stick divergence between probability distributions is defined as follows:
E,(P Q)
sup P(E) ((E)) ege
(14)
We refer to the case when 8 pure DP.
Realistic DP mechanisms satisfy potentially infinite collection of different (c, 5)-DP guarantees. To analyze this collection, we make use of notion of the privacy profile:
Definition A.2 (Balle et al., 2018). mechanism M (-) has a privacy profile ö(e) for every e e R. satisfies (s, (D))
Strong-adversann membership inference. DP can be completely characterised via constraint on the success rate of membership inference attacks, which aim to determine whether given record was part of the input dataset S based on the output of (S). Formally, given sensitive record E D, and partial dataset S E _=-1, consider probability distribution of the algorithm' 's outputs when the record is not part of the dataset, P(E) & (S) E E], and the respective distribution when the record is present in the data, Q A Pro-M(BU(=))) (0 E F... In a ttrong-adversury membership inference attack (see, e.g., Nasr et al., 2021), given knowledge of the mechanism M()). its output 0, a target record z, and a partial dataset S, the adversary aims to determine whether the record was part of the training dataset used to produce 0 or not. other words, the attack a hypothesis test which aims to distinguish between two hypotheses:
Ho 0 ~ P. and H1 : 0 ~ Q.
(15)
"Strong" refers to the fact that the adversary knows all of the partial dataset S.We discuss this threat model further in Section 3.1.
Differential privacy as hypothesis testing. For given hypothesis test (equivalent to membership inference attack) o: θ + {0, 1} which returns when the guess is Ho, and 1 when the guess is Hi, we can quantify the adversary's 's success by characterizing the error rates of the test (Wasserman and Zhou, 2010; Kairouz al., 2015; Dong al., 2022):
as [p(Ø], Sg - 1 111-Egh Eq|Ø],
(16)
where 0gg and Bg are the false positive rate (FPR) and false negative rate (FNR) respectively.
lemma guarantees that there exists an optimal test 6² which achieves the lowest possible FNR B. We can thus characterize the attack setting by a trade-off curve, a function which shows the lowest FNR achieved by the most powerful level test for any level of FPR a E [0;
For any desired FPR level a E [0, 1], the Neyman- Pearson Keyman-Pearson
T(P. (a) &
{3s as S <a} e-
inf
(17)
common way summarize the success of the optimal strong-adversary membership inference attack (SMIA) is via its advantage, the difference between its TPR and FPR (Yeom et al., 2018):
adV
sup &i [-
1 3. as.
We now define f-DP, version of DP which centers the hypothesis-testing interpretation:
16

---

Definition A.3 (Dong et al., 2022). A mechanism M()) satisfies f f-Differential Privacy (f-DP) if. for any pair S S', the trade- off curve of the strong membership inference test bounded:
(SM(S), (())) 2 f(a). Ya E 10,
(18)
where f: 10 [0, is valid trade-off function: convex, continuous, non-increasing function such that f(a) _ 1- -1--aff for all a E [0, 1].
Note that (e, 6)-DP is a special case of /-DP. Specifically, a mechanism (e,6)-DP if and only if satisfies f-DP with the following (aariingg[(]) ((x):
f(a) = max (0, 1- - 6 aa e (1 (((1--aa)
(19)
We make use of the following equivalent representation of
f f-DP:
Lemma 2.1. An algorithm M 20 + θ satisfies f-DP for any measurable E C O and S = S"
Pr(M(()) e E| S ((P((M(S)) E E)).
This form is key deriving our results streamlined way.
A useful property of f-DP is post-processing: if (-) satisfies f-DP, so does go M for any determin- istic or randomized mapping 9-)). In other words, post-processing the results of an f-DP mechanism cannot decrease its privacy or, equivalently, cannot increase the success of the aforementioned deci- sion problem. This a consequence of the Seekwell-SShrman Kaissis et al., 2024; Su, 2024).
theorem (Dong al., 2022;
Total-variation privacy. We also make use of the notion of total variation (TV) privacy:
Definition A.4. A mechanism M 2 - θ satisfies 7V7VV privacy it satisfies (0, n)DP. Equivalently, total variation distance, a special case of E,, with 7 = 1, is bounded for all S ~ S":
EP Q) sup P(E) Q(E) s.
(20)
Ege
where P and Q are the respective probability distributions of (S) and (S').
TV privacy has been extensively studied under equivalent forms and different names litera- ture (Geng and Viswanath, 2015; Bassily et al., 2016; Kulynych et al., 2022a; Chatzikokolakis et al., 2023; Ghazi and Issa, 2023). Although TV privacy is a weak notion of privacy on its own (Vadhan, 2017), any DP mechanism satisfies TV privacy for some ry:
Proposition A.1. The following statements hold:
(e, DDP implies 1V-VV privacy with 17 = e"-1426 (Kairouz et al., 2015).
e+11
. f-DP implies TV privacy with 17 max.ce(o.] f(a) - a.) ) (Kaissis et al., 2024).
Privacy via Rényi divergence. Another notion we use is Rényi DP (RDP) (Mironov, 2017).
Definition A.5 (Mironov, 2017). A mechanism M(-) satisfies (I,e)-RDP ift for all S = S":
D, || Q) SE.
(21)
where P and Q are the respective probability distributions of MS) and M(S"), and D2 || Q) is the Rényi divergence order t 1:
1
P(o)
D. I| Q
log EowQ
Q(0)
where the case oft = 1 defined by continuous extension.
The mechanism satisfies p-zCDP (Bun and Steinke, 2016; Dwork and Rothblum, 2016) for p 2 0 if it satisfies (t, RDP for every t 1.
17

---

A.2 Predicate Singling Out
In this section, we provide a brief overview of the notion of predicate singling out security.
Predicate singling out (PSO) risk, which is defined in Section 3.2, is privacy concept introduced by Cohen and Nissim (2020) to rigorously interpret the "singling out" criterion mentioned in the EU GDPR (General Data Protection Regulation). Their goal was bridge the gap between legal expectations of data anonymity and technical guarantees provided by data anonymization mechanisms. At a high level, in the PSO threat model, the adversary uses the output of a data release mechanism 0 = (S) to find a predicate that matches exactly one individual (row) in the original dataset S with significantly greater success than would be expected by chance. In this context, predicate represents a set of attribute values that characterize person, e.g., "speaks Dutch A vegan A concert pianist A born March 15." If a predicate matches only one individual in dataset, that individual is singled out. Moreover, such a predicate is unlikely to identify person by random chance. Formally, the goal of the adversary is to find a predicate p such that EEes p(z) =
Unlike differential privacy, which operates under a strong threat model to provide formal "upper bounds" to more realistic notions of privacy, PSO takes the alternate approach of intentionally being a necessary but not sufficient condition for privacy, i.e. a "lower bound" to realistic notions of privacy. The goal of the original paper was make claims such as "if you do not satisfy PSO security, you not GDPR compliant". Hence, Cohen and Nissim consider the i.i.d. setting: the dataset S is sampled i..d. from a distribution P known to the adversary. Cohen and Nissim reason about this adversary by considering the baseline (before seeing M (S)) and success probability (after seeing M (S)) of the adversary assuming the adversary's predicate in both cases has a fixed weight w, where weight is defined as w Ep (p), the probability that the predicate evaluates to on a random sample from P.
In this setting, the optimal baseline is the random guessing strategy: before observing the output of the mechanism MS). the adversary constructs a predicate that has a small weight w. Intuitively, predicates such "woman over 60 year old" have high weight and predicates such the Dutch vegan pianist from the previous paragraph have low weight. The best the adversary can do as a baseline is to pick a predicate with weight and hope that they single out. This has probability of base nw(1 - w)"-1 for dataset of size n.
A.3 Previous Bounds on Privacy Risk Notions
PSO Security Assuming fixed weight and approximate DP, Cohen and Nissim (2020) showed that the optimal strategy for PSO can be upper bounded as a function the baseline probability:
Theorem A.1 (Cohen and Nissim, 2020), Suppose that M : Dn + θ satisfies (s, 6)-D w.r.f. replace-one neighhourhood relation. Then, for any given n > 1, data distribution over D, and an adversary An, : θ > Qp with Qp (p p: + (0, 1). Er(p) I w/ for given w E [0, 1/2)
we have:
S nne' w +5) succpso(n, M, P,P,w; P.
(22)
E baserso (n, P, w) w)
no.
(23)
This is the bound we use in Fig. 2.
Reconstruction Robustness Next, we review the state-of-the-art results for bounding reconstruction robustness. We start with the Rényi DP bound due Balle et al. (2022):
Theorem A.2 (Balle et al., 2022). Suppose that M()) satisfies (t, RDD w.r.t. either add-remove or replace-one relation. It holds that:
SUCQ[SRK)
< (base(seæa) "..
(24)
Applying the above result to a p-zCDP mechanism and optimizing t to minimize the upper bound yields the following:
18

---

Corollary A.1 (Balle et al., 2022). Suppose that M.) satisfies p-zCDP W.E. either add add-remove or replace-one relation. holds that:
suCC] S exp
log base
vD
(25)
Corollary A.1 is the bound on SRR used in Figs. 3, 4, and 9. We can also apply Theorem A.2 to mechanism that satisfies continuum of RDP guarantees and minimize over the upper bound:
Corollary A.2. Suppose that M-) satisfies (t, =(t))-RDP for all t 1 w.r.t. either add-remove or replace-one relation. It holds that:
suCC|SRR]
I min (base(ssa)
e )
+
(26)
t>1
We use Corollary A.2 in Fig. 1 as the prior method that we compare our S-DP bound to.
B Additional Discussion on Related Work
Related unification efforts. Recently, Cohen et (2025) proposed a unifying notion of risk called narcissus resiliency, which averages over dataset sampling. The notions of risk we consider under our unifying framework are all tailored the strong threat model, which dataset-specific. We additionally provide bounds on Narcissus resiliency using f-DP in Appendix F. Salem et al. (2023); Cummings et al. (2024) provided taxonomies and reductions between risk notions. Our focus is providing analysis using f-DP, as opposed to a taxonomization.
Bayesian semanties of DP. An alternative way analyze and interpret risk in DP is a Bayesian posterior-to toriior-----oor analysis (see, e.g., Wood et al., 2018; Kifer et al., 2022; Kazan and Reiter, 2024). We focus on security-ban -ased literature instead, where risk is analyzed from the point of view of relevant adversarial models. See Kifer et al. (2022); Kaissis et al. (2024) for connections between the Bayesian view and f-DP.
Attack-aware noise calibration. Kulynych et al. (2024) introduced attack-aware noise calibration, idea of calibrating DP algorithms to given level of operational attack risk as opposed to standard practice of calibrating to given pair of (e, 8) parameters. They evaluated this approach for the use case of calibrating noise to a given level of membership inference risk. One of the applications of our result is that it extends the toolbox of attack-aware calibration to further attack risks, thus enabling practitioners to calibrate DP algorithms to notions risk beyond membership inference. which often appear in data protection guidelines (see Section 1).
C Omitted Proofs
C.1 Additional and Auxiliary Results
We start with proof of useful equivalent form of f-DP.
Lemma 2.1. An algorithm M 2 + θ satisfies f-DP for any measurable E C θ and S ~ S":
(r(M(S) e E| S (S)) E F.).
Note that we only consider the functions f that are valid trade-off functions (Definition A.3). Denote by P the distribution of (S) and by Q the distribution of (SS).
Proof.
Suppose that the algorithm satisfies f-DP. Let C O be any measurable set. Consider the deterministic test o(0) 1 e E]. By the definition of f-DP, for this specific must have:
((E]TØ) < 1 - Er(ø].
Substituting Ep(d] = P(E) and Eo(o]= Q(E), we directly obtain:
f(Q(E)) 1- P(E).
19

---

- Suppose that Eq. (3) holds for any measurable E' S θ and any = S'. Let 6 |0, be any hypothesis test. By the Seyman-Pearson lemma, it suffices to consider likelihood-raid tests. Any such test can be decomposed into a convex combination of two indicator functions:
(0)) = 1 (A(0) > / + ( = 4 (1 c)- 1 > 1 + 1 [[A(0) 2 tl,
for some E [0, 1] and & E R. where A()) 4P/a2(0) is the likelihood ratio.
Denoting by Ei {0 @ A(O): 1) and Eg = {0
A(O) 2 (}, have by the linearity of
expectation and the convexity of f:
f(Eolo)) = f((1 - - -((E) + Q(E2))
s (1 (1 f((((E))
f(Q(E2))
By assumption that Eq. (3) holds for the sets En and Eg:
1 (1 - c) (1 P(E))) + c. (1- P(E2))
1 [ø]
As ap Eq [0] and 3o - Ep[Ø], this implies f(as) S fg. which recovers Eq. (18).
To show the main result on the unified bounds, we make use of the following elementary lemmas. First, due to the properties of the trade-off function f. we can push the expectation inside of f()): Lemma C.I. Suppose that f is a valid trade-off function according Definition A.3. For any random variable W over [0, 11. we have:
E[1 f(W) s 1- f(EW).
(27)
Proof. By assumption, f is concave and increasing. The result immediately follows from applying the linearity of expectation and Jensen's 's inequality.
Second, we can supremize an expectation inside of f(-):
Lemma C.2. Suppose that f is a valid trade-off function according to Definition A.3. For any
random variable V taking values in a set V, and any bounded function g V - [0, 1]. we have:
/1-5(suppp00) (supp(()) LUEV
1 1 (-S(EE(V) 51-1
(28)
Proof. Observe that E (VV S sup (v)). We get the result as 1 - ff is increasing.
Next, we can show result which be seen as version of risk bound for on-average baselines.
Lemma C.3. Suppose that M 2 + satisfies f-DP w.n. add-remove relation. Then, for any bounded function q θ > [0, 1). any partial dataset S DV, and any probability distribution P over D, we have:
EgeP ((LM((L(=)) (q(2;)) < - EG [g(2;
(29)
Moreover, if the M()) satisfies J-DP w.r.l. replace-one relation, we have for any z' E D:
Eg (())())(=)) [a(2; 0)] < 1 (Esw Eg EG [g(2; 0)])
(30)
Proof. Fix any 2 E D. By the form of f-DP in Lemma 2.1 and the post-processing property of f-DP,
we have:
()) (=; 0) < 1 (Eg~M ((z;0) (( g (2; 8) < 1 f (EgrM(3) (()
(31)
By Lemma C. we have for any g + [0, 1]:
E.-p [1 f((())) < 1 f(E.~rg(3)
(32)
We get the sought statement in Eq. (29) by taking the expectation over z ~ P of both sides in Eq. (31) and applying Eq. (32). Finally, we get the result in Eq. (30) analogously from:
(g)M((U(e)) (=;;0) < (Ea=M(Su(E") {(z;)))
20

---

In Appendix E, we also derive an equivalent result with the semantics of standard generalization bounds. Moreover, in Appendix we show that this result immediately implies bounds on recon- struction robustness with an alternative on-average definition of baseline success rate (Guerra-Balle Baraaa al., 2023).
We can now show the general version of our risk bound:
Lemma 3.1. Suppose that M 20 - θ satisfies f-DP w.r. either add-remove or replace-one relation. Then, for any bounded function q D e - [0, 1], any partial dataset E D0-1 with n 2 1, and any probability distribution P over D, we have:
Esur (o(=:)))
Eger Eg la(2; - -
(10)
(ace
Proof. For add-remove relation, we immediately get the result by applying Lemma C.2 to the r.h.s. of Eq. (29), and taking g(0) Ez-p g(;;
Eg-P (S() ((2; 0) E(~M(S) E.-P 0) (())(()) g(0).
Analogously, for replace-one relation, we get the result by applying Lemma C.2 to the r.h.s. of Eq. (30) with:
En-P E ((U(()) (2;;) E P2:: = ESLM(S 9(0)
proceed to showing that the difference between the success and the baseline upper-bounded by TV privacy:
Lemma C.4. Suppose that the algorithm M 2n + θ satisfies n-7V privacy w.r.f. either the
add-remove or replace-one relation. Then, for any bounded function q D x θ + [0, 1], any partial datuset S E D with 2 1, and any probability distribution P over DD, we have:
E Eg 00
- sup El~p(a(2; 0)] S n7.
(33)
Proof. Let us assume that M() satisfies f-DP for some valid trade-off curve f. This is always the case under the assumption of the statement, as r-TV implies f(a) = Denoting by succ = Ex>P Eg ((S(())) 0)] and base supece Plap( 0)]. recall that by Lemma 3.1:
1) by Eq. (2).
succ base - (base) base
To make the r.h.s. independent of the baseline, let us maximize it over all possible baseline values:
1 - f(a) a S max 1- - f(a) a S 17, 0.11
where the last inequality is by Proposition A.1. Therefore, succ base 17, which is exactly the sought result.
C.2
Formal Versions of the Simplified Statements in the Main Body
We can now formally re-state Theorems 3.1 and 3.3:
Theorem C.1 (Formal version of Theorem 3.1). Suppose that the algorithm M 2 - θ satisfies fDP w.r.t. either the add-remove replace-one relation. Then, the following hold:
SPSO. For any 2 1, k 2 2, partial dataset E D data distribution P over candidate
set W C D of size |W] k. weight w E [0, 1), and any adversary P,,. θ - Qg,r
for 0g,p {p p MI + {0,1), E..EEESP
0, Ep(p] w) ), we have:
sUCcsPso PM S w; A a..)) < 1 (basessso P.,,))))
21

---

SRR. For any n 2 1, partial dataset S E D==1, data distribution P over D, loss function 8: X threshold r R. and any adversary AM, : - DD we have:
SUCCSRR (RCSsRR(,,,, P.A.P...M..P... 2, S l(basesaи (P: (P),)))
SAI. For any n. 1, set of attributes (1....,A, ... mapping from records to attributes
D Ph. partial dataset S E D=-1, data distribution P over D, and any adversary
SM + Ph, we have:
SUCCsAr(M, PMM.S, S - f(bassssrr
Proof. Consider the mechanism ((M())), where we omit the subscripts for brevity. It satisfies f-DP by post-processing. Let denote the output space of this mechanism Y. i.e., Y = Qs.P for SPSO, = for SRR, and = A for SAL The upper bounds follow immediately from Lemma 3.1 by taking appropriate choice of q Y - [0, 1]:
SPSO: ((2;p) 1[p(z)
SRR: ((; 1 8) S 7
(34)
SAI: (2;;)) 1[a(2) a]
Theorem C.2 (Formal version of Theorem 3.3). Suppose that the algorithm M 2 - θ satisfies 7-7V privacy w.r.t. either the add-remove or replace-one relation. Then, the following hold:
SPSO. For any n 2 1, k 2 2, partial dataset D=-1, data distribution over a candidate anrany
set W _ D of size |W| = k, weight [0, 1], and any adversary P. θ - Qg.P
for Qs.P {p D 10.
0, Eplp) S w). we have:
succspso ( P, wi AMS.PP.w)) basesrso (8, P. P............ Sn.
SRR. For any 1, partial dataset S D"-1, data distribution P over loss function L D x + R, threshold E B. and any adversary AM, - D, we have:
SuCCSRR (M, M.A.,P.AM.S. AMM..,,,,..)) basesuRl P: P, Sn.
SAI. For any 2 1, set of attributes Pa = "ll....,k,, mapping from records to attributes
a - Ph, partial dataset S E D=-1, data distribution P over D, and any adversary AM,3,P Q - P., we have:
suCcsu Succsu(M,,, AM..,,...)) - bases Cepesar(P,o)) P.,) S
Proof. As before, we obtain the results by applying Lemma C.4 to mechanism A(M())), which satisfies f-DP by post-processing, and an appropriately chosen q(2; in Eq. (34).
D Tighter Bounds under a Bernoulli Prior
In this section, we provide a tighter bound than in Theorem 3.1 assuming a known form of the prior distribution P over ID, specifically,
24 with b ~ Bern(T) for some π E [0, 1]. This setting can model two threats: (1) SAI of a single binary attribute with a non-uniform prior (see, e.g.. Guo et al., 2023) equivalently, SRR with only two points in the support of the prior distribution P, and (2) SMIA with non-uniform prior probability membership (Jayaraman et al., 2021).
We make use of the notion of the Bayes eтror of the attacker (Chatzikokolakis et al., 2023).
Definition D.I (Bayes error for f-DP, Kaissis et al., 2024). Suppose that f is valid trade-off function according to Desinition A.3. For any [0, 1}, define the Bayes error w.rlf the prior as follows:
(T( A min (лa + T))(a)).
.E(0.1]
22

---

Given numeric representation of a trade-off curve f, Bayes enror can be easily computed numerically by, e.g., grid search over grid of values. Additionally, we show an elegant way obtain the Bayes emor directly from the privacy profile 8(e), which was previously unknown in the context of DP:
Proposition D.1 (Based on Sason and Verdú, 2016, Eq. (421)). Suppose that mechanism M-) satisfies f-P and has an associated privacy profile ö(2) w.r.t. any neighbourhood relation. Then, the Bayes error is bounded:
(T(T) 2 (1 (1- [1 8 (1ogit(TT)) where logit(z) log 1 π
(35)
Next, we show a bound on success of SAI/SMI under Bernoulli prior using the Bayes error.
Theorem D.I. Fix any partial dataset S E D= with n 2 1. Suppose that M DD - θ satisfies f-DP w.r.t the replace-one relation. Then, for any prior probability
[0, 1], a set of any two candidate records (2o, 21 S D, and any score function b θ + [0, 1] indicating adversary's confidence of whether 21 or was used for training, we have:
Bem((() (S. [g(2s: 0)] S R2(
(36)
where we define the success indicator q(2; as follows:
b(0)
i = 21
0)
(37)
B(0),
if 20
Proof. We can decompose the l.h.s. in Eq. (36) follows:
b-BBer(xx) [α(=,; 0)]
π²) M 0)] Faa.M(Ss (38)
(~M(SU(=a))
Observe that in the setup of this statement, we have (=1; 0) = 1 ((20: 0). Denote by a =
Ex.-M((((t)))(((1: = 1 ((u 0)]. By Lemma 1. we have:
( < - f(a).
Therefore, can upper bound Eq. (38)
I (1 - π) (1- + (1-
= - R2(m))
where the last equality is by Definition D.I.
Experimental evaluation. We compare our bounds in Theorem 3.1, which are applicable to any prior, and the specialized result in Theorem D.1 for Bernoulli priors. We additionally compare these results to the bounds on SRR based on RDP as Section 4, and the bounds on SAI based on the Fano's inequality (Guo et al., 2023).
For this comparison, under replace-one relation. We use = 10 to compute =. We use two versions of the bounds from Guo et al. (2023): (1) based on an analytical bound on mutual information (MI) between Gaussians, and Monte-Carle (MC) method using 10,000 samples (we repeat each run 10 times). Note that the latter method only provides an estimate of bound, unlike all other evaluated approaches. We show the result in Fig. 5 (error bars for the MC approach are not visible). We can see that for all noise parameters, and all baselines, the bound in Theorem D.1 outperforms the other bounds.
Gaussian mechanism with noise scales {0.5, 1.0, 2.0). analyzed
E Generalization Bounds
In this section, we extend the previous results to the setting in which the dataset is assumed to be sampled i.i.d. from some data distribution P. The results in this section assume the replace-one neighbourhood relation.
23

---

1.55
1.90
2.75
0.0
Method
5482 (Balle is al, sCOP)
MI)
SAI (Guo et al, sia Fano, MC)
0.2
Liiifingg (eis (000)
SAI (ne (.DP)
015
0.6
0.0
10.05
0.7
0.8
Beseline
Baseine
Raseline
Figure 5: We significantly tighten the bounds in the setting of binary aftribute inference (SAI, via (-DP), outperforming the prior bound based on Fano's inequality.
Theorem E.1 (On-average generalization from f-DP). Suppose that M D + θ satisfies f-DP
w.r.t. replace-one relation. Then, for any bounded loss function q D θ [0, 1]. and any probability distribution P over D, we have:
1 Σ ((ai0)s1-
E S.pp (S)
Es- -(2 (s)
(39)
onsaverage train loss
Oll-oveerage
gnp s ((;00) 8-
E Sn (NuM(S)
Σ ((2:00)
(40)
on on-aveenage test foss
on-average troin
where S (21, 22,..... 2-)
Proof. Fix any 2, 2 D. and @ -= By Lemma 2.1 and the post- post-processing property of f-DP, we have:
EG (2; 0) < ((SE)()) {(2;0))
(41)
E ( s (EU)M()U(=H) {(2;)).
By using Lemma C.I after taking the expectation over z, ~ P and S ~ pa-1 of both sides in
Eq. (41), have:
8mpm (2;00)51- S S-p" ((z;0) zuP (~M(s)
z~Unif[S] 0~M((S)
E s-pp (z;0) < 1 zmp (~M
supn g(2;0) ZnUnnf(S] (~M((S
The forms in Eqs. (39) and (40) are equivalent as Eg-Unif[S] ((2;)) 0) = 1. Ei= ()2;;0).
By applying Theorem 3.3, we recover the prior result that sup, (x,1100,1) |erru(g) err S for TVVV algorithms (Kulynych et al., 2022b). Next, we show related result which covers non-linear queries, i... those that do not decompose linearly over the dataset. For this, we make use of the group privacy property of f-DP:
Proposition E.1 (Dong et al., 2022). Suppose that M(- satisfies f-DP w.r.t. replace-one relation. Then, the algorithm satisfies f(k) -DP w.r.t replace-k relation S' [|S|= |S but differ by exactly k points), where [(k = (1 - f) with for denoting repeated k-fold composition of the function as f Ro fo... (z). The function (k) is valid trade-off curve per Definition A.3.
We now show the result for non-ling non-linear queries:

---

Theorem E.2. Suppose that M : D + θ satisfies f-DP w.F.. replace-one relation. Then. for any
bounded function R D θ [0, 11. and any probability distribution P over D, we have:
E Supp M())
R) $ - - f(1))
Eg.T=pn R(T;0) (lM((S)
(42)
PS ((;;0) - 1 f(n) (~M((S)
Sm ( (l)
R(T;0))
(43)
Proof. Fix any S D and T E D By Lemma 2.1 and the group privacy property in Proposition E. we have:
(s) R(S; 8) - - f(a)) (E R(S;0)
(44)
(T) R(S: 0) f(a) (Eo~M(3) R(S: 0))
By using Lemma C.I after taking the expectation over S ~ P" and T pm of both sides in Eq. (44),
we have:
E pm R(S;0) < 1 - f(x) (~)
ES R(S;0) (N)
Pp R( < f (E (E R(S:0) (s)
(~M(TT
We get the desired result by renaming the variables 5 and in the Es,r RR5; M(T)) terms.
In Appendix F, we use this result to bound the notion of narcissus resiliency (Cohen et al., 2025) using f-DP. Unfortunately, the privacy guarantees obtained using this approach can quickly become vacuous, as they scale with the dataset size.
F Bounds for Other Risk Notions
In this section, we show additional bounds based on f-DP for other risk notions beyond the strong- adversary notions in Section 3.2.
Counterfactual memorization and influence. Using the tools in Appendices C and E, we bound notions memorization (Feldman, 2019; Zhang et al., 2023). First, we define cross-influence:
Definition F. -rooss-iflluncce.. Fix a partial dataset E D=-1, two records z, E D, and a bounded loss function É D D + [0, 1]. We define the cross-influence of on
xinf(z < =²) Eg [f(2; 0)] - Eg"wP, e~M((SU(=")) [[(=))).
(45)
When =z', we obtain the special of counterfuctual self-influence, i.e., memorization.
Definition F.2 (Counterfactual memorization). Fix S m be a partial dataset, D to be
fixed record, P to be a distribution over D, and a bounded loss function {: DD x D + [0, 1}. We define the memorization of z as:
mem(2) A Eg- [e(2; 0)] Egep, e~ar( [[(=:))]
(46)
For the special case that E(2; f) is decision rule implementing a membership inference attack which aims to infer the membership of can write the SMIA advantage in replace-one neighbourhood model as follows:
advSMIA A Eg [0(20)) EgSP,, M(((()))))) (0(2;))
(47)
TPR
FPR of
The next result then follows by recognizing that mem recovers the definition of advsMIA's and that adVSMIA' is apper-bounded by the TV privacy parameter:
25

---

Proposition F.1 (n-TV privacy bounds memorization//dvaatgee Suppose that M : D + θ satisfies 1- 1-TV privacy wrr. the replace-one neighbourhood relation. Then, for any n 2 probability distribution P over W. partial dataset $ E D any bounded { + [0. 11, and any target record E holds that:
mem 2) S and adv (2) S
(48)
Proof. Recall that satisfies /-DP for some f. For any fixed a, E D, we have by Lemma 2.1: (B)M(SL(=)) ((;; 0) < - (Eo-M(SU(=1) {(2;0))
Subsequently, taking the expectation over z' P and applying Lemma 3.1, we get:
M ($ (2; 0) - - Be ()):))).
Finally, we obtain the bound in terms of 17 by subtracting E e~ ((S from both sides and recalling that max f() a) S n by Proposition A.1.
Note that a similar connection between memorization and the advantage of membership inference attacks an average-dataset threat model has been observed previously (Kulynych et al., 2022a).
Unbiased reconstruction robustness. Next, we present a variant of reconstruction robustness with an average baseline.
Definition F.3 (Unbiased RR, adapted from Guerra-Balbor et al., 2023). For a given 2 1, mechanism M 2 θ, data distribution P over I, partial dataset E D=-1, loss function e: D ID - R., threshold ry E R, and reconstruction attack A A θ + D, we define the unbiased reconstruction robustness (URR) success rate as follows:
SUCCURR P: &
Pr g 26 AM (.
((z,2) S>
and the baseline success as:
baseuRR (P;
Pr 2,E'P
[8(2, 8) S 7].
2+ B
Theorem F.1. Suppose that the algorithm M :4: D θ satisfies f-DP w.r.t. replace-one relation. Then, for any n. 2 1, partial dataset m- data distribution P over D, loss fanction D + B. threshold y E R. and any adversary AM, θ + D, have:
succuRa (M, P: AM. e, 4,) 1 1
(49)
Moreover,
succuRa(M, P:AM.S.,,&M). k,m) - baseuue (P: S n
(50)
where 1j is the TV privacy guarantee of the mechanism.
Proof. We obtain Eq. (49) by applying Lemma C.3 to mechanism AM.s, (0). which satisfies f-DP by post-processing, and using q(2; chosen as in Eq. (34). We immediately get Eq. (50) by applying Proposition A.I to Eq. (49) in the proof of Lemma C.4.
Narcissus resiliency. We present a recent definition of privacy due to Cohen al. (2025), adapted to our setting:
Definition F.4 (Narcissus resiliency, adapted from Cohen et al., 2025). For a given n 2 1, mechanism
M 2 - O, data distribution P over D, an adversary M O -> V which outputs an element from an arbitrary set V. and bounded function R : m x V + [0, 1}. we define the narcissus resiliency (NR) success rate as follows:
succxa M, P)A,R)
Pr
[R(S,)),
Sup (MM))
and the baseline success as:
base (n, P: A. R) A
Pr
[R(T,
P
DE AC-A,,,,
26

---

Our generalization result for non con-linear functions in Theorem E.2 immediately implies a bound on its success:
Theorem F.2. Suppose that M : D + O satisfies f-DP w.E.t replace-one neighbourhood relation.
Then, for any given 1, data distribution P over D, and an adversary AnM,P Q, have:
suCCNR (n, M, P,A. R)) < - f(1) (basewx P;A, R)).
Proof. After observing that (S)) satisfies f-DP by post-processing, the result is immediate implication of applying Theorem E.2 to A as a mechanism.
Avarage-dataset predicate singling out. We can show the following bound on PSO based on f-DP:
Theorem F.3. Suppose that M D - O satisfies f-DP w.r.t. replace-one neighbourhood relation. Then, for any given n > 1, data distribution over IM and an udversary AnM Qp,w with OP. {p p:D {0, [0,1)..Ep) Eplp] = w) for any given E [0, 1/m]. we have:
succpso M, P. A) S n
f(w)
(51)
Proof. We follow the steps of the proof in Cohen and Nissim (2020). Regardless of the weight of any given predicate we can modify it to have weight less than to via:
p(x) 0
if Ep(p] S if Eplp] >
pd (z)
Note that p' is exactly if p's weight is S and is trivially always 0 else. So, the weight of p" either 0 or Ep(p"]. Moreover, by postprocessing we know that p" is f-DP. We investigate the probability of successful PSO attack S, which occurs when p" (S) _ E/=1""(2) = and Ep(p*] S w. The second condition is always satisfied via the construction of p", so:
succ(n, M, P:A)
Pr
(p(S) 1/n and Epip] s w]
SmPp
MS)
Pr (p"(S) 1/n] Smpn
pt M(S)
Pr [p'(2;) and A H p" p²(2)) 0),
Sm M(S)
where S = (21, 22, ,2,,.,,,, zn).
Now, p" satisfies f-DP, apply Lemma 2.1 in conjunction with Lemma C.1:
Pr Snpp g pe- (S
(2:) = and v Vi j. (2 = 0]
1=1
where + z denotes substitution of x; by z. We can reparametrize without changing the expectation:
Pr (z:) and V (x,) 0] Smp 2>P
(52)
p-M((S
Now, we can upper bound the probability inside f(-) by by Lemma C.2:
- f(w)
1=1
n (1 f(w)).
Note that, to tighten the bound, we slightly modified the definition of the admissible predicate in Thcorem F.3 to only consider predicates of specific weight.
27

---

Baseline 0.01
Baseline
Baseline Worst-case
008
Risk (advantage
0.6
Method Standard. via (c.4) DP J-DP
0.4
0.2
000
Number of queries
Number of queries
Number of queries
Figure 6: Our fDDP based bound enables to perform more statistical queries at the same level of re-identification or other notions of risk.
G Additional Experimental Details
G.1 Additional Case Studies
Tight budget analysis DP query answering terms of risk. One the common use cases of DP is answering statistical queries about dataset (Gaboardi et al., 2020). In real-world instances of such systems, e.g., healthcare, re-identification risk a concern (Raisaro al., 2018).
To evaluate how our bounds apply to risk measurement in this setting, we simulate the release of multiple queries with added Laplace noise. We compare our bound to the default budget computation procedure of smar smartnoise software framework (Gaboardi et al., 2020). which is based on optimal composition results for (c, 5)-DP mechanisms (Kairouz et al., 2015). To apply our bounds, we use the direct method from Kulynych et al. (2024) to obtain the f curve of an adaptive composition of Laplace mechanisms. In this simulation, we assume a fixed noise parameter b 5.0 for each query, corresponding to 0.2 pure DP per query. In Fig. 6, we show how our bounds on risk can enable researchers to conduct significantly more queries while satisfying any given risk requirement, in particular, on re-identification. For example, if the requirement is to ensure at most 0.2 attack advantage under the baseline risk 0.1 (Fig. 6, middle pane), we can issue 15 queries according to analysis 5 with the standard one.
Calibrating noise to image reconstruction risk deep learning. In this case study, as Section 4, we assume the modeler aims to use DP training for CIFAR-10 10 image classification (Krizhevsky et al., 2009) to limit such risks to a given threshold. We train multiple convolutional networks using the approach of Tramer and Boneh (2021) (we provide further technical details next). We train with standard DP-SGD (Abadi et al., 2016) and use five different levels of noise. We obtain the curve under the add-remove relation for each model using the direct method as before (Kulynych al., 2024), and apply Theorem 3.2 to measure risk. We compare this to the RDP-based analysis from Balle al. (2022), as described previously. Fig. shows that if aim calibrate the noise scale to a given level of maximum attack risk, our unifying bound enables to choose a lower noise scale at the same level of risk (left plot), which, in turn, results in better classification accuracy (right plot). E.g., for the risk target of 0.25, we can increase the accuracy from 65% to 68% using our analysis, as opposed RDP-based one.
G.2 Experiment Details
We use an Nvidia GeForce RTX 4070 16 GB GPU machine for the deep learning experiments. The experiments take up to four hours to finish.
Text Sentiment Classification case study details We follow Yu et al. (2021) to finetune GPT-2 (small) (Radford et al., 2019) using L (Hu et al., 2021) with DP-SGD the SST-2 sentiment classification task (Socher et al., 2013) from the GLUE benchmark (Wang al., 2018). We summarize the parameters next:
28

---

Noise
Better Usility
0.0
0.5
Risk (advantage)
0.4
0.3
0.2
0.2
Noise scale
Test accuracy %
Figure 7: Our f-DP based bound enables us to achieve higher classification accuracy for any level of risk.
Parameter
Values
Poisson subsampling probability
Rs 0.004
Expected batch size Gradient noise multiplier (a)
256
(0.5715,0.6072) 0.6366, 0.6945, 0.7498)
Privacy budget (e) at 10
(3.95,3.2,227,11.9 1.45)
Training epochs
Gradient clipping norm (A2)
1.0
LoRA dimension
LoRA scaling factor
32
Image-laassification case study details. We use the method of Tramer and Boneh (2021) train a convolutional neural network. We use CIFAR- 10 (Krizhevsky et al., 2009) image classification dataset with default split. We summarize the parameters next:
Parameter
Values
Poisson subsampling probability
Rs
Expected batch size Gradient noise multiplier (%/az)
8192
(4,5,6,8,
Training epochs
S 100
Gradient clipping norm (A2)
0.1
Learning rate Momentum (Nesterov)
0.9
Software
We use the following key open-source software:
PyTooc (Paszke al., 2019) for implementing neural networks.
opacus (Yousefpour et al., 2021 1) for training PyTTrrch neural networks with DP-SGD.
numpy (Harris al., 2020), pandas (pandas development team, 2020), and jupyter (Kluyver et al., 2016) for numeric analyses.
seaborn (Waskom, 2021) for visualizations.
H Additional Figures
29

---

Table Comparison of average-dataset vs, strong-adversary threat models. nı dataset size, P. data distribution, : mechanism, S: partial dataset, poisoning cap.. whether an adversary has the capability to insert arbitrary records into the dataset, *: the dataset size is implicitly known from the size of the partial dataset S.
Threat model
Risk notion
Reference
Adv. knowledge
Poisoning cap.
Bounds from /-DP
P
M
SPSO
Definition 3.2
Strong
SRR (Balle al., 2022)
Definition 3.3
Theorem
SAI (any k)
Definition 3.4
(k 2)
Detinition 3.4
Theorem
URR (Guerra-Balboe
2023)
Definition F.3
Theorem
Avg. dataset
NR (Cohen et al., 2025)
Detinition F.4
/
/
Theorem F.2
PSO (Cohen and Nissim, 2020)
Definition 3.1
Theorem F.3
1000
11 5000
1.0
1.0
Rook (ahaarag)
0.6
0.6
Method
PSO (Cokes and Noain is, Liilinn (-00)
0.2
02
Figure 8: PSO bounds for Laplace mechanism. See Fig. 2 for details. We do not show the results with the PSO bound based on f-DP, as they are identical to the (e, 6)-based bound for this mechanism.
0.7
Rok [sboonagg)
0.4
0:26
0.16
0.00
0.02
5:87
0.05
0.10
0:67
Baseline
0:67
6.61
Rok [adkmmaze
0.5
7,35
0.4
0.41
Method
sCDF)
..22
0.29
Unibinng (via S-DP)
0.04
Baseline Wort-case
0.69
Risk (ahemtage)
0.5
0.52
6.85
6:51
0.49
0.50
0:35
0:31
0.25
0.2
0.08
0:06
Group
Level
Figure 9: The results for US Census under multiple risk baselines. See Fig. 4 for details.
30

---

500
1000
5000
Rook (elveer agnh
0.8
0.5
Method
PSO (Cobas and Kaain (6.E)
0.4
PSO (vo (-0P)
Unifaix /-DP)
0.2
25
41)
111
231
30
10
20
-31
43
1000
Biok (slvantign)
0.2
0.5
PSO (Cokes and Nodin (6 (.00)
C-4
0.4
084
Uniyarg (ve /-DF)
6.0
110
Figure 10: Result of redoing Fig. 2 (top) and Fig. (bottom) with the improved f-DP bound for PSO derived in Theorem F.3. We observe significant gain in using this bound.
31

---

NeurIPS Paper Checklist
1. Claims
Question: Do the main claims made in the abstract and introduction accurately reflect the paper's contributions and scope?
Answer: [Yes]
Justification:
The abstract succinetly summarizes the main claims of the paper.
Guidelines:
The answer NA means that the abstract and introduction do not include the claims
made the paper.
The abstract and/or introduction should clearly state the claims made, including the
contributions made in the paper and important assumptions and limitations. A No
NA answer to this question will not be perceived well by the reviewers.
The claims made should match theoretical and experimental results, and reflect how much the results can be expected to generalize other settings. is fine to include aspirational goals as motivation as long as is clear that these goals not attained by the paper.
2. Limitations
Question: Does the paper discuss the limitations of the work performed by the authors?
Answer: [Yes]
Justification:
The paper discusses the limitations Section 6.
Guidelines:
The answer NA means that the paper has limitation while the answer No means that the paper has limitations, but those are not discussed in the paper.
The authors are encouraged to create separate "Limitations" section in their paper.
The paper should point out any strong assumptions and how robust the results are to violations of these assumptions (e.g., independence assumptions, noiseless settings, model well-specification, asymptotic approximations only holding locally). The authors should reflect on how these assumptions might be violated in practice and what the implications would be.
The authors should reflect on the scope of the claims made, e.g., if the approach was only tested few datasets or with few runs. In general, empirical results often depend on implicit assumptions, which should articulated.
The authors should reflect on the factors that influence the performance of the approach. For example, facial recognition algorithm may perform poorly when image resolution is low or images are taken in low lighting. Or speech-to-text system might not be used reliably provide closed captions for online lectures because it fails handle technical jargon.
The authors should discuss the computational efficiency of the proposed algorithms
and how they scale with dataset size.
If applicable, the authors should discuss possible limitations of their approach to address problems of privacy and faimess.
While the authors might fear that complete honesty about limitations might be used by reviewers as grounds for rejection, worse outcome might be that reviewers discover limitations that aren't acknowledged
the paper. The authors should use their best judgment and recognize that individual actions in favor of transparency play impor- tant role in developing norms that preserve the integrity of the community, Reviewers will be specifically instructed to not penalize honesty concerning limitations.
3. Theory assumptions and proofs
Question: For each theoretical result, does the paper provide the full set of assumptions and complete (and correct) proof?
Answer: [Yes]
Justification: We describe the high-level setting in Section 1, as well as clearly note all of the lewelevel assumptions Appendix We provide proofs of the statements in the main body in Appendix C.
32

---

Guidelines:
The answer NA means that the paper does not include theoretical results.
All the theorems, formulas, and proofs in the paper should be numbered and cross- referenced.
All assumptions should be clearly stated referenced in the statement of any theorems.
The proofs can either appear in the main paper or the supplemental material, but they appear in the supplemental material, the authors are encouraged to provide short proof sketch to provide intuition.
Inversely, any informal proof provided in the core of the paper should be complemented
by formal proofs provided in appendix supplemental material.
Theorems and Lemmas that the proof relies upon should properly referenced.
4. Experimental result reproducibility
Does the paper fully disclose all the information needed to reproduce the main ex- perimental results of the paper to the extent that affects the main claims and/or conclusions of the paper (regardless of whether the code and data are provided or not)?
Question:
Answer: [Yes]
Justification: We detail on the information required to reproduce the results in Section 4 and Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
If the paper includes experiments, a No answer to this question will not be perceived well by the reviewers: Making the paper reproducible is important, regardless of whether the code and data are provided or not.
the contribution is dataset and/or model, the authors should describe the steps taken to make their results reproducible or verifiable.
Depending on the contribution, reproducibility can be accomplished in various ways. For example, if the contribution is a novel architecture, describing the architecture fully specific model and empirical evaluation, may
might suffice, or if the contribution be necessary to either make it possible for others to replicate the model with the same dataset, or provide access to the model. In general. releasing code and data is often one good way to accomplish this, but reproducibility can also be provided via detailed instructions for how to replicate the results, access a hosted model (e.g., in the case of large language model), releasing of a model checkpoint, or other means that are appropriate to the research performed.
While NeurlPS does not require releasing code, the conference does require all submis- sions to provide some reasonable avenue for reproducibility, which may depend on the nature of the contribution. For example
(a) If the contribution is primarily new algorithm, the paper should make it clear how to reproduce that algorithm.
(b) the contribution is primarily a new model architecture, the paper should describe the architecture clearly and fully.
(c) If the contribution is new model (e.g., a large language model), then there should either way to access this model for reproducing the results or way to reproduce the model (e.g., with an open-source dataset or instructions for how to construct the dataset).
(d) We recognize that reproducibility may be tricky in some cases, in which case authors are welcome describe the particular way they provide for reproducibility. the case of closed-source models, it may be that access to the model limited in some way (e.g., to registered users), but it should be possible for other researchers to have some path to reproducing or verifying the results.
5. Open access to data and code
Does the paper provide open access to the data and code, with sufficient instruc- tions faithfully reproduce the main experimental results, as described in supplemental material?
Question:
Answer: [Yes]
33

---

We provide the code as a supplementary material, accompanied with instruc- tions for reproducing.
Justification:
Guidelines:
The answer NA means that paper does not include experiments requiring code. Please see the NeurlPS code and data submission guidelines (https://nips.cm cc/
Beliic/guides/Cooe
ssssssolicccoooo cy) for more details.
While we encourage the release of code and data, we understand that this might not be possible, "No" an acceptable answer. Papers cannot be rejected simply for not including code, unless this is central to the contribution (c.g., for new open-source benchmark).
The instructions should contain the exact command and environment needed to run to reproduce the results. See the NeurIPS code and data submission guidelines (https:
/ //niss cttpccccpblllcc c/gggiiiiie
iomiissionfl usionPolicy for more details.
The authors should provide instructions data access and preparation, including how to access the raw data, preprocessed data, intermediate data, and generated data, etc.
The authors should provide scripts to reproduce all experimental results for the new proposed method and baselines. only subset of experiments are reproducible, they should state which ones are omitted from the script and why.
At submission time, to preserve anonymity, the authors should release anonymized versions (if applicable).
Providing as much information possible in supplemental material (appended to the paper) recommended, but including URLs to data and code permitted.
6. Experimental setting/details
Question: Does the paper specify all the training and test details (e.g., data splits, hyper- parameters, how they were chosen, type of optimizer, etc.) necessary understand the results?
Answer: [Yes]
Justification: We detail the technical details required to reproduce the results in Section and Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments. The experimental setting should be presented in the core of the paper to level of detail that is necessary to appreciate the results and make sense of them. The full details can be provided either with the code, in appendix, as supplemental material.
7. Experiment statistical significance
Does the paper report error bars suitably and correctly defined or other appropriate information about the statistical significance of the experiments?
Question:
Answer: [No]
Justification: In the main experiments, we compute theoretical quantities directly, thus do not need to empirical statistical procedures.
Guidelines:
The answer NA means that the paper does not include experiments.
The authors should answer "Yes" if the results are accompanied by error bars, confi- dence intervals, statistical significance tests, least for the experiments that support the main claims of the paper.
The factors of variability that the error bars capturing should be clearly stated (for example, train/test split, initialization, random drawing of some parameter, or overall
with given experimental conditions).
The method for calculating the eтror bars should be explained (closed form formula.
call to a library function, bootstrap, etc.)
The assumptions made should be given (e.g., Normally distributed errors).
should be clear whether the error bar is the standard deviation or the standard error of the mean.
34

---

It is OK to report 1-sigma error bars, but one should state it. The authors should preferably report a 2-sigma error bar than state that they have 96% CI, if the hypothesis of Normality of errors is not verified.
For asymmetric distributions, the authors should be careful not to show in tables figures symmetric error bars that would yield results that are out of range (e.g. negative error rates).
error bars are reported in tables or plots, The authors should explain in the text how they were calculated and reference the corresponding figures or tables in the text.
8. Experiments compute resources
For each experiment, does the paper provide sufficient information on the com- puter resources (type of compute workers, memory, time of execution) needed to reproduce the experiments?
Question:
Answer: [Yes]
Justification:
We describe the hardware used in Appendix G.
Guidelines:
The answer NA means that the paper does not include experiments.
The paper should indicate the type of compute workers CPU or GPU, internal cluster, or cloud provider, including relevant memory and storage.
The paper should provide the amount compute required for each of the individual experimental runs well estimate the total compute.
The paper should disclose whether the full research project required more compute than the experiments reported in the paper (e.g., preliminary or failed experiments that didn't make into the paper).
9. Code of ethics
Question: Does the research conducted in the paper conform, in every respect, with the NeurIPS Code of Ethics httpp:////errips..cucuui///tiiie
Answer: [Yes]
Justification: Neither the research process itself nor the outcomes of the research carry significant potential for harm.
Guidelines:
The answer NA means that the authors have not reviewed the NeurIPS Code of Ethics. If the authors answer No, they should explain the special cireumstances that require deviation from the Code of Ethics.
The authors should make sure to preserve anonymity (e.g.. if there is special consid- eration due to laws or regulations their jurisdiction).
10. Broader impacts
Question: Does the paper discuss both potential positive societal impacts and negative societal impacts of the work performed?
Answer: [Yes]
Justification: In Section 6, we reflect on some of the broader implications of our work, both positive and negative.
Guidelines:
The answer NA means that there no societal impact of the work performed.
If the authors answer NA or No, they should explain why their work has no societal
impact why the paper does not address societal impact.
Examples of negative societal impacts include potential malicious unintended uses (e.g.. disinformation, generating fake profiles, surveillance), fairness considerations (e.g., deploymeet of technologies that could make decisions that unfairly impact specific groups), privacy considerations, and security considerations.
The conference expects that many papers will be foundational research and not tied to particular applications, let alone deployments. However, if there is a direct path to any negative applications, the authors should point it out. For example, it is legitimate to point out that an improvement in the quality of generative models could be used to generate deepfakes for disinformation. On the other hand, it is not needed to point out
35

---

that a generic algorithm for optimizing neural networks could enable people to train
models that generate Deepfakes faster.
The authors should consider possible harms that could arise when the technology is being used intended and functioning conrectly, harms that could arise when the technology is being used as intended but gives incorrect results, and harms following from (intentional unintentional) misuse of the technology.
If there are negative socictal impacts, the authors could also discuss possible mitigation strategies (c.g., gated release of models, providing defenses in addition to attacks, mechanisms for monitoring misuse, mechanisms to monitor how system learns from feedback over time, improving the efficiency and accessibility of ML).
11. Safeguards
Does the paper describe safeguards that have been put in place for responsible release of data models that have high risk for misuse (e.g., pretrained language models, image generators, or scraped datasets)?
Question:
Answer: [Yes]
Justification: In Section 6, propose measures for preventing the misuse of our methods.
Guidelines:
The answer NA means that the paper poses no such risks.
Released models that have a high risk for misuse or dual-use should be released with necessary safeguards to allow for controlled use of the model, for example by requiring that users adhere to usage guidelines or restrictions to access the model or implementing safety filters.
Datasets that have been scraped from the Internet could pose safety risks. The authors
should describe how they avoided releasing unsafe images. We recognize that providing effective safeguards is challenging, and many papers do not require this, but we encourage authors to take this into account and make best faith effort.
12. Licenses for existing assets
Question: Are the creators or original owners of assets (e.g.. code, data, models), used in the paper. properly credited and are the license and terms of use explicitly mentioned and properly respected?
Answer: [Yes]
Justification: We cite the sources of the datasets, and the sources for the key pieces of software used for the experimental evaluations in Appendix G.
Guidelines:
The answer NA means that the paper does not use existing assets.
The authors should cite the original paper that produced the code package or dataset.
The authors should state which version of the asset is used and, if possible, include URL
The name of the license (e.g., CC-BY 4.0) should be included for each asset. For scraped data from a particular source (e.g., website), the copyright and terms of service of that source should be provided.
If assets are released, the license, copyright information, and terms of use in the package should be provided. For popular datasets, paperswi phporswithcode. thcode. com com/datasets
has curated licenses for some datasets. Their licensing guide can help determine the license of dataset.
For existing datasets that re- re-packaged, both the original license and the license of the derived asset (if has changed) should be provided. If this information is not available online, the authors are encouraged to reach out to the asset's 's creators.
13. New assets
Question: Are new assets introduced in the paper well documented and is the documentation provided alongside the assets?
Answer: [NA]
Justification: [NA]
36

---

Guidelines:
The answer NA means that the paper does not release new assets. Researchers should communicate the details the dataset/code/moodl as part their
submissions via structured templates. This includes details about training, license, limitations, etc.
The paper should discuss whether and how consent was obtained from people whose
asset is used.
At submission time, remember anonymize your assets (if applicable). You can either create an anonymized URL or include an anonymized zip file.
14. Crowdsourcing and research with human subjects
Question: For crowdsourcing experiments and research with human subjects, does the paper include the full text of instructions given participants and screenshots, if applicable, as well as details about compensation (if any)?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Including this information the supplemental material is fine, but if the main contribu-
tion of the paper involves human subjects, then as much detail as possible should be included the main paper.
According to the NeurIPS Code Ethics, workers involved in data collection, curation, other labor should be paid at least the minimum wage in the country of the data collector.
15. Institutional review board (IRB) approvals equivalent for research with human subjects
Question: Does the paper describe potential risks incurred by study participants, whether such risks were disclosed to the subjects, and whether Institutional Review Board (IRB) approvals (or equivalent approval/review based the requirements of your country or institution) were obtained?
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the paper does not involve crowdsourcing nor research with
human subjects.
Depending on the country in which research is conducted, IRB approval (or equivalent)
may be required for any human subjects research. If you obtained IRB approval, you should clearly state this in the paper.
We recognize that the procedures for this may vary significantly between institutions and locations, and expect authors to adhere the NeurIPS Code of Ethics and the guidelines for their institution.
For initial submissions, do not include any information that would break anonymity (if applicable), such the institution conducting the review.
16. Declaration of LLM usage
Question: Does the paper describe the usage of LLMs if it is an important, original, or non-standard component of the core methods in this research? Note that if the LLM is used only for writing, editing, formatting purposes and does not impact the core methodology, scientific rigorousness, or originality of the research, declaration is not required.
Answer: [NA]
Justification: [NA]
Guidelines:
The answer NA means that the core method development in this research does not involve LLMs as any important, original, or non-standard components. Please refer to our LLM policy (ht /ttps:///eeiip... /eteerrpp..c//oofeereeee//////// what should or should not be deseribed.
for
37


Reviews:
[{"review_id": "B11sOKWuS1", "reviewer": "Reviewer_gnWx", "summary": "This paper proposed an unified view for the success of reconstruction/re-identification/attribute inference attacks through f-DP. The key technical insight is that the properties of f-DP, most importantly post-processing and convexity of the trade-off function, can be used to form a single upper bound on the success of all the aforementioned attacks based on the attacker's baseline success probability. Authors show numerically that the proposed bound provides a more meaningful upper bound than the earlier works.", "questions": "1. Authors could further discuss the connection on the attacks to the DP threat model. In the various security definitions, the unknown sample $z$ is averaged over, while in DP threat model we consider the threat as the supremum of the privacy loss over the $z$. This might make it easier to see the exact connection between the protection against MIA that (f-)DP provides and the threats considered in the attacks.\n2. Authors could add a more detailed description of the singling-out attack. It is somewhat difficult to parse from Definition 3.1., so some general description would make it easier to follow.", "limitations": "yes", "rating": 5, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "## Strengths\n- Deriving tight translations of DP (or f-DP guarantees) to attacks other than membership inference is an important task. With a better characterization of the privacy threats, analyst can better calibrate their noise levels for the private release. As an example of this, authors demonstrate how you can obtain the same operational privacy risk but with significantly reduced noise compared to the prior work. (**Significance + Originality**)\n- The proposed theorems give simple expressions for upper bound for the attack success, only dependent on the baseline vulnerabilities. (**Clarity + Quality**)\n\n## Weaknesses\n- Some empirical experiments on attacks would have strengthened the paper, allowing the reader to better understand the gap between the upper bounds and actual real-world risks. (**Significance**)", "was_revised": true, "final_justification": "Authors response addresses all my concerns. I'm especially happy with the proposed clarity update regarding the threat model discussion, which I expect authors to include in the revised version of the paper. I retain my original positive evaluation that the paper presents an interesting and novel perspective on unifying various notions or privacy threats.", "rebuttal": "Thank you for the review and for the positive assessment of our work. We address your questions and comments next.\n\n_____\n\n> Some empirical experiments on attacks would have strengthened the paper, allowing the reader to better understand the gap between the upper bounds and actual real-world risks. \n\nWe could not run new evaluations for this rebuttal period, but prior work in DP auditing has extensively studied the tightness of the theoretical bounds w.r.t. empirical attacks, and showed that modern accountants such as those that we rely on provide analyses that are essentially tight in the strong threat models. However, within weaker threat models it is unlikely that these bounds are reached. We are thinking of adding the following in Section 6 (Concluding remarks) to clarify this:\n\n_**Practical tightness of the bounds.** Prior work (see, e.g., Nasr et al., 2023) has shown that the $f$-DP curves obtained using state-of-the-art accounting techniques are nearly tight in the worst-case threat models, i.e., we can construct worst-case attacks whose success rates match the theoretically predicted success rates. In more realistic threat models, attacks are unlikely to reach these success rates. Obtaining analyses of risks under relaxed threat models (see, e.g., [Kaissis et al. 2023](https://openreview.net/pdf?id=BRSgVw85Mc), [Swanberg et al., 2025](https://arxiv.org/abs/2507.08158)) is an important direction for future work._\n\n_____\n\n> Authors could further discuss the connection on the attacks to the DP threat model. In the various security definitions, the unknown sample is averaged over, while in DP threat model we consider the threat as the supremum of the privacy loss over.\n\nThis is a good point. The DP threat model is slightly different from the strong-adversary threat model that we consider. In our model, the adversary has a prior distribution over the target record $z$, whereas in the DP threat model the adversary has the target record $z$. Moreover, it was indeed implicit in the discussion of our threat model that the adversary’s goal is to construct an attack with a high success rate on average over the prior. To clarify this, we will add the following (bold) in Sec. 3.1 (Threat model):\n\n_We focus on the risk within the strong threat model in which the adversary has access to the workings of the privacy-preserving algorithm, has access to the partial dataset except for one target record, and has side information about the remaining element in the form of a prior distribution. **Note that the difference with the standard threat model of SMIA (Sec. 2) is that we do not assume that the adversary knows the target record. To quantify the adversary’s success rate, we consider expectations over the prior distribution as well as over the randomness of the algorithm, as we detail next.**_\n\nTaking a supremum over the prior is also a possibility, and should yield a meaningful notion of risk that is still prior-dependent (however, only through the support of the prior distribution), but more pessimistic. This could be related to the notion of maximal leakage ([Issa et al., 2018](https://arxiv.org/abs/1807.07878)), or, equivalently, Sibson’s mutual information, between $X$ and $Y$, where $X \\sim P$ and $Y \\sim M(\\bar S \\cup \\\\{X\\\\})$. Indeed, maximal leakage has an attack interpretation, also depends on $X$ only through its support, and is bounded by DP. Thus, it could be a possible direction for modifying the standard risk notions that we consider to be more pessimistic, and is an interesting direction for future work.\n\n____\n\n> Authors could add a more detailed description of the singling-out attack. It is somewhat difficult to parse from Definition 3.1, so some general description would make it easier to follow.\n\nIn fact, we do include a more detailed description of singling out in Appendix B.2.\n\n____\n\nLet us know if we can clarify anything else."}, {"review_id": "7LWlDVjYWS", "reviewer": "Reviewer_7rsk", "summary": "This paper derives an upper bound on the success probability of any strong adversary against an $f$-DP mechanism. The bound is general—applicable to reconstruction, attribution, and other attack types—and is expressed relative to a chosen baseline. This formulation offers flexibility: for high-risk models one can adopt a universal worst-case baseline, while for lower-risk settings a more specific baseline yields a tighter bound. Empirically, the authors demonstrate that their bound strictly improves on existing Rényi-DP-based bounds for reconstruction attacks.", "questions": "Can the authors please elaborate on whether the proposed baseline‐dependent bound can be used to empirically audit differential privacy, and if so, how this would be carried out?\n\nAdditionally, in many settings, the f function relies on numerical procedure to compute and does not have close form solution, does that affect the interpretation of the results?", "limitations": "Yes", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n\n- The proposed upper bound sheds light on how to DP parameters to defend against specific privacy attacks, a key obstacle to the practical adoption of differential privacy.\n- The authors derive an upper bound on any adversary’s success rate and demonstrate that this bound is tighter than existing reconstruction‐attack bounds. \n\n**Weaknesses**\n\n- The f-DP bound may not extend straightforwardly to mechanisms beyond simple Laplace or Gaussian noise; for example, its tightness under composition (as in DP-SGD) is unclear.\n- Although the bound gains flexibility by depending on a baseline attack, how to select an appropriate baseline remains an open question.", "was_revised": true, "final_justification": "I believe this paper addresses a practical question often raised in DP applications and provide a way to interpret DP parameter in terms of different attack success rates. Their theoretical bounds are tighter than existing ones.\n\nMy main concern— the efficiency and accuracy of the f-DP accountant on more complex mechanisms (and their compositions)— is addressed in the rebuttal. Therefore, I maintain my score and lean toward acceptance.", "rebuttal": "Thank you for the review. The review highlighted two weaknesses:\n1.  _Tightness and applicability of $f$-DP analyses is unclear._ In the response, we provide evidence that the tools for analyzing mechanisms in terms of $f$-DP are reliable, precise, and are applicable to many if not most practical DP algorithms in ML.\n2. _It is unclear how to select the baseline._ We will add examples for how one could select baselines when evaluating risk using our framework in the manuscript. We note that baseline dependence is not unique to our work, and prior work both on singling out and reconstruction robustness uses notions that are equivalent to baseline risks.\n\nWe provide details next.\n_____\n## Tightness and applicability of $f$-DP accounting\n\n> The f-DP bound may not extend straightforwardly to mechanisms beyond simple Laplace or Gaussian noise\n\nThis concern is not well-founded, and we explain why next. The trade-off curve is theoretically equivalent to the privacy profile $\\varepsilon(\\delta)$, i.e., the set of all attainable $(\\varepsilon, \\delta)$ parameters, and these two representations can be losslessly converted between each other in practice via convex conjugation (see [Dong et al., 2022](https://arxiv.org/abs/1905.02383)). Recent privacy accounting tools provide tight privacy profiles for a large variety of practical mechanisms under adaptive composition, including DP-SGD.\n\nIn particular, we use the Connect-the-Dots accountant ([Doroshenko et al. 2022](https://arxiv.org/abs/2207.04380)) which can compute precise privacy profiles for arbitrary adaptive compositions of Gaussian, Discrete Gaussian, Subsampled Gaussian, Mixture-of-Gaussians, Laplace, Discrete Laplace, and Randomized Response mechanisms. This covers a large class of DP algorithms. \n\nWhile some notable DP algorithms cannot yet be analyzed with state-of-the-art accountants, e.g., PATE ([Papernot et al., 2017](https://arxiv.org/abs/1610.05755)) or AIM ([McKenna et al., 2022](https://arxiv.org/abs/2201.12677)), even in these cases, our bound is applicable through a known conversion from Rényi DP or zCDP to $f$-DP (e.g., [Zhu et al., 2021](https://arxiv.org/abs/2106.08567)). \n\n> for example, its tightness under composition (as in DP-SGD) is unclear.\n\nIt is well-established in prior work, e.g., [Nasr et al., 2023](https://arxiv.org/abs/2302.07956) that modern accountants provide analyses that are essentially tight in the strong threat models. We will clarify by extending and rearranging the discussion with the text in bold in Sec 3.4:\n\n_For more complex, e.g., composed, algorithms such as DP-SGD (Abadi et al., 2016), there are two ways to obtain the corresponding $f$ curve. First, we can estimate it using Eq. (2) from the privacy profile of the algorithm (Balle et al., 2018), i.e., the set of all attainable ($\\varepsilon, \\delta)$-DP pairs. This method has been used for privacy auditing previously (Nasr et al., 2023). Second, it is possible to analyze DP-SGD or other algorithms that are compositions of (subsampled) Gaussian and Laplace mechanisms using a direct method (Kulynych et al., 2024). **Both approaches provide tight analyses when using state-of-the-art accounting tools as a backbone, such as the Connect-the-Dots accountant (Doroshenko et al. 2022). In particular, prior work (Nasr et al., 2023) has shown that the upper bounds on privacy leakage obtained with the modern accounting techniques (see, e.g., Gopi et al., 2021; Alghamdi et al., 2022; Doroshenko et al., 2022) can be nearly reached by empirical attacks in the strong-adversary MIA threat model.**_\n\n> the $f$ function relies on numerical procedure to compute and does not have close form solution, does that affect the interpretation of the results?\n\nThe methods described above guarantee that the numerically estimated $\\tilde f$ under composition is correct, that is, it is guaranteed that $\\tilde f$ is a tight lower bound on the the trade-off curve for the mechanism (Doroshenko et al., 2022, Kulynych et al., 2024). Thus, the fact that the $f$ curves are numerically computed does not affect the correctness of the results or the safety of the mechanisms, up to numerical precision.\n\n_______\n## Choosing baseline risk\n\n> Although the bound gains flexibility by depending on a baseline attack, how to select an appropriate baseline remains an open question.\n\nThis is a fair point, however we believe that the tunability of our bounds based on the baseline probability is a strength, not a weakness. Our results enable practitioners to obtain a more precise risk assessment when such a baseline estimate is available, or use the baseline-independent bounds otherwise. We will add additional intuition on how to estimate the baseline in Sec. 3.4 (Tunability).\n\nAs an example, consider releasing outputs of a mechanism trained on tabular medical data which contains a column corresponding to a patient’s HIV status. In this case, we might want to evaluate the risk of an adversary inferring the HIV status under standard threat models considered when releasing medical data ([El Emam, 2010](https://ieeexplore.ieee.org/abstract/document/5470957)) such as _“marketer”_ or _“journalist”_. For instance, the baseline risk of a ”marketer” adversary – who does not target any specific individual – could be modeled as guessing based on the prevalence of HIV in the population. The baseline risk of a ”journalist” adversary – who is assumed to be able to obtain side information on the target from public sources – could be modeled as guessing based on a target patient’s demographics.\n\nThis approach could also be extended to having a distribution over the possible baselines, as studied in prior work in the context of Bayesian interpretation of $f$-DP ([Kaissis et al., 2024](https://arxiv.org/abs/2406.08918)).\n\n> Can the authors please elaborate on whether the proposed baseline‐dependent bound can be used to empirically audit differential privacy, and if so, how this would be carried out?\n\nAbsolutely. One would compare an empirical estimate of attack success (e.g., with a Clopper-Pearson confidence interval if the attack success is binary) against the baseline risk. This is a common approach in auditing (see, e.g., [Nasr et al., 2021](https://arxiv.org/abs/2101.04535)). As in auditing we control the canary addition to the training data set, we could sample the canaries according to a specially constructed prior distribution that would enable easy analytical computation of baseline risk, e.g., uniformly from a discrete set $P \\sim \\mathsf{Unif}\\\\{ c_1, c_2, \\ldots, c_k \\\\}$, in which case the baseline risk of, e.g., an exact reconstruction attack, is $\\mathsf{base} = 1/k$. In this case, if we observe that the Clopper-Pearson  $(1 - 2\\alpha)$-lower confidence bound of the success of exact reconstruction is greater than $1 - f(\\mathsf{base})$, then we can reject the hypothesis that DP is implemented correctly at significance $\\alpha$. \n______\n\nWe are happy to clarify any further points."}, {"review_id": "NCy0IZuOTh", "reviewer": "Reviewer_GSiV", "summary": "A problem when evaluating the privacy risks is that there is not a unified privacy risk calibrating framework for different type of threats, i.e., re-identification, attribute inference, etc. In this paper, the authors borrow f-dp to build an unified privacy-risk evaluation framework for these risks.", "questions": "To my understanding, you design a new risks bounding mechanism which takes the noises, algorithms, baseline success rate as inputs and outputs the theoretical attacking advantage. Is my understanding correct?", "limitations": "No", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 3, "clarity": 3, "significance": 3, "originality": 3, "strengths_and_weaknesses": "Strength:\n\n1. The problem itself is interesting.\n\n\nWeakness:\n\n1. The presentation is not clear enough to follow. For instance, in figure 1, what does $\\frac{\\text{re-identification}}{\\text{attribute inference}}$ mean? Does it mean re-identification \\textbf{or} attribute inference? And what does the f(x) mean in this figure?\n\nI also recommend the author present a notation table to unify the symbols used in the paper.\n\n2. Please convince me the practical reason and need of unifying the different type of risks. To my understanding, membership inference attacks, which are the most easy attacks, is proper to evaluate the privacy risks. For instance, other high-level attacks, e.g., inversion attacks, are harder to apply than membership inference attacks if the adversary has the same level of ability. In this case, if we observe an low membership inference, other type of risks should be smaller. We only need to bound the membership inference risks, why we need to bound other type of risks?", "was_revised": true, "final_justification": "The response addresses most of my concerns. I think unifying the different types of risks is meaningful for the practical usage of DP. For instance, it's possible to more tightly estimate the practical privacy risk behind training data and thus value the data privacy.", "rebuttal": "Thank you for the review. In this rebuttal, we explain:\n- That the problem of quantifying privacy risk in terms of notions of risk that are not membership inference is important in many practical applications.\n- That we have extensively shown with experiments in Sec. 4 and App. G that the unification of different notions of risks _under $f$-DP_ enables one to obtain better utility at the same level of risk in DP, sometimes increasing accuracy by double digits. \n\nWe detail on these and other points raised in the review next.\n________\n\n### MIAs vs. other risks\n\n> To my understanding, membership inference attacks, which are the most easy attacks, is proper to evaluate the privacy risks.\n\nIn data-protection practice, membership inference is far from the main threat considered. For instance, the guidelines from ISO and European Medicines Agency mention re-identification/singling out and inference risks (see L33 in the Introduction), and, as a salient example, in the medical domain, stakeholders are most likely to be concerned about data reconstruction rather than membership inference ([Ziller et al., 2025](https://www.nature.com/articles/s42256-024-00858-y)). Moreover, the notion of reconstruction robustness is also standard in the literature on ML privacy (there are 200+ citations of the work by [Balle et al., 2022](https://arxiv.org/abs/2302.07225) who introduced the definition we use).\n\n>  if we observe an low membership inference, other type of risks should be smaller\n\nYour intuition is correct, but this fact has not been formalized in a precise way previously. Indeed, that all of the standard risk notions (singling out, attribute inference, data reconstruction) can be bounded with the error rate of a binary decision problem which is equivalent to a success rate of the strong-adversary membership inference attack, _(1) is non-trivial, (2) has not been known prior to our work, and (3) is exactly our main result._\n\n> Please convince me the practical reason and need of unifying the different type of risks. \n\nWe do not unify the different types of risk just for the unification’s sake (even though it makes the bounds convenient to use in practice). The primary benefit is that by unifying them under the framework of f-DP, we can provide _substantially_ more precise analyses of risk. Where prior techniques might have indicated that a given algorithm provides no privacy protection whatsoever, our analysis could indicate very low risk (e.g., compare red and orange in Fig. 1 for an example of an analysis of singling out risk). Therefore, if one were to use a prior technique to decide whether data or model sharing is safe, in that case they would likely decide against it and possibly had applied more noise, further hurting utility. Because our analyses provide substantially more precise risk analyses, our method enables data and model sharing with high utility in tightly regulated settings, e.g., in healthcare or financial domains, where data and model releases must not exceed a certain level of privacy risk.\n\n\n________\n\n### Presentation\n\n> Presentation issues in Figure 1.\n\n$f(x)$ is exactly the $f$ in f-Differential Privacy (see the second sentence of the caption and Sec. 2 for the definition). We realize that the stack in the figure could be interpreted as a ratio, which we will fix by changing the line style. The stack signifies the fact that in both the success term (top) and the baseline term (bottom) we can pick any of the three standard types of privacy risk. If you have any suggestions on improving this illustration, we would be very happy to consider them.\n\n> I also recommend the author present a notation table.\n\nAbsolutely, we will add one to the appendix.\n\n\n__________\n\n### Questions\n\n> To my understanding, you design a new risks bounding mechanism which takes the noises, algorithms, baseline success rate as inputs and outputs the theoretical attacking advantage. Is my understanding correct?\n\nYes. To be a bit more precise, given those, our method outputs maximum attainable attack advantage due to mechanism release within the strong-adversary threat model (see Theorem 3.3). Experimentally, we also show that this method is substantially more precise than existing standard methods to conduct similar analyses, and that it enables to attain significantly higher utility when calibrating the algorithm’s parameters (noise) to a given level of risk.\n\n___________\nLet us know if we can clarify anything else."}, {"review_id": "0RhRuJz4Bx", "reviewer": "Reviewer_YNGr", "summary": "This paper introduces a framework for interpreting and calibrating DP guarantees in terms of concrete privacy risks. The main contribution is the use of the $f$-DP formalism to derive a single, unified bound on the success of re-identification, attribute inference, and data reconstruction attacks. The authors propose that for all three risks, the attack success probability is bounded by the formula $\\text{succ} \\le 1 - f(\\text{base})$, where $\\text{base}$ is the adversary's maximum success probability without the mechanism's output. The paper argues that this unifying framework provides bounds that are 1) consistent across risks, 2) tunable to specific baseline threats, and 3) empirically tighter than prior methods, which further allows for better utility.", "questions": "N/A", "limitations": "No, the authors did not discuss the limitations of their work. I believe the authors should acknowledge that the bound is only applicable to risks that can be framed as a hypothesis test within the strong adversary model, but may not address other important and practical privacy risks that arise in modern machine learning.", "rating": 4, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": 2, "clarity": 2, "significance": 3, "originality": 2, "strengths_and_weaknesses": "**Strengths**\n- An elegant and theoretically principled way to tightly bound different privacy risks\n- Promising empirical results\n\n**Weaknesses**\n\nDespite its strong core idea, the paper falls short in several important issues:\n- **Insufficient positioning and comparison to state-of-the-art.**  \n  - The paper fails to position its conceptual contribution with respect to prior work on risk-based calibration. The general idea of calibrating DP noise to a desired level of operational risk has been explored previously, in particular in [1]. While the current work uses the method from that paper as a tool, it fails to discuss the conceptual overlap and clarify what novel contributions it offers to the idea of attack-aware calibration itself.\n  - The paper's central claim of providing \"*tighter estimates of risk compared to prior methods*\" is not backed by comparisons with the state-of-the-art for each specific risk. Most notably, for data reconstruction attacks under DP-SGD, the paper compares its bounds to Balle et al. (2022) but omits the more recent work [1], which provides nearly matching upper and lower bounds on reconstruction, suggesting their bound is already very tight. Without a direct comparison, it is impossible to assess if this paper's bound offers a meaningful improvement over the best-known specialized bound. \n  - I don't think unification is a primary contribution of this paper. To me this is just a direct and unsurprising consequence of defining all risks within the same strong-adversary threat model native to DP. Even a single $(\\varepsilon, \\delta)$-DP guarantee can be translated into an unified upper bound ($\\frac{e^{\\varepsilon}+\\delta}{e^{\\varepsilon}+1}$). Therefore, the novelty does not lie in the unification itself, but rather in the use of $f$-DP to achieve tighter bounds. \n- **Lack of motivation for the $f$-DP framework.**  The paper fails to adequately explain why the $f$-DP framework is more powerful and capable of producing tighter bounds. A critical point (in my view) is that a single $(\\varepsilon, \\delta)$ pair is an incomplete characterization of a mechanism's privacy guarantees. By compressing a full privacy profile into one point, prior analyses lose information, leading to looser bounds. This is in contrast to the $f$-DP framework based on the trade-off curve, which provides a complete characterization. This motivation is critical and should be a more central part of the paper's narrative.\n- **Overstatement.**  The authors overstate the generality of their results by claiming that \"*By bounding the success of the strong adversary, we automatically bound the success of attacks under any other threat model that is weaker or more realistic*\". This claim is only valid for threat models that are strict subsets of the strong adversary model. However, many practical privacy risks, such as training data extraction (or verbatim memorization) from language models, operate under entirely different adversarial assumptions; DP and $f$-DP might not easily translate to an upper bound for these attacks (see [2]). These threat models are not necessarily \"weaker\", but rather orthogonal. The paper should be more precise and qualify its claims, acknowledging that its framework provides tight bounds for risks that can be framed as a hypothesis test within the strong adversary model, but may not address other important, practical privacy risks that fall outside this specific formulation.\n- **Clarity of presentation and notation.** The paper's notation is dense and its definitions of risk are difficult to parse without significant effort. The concept of \"baseline success\" is not built up with sufficient intuition in the main body. For the work to be broadly accessible and impactful, a clearer, more streamlined presentation is needed to explain what the baseline represents and how a practitioner should reason about it.\n\n\n**References**\n\n[1] Kulynych, Bogdan, et al. \"Attack-aware noise calibration for differential privacy.\" Advances in Neural Information Processing Systems 37 (2024): 134868-134901.\n\n[2] Hayes, Jamie, Borja Balle, and Saeed Mahloujifar. \"Bounding training data reconstruction in dp-sgd.\" Advances in neural information processing systems 36 (2023): 78696-78722.\n\n[3] Hu, Yuzheng, et al. \"Empirical Privacy Variance.\" arXiv preprint arXiv:2503.12314 (2025).", "was_revised": true, "final_justification": "I believe this paper presents a solid work and will be of interest to people working on DP. I am therefore leaning towards acceptance.", "rebuttal": "Thank you for the review and for the detailed feedback. We address your comments and questions grouped by topic.\n\n______\n\n\n## The relation to the idea of attack-aware calibration\n\n> The paper fails to clarify what novel contributions it offers to the idea of attack-aware calibration itself\n\nTo clarify this, we will add the following in Section 5 (Related Work):\n\n\n_Kulynych et al., 2024 introduced _attack-aware calibration_, the idea of calibrating DP algorithms to a given level of operational attack risk in contrast to the standard practice of calibrating to a given pair of $(\\varepsilon, \\delta)$ parameters. They evaluated this approach for the use case of calibrating noise to a given level of membership inference risk. One of the applications of our result is that it extends the toolbox of attack-aware calibration to further attack risks, thus enabling practitioners to calibrate DP algorithms to notions of risk beyond membership inference, which often appear in data protection guidelines (see Sec. 1)._\n\n_______\n\n## The relation to Hayes et al. (2024)\n\n> the paper compares its bounds to Balle et al. (2022) but omits the more recent work [1], which provides nearly matching upper and lower bounds on reconstruction.\n\nWe assume there was an incorrect reference here and the reviewer meant Hayes et al. (2024), as we were unable to find lower bounds in [1]. \n\nThere are several core differences of our unified bound results to the method introduced by Hayes et al: (1) they provide a Monte-Carlo sampling-based method rather than a provable bound, (2) their method is specific to DP-SGD, and (3) it only covers reconstruction attacks. In contrast, our work focuses on the fundamental connection between different standard types of risks and the $f$-DP framework, as opposed to providing an approximate method to evaluate a specific type of privacy risk in DP-SGD. Our approach enables us to obtain _provable bounds on risks for general DP mechanisms_. Even though the theoretical underpinnings of our approaches are different, the outputs of the algorithm from Hayes et al. will asymptotically (in the limit of infinite Monte-Carlo samples) converge to our $f$-DP bound in the setting of reconstruction risk in DP-SGD. \n\nWe will make this clear by adding the above in our discussion of that work in Sec. 5 (Related Work).\n\n\n________\n\n## Limitations of the strong-adversary threat model\n\n> The authors overstate the generality of their results by claiming that _\"By bounding the success of the strong adversary, we automatically bound the success of attacks under any other threat model that is weaker or more realistic\"_\n\nThis is a legitimate concern! There certainly are risks to the privacy of individuals whose information is present in the training data that could still exist under DP when it is not an appropriate tool to ensure privacy protection. As the reviewer pointed out, this could be the case when training on public text data from the internet (see, e.g., [Brown et al, 2022](https://arxiv.org/pdf/2202.05520)), where it is not feasible to meaningfully delineate the privacy unit.\n\nImportantly, however, the cited sentence does _not_ overstate the claims of our paper, but rather _inaccurately describes the implications of the standard strong-adversary threat model._ What we wanted to say there is that under the basic assumption – that the privacy unit and, therefore, the neighbourhood relation, are meaningful – the success of the strong-adversary MIA must bound in some way the relative increase in success of _any possible attack_ against the considered privacy unit due to the release of the mechanism outputs. This is a consequence of the fundamental decision-theoretic result known as Blackwell’s informativeness theorem (see, e.g., Theorem 2.10 in [Dong et al., 2022](https://arxiv.org/pdf/1905.02383) for its application to DP).\n\nWe will make the following changes to make the description more precise. First, we will add the clarifications (in bold) in L84:\n\n_We say that two datasets $S, S’$ are neighbouring if they belong to a neighborhood relation denoted as $S \\simeq S’$. **To capture meaningful concerns in privacy of the training data, this relation must correspond to adding, removing, or replacing all of the data that belongs to a single _privacy unit_, e.g., individual or secret. In the rest of the paper, we follow the standard practice and assume that the privacy unit corresponds to a single record.**_\n\nand in L136:\n\n_By bounding the success of the strong adversary, we **also bound the success of attacks against the considered privacy unit that rely on the mechanism output $M(S)$ under other threat models that are weaker or more realistic.**_\n\n> I believe the authors should acknowledge that the bound is only applicable to risks that can be framed as a hypothesis test\n\nWe agree it’s a good call to acknowledge the fundamental limitations of the protection that DP can provide. As we explained before, however, reduction to a hypothesis test is a universal property of any notion of relative success of an attack against the privacy unit due to the mechanism output, as an implication of Blackwell’s informativeness theorem. We propose the following addition to Section 6, which we believe is more accurate:\n\n_**Fundamental limits of DP.** Our bounds on the relative increase in attack success are meaningful only insofar that DP is an appropriate tool and is implemented correctly. For instance, in some applications such as training of language models on open internet data, it might not be practically feasible to define a neighborhood relation in a way that meaningfully captures privacy of individuals, as the sensitive data of any one individual can appear in different forms across multiple documents (see, e.g., [Brown et al, 2022](https://arxiv.org/pdf/2202.05520))._\n\n________\n\n## Clarity\n\n> The concept of “baseline risk” is not built up with sufficient intuition\n\nThis is a good point. We will add additional intuition in Sec. 3.4 (Tunability). As an example, consider releasing outputs of a mechanism trained on tabular medical data which contains a column corresponding to a patient’s HIV status. In this case, we might want to evaluate the risk of an adversary inferring the HIV status under standard threat models considered when releasing medical data ([El Emam, 2010](https://ieeexplore.ieee.org/abstract/document/5470957)) such as _“marketer”_ or _“journalist”_. For instance, the baseline risk of a ”marketer” adversary – who does not target any specific individual – could be modeled as guessing based on the prevalence of HIV in the population. The baseline risk of a ”journalist” adversary – who is assumed to be able to obtain side information on the target from public sources – could be modeled as guessing based on a target patient’s demographics.\n\nWe note that the baseline dependence is not unique to our work, and is in fact fundamental if one cares about obtaining tight bounds on risk. Prior work both on singling out and reconstruction robustness uses notions that are equivalent to baseline risks.\n\n> The paper's notation is dense\n\nFor all the notions of risk we follow the notation from prior work, and, arguably, slightly simplify the notation on singling out. Moreover, we simplify the presentation of our main results, deferring the exact statements to App. C.2 to focus on the high-level ideas in the main body. We are happy to consider any suggestions on simplifying the notation.\n\n________\n\n## On whether our main contribution is unification or the usage of $f$-DP \n\nWe agree that the use of $f$-DP is a significant component of our contributions. We would like to highlight, however, that in our work, the unification and the usage of $f$-DP are quite interconnected.\n\n>  I don't think unification is a primary contribution of this paper.\n\nWe do not unify the different types of risk _just for the unification’s sake_ (even though it makes the bounds convenient to use in practice). The primary benefit is that by unifying them _under the framework of $f$-DP,_ we provide _substantially_ more precise analyses of risk… \n\n\n> Lack of motivation for the f-DP framework.\n\n…and the reason why our bounds are tighter is exactly because we use f-DP and modern precise accounting techniques (see L219). We explicitly mention that this improvement is due to f-DP in L61 of the Introduction. As the prior work has already shown that f-DP enables tight bounds on operational notions of risk [1], we did not dwell on this point further. \n\nWe agree that we should further highlight the role of f-DP. In particular, we are thinking to add the following statement to the conclusions:\n\n\n_**Decision-theoretic analyses of DP mechanisms.** Our empirical and theoretical results demonstrate that the decision-theoretic view of DP via the $f$-DP framework is a useful tool for analyzing privacy-preserving algorithms in terms of operational risks. As we have shown, it enables both substantially tighter characterizations of privacy risk compared to other standard ways to quantify leakage such as Rényi DP or CDP, and easy-to-use unified analyses of various types of privacy risk._\n\n_________\n\nLet us know if we can clarify anything else."}]

Author rebuttal:

Meta-review: The paper develops bounds via f-DP on the (marginal) success rate of various attacks. Empirically, the theoretical bounds are shown to be tighter than previous bounds on a number of applications. Reviewers found the unified approach interesting and useful, and the main reservations are about practicality/extensions of the strong adversary model and the types of attacks studied in the paper.
Decision: Accept (poster)