In Differential Privacy, There is Truth: on Vote-Histogram Leakage in Ensemble Private Learning
Authors: Jiaqi Wang
Roei Schuster
Ilia Shumailov
David Lie
Nicolas Papernot
Venue: NeurIPS 2022 Accept (2022)
Keywords: adversarial
differential privacy
privacy
attacks

Abstract: When learning from sensitive data, care must be taken to ensure that training algorithms address privacy concerns. The canonical Private Aggregation of Teacher Ensembles, or PATE, computes output labels by aggregating the predictions of a (possibly distributed) collection of teacher models via a voting mechanism. The mechanism adds noise to attain a differential privacy guarantee with respect to the teachers' training data. In this work, we observe that this use of noise, which makes PATE predictions stochastic, enables new forms of leakage of sensitive information. For a given input, our adversary exploits this stochasticity to extract high-fidelity histograms of the votes submitted by the underlying teachers. From these histograms, the adversary can learn sensitive attributes of the input such as race, gender, or age. Although this attack does not directly violate the differential privacy guarantee, it clearly violates privacy norms and expectations, and would not be possible $\textit{at all}$ without the noise inserted to obtain differential privacy. In fact, counter-intuitively, the attack $\textbf{becomes easier as we add more noise}$ to provide stronger differential privacy. We hope this encourages future work to consider privacy holistically rather than treat differential privacy as a panacea. 

In Differential Privacy, There is Truth: On Vote Leakage in Ensemble Private Learning
Jiaqi Wang Roei Schuster", Ilia Shumailoy" David Lie", Nicolas Papernot
University of Toronto
Vector Institute
University of Oxford
Abstract
When learning from sensitive data, care must be taken to ensure that training al- gorithms address privacy concerns. The canonical Private Aggregation of Teacher Ensembles, or PATE, computes output labels by aggregating the predictions of a (possibly distributed) collection of teacher models via a voting mechanism. The mechanism adds noise to attain differential privacy guarantee with respect to the teachers' training data. In this work, we observe that this use of noise, which makes PATE predictions stochastic, enables new forms of leakage of sensitive in- formation. For given input, our adversary exploits this stochasticity to extract high-fidelity histograms of the votes submitted by the underlying teachers. From these histograms, the adversary can learn sensitive attributes of the input such as race, gender, age. Although this attack does not directly violate the differential privacy guarantee, it clearly violates privacy norms and expectations, and would not be possible at all without the noise inserted to obtain differential privacy. In fact, counter-inture inttttr-ituitivell.. the attack becomes easier as we add more noise to pro- vide stronger differential privacy. We hope this encourages future work to consider privacy holistically rather than treat differential privacy as a panacea.
Introduction
The canonical Private Aggregation of Teacher Ensembles, PATE, is model-agnostic approach to obtaining differential privacy guarantees for the training data of ML models (T]. (2), that is widely applied (3. 4 and adapted - due to its comparatively favorable trade-off between differential privacy, utility, and ease of decentralization 6)- In PATE, one considers ensemble of indepen- dently trained teacher models. To generate a prediction, PATE first collects the predictions of these teachers to form histogram of votes. It then adds Gaussian noise to the histogram and only reveals the label achieving plurality. This label can be used directly as a prediction, or to supervise the training of student model-in form of knowledge transfer. Because PATE only reveals the label receiving the most votes, it comes with guarantees of differential privacy, i.e., the noisy voting mech- anism allows us to bound how much information from the training data is potentially exposed (8).
But PATE does not explicitly protect from leakage of a key element its inference procedure: the histogram of votes submitted by teachers. While the histogram is used internally and not directly exposed to clients, careful examination of PATE reveals that information about the histogram leaks to clients via query answers.
The histogram can contain highly sensitive information, not the least of which membership in minority groups which, if revealed, can be used to discriminate against individuals. We demonstrate this by showing how an attacker, using the vote histogram PATE ensemble trained to predict an individual's 's income, infer wholly different attributes such as their level of education, when the attacker's ' instance does not contain any information related to education-level. Why is this
36th Conference on Neural Information Processing Systems (NcurIPS 2022).

---

possible? At a high level, the histogram of votes can be interpreted as relatively rich representation of the instance, that reveals attributes beyond what the ensemble was designed to predict.
Next, we ask, is this attack a realistic threat? We answer this in the affirmative by designing an attack that extracts PATE histograms by repeatedly querying PATE, and showing that it reconstructs internal histograms to near perfection. Our attack builds on the fact that repeated executions of the same query produce the same internal histogram and a consistent distribution of PATE's noised answers corresponding to this histogram. Our adversary can thus sample this distribution many times via querying, and use reconstruct the histogram.
This implies that our attack relies on the stochasticity of PATE's output, which is a product of Gaus- sian noise, the very mechanism that was intended to protect privacy. In fact, we find that the larger the variance of noise added to the histogram votes, the more successful our adversary is in recon- structing the histogram. This is in sharp contrast with the known and expected effect in differential privacy, that higher noise scale generally leads to stronger privacy. Put simply: differential privacy makes our attack possible.
An astute reader may observe that histogram leakage does not violate the differential privacy guar- antee, which only protects individual users in the training data, which is not compromised here. While it is absolutely true that our attack does not violate differential privacy, clearly violates societal norms and user expectations that differential privacy is often incorrectly assumed to protect. The fact that differential privacy enables the leakage we exploit nicely underscores the distinction between technical definitions of privacy and common conceptions of privacy.
The attack is difficult to mitigate. Particularly, we show that it is stealthy in the sense that PATE's own accounting of "privacy cost" considers our attacker's s set of queries "cheap", meaning that re- vealing their answers has a relatively small effect in terms of differential privacy. Consequently, PATE's privacy-spending monitoring does not prevent our attack. Our attack also performs only a moderate number of queries in absolute numbers, the same number used by common legitimate PATE clients, so a hard limit queries would impede PATE's utility. We will discuss other mitiga- tion approraches, which are not robust and/or not always usable.
To summarize, our contributions are as follows:
We posit the novel threat of extracting PATE's internal vote histograms. We observe and show that those contain sensitive information such as minority-group membership.
We show that differential privacy is the cause for -nnfgraaminnoomaationn leakage to PATE's querying clients.
We exploit this leakage reconstruct the vote histogram. We achieve this by minimizing the difference between (a) the probability distribution of outcomes observed by repeatedly querying PATE and (b) an analytical counterpart that we derive.
We experiment with standard PATE benchmarks, showing that the attack can recover high- fidelity histograms while using low number of queries that remain well within PATE's budget intended to control leakage.
2 Vote Histograms are Sensitive Information
We consider an ensemble's ' vote histogram, such those computed internally in PATE. Clearly, such histograms contain lot more information on PATE's innerworkings than simply its revealed decision, but it is important to clarify that there are common contexts in which this leakage can actually be used to hurt individuals as they contain sensitive information about them.
As prominent example, minority-gree groupp membership often leaks via histograms, and can of course be used discriminate against group members. To understand this, let's consider minority group that is serves some outliers and meiereepese phenomena such as coincidental correlations or out-of- distribution examples. When data on group members is scarce, each model will tend to over-fit to the outlier phenomena within its own data, creating inter-model inconsistencies and resulting dis- agreement, or low consensus, when predicting on similar inputs at test lime-which readily presents itself on vote histograms. Thus, we expect histograms to reveal members of minority group members via low consensus values. Next, we illustrate this via a simple experiment.
in the training data distributed across PATE's teachers. Each teacher ob-
2

---

Extracting sensitive attributes from UCI Adult-Income histograms. We now simulate an at- tack that receives the vote histogram of minority of the population, specifically, PhD holders. Following the above observation, our at- tack will simply classify all highly-consensus (consensus > 75%) predictions as non-hhD-solders, whereas low-consensus (< 75%) predictions will be classified as PhD holders. This is heuristic attack that relies on intuition rather than learning the ensemble's 's behavior using a labeled dataset. On one hand, it may underestimate the attacker's ability to detect PhD holders; on the other hand, it does not require a labeled dataset and only assumes that the attacker sees the votes histogram.
ensemble and uses to detect small
We use UCI Adult-Income dataset (2), containing around 41,000 data points with basic personal information on people such as age. work hours. weight, education, marital status, and more. PhD holders form about 1% of this dataset. We randomly selected 80% of the dataset for training, and held out the rest for testing. We randomly partitioned the data into 250 disjoint sets. For each, we fitted random forest model (using a hyperparameter grid search, see Appendix DD predicting whether income above or below $50,000. For both training and test data, we removed the data columns explicitly indicating education levels, that is, training and test individuals do not contain any feature that directly distinguishes PhD from non-PhD holders.
Figure D shows the distribution of high-consensus and low-consensus on the test set (to make the effect clearer, we balanced the minority and majority groups in the test set by randomly removing most of the non- non-PhD samples). We observe that low consensus indeed indicates minority- group membership. Our attacker's precision is not partic- ularly high (75% on the balanced set), but they can still use this signal to discriminate against minority groups.
Minority
Majority
0.8
0.7
8.0.6
0.5
0.3
0.2
0.1
End-to-end scenario and other attacks. Appendix E presents this attack in an end-to-end scenario where the attacker does not have direct access to the histogram, and has to first query a PATE instance to infer it, using our methodology in Section More sophisticated attackers can look for distinctive histogram patterns that character- ize certain groups; the attack should become more accu- rate as more models are added to the ensemble, refining the attacker's histogram measurement; and precision can be amplified if the attacker holds multiple samples that are known to belong to the same group. Further, we note that sensitive-atriiuue extrac- tion is not the only example for when vote histograms leak sensitive information: an attack could use votes to try to infer dataset properties [10] or distinguish between different partitions of the data associated with the different teachers in the ensemble.
0.0
Low Consensus High Consensus
Figure 1: High vs. low-consensus distributions of the PhD-detection at- tack: vote histograms of minority-gruv group members present lower consensus, al- lowing an attacker to identify them.
3 How to Extract PATE Histograms
Having established that vote histogram leakage poses risk to privacy and fairness, we proceed to provide a generic method for extracting vote histograms from PATE.
3.1 Problem Formulation and Attack Model
A primer on PATE, The PATE framework begins by independently training an ensemble of mod- els, called teachers, on partitions of the private data. There no particular requirement for the training procedure of each of these teacher models; the only constraint is that the partitions be dis- joint. Queries made by clients are answered as follows: (I) each teacher model predicts a label on the instance, (2) the PATE aggregator builds a histogram of class votes submitted by teachers, (3) Gaussian noise is added to this histogram, and (4) the client receives the noised histogram's 's argmax class (henceforth result class). This noisy voting mechanism gives PATE its differential privacy (DP) guarantee, in what is an application of the Gaussian mechanism [T]..
To preserve differential privacy, PATE tracks the privacy cost of the set of past queries, and stops answering queries once the cost surpasses the privacy budget. The cost computation parameterized by size 8. The key differential privacy guarantee of PATE can be stated as follows: for given set
3

---

of queries with cost E, PATE is (E, differentially private. Put succinetly, e bounds an adversary's s ability to distinguish between any adjacent training datasets, whereas 8 bounds the (usually small) probability, over PATE's randomness, of this bound not holding, We defer additional details on differential privacy in PATE Appendix
Attacker's motivation. Our attacker's goal is to recover the histogram of the vote counts when PATE labels an instance. Formally, given N predic- tors {Pi Px) and target input our attacker wants to infer [hi.....hu, he] where Count counts the number of ap- pearances of each element in [c]. Vote histograms can be used to extract potentially-sensine tion about an instance, such as its race, gender, or religion (see Section 2
PATE
Count (a)..... (a(())
differvntial privacy uuiiee
Bistogram
informa-
offinne
Inbels
recovered histegram
Attacker's access and knowledge. Our attacker can send queries to the aggregator and receive the label predicted by PATE (i.e., the output of the noisy voting mechanism). This may be possible because the aggregator willfully exposes the predictions of PATE, c.g., through MLaaS API. Alternatively, fully-decentralizedd implementations of PATE have been proposed where the central aggregator re- placed with cryptographic multi-party computation protocol 66. and its output is exposed directly. Fig- ure 2 visualizes the workflow of our attack.
Figure 2:
In an online phase, the attacker sends a specific query PATE repeatedly and receives labels output by the noisy argmax. Offline, the attacker uses the labels to recover the histogram by constructing and solving an optimization problem.
In PATE, the parameters (mean, variance) of the noise added during aggregation are public do- main (2: we therefore assume the attacker knows them. We also assume the attacker knows the number of teacher models N, which may or may not public. This assumption only necessary to shift the attacker's learned distribution by constant to attain low L1 approximation error when reconstructing histograms (Section B We note that the attacker could just as casily exploit the leak- age (e.g. to learn sensitive attributes or differentiate between training sets) without it but we chose to instead make this assumption to simplify result presentation and interpretation
3.2 Our histogram reconstruction attack
The idea behind the attack, given in pseudo-code in Algorithm 2 is as follows: let Q be a function that computes output-class probability distribution of PATE given vote histogram H. First, our attacker will sample PATE to find an estimate for this distribution q ~ Q(H). Second, the attacker will use gradient descent to find A that minimizes the Fuclidean distance between Q(A) and q- Finally, they shift the estimated histogram H by constant to account for the number of teachers (this step assumes the number of teachers is known, but done mostly for presentation purposes, see Section 3.I. We now detail these 3 steps.
Step 1: Monte Carlo approximation. The first step will sample PATE M times and estimate the distribution over PATE's outputs q Q(H) by setting each class probability as its Monte Carlo estimated mean frequency, i.. q; + 1 Σド= qf where of indicates whether class was sampled in the jth step. By the law large numbers, as M increases, T converges to i's sampling probability [Q(H),, and we can expect the attacker's estimate produced in the next steps to be more accurate. Our attacker would want to increase M as much as possible, until they exceed PATE's privacy budget.
Indeed, in PATE, the privacy leakage expended by each individual query can then be composed over multiple queries to obtain the total privacy cost needed to answer the set of queries. Once the total
Indeed, we could avoid this assumption while still retaining low error if we measured the attacker's error with shift- invariant distances, like Pearson correlation.

---

privacy cost exceeds a maximum tolerable privacy budget, PATE must stop answering queries to preserve differential privacy. Section d shows that the attack succeeds for values of M that remain well below PATE's privacy budget, and are also moderate in absolute value, as they are similar to the query number of student models that use PATE.
Step 2: constructing the optimization objec- tive. Our attacker wants to find // such that Q( - q is minimized where |1-1|2 denotes
Algorithm 2 Attack pscudocode
Input: NEN
1:
total number of teachers (see
the Euclidean norm. Given a (differentiable) closed-form expression for Q. it becomes nat- ural to program and solve this with modern gradient-based optimization frameworks. The- orem 1 provides a closed form expression; and our attacker will use a differentiable approxi- mation of this expression, as explained below.
Section for why this needed)
2: 0
> PATE instance
3: T,X
D optimization termination threshold and learning rate
Output: H
4: S -- sample(O, M) D. sampling PATE M
times and storing into S E I,..,, M
Theorem 1. Let H [H....., ,Ho] be the vote histogram for the e classes, and let PATE's Gaussion-mechanism function Agg(H) argmax{(,, + S where S = [S SMl is vector of M samples from zero- mean normal distribution with variance o². Then the probability that the randomized aggregator outputs the class k is given by (Q(H)) S I (.(a)xx(a)da where 2.(.) is the cumulative probability distribution (CDF) of NHH o²) (normal distribution with mean H, and variance σ) and (x(+)) is the probability density function (PDF) of (HK, 0²).
5: for 1,2 M do
6:
for j = 1.2. 1.2....... do
7:
of in == j)
D D = 1f
S = j. otherwise
8:
end for
9: end for
10: q < 0F
initialization of with 0 vector
11: for = 1, 1,2..... M do
PHAgg(H) -)
12:
di +
1
M
13: end for
H + 0 initialization of A, here we use an all-zero array of length c
15: while Q(
T do
16: H A - -V
Q -
Proof. ( = k). is the prob- ability that 14 m { [f]]. For any k. Ha + Ss random variable that follows normal distribution with mean equal to Hy and variance equal to o². Let 9k H₂ + Sk. then Ik ~ NHH,,, o²). [Q(H], is the probability of gb is greater than Ij. Vj E (1,...k
=
17: end while
18: Á + Á + N c shift A to sum to N
return H
.). c}
[Q(H), P(Agg(H)
= P(gn > -i,.... gh > 9k-1.9k > 9h+1,...,, > gc)
c.irk
F (gr a g = P(gk a)da
t=l
(o)
The expression in Theorem I is not usable in automatic differentiation and optimization frameworks; we therefore use an approximation of the integral by the trapezoid formula. We select points with higher probability and sum up their values to get an approximation of the integral with infinite bounds. Then we decide what values to select. In the integral 1 Im (a) (ai)da, a is the value of 9a N(HHza0)) Therefore a has the highest probability at Hą. and has the higher probability closer to Hg. More specifically, properties of the normal distribution give us that 6 covers 99% of the values of Gaussian random variable Ni, r). Therefore values of a between
5

---

top vote count
top vote count
250
231
215
199
200
150
low
median
high
low
mediian
high
100
100
50-
50-
6000
9000
8677
17355
26032
index
index
Figure 3: Divisions of the 9,000 and 26,032 histograms of MNIST (left) and SVHN (right) datasets into consensus levels, measured by top-agreed label percentage. The dashed red lines delineate the 33.3% and 66.7% quantiles.
Hy + 6 cover 99% of the integral area. Therefore,
4o c,igé-k II ((())
Σ II [.()))((a))
He Gar i=1
which is differentiable and is handled well by most automatic differentiation packages.
Step 3: accounting for the number of teachers. The distribution estimate produced by our op- timization may be skewed by constant because [Q(H)) only depends on the differences between Ie and 91..... 9t-1..9-11.00 90-11.9......... Ic. so the attacker shifts each element of H by (N - - H so that the histogram f sums up Σ c (N Σ ff)/c = N. Theorem Appendix B
provides proof that shifting QH) by a constant does not affect Q
Evaluation
We evaluate our attack against instantiations of PATE on common benchmarks. We show that the extracted histograms only differ slightly from the true ones underlying PATE's decision. This is despite the low privacy cost of the attacker's 's queries, which remains well within budgets enforced by common PATE instantiations. We also quantify the impact of the choice of scale for the noise being added to preserve DP: we show that higher noise values result in increased attack success for a given number of queries. We offer an hypothesis explain this ostensibly surprising observation.
4.1 Experimental Setup
Data. We use the experimental results from Papernot et al. [ to simulate our attack environ- ment. Papernot et al. released the histograms obtained by PATE using 250 teachers for two 10-class computer-vision benchmarks, MNIST [12) and SVHN [13] There are 9,000 histograms generated by MNIST experiments and 26,032 histograms generated by SVHN experiments, corresponding to the sizes of these datasets' test sets.
We define a histogram's consensus its maximum value, and divide each dataset into three equal- sized groups corresponding to high consensus, medium consensus, and low consensus. Figure illustrates this. We sample five histograms randomly from each group, and mount our attack for various noise levels.
Attack parameterization. We simulated attackers with two types of query limits: first, an attacker limited by PATE's canonical privacy budget; we used the parameterization from Papernot et al. (I), i.e. budgets of 1.97 and 4.96 for MNIST and SVHN and a = 40. Second, an attacker with a hard limit of 1 queries; this is a moderate number of queries for clients wishing to train their own "student" model using the aggregator's labels (see [1] 22 We applied this attack against PATE instantiations for MNIST and SVHN with noise levels a E { (00, 60, 80, 100).
For optimization (see Section B).
we use an adaptive learning rate: at the beginning of training, we where J = Q(H) is the optimization objective. As the optimiza-
use learning rate of 10 ||

---

tion starts to converge, | becomes too large so we switch to learning rate of 1
10
This
| J results in changes to the histogram of the magnitude of vote for each update. We use 0.01 as a threshold on the loss to establish convergence, and thus when ||]]|2 < 0.01, we stop optimizing. estimated histograms started presenting
For the attacks against canonical settings, we stopped negative values, which we found to be a slightly better strategy. (We could also try to constrain it to only-positive values; we discuss improving this optimization procedure further in Section 5
Metrics. For every attack, we measured the enror rate and privacy cost. The error rate is defined the normalized In distance between the ground-truth histogram H [M,,.... He] and attacker's estimate i [H,,..., Mo). i.e., Σ, H; H. (2 H.]). (While the optimization minimizes Euclidean distance, we report L1 errors because they can be interpreted as corresponding to the number of mis-counted votes.)
We define and compute the privacy cost incurred by adversary using established practices. high level (see details in [T) we model PATE as munni-ddfffrennially--riee mechanism and lever- theorems; we attain (non-Rényi) differential privacy via known reduction from differential privacy to Rényi differential privacy.
age known petee--reeeeeeeooieeeeee
The parameter ô is set as 10-5 for MNIST and 10-6 for SVHN, following Papernot al. I
Implementation Our implementation is provided in Python and the optimization uses the Jax library. Our code open-sourced https:///iithb. htwphhu..oomeeeeeeeeeeeeeeeeeeee cleverranss monte- carlo-ady We ran the optimization on an Intel Xeon Processor E5-2630 v4; it takes about 2.5 hours complete for single histogram.
4.2 Results
Our attack has high performance within canonical privacy budgets. We first evaluate our at- tack canonical PATE from Papernot et al. (T). Figure 4 and 4b show our attacker's error rates for the different histograms, averaging 0.1 on the MNIST setup and 0.05 on the SVHN setup.
Our attack extracts high-fidelit, histograms and has low privacy costs. Figure reports the performance of the crivacy-budge limited attack; Figures 6 and 7 show our hard-query-limit at- tacker's error rate and query costs for different noise levels, L.C. values of a. We observe that, across attacks, we attain very low eтror rates, often as low as 0.03, translating to 3% of the votes being miscounted. For the hard-query-lingg the order magnitude for the budget one would plausibly use, for example to attain guarantees similar Papernot et al. (which uses budgets of up in directly comparable setting ours) or Abadi et al. 14 (which also employs a (8, 10-5) (0==)-diifereetialll private mechanism for MNIST).
attack, privacy costs roughly range between 1 to 12, which
H2
H5
H2
H4
0.16
0.16
0.14
0.14
Errer Rate
Rate
0.12
0.10
0.10
0.08
0.08
0.06
0.06
0.04
0.02
0.02
0.00
Median
High
0.00
Median Histogram
High
Histogram
(a) Errrr rates on attacking a canonical MNIST PATE with privacy budget= = 1.97 and = 40
(b) Error rates on attacking canonical SVHN PATE with privacy budget = 4.96 and o = 40
Figure 4: Error rates on budget-limited attack on the canonical PATE
for our 15
low/mediian/ighh-ooeesssu sample histograms.

---

sigma 40
sigma 60
sigma
sigma 100
Privacy Cost
14
Error Rate
0.15
Privacy Cost
0.10
0.00
L1
L2
M1
M2
M3
M4
M5
H1
H2
H3
H4
H5
Histogram
Figure 6: Our attack's error extracting 15 MNIST histograms with low/medium/high consensus (Ll- 5, M1-5, and HI-5 respectively) using different noise scales and a query limit of 10 The red dots and the right axis show the privacy cost of the attack on each histogram.
sigma
sigma
sigma
sigma
Privacy Cost
0.3
Error Rate
Privacy Cost
0.2
0.1
0.0
L1
12 L4
L5
M1
M2
M3
M4
M5
H1
H2
H3
H4
H5
Histogram
Figure 7: Our attack's error extracting 15 SVHN histograms with low/medium/hiihh consensus (L1- 5, M1-5, and H1-5 respectively) using different noise scales and query limit of 102. The red dots and the right axis show the privacy cost of the attack on each histogram.
Adding more noise helps the attacker. Perhaps the most surprising result in this work is that the higher the noise scale, the lower the attacker's error is. This is not necessarily aligned with using up more of the privacy budget. In fact, in many cases, increasing the noise decreases both the attacker's shows the correlation between cost and error.
privacy cost and their error; Figure
This is counter-intuitive, Gaussian scales a usually corre- spond to tighter privacy guarantees. That is, more expected protection against attacks. Specifically, Monte Carlo estimation should be less accurate when higher-variance noise added, as convergence to the mean is slower. Nevertheless, our attack actually performs better with higher noise levels.
larger
Pearson's -0.20
mnist low consensus
Privacy 1
mnist median consensus mnist high consensus
svhn low consensus
svhn median consensus
svhn high consensus
Error Rate
Figure 5: Our attack's average error rate vs. privacy the histograms extracted with 10 queries. Weak inverse cor- relation implies cheaper attacks often more accurate.
To explain this, consider the aggre- gator's output distribution. When it is uniform, classes are sampled with equal probabilities, contributing equal information to each classes have lower probability than others, their
Monte Carlo estimator. Conversely, when estimator will receive less samples. Sharp output distributions, for example, have a peak that es- sentially "eclipses" other classes. To illustrate this, consider the case where noise is added all: here, the output is always the plurality vote, and a black-box querying adversary cannot learn anything about the histogram except its top-voted class, which is already known after single query.
Our results indicate that the mitigation of this eclipsing effect by increasing the noise, can more dominant than the adverse effect that increasing noise has on Monte Carlo convergence. Interest- ingly, this is not always reflected in PATE's privacy-cost score, which often lower for setups that leak more vote histograms. Technically. there is contradiction: privacy cost measures differ- ential privacy, which does not necessarily translate to protection against vote-histogram leakage.

---

5 Discussion
Mitigation. The possibility of this attack is inherent to PATE's aggregation mechanism, as long as the attacker can make multiple queries to PATE. Our experiments in Section show that (1) using tighter privacy budgets does not necessarily mitigate the attack, there is no strong correspondence between the privacy cost and the attack's success, and (2) it would be hard to limit the number of queries some other way without crippling PATE's utilityy, because our attack is successful while using the same number of queries used in common scenarios from the literature.
Theoretically, the attack would be mitigated if PATE returned a consistent answer for each query. PATE can thus try to cache answers to past queries and not recalculate them. Unfortunately, this defense would be exposed to adversarial perturbations that try to evade the caching mechanism without affecting predictions, and would not be possible for settings that keep queries confidential and/or include decentralized aggregation
Finally, we can try to prevent sensitive information from leaking onto vote histograms. Particularly, models that generalize well across subgroups will be more immune to an attacker inferring group membership via consensus. This reduces to the problem of subgroup fairness, an active line of work but no silver-bulle, solutions.
with many proposed approaches [5 19
Limitations. Empirical analysis of sensitive-attribute leakage onto vote histograms (Section D can be expanded to improve more sophisticated attackers, other scenarios, and also other forms of sensitive information that can leak onto histograms. We instead focus our work on extracting histograms from PATE, noting that this can be used as foundation for various different attacks.
A full optimization procedure takes noticeably long time (roughly 10 minutes for single step and 13 hours to convergence on a histogram), which prevented us from fully optimizing its hyper- parameter choices. This is however limitation of our current experimental setup, not of the attack, bearing the main consequence that we are potentially under-estimating our attack's 's capabilities.
Related work. PATE is widely-adopted framework for differentially-private ML, with myriad applications 3 4 and extensions - our attack is generally applicable to many of those frameworks, which inherit their privacy analysis from PATE.
Another prominent decentralized ML framework, Federated Learning (FL) 20). has been exten- sively investigated from a privacy perspective. As we did for PATE in this work, prior work attacking FL uncovered numerous forms of leakage. For example, Hitaj al. (2T reconstructed the average training set representation of each classes; Geiping et al. [22] reconstructed training data with high fidelity; Nasr al. (23 mounted a membership inference attack against the clients; Wang et al. [24) showed how malicious server could distinguish multiple properties of data simultaneously; and Melis et al. (25] inferred the clients' training data sensitive properties. These prior efforts all focus on FL, and are orthogonal to ours. We are the first to evaluate any attack against PATE.
Conclusion We are the first to audit the confidentiality of PATE from an adversarial perspective. Our attack extracts histograms of votes, which can reveal attributes of the input such as race or gen- der, or help attackers characterize teacher partitions. The attacker's success not highly correlated with their queries' privacy cost, which is monitored by PATE. Thus, mitigations of this attack are nontrivial and/or significantly hinder prediction utility. Particularly, using larger Gaussian noise, even when it fortifies the differential privacy guarantee, actually increases risk to the confidentiality of the vote histogram. This surprising tension demonstrates that care must be taken to analyze the protection differential privacy provides within given threat model, rather than treat it as silver bullet protecting against any form of leakage.
Broader Impact Our work studies information leakage in a widely-adoptee system, thus promot- ing our understanding of its risks. Our adversarial method can be used by developers and auditors to evaluate the confidentiality and privacy promises of PATE-based frameworks.
Our observation that differential privacy does not prevent but rather enables the attack is the first of its kind in that it reveals a discrepancy between differential privacy and societal norms of privacy. Characterizing this distinction essential to building technology that uses technical definitions of privacy as instrument to protect privacy norms.

---

Acknowledgments
We would like to acknowledge our sponsors, who support research with financial and in-kind contributions:
Amazon, CIFAR through the Canada CIFAR Al Chair program, DARPA through the GARD program, Intel, Meta, Microsoft, NERF through an Exploration grant, NSERC through the Discovery Grant, the OGS Scholarship Program, a Tier 1 Canada Research Chair and the COHESA Strategic Alliance. Resources used in preparing this research were provided, in part, by the Province of Ontario, the Government of Canada through CIFAR, and companies sponsoring the Vector Insti- tute. We also thank members of the CleverHans Lab for their feedback.
References
[1] N. Papernot, S. Song. I. Mironov, A. Raghunathan, Talwar, and U. Erlingsson, Scalable private learning with pate, 2018, arXiv: [802. 08908 [stat.MLJ
[2] N. Papernot, M. Abadi, U. Erlingsson, Goodfellow, and Talwar, Semi supervsee knowledge trans- fer for deep learning from private training data, 2017. arXiv: 1e1i: [6110.651110 05755 [stat. [Mt
[3] Y. Long, B. Wang. Yang, et al., "G-pate: Scalable differentially private data generator via private aggregation of teacher discriminators," " in Thirty-Fifth Conference on Neural Information Processing Systems, 2021.
[4] C. H. Yang. S. M. Siniscalchi, and Lee, "PATE-AAE: incorporating adversarial autoencoder into pri- vate aggregation of teacher ensembles for spoken command classification," CoRR, vol. 104/2104, 2021. arXiv: 2104. 01271 [Online]. Available: http::ttt// / //tpx//axxvv.vv. www.:orggabbs///e org/abs/2104...... 2ttps//220000221 01271
[5] M. M. Esmacili, I. Mironov, K. Prasad, Shilov, and F. Tramer, "Antipodes of label diffcrential pri- vacy: PATE and ALIBI," in Thirty-Fiite Conference on Neural Information Processing Systems, 2021.
[Online]. Available: ht http///ppereveeee///
[6] C. A. Choquette-Cheeee
N. Dullerud, A. Dziedzic, et al., "Ca(pc) learning: Confidential and private col- laborative learning." " in International Conference Learning Representations, 2021. [Online]. Avail- http:/pprrerieeeeeee/oooooameaa
able:[httpa: hatttp://openreviiie
wMVq
[7] B. Wang, F. Wu, Y. Long, L. Rimanic, C. Zhang, and B. Li. "Datalens: Scalable privacy preserving training via gradient compression and aggregation." " Proceedings the 2021 ACM SIGSAC Conference on Computer and Communications Security, Nov. 2021. DO1: 10. 00.114//3460120 3484444.......447879 3484579 Available: luttp://dx... doi wow..oo/o.ooo.0. 10. 1145/3460122 33844779
[Online].
[8] M. Abadi, A. Chu, I. Goodfellow, et al., "Deep learning with differential privacy." " Proceedings of the
2016 ACM SIGSAC Conference on Computer and Communications Security, Oct 2016. Do1: 1145/ 2976749. 2978318 [Online]. Available: attt://áss doi org/10..011 1141/ /
[9] D. Dua and C. Graff, UCT machine learning repository, 2017. [Online]. Available: 2978318
ics uci edu/ml
[10] K. Ganju, Q. Wang, W. Yang, C. A. Gunter, and N. Borisov, "Property inference attacks on fully con- nected neural networks using permutation invariant representations. in Proceedings of the 2018 ACM SIGSAC conference on computer and communications security, 2018, pp. 619-633.
[11] K. Nissim, S. Raskhodnikova, and A. Smith, "Smooth sensitivity and sampling in private data analysis," in Proceedings of the thirty-ninth annual ACM symposium on Theory of computing, 2007, pp. 75 84.
[12] Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner, "Gradient based learning applied to document recogni- tion," Proceedings of the IEEE, vol. 86, no. 11, pp. 2278-2324, 1998. DOl: 10. 1109/5. 726791
[13] Y. Netzer, T. Wang, A. Coates, A. Bissacco, B. Wu, and unsupervised feature learning," in NIPS Workshop on Deep Learning and Unsupervised Feature Learn ing 2011, 2011. [Online]. Available: http: : wfldl. stanford. edu housenumbers nips2011 housenumbers. pdd
Ng. "Reading digits in natural images with
[14] M. Abadi, A. Chu, I. Goodfellow, et al., "Deep learning with differential privacy." in Proceedings of the 2016 ACM SIGSAC conference computer and communications security, 2016, pp. 508-315
[15] N. V. Chawla, K. W. Bowyer, L. O. Hall, and W. P. Kegelmeyer, "Smote: Synthetic minority over- sampling technique," Journal of artificial intelligence research, vol. 16. pp. 321 2002.
[16] M. Kearns, S. Necl, A. Roth, and Z. S. Wu, "Preventing faimess gerrymandering: Auditing and lcarning for subgroup fairness," in International Conference on Machine Learning, PMLR, 2018, pp. 2564-2572.
[17] M. J. Kearns, R. F.. Schapire, and I.. M. Sellie, "Toward efficient agnostic learning." Machine Learning, vol. 17. no. 2. pp. 115-141, 1994.
[18] M. Mohri, G. Sivek. and A. T. Suresh, "Agnostic federated learning." in International Conference on Machine Learning, PMLR, 2019. pp. 4615-46255
[19] Y. Cui, M. Jia, T.-Y. Lin, Y. Song, and S. Belongie,
loss based on effective number of samples." in P Proceedings of the IEEE/CVF conference on computer vision and pattern recognition,
2019. pp.
10

---

[20] J. Konečný. H. B. McMahan, F. X. Yu. P. Richtarik, A. T. Suresh, and D. Bacon, "Federated learning: Strategies for improving communication efficiencyy. in NIPS Workshop on Private Multi-Part Machine Learning, 2016. [Online]. Available: http:::/eettttts:rtttii org/ abs aaaaaaaa//// /1600.1100.00 05492
[21] B. Hitaj. G. Ateniese, and F. Pérez-Cruz. "Deep models under the GAN: information leakage from col- laborative deep learning," " CoRR, vol. abs/1702.07464, 2017. arXiv: 1702. 1702.07464 [Online]. Available:
http://arziv. http://axiv...gg/bbbaaaae http://b///11...///
[22] J. Geiping. H. Bauermeister,
Dröge, and Moeller. "Iuverting gradients how easy it to break privacy in federated learning?" " In Advances in Neural Information Processing Systems, H. Larochelle, M. Ranzato, R. Hadsell, M. F. Balcan, and H. Lin, Eds., vol. 33, Curran Associates, Inc., 2020, pp. 16937-16 947. [Online]. Available: https: http:///ppeeeens..../// newriinggseeuureeeee neur ips cc/ htcppapprr/222//ff/20/ c4ede56bba98819mm 11leee66112000cbr1151555555 145-
[23] M. Nasr, R. Shokri, and A. Houmansadr, "Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning." " 20/9 IEEE Symposium on Security and Privacy (SP), May 2019. DOI: 10. 1t.10///p.../ 2019.00065 [Online]. Available: http:
dox.doi..zzz www.oii.oggg.... 10. 1109/SP 2019. 2019.00065
[24]
7. Wang, M. Song, 7.. Zhang. Y. Song, Q. Wang. and H. Qi, "Beyond inferring class representatives: User-level privacy leakage from federated learning." CoRR, vol. ahs/1812.00535, 2018. arXiv: 1812.
00535 [Online]. Available: httt:://rxixy org/ abs/1812. 101220055.
[25] I.. M.Mii,, C. Song, E. D. Cristofaro, and V. Shmatikov, "Inference attacks
learning."
CoRR, vol. http/8805.04449 2018. arXiv: 1805. 04049
[Online]. Available: http: : //trx/aaxvvv.///// org
abs 225/18055.om 04049
1. For all authors...
(a) Do the main claims made in the abstract and introduction accurately reflect the paper's
contributions and scope? [Yes]
(b) Did you describe the limitations of your work? [Yes]
(c) Did you discuss any potential negative societal impacts of your work? [Yes]
(d) Have you read the ethics review guidelines and ensured that your paper conforms to them? [Yes]
2. If you including theoretical results...
(a) Did you state the full set of assumptions of all theoretical results? [N/A]
(b) Did you include complete proofs of all theoretical results? [N/A]
3. If you ran experiments..
(a) Did you include the code, data, and instructions needed to reproduce the main experi- mental results (either in the supplemental material or as URL)? [Yes]
(b) Did you specify all the training details (c.g., data splits, hyperparameters, how they were chosen)? [Yes]
(c) Did you report error bars (e.g., with respect to the random seed after running experi- ments multiple times)? [Yes]
(d) Did you include the total amount of compute and the type of resources used (e.g., type of GPUs, internal cluster, or cloud provider)? [Yes]
4. If you using existing assets (e.g., code, data, models) curating/releasing new assets...
(a) If your work uses existing assets, did you cite the creators? [Yes]
(b) Did you mention the license of the assets? [Yes]
(c) Did you include any new assets either in the supplemental material or URL? [No] All the required assets are included in the main text so supplemental material there will be no new assets. Also we put the assets used in reference, so not in any URI.
(d) Did you discuss whether and how consent was obtained from people whose data you're re using/curating? [No] All data we use are popular and open-source, and data owners have given consent for academic use to the public.
(c) Did you discuss whether the data you using/curating contains personally identi- fiable information or offensive content? [No] All data we use are popular and open- source, and there is personally identifiable information or offensive content.
5. If you used crowdsourcing or conducted research with human subjects...
(a) Did you include the full text of instructions given to participants and screenshots, applicable? [N/A]
11

---

(b) Did you describe any potential participant risks, with links to Institutional Review Board (IRB) approvals, applicable? [N/A]
(c) Did you include the estimated hourly wage paid to participants and the total amount spent participant compensation? [N/A]
12


Reviews:
[{"review_id": "sW5TcGhUv5N", "reviewer": "Reviewer_pnDr", "summary": "This paper studies the confidentiality of PATE from an adversarial perspective. This paper shows that the attackers can recover the histograms of votes by querying the voting results multi-times. This paper shows an interesting result that adding larger Gaussian noise actually increases the risk to the confidentiality of the vote histogram.\n\n\n", "questions": "1. Does the model update frequently? Why cannot the model send the same result to the same query? \n\n2. Why do you use the Euclidean distance to measure the distance between $Q\\hat{H}$ and $\\bar{q}$? Why do not use KL or Wasserstein metric to measure the distance?\n\n3. In Line 247, what's the $\\epsilon$ and $delta$ for the DP guarantee? In Line 250, what's the corresponding budget for $\\sigma = 40$ etc?\n\n4. In line 248, what's the DP budget for each query? And what's the total budget for $10^4$ queries?\n\n5. In line 282, $(8, 10^{-5})$ is the DP budget for one query? \n\n6 In Figure 4, what's the corresponding DP budget for $\\sigma=40$?\n\n7. The results shown in Figures 6 and 7 are counter-intuitive. What's the corresponding DP budget for each query? To verify the correctness, it's better to add a large enough noise (i.e. the standard deviation of the Gaussian noise is close to inf.). Another baseline is that we add no noise to the results. Can we reach the same conclusion?\n\n8. Is it possible to perform some experiments that the attacker can steal the private attributes from the recovered histogram with some DP guarantee?\n", "limitations": "See the Weaknesses and Questions part. ", "rating": 3, "confidence": 3, "soundness": 2, "presentation": 2, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Pros: This paper proposed an attack method that can extract the voted histograms by querying the voting results multi-times. This paper uses an example to show that sensitive attributes can be leaked from the voted histograms. \n\nCons: The experimental settings are not clear. More experiments are needed to support the corresponding claims. \n\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ["I don’t know"]}, "extra_text": {}}, {"review_id": "apfcJLQKrs", "reviewer": "Reviewer_acw5", "summary": "This work provides an in-depth investigation of a particularly relevant failure mode of Differential Privacy (DP) when training ML models using the PATE framework.  In a nutshell, PATE takes the prediction of multiple independently trained models and outputs a prediction that is DP by first adding noise to the histogram and then taking the prediction with most votes.   \nThis paper describes a privacy attack based in querying the database multiple times with the same question.  By building up a distribution of these (noisy) responses, they show it is possible to back out the underlying histogram that the noise was meant to protect.  ", "questions": "Honestly, I read everything carefully (including the appendix) and I found it quite clear, thank you! ", "limitations": "The authors address the limitations of their work.  \n\nNot only I don't have any qualms with this work, but I believe that it is an important contribution that could have a major positive societal impact (if the work is taken seriously by the privacy community). \nI think this paper should definitely be given a spotlight talk. ", "rating": 10, "confidence": 4, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is quite enjoyable to read -- it is well-written, easy to follow, logical, and concise. \n- It will likely spur much-needed discussions about the practical usefulness of DP in real applications. \n\nWeaknesses: I don't see any significant weakness. \n\nMinor suggestions: \n- Instead of using $M$ for number of samples and $m$ for number of classes, use different letters.\n- (Line 263-176) I would prefer if in the appendix there was an explanation of precisely how the privacy cost is computed so that the reader doesn't need to refer to Papernot et al. as much.\n\nTiny typo: (line 34) *a* attacker\n\n", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "JdZeisM-_WO", "reviewer": "Reviewer_42Mo", "summary": "The paper first shows that the prediction histogram from several teachers will leak the membership of minority group for this test data. Then in the paper, an attack is proposed to show the possible leakage of histogram under a modern DP approach, PATE. Finally, it concludes DP doesn't protect the leakage of minority group membership.", "questions": "1. I am not clear why the introduced minority group membership leakage problem is a privacy problem for training data. The motivation is a bit confused.\n2. It is better to check the difference between $Q(H)$ and $\\bar{q}$ to support the explanation for better attack performance with higher noise levels.", "limitations": "The authors list some limitations of their proposed attack algorithm. However, I am concerned whether the conclusion is meaningful to the community. PATE is a DP algorithm designed for training data and it likely will not protect the test data's information, e.g. the minority group membership discussed in this paper.", "rating": 7, "confidence": 4, "soundness": 2, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Strengths\n1. This paper takes effort to show what differential privacy can/cannot protect. This big topic is meaningful to the differential privacy community and the one who cares about privacy in applications.\n2. The paper is written well.\n\n### Weaknesses\n1. The main conclusion of this paper is that the differential privacy doesn't protect the membership of minority group for *test data*. This conclusion seems not very surprising to me as differential privacy is to protect the privacy of *training data*.\n2. The experiment result also shows that the leakage of true histogram is more severe when the privacy cost is smaller. This result is counter-intuitively and the explanation is not very convincing to me. The estimation for $q_i$ from a sequence of i.i.d. samples (0/1) from Bernoulli random variable likely wouldn't be more accurate when $q_i$ is larger, but depends on its variance $q_i(1-q_i)$. I would suggest authors to further check the difference between $Q(H)$ and $\\bar{q}$ and see if this difference is smaller when the injected noise is larger.\n3. The experiment doesn't include the end-to-end evaluation between privacy cost to minority group membership leakage.\n\n--------After Rebuttal--------\n\nThank the authors for their reply, which solves W2 and W3 and alleviates my concern in W1.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}, {"review_id": "BUflsDNrtK", "reviewer": "Reviewer_r8cf", "summary": "This paper reveals that the noise added to the PATE voting mechanism (to attain a differential privacy guarantee) enables new forms of leakage of sensitive information. A simple adversary is enough to exploit this noise to extract high-fidelity histograms of the votes. As pointed out in this paper, a low consensus vote indeed indicates minority-group membership. The main technical contribution is the model to extract PATE histograms.\n", "questions": " Weaknesses: The technical part seems too simple. I'm not sure such a simple attack model contains enough technical contribution to appear in NeurIPS. This paper might be more appropriate to be published (as a report paper) at a security conference. ", "limitations": " Weaknesses: The technical part seems too simple. I'm not sure such a simple attack model contains enough technical contribution to appear in NeurIPS. This paper might be more appropriate to be published (as a report paper) at a security conference. ", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 2, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths: This paper is well written. The proposed attack model is simple but interesting. I believe the authors' discovery is significant.", "was_revised": false, "final_justification": "", "rebuttal": "", "claims_and_evidence": "", "methods_and_evaluation_criteria": "", "theoretical_claims": "", "experimental_designs_or_analyses": "", "relation_to_broader_scientific_literature": "", "essential_references_not_discussed": "", "other_strengths_and_weaknesses": "", "other_comments_or_suggestions": "", "questions_for_authors": "", "summary_of_paper": "", "summary_of_recommendation": "", "technical_quality": "", "clarity_of_presentation": "", "potential_impact": "", "robotics_focus": "", "quality_of_limitations": "", "questions_for_rebuttal": "", "reasons_to_accept": "", "reasons_to_reject": "", "questions_to_authors": "", "main_review": "", "summary_of_the_paper": "", "summary_of_the_review": "", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"ethics_review_area": ""}, "extra_text": {}}]

Author rebuttal:

Decision: Accept