Securing Secure Aggregation: Mitigating Multi-Round Privacy Leakage in Federated Learning
Authors: Jinhyun So
Ramy E. Ali
Basak Guler
Jiantao Jiao
Salman Avestimehr
Venue: NeurIPS 2022 Submitted (2022)

Abstract: Secure aggregation is a critical component in federated learning, which enables the server to learn the aggregate model of the users without observing their local models. Conventionally, secure aggregation algorithms focus only on ensuring the privacy of individual users in a single training round. We contend that such designs can lead to significant privacy leakages over multiple training rounds, due to partial user selection/participation at each round of FL. In fact, we show that the conventional random user selection strategies in FL may lead to leaking users' individual models within a number of rounds that is linear in the number of users. To address this challenge, we introduce a secure aggregation framework, Multi-RoundSecAgg, with multi-round privacy guarantees. In particular, we introduce a new metric to quantify the privacy guarantees of FL over multiple training rounds, and develop a structured user selection strategy that guarantees the long-term privacy of each user (over any number of training rounds). Our framework also carefully accounts for the fairness and the average number of participating users at each round. Our experiments on MNIST, CIFAR-$10$ and CIFAR-$100$ datasets in the IID and the non-IID settings demonstrate the performance improvement over the baselines, both in terms of privacy protection and test accuracy.

Securing Secure Aggregation: Mitigating Multi-Round Privacy Leakage in Federated Learning
Abstract
Secure aggregation is critical component in federated learning (FL), which enables the server to learn the aggregate model of the users without observing their local models. Conventionally. secure aggregation algorithms focus only ensuring the privacy of individual users in a single training round. We contend that such designs lead significant privacy leakages over multiple training rounds, due to partial user dalection/participatii the conventional random selection strategies in FL may lead leaking users' individual models within a number of rounds that is linear in the number of users. To address this challenge, we introduce secure aggregation framework, Multi- RoundSecAgg, with multi-round privacy guarantees. In particular, we introduce a new metric quantify the privacy guarantees of FL over multiple training rounds, and develop a structured user selection strategy that guarantees the long-tern tenetterm privacy of each user (over any number of training rounds). Our framework also carefully accounts for the fairness and the average number of participating users at each round. Our experiments on MNIST, CIFAR- 10 and CIFAR 100 datasets the IID) and the non-lll) settings demonstrate the performance improvement over the baselines, both in terms of privacy protection and test accuracy.
2
6
at each round of FL.. In fact, we show that
10
11
13
15
16
17
Introduction
18
19
Federated learning (FL) enables collaborative training of machine learning models over the data collected and stored locally by multiple data-owners. The training in FL typically coordinated by a central server who maintains global model that is updated locally by the users. The local updates are then aggregated by the server update the global model. Throughout the training process, the users never share their
21
22
23
24
Conventvnal eggrogation
RoundSecAAg
Original Images
25
Recondrrncted Images
26
(Geadient estinaatinn inversiou attack)
Figure qualitative comparison of reconstructed images in two settings is shown. The first setting corresponds to the case that model privacy with random user selection (e.g.. FedAvg (25) is protected by conventional secure aggregation schemes as 4 at each round. the second setting, our proposed method ensures the long-term privacy of individual models over any number of rounds, and hence model inversion attack cannot work well. This reconstruction process described detail Appendix [[]]
27
28 data with the server, i.e., the data is always kept
29 on device, rather, they only share their local
30 updates. However, as has been shown recently,
31 the local models may still reveal substantial
32 information about the local datasets, and the private training data can be reconstructed from the local models through inference or inversion attacks (sec c.g., [1 26 42 I2)).
34
36 To prevent such information leakage, secure aggregation protocols are proposed (e.g.. [4] 155
40 2, 38| 30)) to protect the privacy of the local models, both from the server and the other users, while still allowing the server to learn their aggregate. More specifically, the secure aggregation protocols ensure that, at any given round, the server can only learn the aggregate model of the users, and beyond that no further information is revealed about the individual model.
38
40
41
Secure aggregation protocols, however, only ensure the privacy of the individual users in a single 42 training round, and not consider their privacy over multiple training rounds
32
the other hand, due to partial user selection 5 6 28 the server may be able to reconstruct the individual models of some users using the aggregated models from the previous rounds. In fact, we
44
show that after sufficient number of rounds, all local models can be recovered with high accuracy
46 the server uniformly chooses a random subset of the users to participate at every round. As shown

---

Differential privacy (DP), in which each user adds artificial noises to the local models, can be one of the potential solution protect the privacy leakage over the multiple rounds p 37 16] In DP, however, the privacy guarantee sacrifices the model performance, which is known as a privacy-utilin trade-off. is worth noting that secure aggregation and DP are complementary, i.e., all the benefits of DP can be applied to our approach by adding noise to the local models [3. In this paper. our 47 in Fig performing model inversion attack [22 with the recovered local models yields reconstructed images with a similar quality as the original images.
48
49
Contributions. As such motivated, we study long-term user privacy in FI.. Specifically, our contributions are as follows.
50
51 1. We introduce new metric to capture long-term privacy guarantees for secure aggregation protocols in FL for the first time. This long-term privacy requires that the server cannot reconstruct any individual model using the aggregated models from any number of training rounds. Using this metric, show that the conventional random selection schemes can result in leaking the local models after a sufficient number of rounds, even if secure aggregation is employed at each round. structured user selection strategy that ensures the long-term privacy of the individual users over any number of training rounds. This strategy also takes into account the fairness of the selection process and the average number of participating users at each round.
58
55
56 2. We propose Multi- Multi-RRundSecAgg,
57
59
3. We demonstrate that Multi-RoundSecAl
creates a trade-off between the long-term privacy guarantee and the average number of participating users. In particular, as the average number of participating users increases, the long-term privacy guarantee becomes weaker. We provide the convergence analysis Multi- RoundSeegndS. which shows that the long-term privacy guarantee and the average number of participating users control the convergence rate. The convergence rate is maximized when the average number of participating users is maximized. (e.g., the random user selection strategy maximizes the average number of participating users at the expense of not providing long-term privacy guarantees). As we require stronger long-term privacy guarantees, the average number of participating users decreases and a larger number of training rounds is required to achieve the same level of accuracy as the random selection strategy. Finally, our experiments in both IID and non-IID settings on MNIST, CIFAR-10 and CIFAR-100 datasets demonstrate that Multi- Sellii-RounSSeAAAee achieves almost the same test accuracy compared to the random selection scheme while providing better long-term privacy guarantees.
61
63
64
65
67
69
5.
71
2 Related Work
74
The underlying principle of the secure aggregation protocol in [4] is that each pair of users exchange a pairwise secret key which they can use to mask their local models before sharing them with the server. The pairwise masks cancel out when the server aggregates the masked models, allowing the server to aggregate the local models. These masks also ensure that the local models are kept private, i.e., no further information is revealed beyond the aggregate of the local models. This protocol, however, incurs significant communication cost due to exchanging and reconstructing the pairwise keys.
76
78
79
80
Recently, several works have developed computation and communication-efficin protocols [31 15 35 & J0 38), which are complementary to and can be combined with our work. Another line of
81
82 work focused on designing partial user selection strategies to overcome the communication bottleneck in FL while speeding up the convergence by selecting the users based their local loss 7 5 6 28
84
Previous works, either on secure aggregation or on partial user selection, however, do not consider mitigating the potential privacy leakage as result of partial user participation and the server observing the aggregated models across multiple training rounds. While (27] pointed out to the privacy leakage of secure aggregation, mitigating this leakage has not been considered and our work is the first secure aggregation protocol to address this challenge.
85
86
87
86
89
90
91
92
93
94
objective is to understand the secure aggregation itself.
System Model
95
36 In this section, we first describe the basic federated learning model in Section 3.1 Next, we introduce the multi-round secure aggregation problem for federated learning and define the key metries to evaluate the performance of a multi-round secure aggregation protocol in Section 3.2
97

---

99
3.1
Basic Federated Learning Model
100
We consider a cross-device federated learning setup consisting of a server and users. User i [M] has a local dataset D, consisting of m; |Dr data samples. The users are connected to each other through the server, i... all communications between the users goes through the server [24 4 [7]. The goal is to collaboratively learn a global model x with dimension d, using the local datasets that
101
102
103
104
are generated, stored, and processed locally by the users. The training task can be represented by
105
minimizing a global loss function,
N Σ (x),
min L(x) s.t. L(x)=
(1)
21 W1
106
where L; is the loss function of user í and W, 2 0 is a weight parameter assigned to user i to specify the relative impact of that user. A common choice for the weight parameters is w; m; [17] We define the optimal model parameters x" and x as = arg zen L.xx) and x arg yen (x). Federated Averaging with Partial User Participation. To solve (D. the most common algorithm is the FedAvg (federated averaging) algorithm (24). FedAvg is an iterative algorithm, where the model training done by repeatedly iterating over individual local updates. At the beginning of training round r, the server sends the current state of the global model, denoted by x!") to the users. Each round consists of two phases, local training and aggregation. In the local training phase, user i E [N] updates the global model by carrying out E (2 1) local stochastic gradient descent (SGD) steps and sends the updated local model x/() to the server. One of key features of cross-device FL is partial device participation. Due to various reasons such as unreliable wireless connectivity, or battery issues, at any given round, only a fraction of the users are available to participate in the protocol. We refer to such users as available users throughout the paper. In the aggregation phase, the server selects
107
108
109
110
111
112
113
114
115
116
117
119 K S N users among the available users if this is possible and aggregates their local updates. The
server updates the global model follows
(++1)
Σ iEgO)
w/X = x(() pm
(2)
where (0)) is the set of participating users at round r, w/ Ensio w/ and p()) E {0, 1JN is the 121
my
corresponding characteristic vector. That is, pd) denotes a participation vector at round whose i-th
122
entry is when user i is not selected and otherwise. x(1) denotes the concatenation of the weighted
123
N e Nxd. Finally, the server broadcasts the updated global model x<(+1) to the users for the next round.
local models at round i.e., X [m"]x|" ...... w (t))
124
125
126
Threat Model. Similar to the prior works on secure aggregation as 4 15 31,
we consider the conees-but-currine model. All participants follow the protocol honestly in this model, but try to learn
127
as much as possible about the users. At each round, the privacy of individual model x/!" in ( is
128
129
protected by secure aggregation such that the server only learns the aggregated model Σreso w w/x/
130
131
3.2
Multi-round Secure Aggregation
132
Conventional secure aggregation protocols only consider the privacy guarantees over a single training round. While secure aggregation protocols have provable privacy guarantees at any single round, in the sense that information is leaked beyond the aggregate model each round, the privacy guarantees do not extend to attacks that span multiple training rounds. Specifically, by using the aggregate models and participation information across multiple rounds, an individual model may be reconstructed. For instance, consider the following user participation strategy across three training rounds, p = [1. 1, TJ,, p(2) [0, 1, TJ and p = =[1,0, T] Assume a scenario where the local updates do not change significantly over time (e.g., models start to converge, or the server fixes the global model over consecutive rounds), i.e., x; = x for all e [3] and E [3]. Then, the server can single out individual model, e.g., = (x + x - //2 Similarly, the server can single out all individual models x,, even if a secure aggregation protocol is employed each round.
133
134
135
136
137
138
140
141
142
143
In this paper, we study secure aggregation protocols with long-term privacy guarantees (which we term multi-round secure aggregation) for the cross-device FL setup which has not been studied before.
3

---

We assume that user i [N] drops from the protocol at each round with probability Pt. 70(0) denotes the index set of available users at round I and u( E {0. 1) is a vector indicating the available users such that )n = ] E ) where { is j-th entry of и and 1(-) is the indicator function. The server selects K users from 24(0) if (1( 2 K, based on the history of selected users in previous rounds. If |1 < K, the server skips this round. The local models of the selected users are then aggregated via secure aggregation protocol (i.e., by communicating masked models), at the end of which the server learns the aggregate of the local models of the selected users. Our goal is to design a
145
146
147
148
149
151
user selection algorithm Al) {0, 1JtNN x {0. 1) - 13%,
152
(3) to prevent the potential information leakage over multiple rounds, where pl)) E {0, 13 is the participation vector defined in (2), ||x||o denotes the Lo Lo""norm" of vector x and K denotes the number of selected users. We note that A() can be random function. p(t) is matrix representing the user participation information up to round r, and is termed the participation matrix, given by
l (plo) u ()) = p such that Ip E (O.
153
154
155
156
p() = [p p())
E (0, 1)
(4)
Key Metries. A multi-round secure aggregation protocol can be represented by A === (e
157
where (f) is the user selection algorithm at round r defined in ( and is the total number of rounds. The inputs of (()) are a random vector u("), which indicates the available users at round I, and the participation matrix p()) defined in 4 which can be random matrix. Given the participation matrix pv), we evaluate the performance of the corresponding multi-round secure aggregation protocol through the following metrics.
158
159
162
165
1.
Multi-round Privacy Guarantee. The secure aggregation protocols ensure that the server can only learn the sum of the local models of some users each single round, but they do not consider what the server can learn over the long run. Our multi-round privacy definition extends the guarantees of the secure aggregation protocols from one round to all rounds by requiring that the server can only learn a sum of the local models even if the server exploits the aggregate models of all rounds. That is, our multi-round privacy guarantee is a natural extension of the privacy guarantee provided by the secure aggregation protocols considering a single training round. Specifically, a multi-round privacy guarantee 7 requires that any non-zero partial sum of the local models that the server can reconstruct, through any linear combination XT XTP()TT z, where Z E R \ (0), must be of the form I
184
185
186
167
168
169
170
171
172
XTP(J)T == Σ ai Σ
Xj = a1
Σ Ex,+a JES
+ a2
Σx++ JCS:
an Σ xj. JeS,
(5)
[c[n]
JES;
173
where |S,] 2 a, # O, Vi [n] and n 2 Here all the sets S,, the number of sets n1, and each a, could all depend on z. In equation (5) we consider the worst-case scenario, where the local models do not change over the rounds. That is, X = X, Vr [J]. Intuitively, this guarantee ensures that the best that the server can do is to reconstruct a partial sum of 7' local models which corresponds to the case where n = 1. When 7 2 2, this condition implies that the server cannot get any user model from the aggregate models of all training rounds (the best it can obtain the sum of two local models).
174
175
176
177
178
179
180
Remark 1. (Weaker Privacy Notion). It is worth noting that, a weaker privacy notion would require that [IP(J) T cannot reconstruct any individual model (the best it can do is to obtain linear combination of two local models). This notion, however, allows constructions in the form of ax; + bx, for any a. b E RR (0). When a > b, however, this is almost the same recovering x; perfectly, hence this privacy criterion is weaker than that of (5).
zllo 2 T when p(J) 2 # O. When T 2, this definition requires that the server
181
182
183
185
Remark 2. MMulti-rouna Privacy of Random Selection). In Section 6. we empirically show that random selection strategy in which K available users are selected uniformly at random at each round does not ensure multi-round privacy even with respect to the weaker definition of Remark Specifically, the local models can be reconstructed within a number of rounds that is linear in N. We also show theoretically in Appendix H that when min(N K, K) cN, where 0 constant, then the probability that the server can reconstruct all local models after N rounds is
187
188
189
I
190
181
We assume that w/ 2 Vi [N] in this paper.

---

at least 1 1- ce for a constant c' that depends on Finally, we show that a random selection scheme in which the users are selected in an i.id fashion according to Bern( w(i-p) reveals all
192
193
194
local models after N rounds with probability that converges to I exponentially fast.
Remark 3. (Worst-Case Assumption). In (5), we considered the worst-case assumption where the models do not change over time. When the local models change over rounds, the multi-round privacy guarantee becomes even stronger as the number of unknowns increases. In Fig. [ and Appendix(H) H we empirically show that the conventional secure aggregation schemes leak extensive information of training data even in the realistic settings where the models change over the rounds. A ggregationn Fairness Gap. The average aggregation fairness gap quantifies the largest gap between any two users in terms of the expected relative number of rounds each user has participated in training. Formally, the average aggregation fairess gap is defined as follows
196
198
200
2.
201
F max lim sup iE[N] J -0000
Σ
((p 1=
13]
min lim inf iE[N] J J
/
Σ 1=0
[((""): (6)
where (p is i-th entry of the vector p( and the expectation is over the randomness of the user selection algorithm A and the user availability. The main intuition behind this definition that when F = 0, all users participate on average on the same number of rounds. This is important to take the different users into consideration equally and our experiments show that the accuracy of the schemes with small F are much higher than the schemes with high F.
203
204
206
208
3.
Average Aggregation Cardinality. The aggregation cardinality quantifies the expected number of models to be aggregated per round. Formally, is defined as
209
/-1 lpp [lo]
C= lim inf -0000
210
where the expectation is over the randomness in A and the user availability. Intuitively, less number of rounds are needed to converge as more users participate in the training. In fact, show in Section 5.2 C directly controls the convergence rate.
212
213
3.3
Baseline Schemes
In this subsection, introduce three baseline schemes for multi-round secure aggregation. Random Selection. In this scheme, at each round, the server selects K users at random from the set of available users if this is possible.
215
216
217
Random Weighted Selection. This scheme is a modified version of random selection to reduce F when the dropout probabilities of the users are not equal. Specifically, K users are selected at random from the available users with the minimum frequency of participation in the previous rounds.
218
219
220
N/ equal-sized GG. At each round, the server selects one of the groups if none of the users in this group has dropped out. If multiple groups are available, to reduce the aggregation fairness gap, the server selects group including user with the minimum frequency of participation in previous rounds. If no group available, the server skips this round.
User Partitioning (Grouping). In this scheme, the users are partitioned into
221
groups denoted as GI.G2.
222
223
224
Proposed Scheme: Multi-RoundSecAAg
225
226
In this section, we present Multi- Multi-RRundSecAgg, which has two components as follows.
227
The first component designs family of sets of users that satisfy the multi-round privacy requirement. The inputs of the first component are the number of users (N), the number of selected users at each round (K), and the desired multi-round privacy guarantee (T). The output is family of sets of K users satisfying the multi-round privacy guarantee T, termed as a privacy- famiil. This family is represented by matrix B, where the rows the characteristic vectors of these user sets.
228
230
The second component selects a set from this designed family to satisfy the faimesss guarantee. The inputs to the second component are the family B, the set of available users at round r, U)), and the frequency of participation of each user. The output is the set of users that will participate at round t.
233
234
We now describe these two components in detail.
5

---

236
Component 1 (Batch Partitioning (BP) of the users to guarantee multi-round privacy). The first component designs a family of RBP sets, where REP is the size of the set, satisfying the multi- round privacy requirement T. We denote the RBP x N binary matrix corresponding to these sets by = [b...... b where |lb:llo = K, Vi e [RBr]. That is, the rows of B are the characteristic vectors of those sets. The main idea of our scheme is to restrict certain sets of users of size T, denoted
237
239
240
241 as batches, to either participate together or not participate at all. This guarantees a multi-round privacy
T as we show in Section
243
To construct a family of sets with this property, the users are first partitioned into N/T batches. At any given round, either all or none of the users of a particular batch participate 245 in training. The server can choose K/T batches to participate in training, provided that all users in any given selected batch are available. Since there are (x/7) possible sets with
244
246
247
this property, then the size of this preserving family of sets is given by RBP In the extreme case 7' 1, this strategy specializes to random selection where the server can choose any K possible users. In the other extreme case of T = K, this strategy specializes to the partitioning strategy where there are N/ K possible sets. We next provide an example to illustrate the construction of B.
def N IT
K/T
248
1
0
0
0
01
1
1
250
110
0
0
B=
0
0
1
1
0
011
1:0
U1
252
0.0 0.1
111
253
are partitioned into batches as 9 = {1, (..2)....... G2 (3,4).9;= Figure 2: Example of our construction
Example 1 (N 8, K = =, 2).. In this example, the users
254
with N N==. K = and T= 22 ().6) and G4 () as given in Fig. 2 The server can choose any two batches out of these 4
butches, hence we have RBP ()) 6 possible sets. This ensures multi-round privacy T T= 2.
Component (Available batch selection to guarantee fairness). At round t, user [N] is
258
available to participate in the protocol with a probability p-p: E (0, 1]. The frequency of participation ( (), = 13. Given the set of available users at of user before round / denoted by y( (()) Σj=b 1
259
round r, ((()) and the frequencies of participation f(r-1) = (f((t-))... ..... ./ _((-)),, the server selects K users. To do so, the server first finds the submatrix of B denoted by B(r) corresponding to 4 Specifically, the i-th row of B denoted by bj is included in (CO) provided that supp(b;) S 41)), If (t) is an empty matrix, then the server skips this round. Otherwise, the server selects row from B(r) uniformly at random if p; = p. Vi E [N]. If the users have different Pt. the server selects a row from p(r-1)def arg min f ((t-1))
280
262
264
B (?) that includes the user with the minimum frequency of participation 'min
285
266
If there are many such rows, then the server selects one of them uniformly at random.
267
Remark 4. (Necessity of the Second Component). The second component is necessary to guarantee that the aggregation fairness gap goes to zero as we show in Theorem I and Section
288
Overall, the algorithm first designs privacy-preservie privacy guarantee T. Then specific sets are selected from this family to ensure fairesss. We describe the two components of Multi-RoundSecAgg in detail in Algorithm and Algorithm 2 in Appendix D
family of sets to ensure the multi-round
270
5
Theoretical Results
273
In this section, we provide the theoretical guarantees of Multi-RoundSecAgg in Section 5.1 and the convergence analysis of Multi-RRundSeAAgg in Section 5.2
274
275
5.1
Theoretical Guarantees of Multi- RouddeRgunSe
276
In this subsection, we establish the theoretical guarantees of
in terms of the
277
ruuti-round privacy guarantee, the aggregation fairness gap and the average aggregation cardinality.
Theorem 1. Rondd- with parameters N, K,T ensures multi-round privacy guarantee
279
T,, , an aggregation fairness gap O, and an average aggregation cardinality given by
N/T E
(N/T))
C= K
1
(1 NIT-1
iEN iNN [TT
We assume for simplicity that N/T and K/T are integers.

---

where q 1 (1-p) p)², when all users have the dropout probability p.
280
281
We provide the proof of Theorem ! iin Appendix A
Remark 5. (Trade-off between "Multi-round Privacy Guarantee" and "Average Aggregation indicates a trade-off between the multi-round privacy and the average aggregation cardinality since as 7' increases, C decreases which slows down the convergence
283
Cardinality""). Theorem |
285
show in Sec. 5.2 We show this trade-off in Fig. 3
286
Remark (Necessity of Batch Partitioning (BP)). We show that any strategy that satisfies the privacy
287
guarantee in Equation (5) must have a batch partitioning structure, and for given N, K,T, K S N/2, the largest number of distinct user sets in any strategy is at most (x (N/T) which is achieved in our (x/T)
289
design in Section 4 We provide the proof in Appendix C
290
Remark 7. (Non-linear Reconstructions of Aggregated Models). The privacy criterion in Eq. (5) considers linear reconstructions of the aggregated models. One may also consider more general non-linear reconstructions. The long-term privacy guarantees of batch partitioning hold even under such reconstructions as the users in the same batch always participate together or do not participate at all. Hence, the server cannot separate individual models within the same batch even through non- nin-linear operations.
291
233
295
296
5.2
Convergence Analysis of Multi-RoundSeede
locnssed
0.2
297
For convergence analysis of Multi-RoundSe gg. we first introduce a few common assumptions [23 (9].
6.5
6.0%
298
0.5
Ass Assumption 1. LI...., Ln in ①1 are all p-smooth: for all a, b E Rd and E [M], L((a) s (b) + (a-
300
b) (b) &lla f1la-bli bll..
Figure 3: An illustration of the trade-off between the multi muulti-oound privacy guarantee T and the average aggregation cardinality C. In this example, = 120 and K = 12.
302
Assumption 2. Li...., ., in ① are all p-strongly convex: for all a. Bd and [N], Li(a) (; (a-b) VL,
303
Assumption 3. Let E be sample uniformly selected from the dataset Dj. The variance of the stochastic gradients at each user is bounded, ie., (x)V " (L,))x
305
306
for e [N]. Assumption 4. The expected squared norm of the stochastic gradients is uniformly bounded, i.e.,
(x) e(2)11 s G² for all i e [N].
308
309
We now state the convergence guarantees of Julti-RoundSecAgg.
310
Theorem 2. Consider a FL setup with N users to train a machine learning model from I Assume
K users selected by Multi-RoundSecAgg with average aggregation cardinality C defined in (7) to (2), and all users have the same dropout rate, hence Multi-RoundSecAee selects random set of K users uniformly from the set of available user sets each round. Then, the following is satisfied
312
update the global model from
313
314
B[ L'
P
2(a+B)
-/1112000 - x11²).
(8)
y+ GEJ -1
#²
where 1/ EN of B=
4)N-K)
N Li and y max 88 -= L' NNN
315
K(N-1)
316
We provide the proof of Theorem in Appendix B
317
Remark 8. (The average aggregation cardinality controls the convergence rate.) Theorem shows how the average aggregation cardinality affects the convergence. When the average aggregation cardinality is maximized, i.c., C = K, the convergence rate in Theorem pearremmeequllss that of the random selection algorithm provided in Theorem 3 of 233 In we have the additional term E (number of
319
320
321
local epochs) in front of J compared to Theorem of 23 as we use global round index instead of using step index of local SGD. As the average aggregation cardinality decreases, greater number of training rounds is required to achieve the same level of accuracy.
322
323
324
Remark 9. (General Convex and Non-Convex Convergence Rates). Theorem considers the strongly-conver case, but we consider the general convex and the non-convex cases in Appendix [
7

---

328
Remark 10. (Different Dropout Rates). When the dropout probabilities of the users are not the same, challenging. This is due the
327
characterizing the convergence guarantees of Multi-RoundSeer fact that batch selection based on the frequency of participation breaks the conditional unbiasedness of the user selection, which required for the convergence guarantee. In experiments, however, we empirically show that Multi-RoundSecAg guarantees the convergence with different dropout rates.
329
330
Experiments
331
332
Our experiments consist of two parts. We first numerically demonstrate the performance of Multi- RoundSecAge compared to the baselines of Section 3.3 in terms of the key metrics of Section 3.2
333
334
Next, we implement convolutional neural networks (CNNs) for image classification with MNIST 21I. 100 and CIFAR-100 [20] to investigate how the key metrics affect the test accuracy.
336
Setup. We consider FL setting with N = 120 users, where the server aims to choose K = 12 users at every round. We study two settings for partitioning the CIFAR-100 100 dataset across the users.
337
IID Setting. 50000 training samples are shuffledd and partitioned uniformly across N = 120 users. 339
Non-III> Setting. We distribute the dataset using a Dirichlet distribution [13], which samples Dir = 0.5) which specifying the prior class distribution over 100 classes, and allocate a portion de,i of the class to user i. The parameter B controls the heterogeneity of the distributions at each user, where B - oo results in IID setting.
340
de
342
343
We implement* a VGG-11 [29], which is sufficient for our needs, as our goal is to evaluate various schemes, not to achieve the best accuracy. The hyperparameters are provided in Appendix F
344
345
Modeling dropouts. To model heterogeneous system, users have different dropout probability Pa selected from 0.2, 0.3, 0.4, 0.5). At each round, user i [N] drops with probability pi-
346
347
Implemented Schemes. For the benchmarks, we implement the three baselines introduced in Sec. 3.3 referred to as Random, Weighted Random, and Partition. For Multi-RRundSecAgg we construct three privacy- preserving families with different target multi-round privacy guarantees, T 6, T 4, and T = 3 which
Scheme
Family size (= R)
Random selection
10
349
Weighted random selection
10
User partition
10
351
Multi- SaatiiRRundSecAAgge T=6
190
T=4
4060
Multi-RoundSecAgg. T=3 91389
353
we refer to as Multi-RRunddeeAgg (T = 6). Multi-
354
RoundSecAgg (7' = 4), and Multi-RoundSecAgg (T= 3), respectively, One can view the Random and Partition as extreme cases of Multi-RoundSecAgg
Table 1: Family size with N = 120, K = 12.
355
356
with 7' and 7' = K, respectively. Table [ summarizes the family size R defined in Section 4
357
Key Metrics To numerically demonstrate the performance of the six schemes in terms of the key metrics defined in Sec. 3.2 at each round, we measure the following metrics.
359
For the multi-round privacy guarantee, we measure the number of models in the partial sum that the server can reconstruct, which is given by T := minger.) ||z " s.t. p()) # O. This corresponds to the weaker privacy definition of Remark I We use this weaker privacy definition as the random selection and the random weighted selection strategies provide the worst privacy guarantee even with this weaker definition, as demonstrated later. On the other hand, Multi- RoundSecAgg provides better privacy guarantees with both the strong and the weaker definitions. For the aggregation fairness gap, we measure the instantaneous fairness gap. F(1) == 385
360
362
363
364
m P! min F.") where F( E Ei= 1 ((p ); 1}.
We measure the instantaneous aggregation cardinality as c()) = सम E/ (l llo.
387
We demonstrate these key metrics in Figure 4 We make the following key observations.
369
Multi-RoundSecAPee achieves better multi-round privacy guarantee than both the random selection and random weighted selection strategies, while user partitioning achieves the best multi- privacy guarantee, = K 12. However, the partitioning strategy has the worst aggregation cardinality, which results in the lowest convergence rate as demonstrated later.
370
371
372
373
Figure 5 demonstrates the trade-off between the multi-round privacy guarantee T and the average aggregation cardinality C. Interestingly, Multi-RRundSecAgg when T =
374
4 achieves better multi-round privacy guarantee than both the random selection and the weighted random selection strategies while achieving almost the same average aggregation cardinality.
375
376
8

---

12-
12
Weighted
C.R
Purtion
Sens- Tw5
NuttReunssScckg T-4
0.4
NutsRtun::Secppp T-3
6.2
6.0
Rounds
Rounds
Rounds
(a) Multi-round privacy guarantee.
(b) Aggregation fairness gap. (c) Average aggregation cardinality.
Figure 4: The key metries with 120 (number of users), K 12 (number of selected users at each round).
TM
Random
Panttio
HJ:: heardSeckgg THE
besrdSeckgp
Po (h1 0.80-00 pndoocgg (-34
SanggeoorrgennnnCnnn Cartaakyy
Figure 5:
Trade-off between
(a) IID data distribution.
(b) Non-IID data distribution.
multi-round privacy and average aggregation cardinality with N
Figure 6: Training rounds versus test accuracy VGGII in on the CIFAR-I00 with N 120 and = 12.
120, 12.
377
Remark 11. (Multi-round Privacy of Random and Weighted Random). The multi-round privacy guarantees of Random and Weighted Random drop sharply as shown in Fig. [ the participating matrix p()) {0, 1)rxN becomes full rank with high probability when 2 N, and hence the server can reconstruct the individual models by utilizing pseudo inversion of the matrix p(t), More precisely, Theorem B in Appendix HH shows this thresholding phenomenon, where the probability that the server can reconstruct individual models after certain number of rounds converges to exponentially fast.
380
381
382
383
Key Metries versus Test Accuracy. To investigate how the key metrics affect the test accuracy. we measure the test accuracy of the six schemes in the two settings, the IID) and the non-IlI settings. Our results are demonstrated in Figure 6
385
We make the following key observations.
386
the IID setting, the Multi- Solii-RRundSeeAggg schemes show test accuracies that are comparable the random selection and random weighted selection schemes while the Multi-RRundSecAgee schemes
387
386
provide higher levels of privacy. Specifically, the Multi-RoundSecAgg schemes achieve T = 3, 4, based on the privacy-preserving family design while the random selection and random weighted selection schemes have T = I, i.e., the server can learn an individual local model.
390
391
In the non-llD setting, Solli--RundSecAgg not only outperforms the random selection scheme but also achieves smaller aggregation fairness gap as demonstrated in Fig. (bb)
383
In both IID and non-IID settings, the user partitioning scheme has the worst accuracy as its average aggregation cardinality is much smaller than the other schemes demonstrated in Fig. 4(c)
394
We also implement additional experiments on MNIST and CI datasets in Appendix H and present ablation study for various settings of (N, K,7) in Appendix
396
387
7
Conclusion
398
Partial user participation may breach user privacy in federated learning, even if secure aggregation is employed at every training round. To address this challenge, we introduced the notion of long-term privacy, which ensures that the privacy of individual models are protected over all training rounds. We developed Multi- Rollii-RoundSeAAgg.. a structured user selection strategy that guarantees long-term privacy while taking into account the fairness in user selection and average number of participating users, provides trade-off between long-term privacy and average number of participating users (hence the convergence rate). Our experiments on the CIFAR-100, 10,, and MNIST datasets on both the IID and non-III settings show that Multi-RRunddecAgee
399
400
402
403
and showed that
404
406
achieves comparable accuracy to the random selection strategy (which does not ensure long-term privacy), while ensuring long-term privacy guarantees.

---

References
408
409
[1] Martin Abadi, Andy Chu, Ian Goodfellow, H Brendan McMahan, Ilya Mironov, Kunal Talwar, and Li Zhang. Deep learning with differential privacy. In Proceedings of the 2016 ACM SIGSAC conference on computer and communications security, pages 308-33 318, 2016.
410
412
[2] James Henry Bell, Kallista A Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. Secure dinle--erver aggregation with (poly) logarithmic overhead. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pages 1253-1269, 2020.
414
415
[3] Kallista Bonawitz, Peter Kairouz, Brendan McMahan, and Daniel Ramage. Federated learning and privacy: Building decentralized data. Queue, 19(5):87-114, 2021.
systems for machine learning and data science on
417
418
[4] Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy-preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 1175-1191, 2017.
419
420
421
422
[5] Wenlin Chen, Samuel Horvath, and Peter Richtarik. Optimal client sampling for federated learning. arXiv preprint arXiv:2010.13720 2020.
424
[6] Yae Jee Cho, Samarth Gupta, Gauri Joshi, and Osman Yagan. Bandit-based communication efficient client selection strategies for federated learning. arXiv preprint arXiv:2012.08009, 2020.
425
427
[7] Yae Jee Cho, Jianyu Wang, and Gauri Joshi. Client selection in federated learning: Convergence analysis and power-of-choice selection strategies. arXiv preprint arXiv:2010.0/243, 2020.
[8] Beongjun Choi, Jy-yong Sohn, Dong-Jun Han, and Jaekyun Moon. Communication- computation efficient secure aggregation for federated learning. arXiv:2012.05433, 2020.
430
arXiv preprint
432
[9] Cynthia Dwork, Aaron Roth, et al. The algorithmic foundations of differential privacy. Foundations and Trends@ in Theoretical Computer Science, (13344):1144444 2014.
433
[10] Ahmed Roushdy Elkordy and A Salman Avestimehr. Secure aggregation with heterogeneous quantization in federated learning. arXiv preprint arXiv:2009. 040::0809944488, 2020.
435
436
[11] Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confidence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Conference on Computer and Communications Security, pages 1322-1333. 2015.
437
438
[12] Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients- how easy is it to break privacy in federated learning? arXiv preprint arXiv:2003. 14053, 2020.
440
441
[13] Tzu-Ming Harry Hsu, Hang Qi, and Matthew Brown. Measuring the effects of non-identical data distribution for federated visual classification. arXiv preprint arXiv:1909.0633: 2019.
443
[14] Vishesh Jain, Ashwin Sah, and Mchtaab Sawhney. Singularity of discrete random matrices ii arXiv preprint arXiv:2010.06554 2020.
445
446
[15] Swanand Kadhe, Nived Rajaraman, O Ozan Koyluoglu, and Kannan Ramchandran. Fastsecagg: Scalable secure aggregation for arXiv:2009.1 1248, 2020.
federated learning. arXiv preprint
448
449
[16] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings. al. Advances and open problems in federated learning. Foundations and Trends Machine Learning, 14(1-2):1-210 2021.
451
10

---

453
[17] Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Keith Bonawitz. Zachary Charles, Graham Cormode, Rachel Cummings. et al. Advances and open problems in federated learning. arXiv preprint arXiv: 1912.49977, 2019.
454
455
456
457
[18] Sai Praneeth Karimireddy, Satyen Kale, Mehryar Mohri, Sashank Reddi, Sebastian Stich, and Ananda Theertha Suresh. Scaffold: Stochastic controlled averaging for federated learning, In International Conference on Machine Learning, pages 5132-5143, PMLR, 2020.
458
459
[19] Alexander Kolesnikov, Lucas Beyer, Xiaohua Zhai, Joan Puigcerver, Jessica Yung, Sylvain Gelly, and Neil Houlsby. Big transfer (bit): General visual representation learning. In Computer Vision- ECCV 2020: 16th European Conference, Glasgow, UK, August 23-28, 2020, Proceedings, Part 16, pages 491-507. Springer, 2020.
461
463
[20] Alex Krizhevsky and Geoffrey Hinton. Learning multiple layers of features from tiny images. Technical report, Citeseer, 2009.
465
488
[21] Yann LeCun, Corinna Cortes, and CJ Burges. MNIST handwritten digit database. http://yann. lecun, com/exil/mnnist, 2010.
467
488
[22] Yann LeCun, Patrick Haffner, Léon Bottou, and Yoshua Bengio. Object recognition with gradient-based learning. In Shape, contour and grouping in computer vision, pages 319-345. Springer, 1999.
489
470
[23]
Xiang Li, Kaixuan Huang, Wenhao Yang, Shusen Wang, and Zhihua Zhang. On the convergence of fedavg on non-iid data. In International Conference on Learning Representations, 2019.
472
[24] H Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-effiiiee learning of deep networks from decentralized data. In Int. Conf. on Artificial Ini. and Stat. (AISTATS), pages 1273-1282, 2017.
474
476
[25] H Brendan McMahan, Daniel Ramage, Kunal Talwar, and Li Zhang. Learning differentially private recurrent language models. Int. Conf. on Learning Representations (ICLR), 2018.
477
[26] Milad Nasr, Reza Shokri, and Amir Houmansadr. Comprehensive privacy analysis of deep learning: Passive and active white-box inference attacks against centralized and federated learning. In 2019 IEEE symposium on security and privacy (SP), pages 739-753. IEEE, 2019.
479
480
481
[27] Balázs Pejó and Gergely Biczók. Quality inference in federated learning with secure aggregation. arXiv preprint (rXiv:2007.06236 2020.
483
[28] Monica Ribero and Haris Vikalo. Communication-effiiiennn federated learning via optimal client sampling, arXiv preprint 1rXiv:200...5197,, 2020.
484
[29]
Karen Simonyan and Andrew Zisserman. Very deep convolutional networks for large-scale image recognition. arXiv preprint 14X9 1556, 2014.
486
30] Jinhyun So, Ramy E Ali, Başak Güler, and A Salman Avestimehr. Secure aggregation for buffered asynchronous federated learning. arXiv preprint 10.02721 2021.
488
[31] Jinhyun So, Başak Güler, and A Salman Avestimehr. Turbo-aggregate: Breaking the quadratic aggregation barrier secure federated learning. IEEE Journal on Selected Areas in Information Theory, 2(1):479-489 2021.
490
482
[32] Jinhyun So, Corey Nolet, Chien Chien-Sheng Yang, Songze Li, Qian Yu, Ramy E Ali, Basak Guler, and Salman Avestimehr. Lightsecagg: lightweight and versatile design for secure aggregation federated learning. Proceedings of Machine Learning and Systems, 4:694-720, 2022.
493
494
495
[33] Sebastian U Stich. Local sgd converges fast and communicates little. arXiv preprint
1rXiv:1805.0976) 2018.
497
[34] Mingxing Tan and Quoe Le. Efficientnet: Rethinking model scaling for convolutional neural networks. In International Conference Machine Learning, pages 6105-6114. PMLR, 2019.
11

---

[35] Minxue Tang, Xuefei Ning, Yitu Wang, Yu Wang, and Yiran Chen. Fedgp: Correlation-basel based active client selection for heterogeneous federated learning. arXiv preprint arXiv:2103.13822 2021.
500
[36] Tuan Tran. The smallest singular value of random combinatorial matrices. arXiv preprint arXiv:2007.0631 2020.
503
504
[37] Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and H Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions on Information Forensics and Security, 15:3454- 3469, 2020.
506
507
508
[38] Chien-Sheng Yang, Jinhyun So, Chaoyang He, Songze Li, Qian Yu, and Salman Avestimehr. Lightsecagg: Rethinking secure aggregation in federated learning. arXiv preprint arXiv:2109.144: 2021.
509
510
511
[39] Hao Yu, Sen Yang, and Shenghuo Zhu. Parallel restarted sgd with faster convergence and less communication: Demystifying why model averaging works for deep learning. In Proceedings of the AAAI Conference on Artificial Intelligence, volume 33, pages 5693-5700, 2019.
513
514
[40] Yizhou Zhao and Hua Sun. Information theoretic secure aggregation with user dropouts. arXiv preprint arXiv:2 20l.://00.77500 2021.
[41] Yue Zhao, Meng Li, Liangzhen Lai, Naveen Suda, Damon Civin, and Vikas Chandra. Federated learning with non-iid data. arXiv preprint arXiv:1806.0083 2018.
517
518
[42] Ligeng Zhu and Song Han. Deep leakage from gradients. In Federated Learning, pages 17-31.
519
Springer, 2020.
12


Reviews:
[{"review_id": "vdti8RZuFXI", "reviewer": "Reviewer_Rb6v", "summary": "The paper concentrates on privacy-leakage in federated learning over multiple rounds. The authors note that secure aggregation protocols only have guarantees for a single aggregation round, whereas in federated learning the model is trained iteratively.  The paper proposes to measure and mitigate this privacy leakage over iterations. The main idea in the mitigation is to choose fixed groups of parties for model updates, so that an adversary can only ever see a contribution from the fixed group. This makes identifying any single individual party's contribution based on differences between iterations harder, since the individual contribution is always mixed in with the other group members. The proposed method essentially involves creating fixed subsets of users who are always chosen together for model updates. Another consideration is fairness in the sens of each party contributing an equal number of updates: the authors also propose a method by which all parties are chosen for updates an equal number of times on expectation. The paper then analyses convergence properties of the proposed method, and tests it empirically with several standard network structures and datasets.", "questions": "1) In the experiments, is there some reason to stop training when you do? Would e.g. the partition baseline eventually reach ~ same performance, and the main issue is convergence speed, or is there some other reason why it would perform worse?\n\n2) It seems that the proposed method assumes that the other parties in the same group are honest(?). Please mention the actual assumption as part of the the threat model.\n\n3) I think Remark 7 on lines 290-295 would make more sense as a separate theorem: this seems like an important property that should be stated more formally.\n\n\n#### Minor details:\n\nPlease add a table on the notation to Appendix: trying to follow the derivations can be frankly painful when one needs to hunt for the meaning of symbols all over the place. Fix typos on lines 113,224.", "limitations": "There is no discussion on the limitations of the proposed method, including in Section 7, which is pointed out as containing such discussion in the paper checklist.", "rating": 6, "confidence": 4, "soundness": 3, "presentation": 2, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "### Update after discussions\n\nAfter the rebuttal and the discussions, I raise my score to recommend acceptance. I trust that the authors will improve the paper based on the discussions.\n\n### Strengths\n\n+ The idea of having some secure aggregation-type guarantees over several iterations seems like a fine one.\n+ The theoretical results backing up the method are comforting, e.g., in the sense that the proposed method can be shown to converge under some fairly standard assumptions.\n\n\n### Weaknesses\n\n- The most glaring issue with the paper is that it completely omits discussing or even mentioning differential privacy (DP) and related definitions, which have been the standard privacy definition in machine learning for years, and that have also been widely used with federated learning (see e.g. Kairouz et al. 2019 for a quick overview of the basic idea in the context of federated learning, Dwork & Roth 2014 for a basic introduction to DP). Instead, the privacy discussed in the current paper is more related to secure computation, where the formal guarantees are on revealing only the end result of a computation. Calling such definitions privacy preserving is problematic for various reasons. One major issue is that the end result might well give out the input data in the clear without having any problems in satisfying this kind of definition of privacy-preserving (e.g. by choosing local loss functions s.t. the optimal value is an actual data point for a single client and 0 for everyone else would give out the single data point while still satisfying this kind of privacy guarantees). \nThe guarantees are also brittle in the sense that any side information might lead to a catastrophic privacy breach, where one or more input data points are suddenly revealed (e.g. consider what happens to others if one of the fixed group members gives out it's updates, or an adversary gains information on such values from other sources).\nAs an immediate fix, I would suggest including some discussion on the privacy-definition that also considers DP, clarifying the claims that this is the first paper that considers privacy-leakage in federated learning over iterations (e.g. lines 51, 84-88), and changing the emphasis to be less on general privacy-preservation and more specifically on what this method tries to protect. More interesting, although also more work-intensive and hence probably out of the question for now, would be to try and combine the current papers' results with DP and show that the proposed method does indeed enable better privacy by limiting the amount of information an adversary can gain.\n- Related to the previous point: I have a hard time understanding what are the consequences of providing privacy in the sense used in this paper.\n\n\n### References\n\nDwork & Roth 2014: The algorithmic foundations of differential privacy.\nKairouz et al. 2019: Advances and open problems in federated learning.", "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": "us6NM8mhXRy", "reviewer": "Reviewer_2oqH", "summary": "Secure aggregation-based protocols can leak privacy over multiple training rounds in FL and do not provide long-term privacy guarantees. The partial user selection enables the reconstruction of the client's models. The authors propose a user-selection strategy that will provide long-term privacy guarantees and provide theoretical and convergence analysis. New metrics are proposed to capture the privacy guarantees.", "questions": "1- Will multi-secagg work for cross-silo setup with partial user selection?\n2- Will experiments with N=K show any deviation?\n\nminor edits:\nLine 113: \"their.\"\nLine 41-42: Refer/Cite the basis\nLine 224: \"number of selected at each\"", "limitations": "Limitations are discussed in form of assumptions and remarks.", "rating": 7, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 3, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "Strengths:\n- The paper is well-written and clear.\n- Multi-RoundSecAgg is a novel scheme that provides privacy in FL in long term. It also ensures a fair selection of clients and shows tradeoffs between convergence and privacy.\n- Proposed metrics are interesting, they allow for comparison between different user selection schemes in terms of privacy and that all clients participate in an equal number of rounds.\n- Comparison with baseline experiments demonstrates the effectiveness of the metrics proposed.\n- The remarks and assumptions provided are a plus.\n\nWeaknesses:\n- The privacy leakage of the aggregated models over multiple rounds is not addressed. This may be considered as future work.\n- Applicability to cross-device only is missing.", "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": "iL0DlWht_Ya", "reviewer": "Reviewer_moUb", "summary": "The paper proposes a framework for sampling clients in each round of a Federated Learning training session. The proposed framework balances a notion of privacy (essentially a lower bound on number of sumands of any partial sum a server my reconstruct via linear combination of model updates retrieved throughout training), fairness gap (average gap in client participation across all rounds), and aggregation cardinality (average number of sumands in each round). The paper studies the relationship between these metrics, in relation to the convergence of the training. This is done by proposing new client sampling strategies, studying their properties, and comparing with naural baselines. The authors also provide experiments to support the analytical findings.", "questions": "- I am unsure about the practical relevance of the assumptions regarding values of K and N. For example, See Table 1 in https://arxiv.org/pdf/1912.04977.pdf. This seems to suggest that in practice N is huge with respect to K (several orders of magnitude), and that the number of training rounds is also smaller than N. I am thinking: K in the 100s, N in the millions, and number of training rounds L in the thousands. With this in my opinion more relevant setting in mind, a given client will participate in no more than 2 sums. The results in appendix H, as refelected in the experiments section, seems to rely on N and L being of the same order. It be useful for the paper to state upfront some examples of values of N, K, L of relevance to the paper, and found in practice.\n- The privacy guarantee is defined with respect to a particular time of reconstruction attack. In fact the sort of differentiation attacks that you describe motivates differential privacy. Using DP, one could ensure that a particular sumand does not alter the sum too much. Of course, if a user participates in many rounds this guarantee will degrade quickly, but that goes back to the choice of N, K.\n- How does one implement your proposed mechanim at the scale of the above numbers (and the ones in the referenced paper)? Are there any challenges there? The experiments use small values of K and N.", "limitations": "-", "rating": 4, "confidence": 3, "soundness": 3, "presentation": 3, "contribution": 1, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "- I am unsure about the practical relevance of the assumptions regarding values of K and N.\n- There does not seem to exist a lot of literature in client selection in FL with the purpose of improving privacy with respect to the server. The framework of differential privacy seeems important in that discussion, but the submission does not discuss that.\n- The privacy guarantee is defined with respect to a particular time of reconstruction attack.\n- The technical results give a good intuition on how the different metrics interact, even with baseline client selection strategies, which might be useful to practitioners. However, the assumption that dropout probability is the same across all clients seems unrealistic (although hard to avoid). ", "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": "TCJjEp1DPFd", "reviewer": "Reviewer_Y96F", "summary": "The paper explores the question of multi-round privacy leakage in federated learning with secure aggregation. To this end, the paper proposes a novel metric for multi-round privacy in FL. Existing FL secure aggregation protocols guarantee that the server can only learn the sum of N local models in any single round. The proposed multi-round privacy metric extends this guarantee to all training rounds. The paper motivates the need for multi-round privacy guarantees by demonstrating theoretically and experimentally that, under the assumption of partial user participation, existing secure aggregation protocols are vulnerable to attacks that aggregate models across multiple training rounds. To address this vulnerability, the paper proposes Multi-RoundSecAgg, a novel algorithm that provides a multi-round privacy guarantee. Theoretical analyses of the multi-round privacy, aggregation fairness gap and average aggregation cardinality guarantees of the proposed method are presented, as well as a convergence analysis. Finally, the proposed method is validated experimentally over range of FL settings and image datasets.", "questions": "H. Given that T=4 is not a very strong privacy guarantee and that for T=6 the convergence rate already starts to take a significant hit, I wonder whether you're not better off adding noise to the gradients as in DP-FedAvg to protect the local data. Did you consider this option?\n", "limitations": "The authors adequately address the limitations and potential negative societal impact of their work.", "rating": 8, "confidence": 3, "soundness": 4, "presentation": 4, "contribution": 4, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "# Strengths\n\nA. The writing and figures are very clear.\n\nB. Strong motivation. The paper demonstrates that, under the assumption of partial user participation, existing secure aggregation protocols are vulnerable to attacks that aggregate models across multiple training rounds. This is an important limitation of existing methods, which merits attention from the community.\n\nC. Strong novelty. The paper presents a novel multi-round attack on existing secure aggregation protocols. The paper proposes a novel metric for multi-round privacy in FL. The paper proposes a novel secure aggregation method that provides a multi-round privacy guarantee. The paper provides novel theoretical results for both existing secure aggregation methods and the proposed method. All of these are important contributions.\n\nD. Strong theoretical results. The paper provides the theoretical guarantees of the proposed Multi-RoundSecAgg method in terms of multi-round privacy, aggregation fairness gap and average aggregation cardinality. The paper also provides a convergence analysis of the proposed Multi-RoundSecAgg method. These results provide important insights about the proposed method and its functioning.\n\nE. Strong experimental results. Relevant baselines are compared against over a range of FL settings and datasets. Across all evaluations, the proposed method shows a better multi-round privacy guarantee, yet comparable test accuracy compared to the baselines.\n \n\n # Weaknesses\n\nF. Experimental evaluations with real-world datasets and SOA model architectures would strengthen the paper. That said, this is not a major issue given the novelty of the work and breadth of theoretical results.\n\nG. Given the focus on reconstruction attacks, the paper is missing a discussion of differentially private federated learning as a potential solution to the multi-round privacy vulnerability. ", "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: Reject