Attack-Aware Noise Calibration for Differential Privacy

The neighbourhood relation is inconsistent: Section 2.1 describes substitute neighbourhood, while Section 2.2 describes add/remove neighbourhood.

Thank you for pointing this out! Our analyses are independent of the choice of the neighborhood relation, and our experiments are done with the add-remove relation. We will remove the substitution relation in Section 2.1 paragraph “Setup and notation”, mention that we use the add-remove relation in our experiments in Section 2.1, paragraph “DP-SGD”. Moreover, in Section 2.2 we will emphasize that our results are not tied to the add/remove relation.

TPR does not necessarily need to be high for a MIA to be a relevant threat. For example, if TPR = 1% at FPR = 0.01%, the attack can very accurately identify the presence of a small number of individuals, which violates the privacy of those individuals.

This is a great point! Ultimately, defining acceptable thresholds on TPR/FPR, as we mention in the Concluding Remarks, is an open problem. We note that acceptable thresholds can be made in a context and application specific manner. For example, from the computer security literature (see, e.g., Wang, 2018), we know that if the prior probability of membership is lower than the attack’s FPR, then the majority of the attack's positive predictions will be incorrect, even if TPR is 100% (Wang 2018, p.2; formally, prior-aware positive predictive value, ppv = P(member | attack predicts 'member') can be low even if TPR = P(attack predicts 'member' | member) is high, as it depends on the base rate P(member) and is more significantly influenced by FPR than TPR). Our framework fits nicely with this literature. If in a particular context we have a guess for the adversary’s prior probability, this can be used to inform an acceptable TPR/FPR thresholds.

We will expand the short discussion in the Concluding Remarks on this limitation as follows:

“We leave open the question on how to choose the target FPR $\alpha^\star$, e.g., whether standard significance levels in sciences such as $\alpha^\star = 0.05$ are compatible with data protection regulation, as well as what are the acceptable attack TPR levels for a given FPR. Future work is needed to develop concrete guidance on the choice of target FPR and TPR informed by legal and practical constraints.”

The results in Figure 1 could have uncertainty estimates.

Thank you for the suggestion. In the new experimental demonstration on private histogram release, described in the general response, we added uncertainty regions for utility measurements done over 100 mechanism runs with different random seeds.

Restating the theorems before their proofs and having the proofs in the same order as the main text would make the proofs much easier to read.

We will implement this in the final version!

---

Are $P$ and $Q$ the correct way around in Eq. (1)? They seem to be the other way around in Gopi et al. [2021].

$P$ and $Q$ are the correct way in Gopi et al. We will fix this in the final version.

Are the image classification results in Figure 1 comparable between standard and attack risk calibrations, since you had to use RDP due to data augmentations with the standard accountant?

Thank you for raising this point. We indeed agree that this comparison is somewhat unfair. We now reanalyzed the training pipeline from Tramer & Boneh, 2021 using Doroshenko et al. accounting so that the methods are exactly comparable. We provide the updated figure in the PDF attached in the general response. Indeed, the TPR values obtained with standard calibration and tight accounting are somewhat lower than with RDP accounting, especially in the small $\alpha$ regime, but the general trend remains: attack-aware calibration significantly increases task accuracy at the same risk level.

What type of subsampling and which neighbourhood relation did you use in the DP-SGD experiments?

We use the add-remove relationship in our experiments, as it is standard with modern accountants. We use Poisson sampling. The batch size in the experimental details is supposed to mean the expected batch size. To avoid confusion, we will clearly specify the neighborhood relation and write in the format “subsampling rate $p = 0.003801$ (corresponding to the expected batch size of 256)”.

Line 97: the domain and range of epsilon_omega are the wrong way around. Line 164: should this have $\alpha^\star$ instead of $\alpha$? Should the support of $Y$ in line 666 be $\\{y_1, …, y_{l+1}\\}$ instead of $\\{x_1, …, x_{l+1}\\}$? Line 649: $\phi$ outputs the probability that the sample came from $Q$. I don't think Algorithm 1, line 2 works with $\alpha = 1$, the strict inequality is never satisfied. Though this should be easy to fix.

That’s right, thank you so much for spotting these! We will fix them.

We would like to thank you for such a detailed reading of our work, and especially the proof! We appreciate it.

Theorem 3.4

Q1. In the reasoning around lines 673-675, why is it not possible that $\alpha$ just happens to be one of the possible values of Eq. (42)? On line 659, it is said that this reasoning should work for all $\alpha$. This case is considered explicitly later, but only after this line of reasoning is concluded.

We agree that this line of reasoning appeared too early in the proof. We will move it to the part of the proof where we only consider $\alpha$ that are not one of the possible values of the reverse CDF of $X$ in Eq. (42).

Q2. Doesn't the conclusion that there can be multiple ways values of $\gamma$ and $\tau$ that satisfy the constraint on line 695 imply that the choice of the optimal test is not unique, though the FPR and FNR are unique?

Not necessarily! What we are saying in line 695 is that the optimal test, which is unique, can have two different parameterizations: $(\tau_1 = x_t, \gamma_1 = 0)$ and $(\tau_2 = x_{t+1}, \gamma_2 = 1)$. That these two parameterizations yield the same test follows by observing that $\phi^*_{\tau_1, \gamma_1}(o)$ outputs 1 if $\log \frac{Q(o)}{P(o)} > x_t$ and 0 otherwise, while $\phi^*_{\tau_2, \gamma_2}(o)$ outputs 1 if $\log \frac{Q(o)}{P(o)} \geq x_{t+1}$ and 0 otherwise. Since the test statistic $\log \frac{Q(o)}{P(o)}$ lives on a discrete grid and cannot take on values between $x_t$ and $x_{t+1}$, it follows that $\phi^*_{\tau_1, \gamma_1}$ and $\phi^*_{\tau_2, \gamma_2}$ will classify each observation $o$ identically.

Q3. Why is the test that is found on lines 690-698 optimal?

Our response to Question 2 should address this concern as well. Lines 690-698 do NOT identify two distinct tests and choose one as the optimal without proof. Instead, lines 690-698 identify two different parameterizations for the unique and optimal test. One is free to choose either parameterization (or any other!) for implementation. In our implementation, we choose $(\tau_1 = x_t, \gamma_1 = 0)$. We will make this distinction between different parameterizations and different tests clear in the final version of the proof (see next).

Q4. It is not clear if Theorem 3.4 claims "for all" or "for some" $\gamma$ and $\tau$.

Theorem 3.4 indeed holds for all $\tau \in \mathbb{R}$ and $\gamma \in [0,1]$, and we will make this clear by specifying the “for all” quantifier. To clarify this in the proof, in each of the three studied regions of $\alpha$, we will specify (i) the optimal test and (ii) all possible parameterizations $(\tau, \gamma)$ for the optimal test, as described next.

In the case when $\alpha = 1$, we have only one possible parameterization for the optimal test: $(\tau = -\infty, \gamma = 0)$. When $\alpha$ is one of the $k+1$ values in Eq. 42, we have the two parameterizations in Question 2 along with a continuum $\{ (\tau, \gamma) \mid \tau \in (x_t, x_{t+1}), \gamma \in [0,1] \}$ if $t<k$, and $\{ (\tau, \gamma) \mid \tau \in (x_k, \infty), \gamma \in [0,1]\}$ if $t = k$. Finally, when $\alpha$ does not fall into any of the remaining categories, we have one unique parameterization $(\tau = x_t, \gamma = \text{Eq (49)})$ for all $t$.

This covers all $\tau \in \mathbb{R}, \gamma \in [0,1]$, and shows that Theorem 3.4 claims holds "for all'' parameter values.

Catastrophic Failures

Figure 5 shows that the $\delta'$ corresponding to the attack TPR/FPR calibration is very large compared to the standard $\delta$. The standard $\delta$ is chosen to be small, as the mechanism that randomly outputs one individual's data is $(0, 1/n)$-DP with $n$ datapoints. I think the paper should discuss how this mechanism behaves with the TPR/FPR calibration.

This is a great point that we thought about a lot, although a detailed discussion didn't make the final cut in this submission (it will be added to the revised version). The reviewer correctly notes that the standard convention of computing $\varepsilon$ for $\delta \ll \frac{1}{n}$ is based on the existence of an $(\varepsilon, \delta)$-DP mechanism allowing catastrophic failures with probability $\delta$. Given our calibration in Figure 5 allows for $\delta > \frac{1}{n}$, there exists a mechanism achieving our target TPR/FPR with a high probability of catastrophic failure, and the reviewer provided an example of such mechanism. However, we introduce our calibration approach in the context of choosing a noise scale $\omega$ for a given parameterized mechanism $M_\omega$. Most if not all practical mechanisms, including those we investigated (DP-SGD), do not admit catastrophic failures (see, e.g., this post). We argue that the existence of a mechanism achieving our TPR/FPR calibration with a high probability of catastrophic failure is irrelevant when calibrating the noise parameter $\omega$ of a specific mechanism that we know does not admit failures. Consequently, our methods should only be used for mechanisms without catastrophic failures. We will clarify this in the final version by adding the following paragraph in the Concluding Remarks:

“Our calibration algorithms are supposed to be used with mechanisms that do not admit catastrophic failures, i.e., those that ensure attack TPR of zero when FPR is also zero, or, equivalently, mechanisms whose trade-off curve is such that $T(M(S), M(S’))(0) = 1$ and $T(M(S), M(S’))(1) = 0$ for all $S \simeq S’$. Although practical mechanisms such as DP-SGD have this property, one can in principle construct mechanisms which do admit catastrophic failures (e.g., a “name-and-shame” mechanism which outputs one of the records in the clear [see, e.g., Aerni et al. 2024]). In such pathological cases, standard calibration should be used to ensure $\delta \ll \frac{1}{n}$.”

---

We respond to the minor points in the next comment.

Thank you for the comprehensive response. You addressed most of my concerns, most importantly those regarding the proof of Theorem 3.4.

Regarding my point about catastrophic failures, it seems that I didn't make my concern quite clear in the initial review. You are correct in saying that many mechanism do not actually allow the catastrophic privacy failure, so it may not be necessary to set a conservative TPR@FPR bound to account for them.

However, the same reasoning can be used to argue that we do not need $\delta \ll \frac{1}{n}$. As a result, the utility increase of TPR@FPR calibration over $(\epsilon, \delta)$-calibration seems to come from using this argument for one definition, but not the other. Reading the paper again, I noticed that you have alluded to this in the caption of Figure 5, but this point is important enough to discuss in the main text. Currently, the Abstract and Introduction give the impression that the utility benefit is due to some intrinsic difference between $(\epsilon, \delta$) and TPR@FPR bounds, and not simply a consequence of what values are typically considered acceptable for the bounds.

On the other hand, I recognise that calibrating to attack risk is useful, and your method for this calibration is much easier to use than first finding the optimal $(\epsilon, \delta)$-bound corresponding to the attack risk, and then calibrating the mechanism. As a result, the paper makes a valuable contribution, and I'm increasing my score accordingly.

Thank you for the review and suggestions!

Weaknesses

I suggest the authors include more downstream tasks and utility metrics to further demonstrate the effectiveness of the theoretical results.

We have added a new experiment on a common use case of DP – private histogram release – which shows that attack-aware noise calibration also enables to significantly reduce the error when privately releasing histograms. See the general response and the attached PDF for details.

High-level intuitions for different variables in Theorem 3.4, such as $\alpha(\tau, \gamma)$ and $\beta(\tau, \gamma)$, would be beneficial.

We will add the following lines after Theorem 3.4:

“The proof for Eq. (12) works by using the Neyman-Pearson lemma to explicitly construct the optimal most powerful attack at level $\alpha$. We parameterize the optimal attack in terms of intermediate parameters $\tau$ and $\gamma$, where $\tau$ is the threshold for the Neyman-Pearson test statistic and $\gamma$ is the probability of guessing in case the test statistic exactly equals the threshold.”

Questions

Will choosing a discrete-valued dominating pair of the mechanism be a sub-optimal choice for advantage calibration?

Any dominating pair, whether discrete or continuous, suffices for advantage calibration. Moreover, the results of Doroshenko et al. 2022 imply that a carefully-crafted discrete-valued dominating pair can provide arbitrarily tight privacy bounds to a continuous mechanism. Since we use the algorithm proposed by Doroshenko et al., the answer to this question is no: a discrete-valued dominating pair is not sub-optimal for advantage calibration.

How is the discretized PLRV typically obtained for a general mechanism?

In Appendix E, we detail the technique from Doroshenko et al. for constructing PLRVs for a general mechanism given its privacy curve. The technique discretizes the privacy profile curve, and builds pmfs of the dominating pair $P$, $Q$ using the discretized values. The distributions of the PLRVs can then computed using the pmfs of $P$, $Q$.

Thank you for your review and suggestions. We address some of points raised directly below, but they are also partially covered in our general response, to which we refer when relevant.

The notation in this paper is heavy, could you provide notation tables?

We agree. See the general response for the notation table.

Could you provide a more detailed algorithm in the appendix about how to use $\epsilon$, $\delta$ , and $q$ to generate Advantage Calibration’s $X_\omega$ , $Y_\omega$. It’s quite hard to follow in Section 3’s demonstration. I think authors need an algorithm to demonstrate how they did the experiment from the supplement's code.

In Section 3, following Theorem 3.4, we point to Appendix E for how we construct $X_\omega$, $Y_\omega$ for a general mechanism given its privacy curve. We will clarify in L226 as follows:

“Given a method for obtaining valid PLRVs $X_\omega$ , $Y_\omega$ for any $\omega$, such as the one provided by Doroshenko et al. 2022 (see Appendix E), …”

We want to emphasize to the reviewer that Appendix E is a summary of the algorithm proposed by Doroshenko et al. 2022, which we used in all of our experiments. Moreover, this algorithm uses the entire privacy curve and mechanism-specific functions such as $q$ to construct $X_\omega$, $Y_\omega$, not just a single $(\epsilon, \delta)$ pair.

Additionally, we provide a more detailed description of the steps involved in the calibration algorithms in the general response.

Thank you for the review and the suggestions! We respond to the comments and questions next. Note that we also address some of them in the general response, and we refer to it when relevant.

The paper includes numerous definitions and symbols, which can be confusing for readers. Creating a table to summarize these terms and explain their meanings would greatly enhance clarity and help readers follow along more easily.

See the general response for the notation table.

In Section 2, the problem statement is not clearly articulated, making it difficult to discern the main goal and the specific problem being addressed. Highlighting the main goal and explicitly defining the problem would make this section more readable and comprehensible.

The problem statement appears in the discussion of Section 2.3. We will highlight this more clearly in the final version, and change the title of Section 2.3 to “Our Objective: Attack-Aware Noise Calibration” to clearly signal that the problem statement is there. To be clear, our problem is to solve the calibration problem $\min \omega \text{ s.t. } risk_\omega \leq threshold$, in particular, by providing a method to efficiently compute $risk_\omega$ for standard notions of operational attack risk in DP.

Questions

In the experiment section, how about the results of other low FPR regimes?

See the attached PDF in the general response for the trade-off curves for all five models in the language modeling experiment. Using these curves, one can glean the behavior in terms of FPR/FNR trade-off for different levels of noise scale/task accuracy and for all $\alpha \in [0, 1]$ as opposed to $\alpha \in \{{0.01, 0.05, 0.1\}}$. We will add these plots in the Appendix in the final version.

Limitations

In Section 3.1, please include reference for ensuring advantage calibration in the appendix.

Eq. 13 in Section 3.1 shows (1) the optimization problem corresponding to advantage calibration and (2) how we compute advantage given dominating PLRVs $(X_\omega, Y_\omega)$. Moreover, in Appendix E we explain how to obtain $X_\omega, Y_\omega$ from an arbitrary mechanism given its privacy curve, and in Section 2.3 we explain how we solve an optimization problem in the form of Eq 13. In the final version, we will consolidate all this information into one algorithm in the Appendix, as showed in the general response.

The two figures at the top of page 7 lack figure names. It appears they should be labeled as Figure 2.

Thank you for spotting this issue! Indeed, this Figure is missing a caption. We will fix this in the final version.