Auditing Privacy Mechanisms via Label Inference Attacks

• Why are additive and multiplicative measures both needed?

The multiplicative measure is generally stronger, in that a small multiplicative advantage implies a small additive one, but not vice versa. We studied both additive and multiplicative measures for a few reasons. While the multiplicative measure is closer to the standard DP interpretation of privacy, the additive measure may be more naturally interpretable in terms of X% increase in inference risk. Besides, the additive measure is more generous to LLP, so the fact that DP mechanisms in practice outperform LLP even when we use the additive measure becomes even more surprising.

• Is the classifier calibrated? (See 823 in appendix)

As explained in LL. 823-836 in the appendix, we had initial experiments with both Deep Neural Network (DNN) architectures and k-Nearest Neighbor (kNN) classifiers. When trained with event-level (that is, non-private) labels, DNNs are not guaranteed to give rise to calibrated classifiers, while a kNN classifier is typically calibrated. Since we observed in our initial experiments that the two resulted in similar overall outcomes, we decided to go with DNNs as the underlying classifier throughout.

• How would you envisage these measures being applied? Would they be used to tune privacy parameters? Compare privacy-preserving mechanisms?

An organization that is considering multiple otherwise incomparable PETs could use our measures to 1) establish which one has the best privacy/accuracy tradeoff for the types of data and downstream tasks they’re concerned with, and 2) set privacy parameters according to their risk tolerance. For example, in our case, Figure 3 shows that RR achieves the best tradeoff for our setting. In addition, the curves can help with choosing epsilon in an informed manner, though of course the decision should consider other contextual factors, and more than one measure of advantage.

• Why is the model of the adversary’s uncertainty reasonable? Side information.

We emphasize that we do model a particular kind of side information. However, we make the assumption that, conditioned on the adversary’s side information and the public features, the labels within a batch are independent of each other. Our model aims to strike a balance between minimizing assumptions (as conservative approaches like DP do) and expressiveness. Alas, very conservative approaches will immediately disqualify deterministic mechanisms. Our goal is a reasonable framework that allows one to put deterministic mechanisms and randomized ones on the same footing.

We use a nonprivately trained predictor to capture adversarial uncertainty. This felt like the right way to get a “population-level” knowledge.

Given that bagging is done randomly, such population-level modeling seems like a good fit for the mechanisms we consider. If bags were not generated uniformly (e.g., in the extreme, if records from users in the same household were bagged together), then distributional assumptions would seem like the wrong approach, and the conservativeness of DP would make more sense.

In the context of online advertising: we imagine that existing predictive models could be used as the source of baseline probabilities. The experiments with the kdd12 data set (which comes from online advertising) provide a simple illustration.

• Why does the definition of expected attack utility differ from Wu et al. (2022)?

Unlike label DP mechanisms analyzed by Wu et al., LLP does not easily admit bounds that hold for all data distributions and are conditioned on arbitrary feature vectors $x$. In particular, in order to obtain a bound that has a clear dependence on the bag size $k$, the conditional distribution $\eta(x)$ must be bounded away from 0 and 1–see Remark A.15 in the appendix. Hence, since we wanted to measure advantage for both label DP and label aggregation, so as to put the two on the same footing, we had to consider a wider spectrum of measures. Specifically, we considered three guarantees in terms of $x$ (from weaker to stronger): (i) expected advantage, where the guarantee is only in expectation over the distribution of $x$;. (ii) advantage in high probability over $x$; and (iii) “for all $x$” advantage (that is, conditioning on $x$, as in Wu et al.). In all three cases, though, the guarantees are in expectation over the conditional distribution of $y$ given $x$. For label aggregation (LLP), the latter two guarantees are basically only contained in the appendix (Section A.5 there in -- see, e.g., Thm A.9 and Remark A.15).

The reviewer’s main criticisms focus on: (a) comparison to related work, and (b) clarity of the mathematical setup and notation.

Comparison to related work

• “it is important to understand what we can learn from these measures. [...] Other measures exist, like entropy based. The paper doesn't motivate why [...] preferable over existing measures.”

We do discuss related work extensively in Section 3.3. Indeed, our paper explicitly builds on several other works that aim to measure advantage. We are not aware of entropy-based measures being applied in the specific context of label aggregation, or label privacy more generally. Yet, we would be very interested to add comparisons to such works if the reviewer could suggest some specific starting points.

One possibly relevant point is that multiplicative measures such as the one we consider here generally upper bound entropy-based quantities like mutual information (which corresponds to the reviewer’s suggestion of entropy drop from prior to posterior). We can add a general discussion of that point to Section 3.2.

• The paper doesn’t discuss limitations.

This is not accurate, please see Section 5.

Mathematical setup and notation

• On our measures and the associated theoretical results.

There seem to be two general misunderstandings regarding our theoretical setting. First, in our definitions of attack utility and attack advantage we are assuming the adversaries (both the informed and the uninformed ones) have full knowledge of the distribution $D$ generating the data. Second, for the PETs we actually analyze, since the data is i.i.d. the attack advantage is either depending on a single example $(x_1,y_1)$ (for Randomized Response) or a single bag of examples (for label aggregation). This is why, for instance, the bounds for label aggregation in Thm 3.2, 3.3 and 3.4 are referring to a single random bag of size $k$ instead of a set of $n$ bags of size $k$, and thus we dropped the bag index $i$ from the notation. Please recall LL. 185-189.

• L. 154, syntactic mismatch.

Yes, this is a minor abuse of notation (and the specific sampling that we use is described in lines 82-84). In general we identify elements of $X^m \times Y^m$ and $(X \times Y)^m$ if they describe the same sequence of labeled examples. We will fix it throughout so as to avoid this notational inconsistency.

• L. 154, is $\mathcal{A}(...)_i$ the i-th component of the output of $\mathcal{A}$ ?

Yes, your interpretation is correct. As described on L. 148, the attacker receives the feature vectors for each example, the output of the PET, and they output a prediction for the label of each example. We will add a clarification to that effect, thanks.

• In line 198, Thm 3.2, ambiguity in the distribution and meaning of $\alpha$.

Thank you for identifying this ambiguity. Theorem 3.2 deals with a single bag containing $k$ examples, and the relevant distributions are: the $k$ pairs $(x_j,y_j)$ are drawn i.i.d. from $D$, and $\alpha$ is set to be the average over the $k$ labels. The theorem focuses on the case of a single bag since when using the $M_{LLP}$ mechanism, the bags observed by the attacker are independent and, since $D$ is known, the attacker gains no extra advantage from operating on an entire dataset of bags at once. It is thus sufficient to measure their success on a single bag. We will add some clarifying text to the paper.

• Thm 3.2: role of $\beta$ and two bounds.

Thm 3.2 provides two guarantees. As you point out, one of the guarantees holds without any condition on $p$, while the other requires that $p$ is sufficiently far from $1/2$. In particular, as long as $p$ is bounded away from $1/2$, the expected advantage decreases exponentially with $k$, rather than at the much slower rate of $k^{-1/2}$. The parameter $\beta$ in the exponent quantifies how far from $1/2$ that $p$ is. Thus, $\beta$ is a property of distribution $D$. The two bounds we give are generally incomparable, but when $k$ is large and there is a big enough gap $\beta$, the second bound is clearly better.

• L 528-529 meaning of conditioning on $\Sigma$.

Given that $\alpha$ is the proportion of the $k$ examples that had positive labels, $\Sigma = k\alpha$ is the number of positive labels in the bag, so $\Sigma$ is a random variable supported on \{0, …, k}. It is valid to condition probabilities on random variables. The notation $P(...| \Sigma)$ is nothing else than a conditional expectation, which is itself a random variable since it is a function of the random variable $\Sigma$.

• L 208, when $k$ increases, is $n$ kept constant?

As said above, because the bags are independent, we only need to consider a single bag when computing advantage. So $n$ is irrelevant to the advantage result in Theorem 3.3 (and subsequent results as well) since the attacker’s ability to predict the labels in one bag does not depend on the number of bags they have.

• Theorem 3.3 unexpectedly suggests that if $\eta(x) \in \{0,1\}$ then EAdv = 0.

As stated on LL. 160-163, both the uninformed and the informed attackers know the data distribution $D$ (one can also infer this from the definitions, since for a fixed $D$, we take the sup over adversaries–including ones that know $D$). Thus, when $\eta(x) = 0$ or $\eta(x) = 1$, both attackers have perfect knowledge of the label regardless of what the mechanism releases, since the label is unambiguously determined by the features (which are assumed to be public). So the inference advantage (conferred by the mechanism) is 0.

• Often $M$ is called a mechanism rather than a PET. Usually, one uses PET to refer to a strategy [...] not to a learning algorithm.

It is true that we use both PET and Mechanism to refer to privacy enhancing technologies. However, we would like to emphasize in all cases, the PETs/Mechanisms we discuss are strategies for enhancing privacy and not learning algorithms. We will make this clearer in the paper.

• Can you publish/provide the code?

We will publish the code, subject to internal organizational approval.

• As the measure is defined as the maximum advantage of all label inference attack and the paper shows how to calculate the measure exactly for two mechanisms, it would be great to see how the existing label inference attack is bounded. This is because the measure is generally hard to compute, e.g. for the mechanisms that are not analyzed in the paper. If an existing label inference attack is shown to be tight to the exact upper bound, this attack can be used as an empirical indicator of the measure too.

Indeed, if there was an attack that achieved the theoretical optimum, then it could potentially be used to empirically compute the label inference measures on PETs for which this is harder to compute analytically. In practice, this is complicated by the fact that the optimal attack depends on both the data distribution and the PET itself, so an attack that is optimal in one setting may not generalize to other PETs and distributions. It’s unclear how to reconcile this, but at the very least the attack could provide a lower bound on label inference success. In our experiments (for both the informed and uninformed adversary) we either analytically computed the Bayes optimal attack (on the synthetic datasets) or an approximation to the Bayes optimal attack (on the real-world datasets) by training an ML model on non-private data. This approximation to the Bayes optimal attack may turn out to be reasonably tight if we have enough training data.

• Explain how to compute proposed metrics or posterior distributions.

We will include more details on how we compute the posterior distributions for each mechanism. As suggested, we do apply Bayes’ theorem to compute the posterior:

$$Pr(y_i = 1 | x, \mathcal{M}(x,y) = z) = \frac{Pr(\mathcal{M}(x,y) = z | x, y_i=1) \cdot Pr(y_i=1 | x )}{Pr(\mathcal{M}(x,y) = z | x)} = \frac{Pr(\mathcal{M}(x,y) = z | x, y_i=1) \cdot Pr(y_i=1 | x_i )}{Pr(\mathcal{M}(x,y) = z | x)} .$$

Now, because in the above $x$ is fixed, this ratio is simply a function of the $\eta(\cdot)$’s, as well as any randomness in $\mathcal{M}$. For Randomized Response (RR) with flipping probability $p$ this ratio is $\frac{p\eta(x_i)}{p\eta(x_i) - (1-p)(1-\eta(x_i)}$ if the outcome of $RR(y_i) = 0$, and $\frac{(1-p)\eta(x_i)}{(1-p)\eta(x_i) - p(1-\eta(x_i)}$ if the outcome is 1.

For label aggregation (LLP), $\mathcal{M}$ is deterministic, so in the numerator $Pr(\mathcal{M}(x,y) = z | x, y_i=1)$ is the probability density at $z$ of a Poisson binomial with flipping probabilities $(\eta(x_1),\ldots, \eta(x_{i-1}), 1, \eta(x_{i+1}), \ldots, \eta(x_k))$. Similarly, in the denominator $Pr(\mathcal{M}(x,y) = z | x)$ is the probability density at $z$ of a Poisson binomial with flipping probabilities $(\eta(x_1), \ldots, \eta(x_k))$.

For LLP + Geom and LLP + Lap, the terms in the ratio are convolutions of the posterior for LLP and the Geometric or Laplace distribution, respectively.

Some of these posterior calculations can be found in the appendix, for example, in Line 561 for bags, and in Line 720, Eq (15) and (16), for Randomized Response.

• Other suggestions/typos.

We will implement the suggestions and fix the typos – thanks !

I read through the authors' responses to my own comments and to the other reviewers. In response, I have increased my score to strong accept (8).

My one comment is that, if computing the posterior probabilities in Figures 1/4 for the LLP-Geom/Laplace mechanism involves convolving (either numerically or analytically) a Geometric/Laplace random variable with a PoissonBinomial to obtain the likelihood $\text{Pr}(\mathcal{M}(\mathbf{x},\mathbf{y}) = z \mid y_i=1, \mathbf{x})$, that this convolution step should be explicitly mentioned somewhere in the Appendix.