Communication-Computation Efficient Secure Aggregation for Federated Learning
Authors: Beongjun Choi
Jy-yong Sohn
Dong-Jun Han
Jaekyun Moon
Venue:  (2021)
Keywords: Federated Learning
Privacy
Graphs
Secure Aggregation
Communication-Efficient
Computation-Efficient

Abstract: Federated learning has been spotlighted as a way to train neural network models using data distributed over multiple clients without a need to share private data. Unfortunately, however, it has been shown that data privacy could not be fully guaranteed as adversaries may be able to extract certain information on local data from the model parameters transmitted during federated learning. A recent solution based on the secure aggregation primitive enables privacy-preserving federated learning, but at the expense of significant extra communication/computational resources. In this paper, we propose communication-computation efficient secure aggregation which reduces the amount of communication/computational resources at least by a factor of $\sqrt{n/ \log n}$ relative to the existing secure solution without sacrificing data privacy, where $n$ is the number of clients. The key idea behind the suggested scheme is to design the topology of the secret-sharing nodes (denoted by the assignment graph $G$) as sparse random graphs instead of the complete graph corresponding to the existing solution. We first obtain a sufficient condition on $G$ to guarantee reliable and private federated learning. Afterwards, we suggest using the Erd\H{o}s-Rényi graph as $G$, and provide theoretical guarantees on the reliability/privacy of the proposed scheme. Through extensive real-world experiments, we demonstrate that our scheme, using only 50% of the resources required in the conventional scheme, maintains virtually the same levels of reliability and data privacy in practical federated learning systems.

Under review as a conference paper at ICLR 2021
COMMUNICATOON-COMPUTTTTIO EFFICIENT SECURE AGGREGATION FOR FEDERATED LEARNING
Anonymous authors
Paper under double-blind review
ABSTRACT
Federated learning has been spotlighted as way to train neural network models using data distributed over multiple clients without a need to share private data. Unfortunately, however, has been shown that data privacy could not be fully guaranteed as adversaries may be able to extract certain information on local data from the model parameters transmitted during federated learning. recent solu- tion based on the secure aggregation primitive enables srivacy-preservngg feder- ated learning, but at the expense significant extra conmunicatioo/commttaiiiin resources. In this paper, we propose communication-comppuiii cure aggregation which reduces the amount of communication/computaaii sources at least by a factor of /n/ / log n relative to the existing secure solution without sacrificing data privacy, where is the number of clients. The key idea behind the suggested scheme is to design the topology of the secret-sharing nodes (denoted by the assignment graph G) sparse random graphs instead of the com- plete graph corresponding to the existing solution. We first obtain a sufficient condition G to guarantee reliable and private federated learning. Afterwards, we suggest using the Erdós-Rése Rényi graph as G, and provide theoretical guarantees on the reliability/privacy of the proposed scheme. Through extensive real-world experiments, we demonstrate that our scheme, using only 50% of the resources required in the conventional scheme, maintains virtually the same levels of relia- bility and data privacy in practical federated learning systems.
efficient se- re-
INTRODUCTION
Federated learning (McMahan et al., 2017) has been considered as a promising framework for train- ing models in decentralized manner without explicitly sharing the local private data. This frame- work is especially useful in various predictive models which learn from private distributed data, e,g., healthcare services based medical data distributed over multiple organizations (Brisimi et al., Xu & Wang/ 2019) and text prediction based on the messages of distributed clients (Yang al. 2018 Ramaswamy et al. 2019). In the federated learning (FL) setup, each device contributes to the global model update by transmitting its local model only; the private data is not shared across the network, which makes FL highly attractive (Kairouz al. 2019 Yang al. 2019).
2018
Unfortunately, however, FL. could still be vulnerable against the adversarial attacks on the data leakage. Specifically, the local model transmitted from device contains extensive information on the training data, and an eavesdropper can estimate the data owned by the target device (Fredrikson al. 2015 Shokri al. 2017 Melis al. 2019). Motivated by this issue, the authors of (Bonawitz et al.
2017 suggested secure aggregation (SA), which integrates cryptographic primitives into the FL framework to protect data privacy. However, SA requires significant amounts of additional re- sources communication and computing for guaranteeing privacy. Especially, the communication and computation burden of SA increases as a quadratic function of the number of clients, which limits the scalability of SA.
Contributions We propose coumuniccationcoopptteee efficient secure aggregation (CCESA), which maintains the reliability and data privacy in federated learning, with reduced resources on communication and computation compared to conventional SA. Our basic idea is illustrated in Fig.

---

Under review as a conference paper at ICLR 2021
8, 8, + (b)
8, (RG(b.)
+ (1. + (1a
+ PPRG(s.a) PRG()La)
+ PRG (1.)) (RG()
(a) Existing algorithm
(b) Suggested algorithm (CCESA)
Figure 1: Conventional secure aggregation (SA) (Bonawitz et al. 2017) versus the suggested communication- computation efficient secure aggregation (CCESA). Via selective secret sharing across only a subset of client pairs, the proposed algorithm reduces the communication among clients) and computational cost (for generating secret shares and pseudo-random values, and performing key agreements), compared to the existing fully-shared method, CCESA still maintains virtually the same levels of reliability and privacy, as proven by the theoretic analysis of Section
(for exchanging public keys and secret shares
Tekknng lxog
(9)
Figure 2: A training image and the reconstructed images using model inversion attacks with (a) the proposed scheme (CCESA). (b) existing secure aggregation (SA) (Bonawitz et al. 2017). (c) federated averaging with no security measures (McMahan al. (017). The federated averaging scheme leaks private data from the trans- mitted model, while SA and the proposed CCESA do not. Note that the required communication//ompuaattooo resources of CCESA are only 40% of those SA. Additional examples are given Supplementary Materials.
for n 5 clients. Compared to the existing scheme (Bonawitz al. 2017), which applies secret sharing for all client pairs, we suggest sharing secrets for a subset of pairs in a way that data privacy is preserved. Using theoretic analysis, we provide sufficient condition private and reliable federated learning. As summarized in Table [ the proposed CCESA algorithm maintains both reliability and privacy against an eavesdropper who can access to any information transmitted between every client and the server, while the required amount of resources reduces by factor of at least O(Vn/ n)) compared to SA. Notably, the reduction factor gets bigger with increasing n, suggesting that the proposed scheme a scalable solution for privacy-preservee federated learning. Our mathematical results are also confirmed in experiments on two real datasets of AT&T face database and CIFAR-10. Especially, under the model inversion attack on the face dataset, the results in Fig. 2 show that the suggested scheme achieves perfect data privacy by using less amount of resources than SA, while federated averaging without security measures (McMahan et al. 2017) significantly compromises the privacy of the data.
the graph topology for
Related work Focusing on the collaborative learning setup with multiple clients and a server, previous works have suggested solutions prevent the information leakage in the communication links between the server and clients. One major approach utilizes the concept of differential privacy (DP) (Dwork et al., 2014) by adding artificial random noise to the transmitted models (Wei al.
2020
Geyer et al. 2017 ruex et al., 2020) or gradients (Shokri & Shmatikov] 2015 Abadi et al,,
2016
Balcan et 2012 Depending on the noise distribution, Da-based collaborative learning
generally cxhibits a trade-off between the privacy level and the convergence of the global model.
Another popular approach is deploying secure multiparty computation (MPC) (Ben-Or al. 1988
Damgard et al. [012 Aono et al. 2017 Lindell et al. 2015 Bonawitz et al. 2017 Zhang et al.,
2018]Tjell Wisniewski 2019 Shen et al.) [020] So et al., 2020) based on the cryptographic
primitives including secret sharing and the homomorphic encryption (Leontiadis et al.) 2014 2015
Shi et al. 2011] |Halevi et al. (01T). Although these schemes guarantee privacy, they suffer from high communication burdens while reconstructing the secret information distributed over multiple clients. A notable work (Bonawitz et al.) (017)) suggested secure aggregation (SA), which tolerates
Elahi et al. 2014: Jansen & Johnson| 2016 Goryczka & Xiong] 2015). A recent work (So et al. 2020 suggested surbo-aggregate which partitions n computing devices into L groups and updates the global model by utilizing the circular aggregation topology. However, each client in Turbo-aggregatt requires a communication cost of at least 4mnR/ L bits, which is much larger than that of our scheme (CCESA) requiring communication cost of /n log (2ax 5ag) + m mIRl For example,
multiple client failures by applying pairwise additive masking (Acs & Castelluccia 2011
Here, m is the number of model parameters where each parameter is represented in R bits, ax and as are the number of bits required for exchanging public keys and the number of bits in secret share, respectively.

---

Under review as a conference paper at ICLR 2021
CCESA
SA
FedAvg
Communication
Client
Olyn log + m)
O[n + m)
O(m)
cost
Server
O(n log mn)
O(n² + mm)
O(mn)
Computation
log my/llogg))
O(n² + mn)
cost
Server
O(mn log
O(mmn)
O(mn)
Reliahiliny
O(ne Vulogn)
O(ne ")
Privacy
1- O(n - for
Table 1: Communication and computation cost of the proposed CCESA algorithm. Secure Aggregation (SA) in (Bonawitz et al. 2017), federated averaging (FedAvg) in (McMahan et al. 2017). Detailed expressions and
derivations in Section 4 and Supplementary Materials, respectively.
in practical scenario with 100000000 R 32, 100, L 10 and ag as 256, our scheme requires only 3% of the communication bandwidth used in Turbo-aggregate.
The idea of replacing the complete graph with low-degree graph for communication efficiency has been studied in the areas of distributed learning (Charles et al.] [017] [Sohn et al.) (020)) and multi-party computation (Fitzi al. 2007 Harnik et al. 2007). A very recent paper (Bell et al. 2020) proposed new protocols using k-regular graphs for communication in the secure aggrega- tion (Bonawitz et al. 2017) framework, which robust against semi-honest and semi-malicious threat models, respectively. However, the results in (Bell et al., (020) is based on a strong assump- tion on the number of clients dropped out of the protocol, while our work does not assume anything on the number of dropouts.
2 BACKGROUND
Federated learning Consider a scenario with one server and clients. Each client has its local training dataset D, { x1, N; where x and yt are the feature vector and the label of the k-th training sample, respectively. For each round f, the server first selects set Sy of en clients (0 c S 1) and sends the current global model o(() to those selected clients. Then, each client
i E St updates the received model by using the local data D, and sends the updated model e((+ to the server. Finally, the server updates the global model by aggregating local updates from the selected clients, i.e., i.e. (bttt1) global
Eies, Ni o(t(t+)) where N = Eies, N..
Cryptographic primitives for preserving privacy Here we review three cryptographic tools used in SA (Bonawitz et al.) 2017). First, t-out-of-n secret sharing (Shamir 1979) is splitting a secret into n shares, in way that any shares can reconstruct s, while any shares provides absolutely
no information on 8. We denote l-out-of-n secret sharing by (t.m) (8* ke])) where se indicates the ktth share of secret and [n] represents the index set {1, ....,,,,, n]. Second, the Diffe-Hellman key agreement is used to generate a secret 8i, that is only shared by two target clients i, E [n]] The key agreement scheme designs public-private key pairs (sPK ,s for clients u E [n]] in a way that SLj = f( 555k) = [("]" 555K) holds for all i, [ri] for some key agreement function f- The secret $i.j is unknown when neither sf nor SK is provided. Third, symmetric authenticated encryption is peee/deigg/e message using a key k shared by two target clients. This guarantees the integrity of the messages communicated by the two clients.
Secure aggregation (Bonawitz et al., 2017) For preeecy-preservigg federated learning, SA has been proposed based on the cryptographic primitives of Shamir's 's secret sharing, key agreement and symmetric authenticated encryption. The protocol consists of four steps: Step 0 Advertise Keys, Step 1 Share Keys, Step 2 Masked Input Collection, and Step 3 Unmasking.
Consider a server with n clients where client i & [n] has its private local model 0, Denote the client index set as Vo V (n]. The objective of the server is to obtain the sum of models Σ, 0g without getting any other information on private local models. In Step 0, client E Vo generates key pairs (sf"K s.s SSK) and (c."K, csS) by using key agreement scheme. Then, client advertises its public keys (sP" K .PK) to the server. The server collects the public keys from client set V12 C Vo, and broadcasts {(i, sf"k (e"K)ee to all clients in V1. In Step 1. client generates random element b, and applies t-out-of-n secret sharing to generate n shares of b, and si i.e., by (t.m), (bL.)se(M)
and s.S (l.m), (s jj((n) By using the symmetric authenticated encryption, client i computes the

---

Under review as a conference paper at ICLR 2021
SK as messages and C. fle.", ..k) ciphertext ei, for all j E Vi by taking bij and $i as a key, where f is the key agreement function. Finally, client sends {(i, eig)) to the server. The server collects the message from at least clients (denote this set of client as 1/2 C V2) and sends {(i. ((.g) en.)) Nev, to each client j E V2. In Step 2, client i computes the shared secret Sij ==j= f(s K s for all j 12 Then, client computes the masked private vector
= (b) +
Σ PRG():.)-
E PRG()
JEVanea
JEVANCS
and sends 0g the server, where (2)(2) indicates a pseudorandom generator with seed x out- putting a vector having the dimension identical to 8,. Note that the masked vector 8, gives no information on private vector 0g unless both s55 and b, are revealed. The server collects 0 from at least i clients (denote this set as V/3 C V2), and sends V3 to each client i E V3. In Step 3, client j ,c (SK) to obtain {br,) (eshee and { h)) Each client j sends set of shares hev, U (K
decrypts the ciphertext {eir heva)() by using the key Ci.j = f(a. "(
{ hevvsv \ to the server. The server collects the responds from least t clients (denote this set of clients as V1 C. V2). For each client i E V3. the server reconstructs b; from (iv, and computes (R.( Similarly, for each client i E V2 the server reconstructs s5K from (K Jeev and computes PRG(s.,) for all j E 1/2. Using this information, the server obtains the sum of private local models by computing PRG( (2)
Σ 0: =
Σ 0:
Σ (b.(
Σ
PRG(( +
Σ
V
EE
V
VEV3
JVV2
VVV
3 SUGGESTED ALGORITHM
In the secure aggregation [Bonawitz et al. 2017). the public keys (c. s!*K) and the shares of secrets (sşK b,)) are transmitted between clients and the server, which requires additional commu- nication/compuuttionaal resources compared with the vanilla federated learning. Specifically, since each client needs to receive information from all other clients j + i, the required amount of resources increases as a quadratic function of the number of clients n.
In this paper, we suggest variant of secure aggregation, dubbed as communication-con compputtiiiicoomttttttitoooooonn ef- ficient secure aggregation (CCESA), which enables to provide a more scalable solution for privacy- preserving federated learning by improving the conmunication//oompuaaiionn efficiency. The basic idea of the proposed algorithm is to allow each client to share its public keys and secret shares to a subser of other clients, instead of sharing them with all other clients. By doing so, compared with SA, the suggested scheme achieves two advantages in resource efficiency, without losing the reliability of learning algorithms and the data privacy. The first advantage is the reduction of the communication cost, since each node shares its public keys and secrets with less clients. The second advantage is a reduction of the computational cost of each client, since a smaller number of masks used while computing its masked private vector.
The proposed algorithm is specified by the assignment graph which represents how public keys and secret shares assigned to the other clients. Given clients, the assignment graph G EV consists of n vertices where the vertex and the edge set of G are represented by V and E, respectively. We set V [n] where each index connecting vertices i and j indicates that client i and j exchange their public keys and secret shares. For vertex [n]] we define (i) == { ji E E} as the index set of vertices adjacent to vertex i. In our algorithm, public keys and secrets of client are shared with clients j E Adj
V represents client i, and the edge {i.j} E
Now, using the assignment graph notation, we formally define the suggested algorithm. Due to the space limitation, we put the algorithm in Supplementary Materials A here we only describe what differs from SA. In Step 0, instead of broadcasting the public keys (c, s.'K for client j to all other clients, the server sends the public keys only to the client satisfying E Adj(i) n Vi. In Step 1, each client i V1 uses ofut-of-((Adj(t + 1) secret sharing scheme to generate shares of 5 and b,, i.e., SSK (t., (1,1)d)(1111, (5f A and b, (f..) (+.A)00))) (e and sends the encrypted s masked private model
SK and bug to client j through the server. In Step 2, client i computes the
0. =; PRG((::+ +
Σ
PRG(sis)
Σ
PRG(
(3)
A

---

Under review as a conference paper at ICLR 2021
and transmits 0 to the server. In Step 3, client sends 65,5 to the server for all j E V/3 n Adj())) and sSK to the server for all j E (V2) (/2 ) n Adj(t). After reconstructing secrets from shares, the sends 5, server obtains the sum of the local models 0g as
Σ = iEV
Σ 0. iEV
Σ V
PRG
E (RG() +
Σ (R.()
(4)
Note that the suggested protocol with n-complete assignment graph G reduces to SA.
Here we define several notations representing the evolution of the assignment graph G as some of the nodes may drop out of the system in each step. Recall that V. V and Vi+1 is defined as the set of survived nodes in Step i E {0, ... 3)- Let us define G; as the induced subgraph of G whose vertex set V,, i.e., G; = G (V),). Then, Gi+1 represents how the nodes survived until Step i are connected. We define the evolution of assignment graph during the protocol as G -Go, GI, G4))
In [ig-[] we illustrate example of the suggested algorithm with = 5 clients. Fig. corresponds to SA (Bonawitz et al., 2017). while Fig. [b depicts the proposed scheme. Here, we focus on the resources of client 1. Note that each client exchanges public keys and secret shares with its adjacent clients. For example, client exchanges the data with four other clients in the conventional scheme, while client exchanges the data with clients 3 and 5 in the suggested scheme. Thus, the proposed CCESA requires only half of the bandwidth compared to the conventional scheme. In addition, CCESA requires less computational resources than conventional scheme, since each client generates less secret shares and pseudo-random values, and performs less key agreements.
required communicatioon/cmmpuutaccc
THEORETICAL ANALYSIS
4.1 PERFORMANCE METRICS
The proposed CCESA algorithm aims at developing private, reliable and resource-cfficient solutions for federated learning. Here, we define key performance metrics for federated learning systems including federated averaging (McMahan et al.) 2017). SA (Bonawitz et al.) 2017) and CCESA. Recall that the server receives (masked) model parameters 0; from clients Va, and wants to update the global model as the sum of the unmasked model parameters, i.e., Ogtohal < Eiev, O.. The condition for successful (or reliable) global model update is stated as follows.
Definition 1. A system is called reliable if the server successfully obtains the sum of the model parameters Eiev, Og aggregated over the distributed clients.
Now, we define private federated learning. In our analysis, we focus on a passive eavesdropper who can access to any information transmitted between any client and the server throughout running CCESA algorithm, namely, public keys of clients, secret shares, masked local models and the indices of survived clients V Once eavesdropper gets the local model 0; of client it can reconstruct the private data (e.g., face image or medical records) of the client or can identify the client which contains the target data. In general, an cavesdropper obtains the sum of local models occupied by subset T of clients, similar privacy attack is possible for the subset of clients. Thus, to preserve the data privacy, it is safe to protect the information on the partial sum of model parameters against the eavesdropper, we formalize this.
Definition 2. system is called private if ((ieT = O./E) holds for all T satisfying T C. V3 and T & {Ø, Vs). Here, H is the entropy function, and E is the information accessible to the eavesdropper.
When both reliability and privacy conditions hold, the server successfully updates the global model, while an cavesdropper cannot extract data in the information-thhoreee sense. We define p(r) and p(p) as the probabilities that reliability and privacy conditions do not hold, respectively.
OOur threat model is equivalent to the "server-only" "client-server collusion" adversary considered in secure aggregation (Bonawitz et al. 2017
adversary, which is weaker than

---

Under review as a conference paper at ICLR 2021
4.2 RESULTS FOR GENERAL ASSIGNMENT GRAPH G
Recall that our proposed scheme is specified by the assignment graph G. We here provide mathe- matical analysis on the performance metrics of reliability and privacy. in terms of the graph G. To be specific, the theorems below provide the necessary and sufficient conditions on the assignment graph G' enable reliable/private federated learning, where the reliability and privacy are defined in Definitions] I aand 2 Before going into the details, we first define informative nodes as below.
Definition 3. node E Vo is informative if (i)j(i) U (i)) n Val 2 t holds.
Note that node is called informative when the server can reconstruct the secrets (by or 8 of node i in Step of the algorithm. Using this definition, we state the condition on graph for enabling reliable systems as below.
Theorem 1. The system is reliable if and only if node i in informative for all i E V/z. where V/3 = 133 fiE V2 Adj(i) n V33 + 2} is the union of Va and the neighborhoods of V3 within V2.
Proof. The full proof is given in Supplementary Materials; here we provide sketch for the proof. Recall that the server receives the sum of masked models Σ V/ 0,, while the system is said to be
reliable if the server obtains the sum of unmasked models Σ leV; 0g. Thus, the reliability condition holds if and only if the server can cancel out the random terms in (4), which is possible when either
sgK or is recovered for all E V/z"_ Since a secret is recovered if and only if at least & shares are gathered from adjacent nodes, we need (i) U (i)) n Val 2 4. which completes the proof. L
Now, before moving on to the next theorem, we define some sets of graph evolutions as below:
Gc = {G (Go, GI, ............................... G4): G3 is connected },
Gn = [ = (Go, GI.... G4)= G3 is not connected },
GNI = {G E Go : VI E [n], Ei E Ci such that node i is not informative).
Here, when G3 is a disconnected graph with 2 2 components, Ct is defined as the vertex set of the 1th component, and Ci == C. U (i E V/2 (d) n Ci * Ø0.. Using this definition, we state a sufficient condition on the assignment graph to enable private federated learning.
Lemma 1. The system is private G Gc.
Proof. Again we just provide a sketch of the proof here; the full proof is in Supplementary Mate- rials. Note that G3 is the induced subgraph of G whose vertex set is V3. Suppose an eavesdropper has access to the masked local models (0. of a subset T C V/3 of nodes. Now, the question is whether this eavesdropper can recover the sum of the unmasked models ΣiST 0g. If G3 is con- nected, there exists an edge {p. 9} such that p E T and g Vs Note that Eier 0 contains the (Rp.g)))) term, while Sp.q is not accessible by the eavesdropper since p. q E Vg- Thus, from 4h the eavesdropper cannot obtain Σier O,, which completes the proof.
Based on the Lemma above, we state the necessary and sufficient condition for private system as below, the proof of which is given in the Supplementary Materials.
Theorem 2. The system is private if and only if G e Go UGNI.
The theorems above provide guidelines on how construct the assignment graph G to enable re- liable and private federated learning. These guidelines can be further specified when we use the Erdös-Rényi graph as the assignment graph G. In the next section, we explore how the Erdös-Rényi graph can be used for reliable and private federated learning.
4.3 RESULTS FOR ERDŌS-RÉNTE ASSIGNMENT GRAPH G
The Erdōs-Rénys graph E G(n, p) is a random graph of n nodes where each edge connecting two arbitrary nodes is connected with probability p. Define CCESA(n. p) as the proposed scheme using the assignment graph of G E ((n.)). According to the analysis provided in this section, CCESA(n, p) almost surely achieves both reliability and privacy conditions, provided that the con- nection probability is chosen appropriately. Throughout the analysis below, we assume that each client independently drops out with probability g at each step (from Step 0 to Step 3), and the secret sharing parameter f; is set to f for all i E [n].

---

Under review as a conference paper at ICLR 2021
4.3.1 FOR ASYMPTOTICALLY LARGE n
We start with the analysis on CCESA(n,) p) when is asymptotically large. The following two theorems provide lower bounds on p to satisfy reliability/privacy conditions. The proofs are provided in Supplementary Materials.
(n=-1)log(nn1)) (n- ()(2)) (2((1])) -)
Theorem 3. CCESA(n, p) is asymptotically almost surely reliable if >
Theorem 4. CCESA(n. p) asymptotically almost surely private if
log log[[n( 1-01² n log
((1--)00-0 log
From these theorems, the condition for achieving both reliability and privacy is obtained as follows.
Remark 1. Let
( - 9)a vn log
3 / - 1) log(n 1) 1)
p maxx
(5)
[x(1 - 9)) /n log (n 1)(2(1 -)
p > p". then CCESA(n, p) is asymptotically almost surely (a.a.s.) reliable and private. Note that the threshold connection probability p' is decreasing function of Thus, the proposed algorithm is getting more resource efficient than SA as grows, improving the scalability of the system.
In the remarks below, we compare SA and the proposed CCESA, in terms of the required amount of communicaioo//compuaatoono resources to achieve both reliability and privacy. These results are summarized in T
Remark 2. Let B be the amount of additional communication bandwidth used at each client, com- pared to that of federated averaging (McMahan et al.) 2017). Since the bandwidth is proportional np, we have BOCES A(n.p) tocol utilizes a much smaller bandwidth compared to SA in (Bonawitz el al. 2017). The detailed comparison is given in Section of the Supplementary Materials.
log and Bşa ~ On). Thus, the suggested CCESA pro-
Remark 3. Compared to SA, the proposed CCESA algorithm generates a smaller number of secret shares and random values, and performs less key agreements. Thus, the computational burden at the server and the clients reduces by a factor of at least Ol logn). The detailed comparison is given in Section D.2 the Supplementary Materials.
4.3.2 FOR FINITE n
We now discuss the performance of the suggested scheme for finite n. Let p(P) be the eπrr prob- ability that CCESA(n, p) does not satisfy the the privacy condition, and define p(v) the error probability that CCESA(n, p) is not reliable. Below we provide upper bounds on p!P) and p!!)
Theorem 5. For arbitrary n.p.q and t, the error probability for reliability p!!)) is bounded by p! S ne (m-1)DRal t-1 (1((1-4)*) where DKL is the Sellback-Leibler (KL) divergence.
Theorem 6. For arbitrary n, p.p and q. the error probability for privacy p(P) is bounded by
[m/22]
p(p)
m 9)
3m (1 ())3)(nmm))
m
(1 k(m--))
Fig. 3 illustrates the upper bounds p(p) and (!r) obtained in Theorems and 6 when p p-- Here, quoal := 1- (1-11-11mm) (1--00 4)+
is defined as the dropout probability of the entire protocol (from Step 0 to Step 3). Note that the upper bounds in Theorems and 6 are decreasing functions of Therefore, the plotted values in Fig. are indeed upper bounds on the error probabilities for arbitrary p > p²- It is shown that system with the suggested algorithm is private and reliable with high probability for an arbitrary chosen p > p². The error probability for the privacy p.P) is below 10 40, which is negligible even for small The error probability for the reliability ( is below 10-2 which means that in at most one round out of 100 federated learning rounds, the (masked) models {0, jivv received by the server cannot be converted to the sum of (unmasked) local models Σiev, 0g- Even in this round when the server cannot obtain the sum of (unmasked) local models, the server is aware of the fact that the current round is not reliable, and may maintain the global model used in the previous round. This does not harm the accuracy of our scheme, shown in the experimental results of Section

---

Under review as a conference paper at ICLR 2021
Upper Seandan pit
Upper on pib)
10
10
12"90
Number Cllnns (1)
Figure 3: Upper bounds on the error probabilities p(r)) and P(a) in Theorems 5 and for p", where p is the threshold connection probability for achieving both reliability and privacy in Note that for arbitrary
p > p', the error probabilities are lower than the upper bounds marked in the figure. One can confirm that the suggested CCESA algorithm private and reliable with a high probability, provided that p p'
Soxal
Step
Step
Step 2
Seep
Server
100
0
51
3572
3533
85
13
100
51
3540
3365
9847
SA
300
0.1
151
10502
10153
255
72847
500
251
19097
18196
449
198
300
17315
432
529645
100
0.6362
2216
100
0.1
51
0.7953
2715
26488
66
8067
CCESA
300
83
0,4100
4435
4354
110
54
5382
500
112
0.3327
3954
3846
145
132
500
0.1
133
0.4159
7634
7403
184
148511
Table 2: Running time (unit: ms) of SA (Bonawitz et al.
2017
and suggested CCESA
EXPERIMENTS
Here we provide experimental results on the proposed CCESA algorithm. We compare CCESA and secure aggregation (SA) of (Bonawitz et al., 2017) in terms of time complexity (running time), reliability, and privacy. We tested both schemes on two real datasets, T Cambridge database of faces (https://www. wwwpwwwwwwwww.oc../.../..
and CIFAR-10. For the AT&T face dataset containing images of 40 individuals, we considered a federated learning setup where each of n 40 clients uses its own images for local training. All algorithms are implemented in python and PyTorch (Paszke et al. 2017). Codes will be made available to the public.
5.1 RUNNING TIME
In Table 2,
we tested the running time of our CCESA and existing SA for various n and qoal- Similar to the setup used in (Bonawitz et al. 2017), we assumed that each node has its local model with dimension m = 10000, where each element of the model is chosen from the field F2 Here, & is selected by following the guideline in Supplementary Materials, and p is chosen p*
O( O(v ((Vlog n/nn defined in (5) which is proven to meet both reliability and privacy conditions. For every Qotal setup, the proposed CCESA(R. p) requires p times less running time compared with the conventional SA of (Bonawitz al.) 2017 This is because each client generates p times less number of secret shares and pseudo-random values, and performs times less number of key agreements. This result is consistent with our analysis on the computational complexity in Table TI
5.2 RELIABILITY
Recall that a system is reliable if the server obtains the sum of the local models Eiey, O.. Fig. shows the reliability of CCESA in CIFAR-10 10 dataset. We plotted the test accuracies of SA and the suggested CCESA(n,, p) for various p. Here, we included the result when p = p = 0.3106, where p" is the provably minimum connection probability for achieving both the reliability and privacy according to Remark M One can confirm that CCESA with p = p achieves the performance of SA in both i.i.d. and non-i.i.d. data settings, coinciding with our theoretical result in Theorem B Moreover, in both settings, selecting p = 0.25 sufficient to achieve the test accuracy performance of SA when the system is trained for 200 rounds. Thus, the required communication/coopptaiii resources for guaranteeing the reliability, which is proportional to np, can be reduced to 50% of the conventional wisdom in federated learning. Similar behaviors are observed from the experiments on AT&T Face dataset, as in Fig. B.I of the Supplementary Materials.
5.3 PRIVACY
We first consider a privacy threat called model inversion attack (Fredrikson et al. 2015). The basic setup is as follows: the attacker cavesdrops the masked model 0 sent from client to the server, and reconstructs the face image of a target client. Under this setting, we compared how the eavesdropped model reveals the information on the raw data for various schemes. As in Fig. and Fig. B.2 in the

---

Under review as a conference paper at ICLR 2021
Test Accuracy
80
Test Accuracy
80
60
60
40
40
20
20
pm0 5.
pr0.22
px0.15
20
40
60
80
100
120
140
160
190
200
40 50
100
120
140
160
180
200
Federated Learning Round
Federated Learning Round
(a) i..d. data across clients
(b) non-iid. data across clients
versus proposed CCESA(n, p) with various connection probability p. for federated learning using CIFAR-10 10 dataset. Here, we set n = 1000 and qaoai = 0.1. The suggested CCESA
Figure Test accuracies
achieves the ideal test accuracy by using only 75% of the communicatio//comuaatiio
resources used in the
conventional SA. This shows the reliability of CCESA in real-world scenarios.
Schemes \ Number training data (Moxin)
5000
10000
15000
50000
Federated Averaging (MMMahan
72.49%
70.72%
72.80%
66.47%
Secure Aggregation (SAT [Bonawalz ef 2017
49.67%
49.96%
49.85%
49.33%
CCESA (Suggestel)
49.291%
50.14%
49.02%
50.009
Table 3: Accuracy of the membership inference attack on local models trained on CIFAR-IO. The scheme with a higher attack accuracy is more vuinerable to the inference attack. In order to maximize the uncertainty of the membership inference, the test set for the attack model consists of 5000 members (training data points) 5000 non- non-members (evaluation data points). For proposed CCESA, the attacker no better than the random guess with accuracy = 50%, showing the preeeeviie ability of CCESA.
Supplementary Materials, the vanilla federated averaging (McMahan et al., 2017) with no privacy- preserving techniques reveals the characteristics of individual's ''s face, compromising the privacy of clients. On the other hand, both SA and CCESA do not allow any clue on the client's face; these schemes are resilient to the model inversion attack and preserve the privacy of clients. This observa- tion consistent with our theoretical results that the proposed CCESA guarantees data privacy. We also considered another privacy threat called the membership inference attack (Shokri al. 2017).
Here, the attacker eavesdrops the masked model 0 and guesses whether target data a member of the training dataset. Table B summarizes the accuracy the inference attack for CIFAR-10 10 dataset, under the federated learning setup where Uraain training data is equally distributed into n. 10 clients. The attack accuracy reaches near 70% for federated averaging, while SA and CCESA have the at- tack accuracy of near 50%, similar to the performance of the random guess. This shows that both SA and CCESA do not reveal any clue on the local training set, which secures data privacy.
6 CONCLUSION
We devised communication-comppene preserves the data privacy of federated learning in a highly resource-efficient manner. Based on graph-theoretic analysis, we showed that using On log n) resources is sufficient for guaranteeing reliability and privacy of the proposed system with n clients, which is much smaller than ( resources used in the conventional wisdom. Our experiments on real datasets, measuring the test accuracy and the privacy leakage, show that CCESA requires only 50% of resources than the con- ventional wisdom, achieve the same level of reliability and privacy.
efficient secure aggregation (CCESA) which successfully

---

Under review as a conference paper at ICLR 2021
REFERENCES
Martin Abadi, Andy Chu, Ian Goodfellow, 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, pp. 308-318, 2016.
Gergely Acs and Claude Castelluccia. I have dream dreamm!(iiffrrentially private smart metering). In International Workshop on Information Hiding, pp. 118-132. Springer, 2011.
Yoshinori Aono, Takuya Hayashi, Lihua Wang, Shiho Moriai, et al. Privacy-pree seeaccypreeevvingg deep learn- ing via additively homomorphic encryption. IEEE Transactions on Information Forensics and Security, 1333)11333-1345, 2017.
Maria Florina Balcan, Avrim Blum, Shai Fine, and Yishay Mansour. Distributed learning, commu- nication complexity and privacy. In Conference on Learning Theory, pp. 26-1, 2012.
James Henry Bell, Kallista A Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. Secure single-server aggregation with (poly) logarithmic overhead. In Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, pp. 1253-1269, 2020.
Michael Ben-Or, Shafi Goldwasser, and Avi Wigderson. Completeness theorems for non- cryptographic fault-tolerant distributed computation. In Proceedings of the twentieth annual ACM symposium on Theory of computing, pp. 1-10. 1988.
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Kam Seth. Practical secure aggregation for privacy- preserving machine learning. In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pp. 1175-1191, 2017.
Theodora Brisimi, Ruidi Chen, Theofanie Mela, Alex Olshevsky, loannis Ch Paschalidis, and Wei Shi. Federated learning of predictive models from federated electronic health records. Interna- tional journal of medical informatics, 11::59-67, 2018.
Zachary Charles, Dimitris Papailiopoulos, and Jordan Ellenberg. Approximate gradient coding via sparse random graphs. arXiv preprint 1711.v1 2017.
Ivan Damgård, Valerio Pastro, Nigel Smart, and Sarah Zakarias. Multiparty computation from somewhat homomorphic encryption. In Annual Cryptology Conference, pp. 643-662. Springer, 2012.
Cynthia Dwork, Aaron Roth, al. The algorithmic foundations of differential privacy. Foundations and Trends in Theoretical Computer Science, 93-44)211 1077 2014.
Tariq Elahi, George Danezis, and Ian Goldberg. Privex: Private collection of traffic statistics for anonymous communication networks. In Proceedings of the 2014 ACM SIGSAC Conference on Computer and Communications Security, pp. 1068- 1079, 2014.
Matthias Fitzi, Matthew Franklin, Juan Garay, and Harsha Vardhan. Towards optimal and efficient perfectly secure message transmission. In Theory of Cryptography Conference, pp. 311-322. Springer, 2007.
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures. In Proceedings of the 22nd ACM SIGSAC Confer- ence on Computer and Communications Security, pp. 1322-1333, 2015.
Robin Geyer, Tassilo Klein, and Moin Nabi. Differentially private federated learning: A client level perspective. arXiv preprint arXiv:1712.07557, 2017.
Slawomir Goryezka and Li Xiong. A comprehensive comparison of multiparty secure additions with differential privacy. IEEE transactions on dependable and secure computing, 14(5):463- 477, 2015.
Shai Halevi, Yehuda Lindell, and Benny Pinkas. Secure computation on the web: Computing with- out simultaneous interaction. In Annual Cryptology Conference, pp. 132-150. Springer, 2011.

---

Under review as a conference paper at ICLR 2021
Danny Harnik, Yuval Ishai, and Eyal Kushilevitz. How many oblivious transfers are needed for secure multiparty computation? In Annual International Cryptology Conference, pp. 284-302. Springer, 2007.
Rob Jansen and Aaron Johnson. Safely measuring tor. In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pp. 1553-1567, 2016.
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.04997, 2019.
Iraklis Leontiadis, Kaoutar Elkhiyaoui, and Refik Molva. Private and dynamic time-series data ag- gregation with trust relaxation. In International Conference on Cryptology and Network Security, pp. 305 305-320..00 Springer, 2014.
Iraklis Leontiadis, Kaoutar Elkhiyaoui, Melek Önen, and Refik Molva. Puda privacy and unforge- ability for data aggregation. In International Conference on Cryptology and Network Security, pp. 3-18. Springer, 2015.
Ychuda Lindell, Benny Pinkas, Nigel P Smart, and Avishay Yanai. Efficient constant round multi- party computation combining bmr and spdz. In Annual Cryptology Conference, pp. 319-338. Springer, 2015.
Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. Communication-efficeen learning of deep networks from decentralized data. In Artificial Intelli- gence and Statistics, pp. 1273-1282. PMLR, 2017.
Luca Melis, Congzheng Song. Emiliano De Cristofaro, and Vitaly Shmatikov. Exploiting unintended feature leakage in collaborative learning. In 20/9 JEEE Symposium on Security and Privacy (SP), pp. 691-706. IEEE, 2019.
Adam Paszke, Sam Gross, Soumith Chintala, Gregory Chanan, Edward Yang, Zachary Viio, Zeming Lin, Alban Desmaison, Luca Antiga, and Adam Lerer. Automatic differentiation in pytorch. 2017.
Swaroop Ramaswamy, Rajiv Mathews, Kanishka Rao, and Françoise Beaufays. Federated learning for emoji prediction in mobile keyboard. arXiv preprint arXiv: /906/ 04329, 2019.
Adi Shamir. How share a secret. Communications of the ACM, 22(11):612 613, 1979.
Sheng Shen, Tianqing Zhu, Di Wu, Wei Wang, and Wanlei Zhou, From distributed machine learning to federated learning: In the view of data privacy and security. Concurrency and Computation: Practice and Experience, 2020.
Elaine Shi, TH Hubert Chan, Eleanor Rieffel, Richard Chow, and Dawn Song. aggregation of time-series data. In Proc. NDSS, volume 2, pp. 1-17. Citeseer, 2011.
Reza Shokri and Vitaly Shmatikov. Privacy-preserving deep learning. In Proceedings of the 22nd
ACM SIGSAC conference on computer and communications security, pp. 1310-1321,2015,
Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. Membership inference at- tacks against machine learning models. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 3-18. IEEE, 2017.
Jinhyun So, Basak Guler, and A Salman Avestimehr. Turbo-aggregate: Breaking the quadratic aggregation barrier in secure federated learning. arXiv preprint urXiv:2002.04156. 2020.
Jy-yong Sohn, Dong-Jun Han, Beongjun Choi, and Jaekyun Moon. Election coding for distributed learning: Protecting signsgd against byzantine attacks. Advances in Neural Information Process- ing Systems, 33, 2020.
Katrine Tjell and Rafael Wisniewski. Privacy preservation in distributed optimization via dual de- composition and admm. In 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 7203-7208. IEEE, 2019.

---

Under review as a conference paper at ICLR 2021
Stacey Truex, Ling Liu, Ka-Ho Chow, Mehmet Emre Gursoy, and Wenqi Wei. Ldp-fed: federated learning with local differential privacy. In Proceedings of the Third ACM International Workshop on Edge Systems, Analytics and Networking, pp. 61-66, 2020.
Kang Wei, Jun Li, Ming Ding, Chuan Ma, Howard H Yang, Farhad Farokhi, Shi Jin, Tony QS Quek, and Vincent Poor. Federated learning with differential privacy: Algorithms and performance analysis. IEEE Transactions Information Forensics and Security, 2020.
Jie Xu and Fei Wang. 19100220, 2019.
Federated learning for healthcare informatics.
arXiv preprint
Qiang Yang. Yang Liu, Tianjian Chen, and Yongxin Tong. Federated machine learning: Concept and applications. ACM Transactions on Intelligent Systems and Technology (TIST), 10(2):1-19, 2019.
Timothy Yang, Galen Andrew, Hubert Eichner, Haicheng Sun, Wei Li, Nicholas Kong, Daniel Ra- mage, and Françoise Beaufays. Applied federated learning: Improving google keyboard query suggestions. arXiv preprint arXiv:1812.0200000 2018.
Chunlei Zhang, Muaz Ahmad, and Yongqiang Wang. Admm based privacy-preserving decentralized optimization. IEEE Transactions on Information Forensics and Security, 14(3):565-580, 2018.
12

---

Under review as a conference paper at ICLR 2021
A DETAILED DESCRIPTION OF THE CCESA PROTOCOL
Algorithm 1: Communication Commuuttioonnoo Efficient Secure Aggregation (CCESA) Protocol
Input: Number of clients assignment graph G. privacy thresholds f; of all clients i E [n] local models 0, of all clients i E [n]. Jaffie-Hellman key pairs (c, (c"K esk) ), (s : 5K) ce,
of all clients E [ni] and corresponding key agreement function pseudo-random generator PRG
Step 0. Advertise Keys
Client
Sends
cf oe , ,K to the server
Server:
Collects the messages from clients (denote this set of clients as Vi)
Sends {(1, c, s
"ee A4t)))n to clients j E Vi;
PK
Step 1. Share Keys
Client
Generates random element bj
Applies t--out-of-(IAdj(()) + 1) secret sharing schemes to b, and se
b; (+.AA (b..)) (01,))E((A)())))))) sg ((.1Adr())+)) (s Agtt))))))
Encrypts [b $5 to [b, se using the authenticated encryption with key [c,f ,csS)
Sends [(i, j. big. s (a5e)) to the server
Server:
Collects the messages from clients (denote this set of clients V2)
Sends ji brg s.) The to all clients j V2
Step 2. Masked Input Collection
Client
Computes $1, = [[s 8 SSK) and
0. 0, + PRG((.) + EsEVenA PRG(sL.) ΣjEVSnAN(ONNSS (RG():.)
Sends (i. 8.) to the server
Server:
Collects the messages from clients (denote this set of clients as V/))
Sends V/3 to all clients j in V3
Step 3. Unmasking
Client
Decrypts bis with key Mafk, o to obtain b,, for all j E Adj n V/3 SK for all j E Adj(i) n (V2(1) Decrypts 5 with key flafk o5k) to obtain st
Sends (basheendggn) { (1 to the server Server:
Collects the messages from clients
Reconstructs by from (bi.j) Jeasson,, for all i V/3
Reconstructs s5SK from (sSK }eeas(nn(ssa)) for all V/\V,
Computes $r.j = f(s PK s for all E Ai)
Computes the aggregated sum of local models
Σien, 0: Σiev, 0, Σiev, PRG(b.) - (RG()
+ LEVEi
(RG(s..))

---

Under review as a conference paper at ICLR 2021
Test Apouracy
100
Tect Accuracy
SA -p=0.7
SA
p=0.75
80
8
p=0.6
-p=0.7
9-0.85
10
15
20
25
30
25
40
45
50
30
Federated Learnnng Round
Federated Learning Round
(a) nooa 0
(b) Tunal 0.1
Figure B.1: Test accuracies of SA versus proposed (c, p) with various connection probability p. for
federated learning using the AT&T face dataset. Here, we set 40 and f 21. The suggested CCESA achieves the ideal test accuracy by using only 70% of the communicaioo///comptttionn resources used in the conventional SA.
Schemes \ Number of training data (Mtrain)
5000
10000
15000
50000
Federated Averaging McMahan 2017)
70.41%
65.82%
65.89%
60.62%
Secure Aggregation (SA) (Bonawitz et al. 2017
49.78%
49.97%
49.91%
10%
CCESA (Suggested)
49.48%
50.07%
49.16%
50.00%
Table B.1: Precision of the membership inference attack on local models trained on CIFAR --. The scheme with a higher attack precision is more vulnerable to the inference attack. For the proposed CCESA, the attacker is no better than the random guess with precision = 50%, showing the privacy-preserving ability of CCESA.
B ADDITIONAL EXPERIMENTAL RESULTS
B.1 RELIABILITY
In Fig. 4 of the main paper, we provided the experimental results on the reliaiblity CCESA on CIFAR-I0 10 dataset. Similarly, Fig. B.1 the reliability of CCESA in AT&T Face dataset, where the model trained over n = 40 clients. We plotted the test accuracies of SA and the suggested 0.7 is sufficient to achieve the test accuracy performance of SA when the system is trained for 50 rounds. Thus, the required communication//omppaaiinn
CCESA(n,P) for various p. In both settings of quall selecting
resources for guaranteeing the reliability, which is proportional to np, can be reduced to 70% of the conventional wisdom in federated learning.
B.2 PRIVACY
In Section 5.3 and Fig. of the main paper, we provided the experimental results on the AT&T Face dataset, under the model inversion attack. In Fig. B.2 we provide additional experimental results on the same dataset for different participants. Similar to the result in Fig. [ the model inversion attack successfully reveals the individuals identity in federated averaging (McMahan et al.) (017), while the privacy attack is not effective in both SA and the suggested CCESA.
In the main manuscript, we have also considered another type of privacy threat called membership inference attack (Shokri al., 2017). where the attacker observes masked local model 0, sent from client i to the server, and guesses whether particular data is the member of the training set. We measured three types of performance metrics the attacker: accuracy (the fraction of the records correctly estimated the membership), precision (the fraction of the responses inferred members of the training dataset that are indeed members) and recall (the fraction of the training data that the attacker can correctly infer members). Table in the main manuscript summarizes the attack accuracy result, while Table B. shows the attack precision for CIFAR- 10 dataset. We also observed that recall is close 1 for all schemes. Similar to the results on the attack accuracy, Table B. shows that the attack precision of federated averaging reaches near 70%. while that of SA and CCESA remain around the baseline performance of random guess. This shows that both SA and CCESA do not reveal any clue on the training set.

---

Under review as a conference paper at ICLR 2021
(a)
(
(c)
(d)
Figure B.2: The result model inversion attack to three schemes, (b) suggested scheme (CCESA), (c) SA (Bonawitz et al. (017)) and (d) federated averaging (McMahan et al. (017)), for AT&T Face datasct. The original training images at (a) can be successfully reconstructed by the attack only in federated averaging setup, i.c. both SA and CCESA achieve the same level of privacy.

---

Under review as a conference paper at ICLR 2021
C
PROOFS
C.I PROOF OF THEOREM I
Proof. Note that the sum of masked local models obtained by the server is expressed
Σ 1EV3
0
Σ 8 Σ
PRG(b;) +z
iEV/
where
2 Σ
Σ
(RG() Σ
Σ
(R.
KEV, (V))
SEV, (VVn))((())))
Here, z can rewritten as
Σ
Σ
PRG(S
Σ
E
PRG()
iEVs JEVa
iEVs jEVaradd(()ss
Σ
Σ
PRG(S
E
Σ
PRG(
JEVS Adj(t)
JEV, iEV
Σ
Σ
PRG( Σ
Σ
PRG((
JEVi (aliiVVaniiiiiie (d)()
NEV2 JEVanA(()i
Σ
Σ
PRG(S Σ
Σ
PRG(
iEVs Adj
NEVs JE(VE) V Vo)nAd(()))))
Σ
Σ
PRG(3:3)
Σ
E
PRG($1.)
VEVa JEVaNAd((innss
VEVi\V jEVanAd((iiiss
Σ
Σ
PRG()
Σ
E
PRG($i,)
EV
JEV, (VV1VV1AAnn))))))
Σ
Σ
PRG(s
Σ
Σ
PRG()
NEV JELS
iEV;
Σ
Σ
PRG() Σ
Σ
PRG($
IEVs JE(VANGNNAAAjoON
JEVS
Σ
Σ
PRG( Σ
Σ
PRG(
iEVs jE(Vs' (K))A((0)ssss
jE(V VG)nAd(();>))
where (a) and (b) come from 8i, = 83,. In order to obtain the sum of unmasked local models Eiev, O, from the sum of masked local models Σiev, 6, the server should cancel out all the ran- dom terms in Σiev, PRG(b,) + z. In other words, the server should reconstruct b, for all i E V3 and .5 for all j V Since the server can obtain (idj(()) ( secret shares of client i in Step 3. (Adj(1) U {+)) n Vil 2 t; for all E Vi= is a sufficient condition for reliability.
Now we prove the converse part by contrapositive. Suppose there exists i V33 such that (idj(i)) (V)) < t, In this case, note that the server cannot reconstruct both s and b, from the shares. If E Va, the server cannot subtract PRG(b:) from Eiev, 6,. As a result, the server cannot obtain Eie 0,- If ViS Vg. the server cannot subtract PRG(s;,) for all j E Va3 since the server does have any knowledge of neither siK nor SK Therefore, the server cannot compute Σ.ev, 0,, which completes the proof.
C.2 PROOF OF LEMMA I
Proof. Let V/3 be an arbitrary of clients satisfying 7 (Ø, V3). is sufficient prove the following statement: given connected graph G3, an eavesdropper cannot obtain the partial sum of

---

Under review as a conference paper at ICLR 2021
local models ΣieT 0g from the sum of masked models ΣJET 0g. More formally, we need to prove
H
0,) H
Σ
0.)-
SET
SE
SET
Note that the sum of masked local models Σier 02 accessible to the eavesdropper is expressed as
Σ 1ET
0,
= _e +
PRG(
+z.
(6)
ET
ET
where
2
Σ
E
PRG(S:.)
Σ
PRG($:.)
ET Ady()is
iET
iET JEVanAd
Σ
Σ
PRG()
Σ
E
(RG()
iET
JEV, (ETAA
Σ
Σ
PRG(S:s)
Σ
E
PRG($
AEVarAd((isi Adj())iis ET JEVi
iEV: JETNAA(()HiC
PRG() + iE JETNA((():K))
Σ
E
Σ
Σ
(RG()
iET SEVAATTTAAIOON
E
E
PRG() - E
E
PRG($
iET (E
VEViT JETNA()():ss))
Σ
PRG($ Σ
E
PRG(s
JET NE(VANTTAAAOO)
Σ
PRG(S.)) Σ
E
PRG()..)
ET JE(VA (TAAT)AA
iET jE(V) JEVVATTTAAee
Σ
PRG(S Σ
Σ
PRG($.))
NET (AAAA)))A
NET JE(VANSJAAAAO
Σ
PRG($ - Σ XE JE(SST)AAA(OOIK
Σ
NET JE(Vs)))nAd(( (s.)))
Σ
Here, (a) and (b) come from 8új -jj.. If G3 (V/, Ea) is connected, there exists edge = {p. q) such that p E T and (Va)T), As a consequence, pseudorandom term (RG(s
is included in and its coefficient Cp.9 is determined (if p q). -1 (if > q). Note that equation (6) can be rewritten as
Σ ET
- 0, Cp.q" PRG + ST
where r is the sum of pscudorandom terms which do not include PRG(sp.g). In order to unmask PRG(sp.g). the cavesdropper need to know at least one of the secret keys of clients p and q. However, the eavesdropper cannot obtain any shares of the secret keys since the server do not request the shares of sp and sSK in step 3. Therefore, due to the randomness of pseudorandom generator,
H H(EEET 0.1 ΣiET 0.) = H(ETT 0.) holds, which completes the proof.
C.3 PROOF OF THEOREM 2
Proof. We first prove that the system is private if G E Go UNII- When G E Go, the statement holds directly from Lemma Thus, below we only prove for the case of G E GNT. Note that it is sufficient to prove the following statement: given a graph evolution G (Go, GI,... G4) E GNz, an eavesdropper cannot obtain the partial sum of local models ΣiET O, from the sum of masked models Σier for every T C V/3 satisfying T & (Va, Ø3. More formally, we need to prove
H
H
0
0 H H
02)
SET

---

Under review as a conference paper at ICLR 2021
When T = Cj for some / E [k], there exists i* O such that node i is not informative, according the definition of INy. Thus, the server (as well as eavesdroppers) cannot reconstruct both and se Note that the sum of masked models is
Σ 0, VET
(b) + jET (EV2UA((()
Σ (-1)4>>-PG(()A)))
(8)
iT
RE
where 1 is the indicator function which is value 1 when the statement A is true, and 0 otherwise. When i" E C = T, we cannot unmask PRG(b;-) in this equation. When E CCt',r, there exists j E C₁ such that [i*, E F. Note that the eavesdropper needs know either s5K or s order to compute PRG( Since it is not informative, the eavesdropper cannot get s Moreover, since the server has already requested the shares of bj. the eavesdropper cannot access sgK Thus, the eavesdropper cannot unmask PRG($ from (8) All in all, the eavesdropper cannot unmask at least one pseudorandom term in Σier 0,, proving 77)
When T + Ci VI E [k], there exists an edge E = {p, of such that p E T and E (Va)7) Thus, we cannot unmask (8G()) from Σier 0.. Following the steps in Section C.2
we have
Now, we prove the converse by contrapositive: if = (Go, G), G4) E GD n g then the system is not private. In other words, we need to prove the following statement: if G3 is disconnected and there exists a component Ct such that all nodes in C are informative, then the system is not private. Let Cj. Then, the eavesdropper obtains
Σ iET
0.
= Σ
0 Σ
PRG(b.) + +z,
iET
iET
where
2 = E
(g)
E-(1) 1:0 PRG().)) (b) 0.
ËET JEV2nAdj(1)
JET
Note that (a) holds since T is component, (b) holds from stj = 8j.. Moreover, the eavesdropper can reconstruct by for all E T in Step 3 of the algorithm. Thus, the eavesdropper can successfully unmask random terms in Eee 0, and obtain Eier 0, This completes the proof.
C.4 PROOF OF THEOREM 3
Proof. Consider Erdös-Rény Rényi assignment graph G E p). Let == (id be the degree of node and X; == (d) n Val be the number of clients (except client i) that successfully send the shares of client to the server in Step 3. Then, N₂ and X, follow the binomial distributions
N B(2 1,p), X, BNN (1 - 4)t) B(n 1. p(1 - 9)*),
respectively, By applying Hoeffding's 's inequality random variable X,, obtain
P(X, < (n 1)p(1 - 9)* v(n log(n - 1)) s 1/(n - 1)?.
Let E be the event that the system is not reliable, i.e., the sum of local models Σiev, 0 is not reconstructed by the server, and E, be the event (I(Adj()) U (V)) < f), i.e., secret of client i not reconstructed by the server. For given p
++ / [n-
(og
1-1)((10)* we obtain
P(E) (a) P(Usevt B.) S Plu (Xi<1))s Σ P(X, <1)
iEV;
P(X, t) = nP({ <t)
iE(n]
SnP(Xi < (n- 1)p(11 - q)º ((n - 1) log(n 1)) <
n
12+00 0,
(n 1)2

---

Under review as a conference paper at ICLR 2021
where (a) comes from Theorem Therefore, we conclude that CCESA( p) is asymptotically
almost surely (a.a.s.) reliable if p ++/(n1))og(t=-)) Furthermore, based on the parameter (x-1][1-9)
selection rule of in Section we obtain a lower bound on p as
p + n2 1) log(n - (n-1)pt (n log(n 1)+1 + (n log(n - 1)
1) 9)
1) 9)
Rearranging the above inequality with respect to yields
3/ (n 1) log(n 1)
p (n 1)(2(1 1)
C.5 PROOF OF THEOREM 4
Proof. Let X := |/3l be the number of clients sending its masked local model in Step 2. Then, X follows Binomial random variable (n,, (1-q) "). Given assignment graph of CCESA(n, p), note that the induced subgraph G3 G VV is an Erdōs-Rényi graph G(X,p).
First, we prove
P(G3 is connected|| |X - n11 - 4) Vn
1,
(9)
In([n(1-0)*
if p"
(1 + c). The left hand side of (9) can be rewritten as 1 Vnlan
P(G₂ is connected
X- n(1 g) Vnlnn)
Eie(n(1- 0) V P(X (),((G(L,)) is connected)
Lie(((1-))) <a
P(X -
Here, we use a well-known property of Erdōs-Rényí graph: pl,,p) asymptotically almost surely (a.a.s)) connected p > (1+e) lnl for some > 0. Since ln! is a decreasing function, G(L, p) is a.s.s !
connected for all E [n(1 4)8 Vnlnn, n(1 q)s + vnlnn) when > Thus, for given > p", we can conclude
[n[[n(1-)) Innnn)) [n[ - 0) Vnlnn
P(G3 is connected|| n(1 - 91 Inn) m-000 1.
Now, we will prove that CCESA(n, p) is a.a.s. private when p V². CCESA(n,p) p) is private is lower bounded by
The probability that
P(CCESA(m, p) is private)
P(Gg is connected)
P([XX n1( 1 P(n is connected] X- - -) S Inn))
+ P - 9) Inlnn) is connected| |X n(1 - 9)31 > Vnlun)
( (1-2/nn)) is connected n(1 9) Vn ~-00 1.
where (a) comes from Lemma 1 and (b) comes from Hoeffding's inequality
P([X n(1 4) Vnlnn) 2/n²,
which completes the proof.
C.6 PROOF OF THEOREM 5
Proof. Consider an Erdös Rényi assignment graph G G(n,p). Let N; := [Ad)(i) be the degree of node i, and X; == (Adj(i) n V4 be the number of clients (except client i) that successfully send the shares of client i to the server Step Then, N; and X; follow the binomial distributions
N₂ (nn 1. 1,,), X; B(N, (1 4)² B(n 1. p(1 - -)
19

---

Under review as a conference paper at ICLR 2021
respectively, Let E; be an event (1) U {i}) n Vil < t). i.e., secret of client is not recon- structed by the server. We obtain an upper bound on P( P():) as
1 ) (p(1 () p(1 q)
( =
e (
where (a) comes from Chernoff bound on the binomial distribution. Thus, pfr) is upper bounded by
p(r) (b) P(u E.) & P( (X, <t)) Σ P(X; <t)
'VV
Σ
P(X, < t) nP(x < = ne (n 1)D( (1(1)))))))))
RE(n]
where (b) comes from Theorem
C.7 PROOF OF THEOREM 6
Proof. Let Pac(n, p) be the probability of an event that Erdös-Rényi graph G E G(n,p) is discon- nected. Then, (n, p) is upper bounded as follows.
(n) = P(G(n,p) p) is disconnected)
P(U (there exists subset of k nodes that is disconnected))
ln/2]
P(there exists a subset of is nodes that is disconnected)
ln/2]
P(a specific subset of & nodes is disconnected)
1=1
l2/2]
(1 p) R((n-R
Therefore, p(p) upper bounded by
(a) p(p) I P(Gg = G - V\Va is disconnected)
n
P(Gs has m
p)
Σ
(1
3m (1 1- (mnm)) (ac p)
m
M=0
1m/2
n
(1 q) 3 (1 (1 - 1)
Σ
m
(1 p) km)
k:
m
where (a) comes from Lemma
D REQUIRED RESOURCES OF CCESA
D.1 COMMUNICATION COST
Here, we derive the additional communication bandwidth BCCESA used at each client for running CCESA, compared to the bandwidth used for running federated averaging (McMahan et al. 2017
20

---

Under review as a conference paper at ICLR 2021
We consider the worst-case scenario having the maximum additional bandwidth, where no client fails during the operation.
The required communication bandwidth of each client is composed of four parts. First, in Step O, each client sends two public keys to the server, and receives Ad)) public keys from other clients. Second, in Step 1, each client sends encrypted 2| A| (i) shares to other nodes, and re- ceives 21.Adj(i) shares from other nodes through the server. Third, in Step 2. each client sends masked data y/s of mR bits. Here, is the dimension of model parameters where each parameter represented in bits. Fourth, in Step 3, each client sends [ddj(t) + shares to the server. Therefore, total communication bandwidth of client can be expressed as
(total communication bandwidth) = Adj + 1)ax + (5)Ad(()) + 1)ag + mR,
where 0g and as are the number of bits required for exchanging public keys and the number of bits in a secret share. Since each client requires m. bits to send the private vector 8 in the federated averaging (McMahan et al. 2017), we have
BECESA = 2([Addj()) + 1)ax + (5]Adj(1) + 1)as.
If choose the connection probability p (1 + c)p² for small > O. have BECESA O( log r2), where p* is defined in ( Note that the additional bandwidth Вςл required for SA
can be similarly obtained as BSa- 2nak (5n 4)as having BSA O(n). Thus, we have
BOCESA +0
Bsa
as n increases, showing the scalability of CCESA. These results are summarized in Table Iin in the main manuscript.
D.2 COMPUTATIONAL. COST
We evaluate the computational cost of CCESA. Here we do not count the cost for computing the signatures since it is negligible. First, we derive the computational cost of each client. Given the number of model parameters and the number of clients n, the computational cost of client i is composed of three parts: (1) computing 2) Ad)) key agreements, which takes (i))djii) time, (2) generating shares of f--out-of-|Adjj (i) secret shares of sith and b; which takes (((Ad(())) time, and (3) generating masked local model 0,, which requires O ((m]Adj(i) Adj(t))) time. Thus, the total computational cost of each client is obtained as A(]Ad(i)) + ml)d((i))). Second, the server's computational cost is composed of two parts: (1) reconstructing o--outof--AAdji secrets from shares for all clients E [n)]. which requires O(IAdjii)²) time, and (2) removing masks from masked sum of local models > 0,, which requires ((m ((m)))((i))*) time in the worst case. As result, the total computational cost of the server is ((m) (mm)Adj(() Adj(i) 3). If we choose p = (1 + e)p² for small 6 > 0, the total computational cost per each client is (n log n + mm/n/n log n), while the total computation cost of the server is (mm log n)). The computational cost of SA can be obtained in similar manner, by setting Adj(i) = n 1; each client requires O(n² + mn) time while the server requires Omm?²) time. These results are summarized in Table | in the main manuscript.
E RELIABILITY AND PRIVACY OF CCESA
Here, we analyze the asymptotic behavior of probability that a system is reliablc/private. In our analysis, we assume that the connection probability is set to p" and the parameter t used in the secret sharing is selected based on the rule Section First, we prove that a system is reliable with probability 2 1 One -n ") Using Theorem the probability that system is reliable can be directly derived as
P(A system is reliable) =1 - ((r)
21 - ne (n- ()= (=- (1-00))))
Using the fact that Kullback-Leebbee divergence term satisfies
1 DKL (
1p' -) L n - 1 log
I-1 p1 +
1-
1-1 log
1 1-1
n
n
1 1 (1 9)
=0(Vlogn/n).
21

---

Under review as a conference paper at ICLR 2021
we conclude that CCESA(n, p²) is reliable with probablilty 2 1 - One Vollog))
Now we prove that a system is private with probability 1 1n for arbitrary C' > Using Theorem 6 the probability that a system is private can be obtained as
P(A system is private) =1 P(p)
21
Σ m=0
Om m
where am (1) - q) 3m (1- (1 )) and bm
1m/ (1) (1 p") p²)
Lk=l
Note that the summation term Em= am bm can be broken into two parts: Em Om bm and 2m=ma++1 am bm. where Mah = [n(1 9)²² /2]. In the rest of the proof, we will prove two lem-
mas, showing that Ema ambn O -) and Σ m==ma +1 ambm O(n respectively.
Lemma 2.
Om ambm O
m=
Proof.
Since bm I for all m, we have
Mash
Wehh
ae bm
Om
Note that 4m P(X = =m) holds for binomial random variable X B(n, (1 - -) By utilizing
Hoeffding's inequality, have
Om = P(X S meh) Se -xm S se- en-(-_)))
Therefore, conclude that Emei am O)
Lemma 3.
bmbn = C
m m=mu +1
Proof. Since am I 1 for all m, have
ambn
bm-
+=
m= +1
Let C' > 0 be given. Then, the upper bound on bm can be obtained
[m/2]]
[m/2]
bm =
m
(1
p²
bm)
<
m
e
k(m-k)p"
1:
k:
1=1
[m/2]
mm
-Nk(m ->k(m-k)/m Cm + dm
m
where X = ppnn/long"" n, Cm = (ml Σ 1= m (M(mmk)/mm dn
m
41 m Ak(mm and
mm/2]
k
k*
== [[m(1 - [42) for some C. >
0. The first part of summation is upper bounded by
3"
k*
Cm Σ
m
Ak(m (6(mmm))) k)mm
m A [1(mm-))/m-1)
m [-MAA(Mm*))/mm
m
kml
# km1
Rm l
Am(
k/mm-
(C+1)
1 m A(m -mmm-kmmm-11
m (C+1)
22

---

Under review as a conference paper at ICLR 2021
The second part of summation, we will use the bound bounded by
(A)
(1)
S
Using this bound, dm is upper
dm
1m/22] Σ
m
m
Ak(mm k1/m
m//2
Σ
eml
em
A(m km/m
[m/2]
em 1 -A(m-k)/m
(k)
h
ho +
Aom +1
Jo d +1
Am +1
m/22
em A(m - k3/m
[m/2]
em 2A/2
1 (C +
1- 2)
1= +1
K= +1
For sufficiently large X, have em -A/2 /11 --- 2)) < for some 1. Therefore, dmn. is upper bounded by
dm
8
0
km
where C' = (1- 2)) > 0. Combining upper bounds on cm and dms we obtain bm (C+1)).
O(m Om--(C+))) Since bm is a decreasing function of m,
bmnn+1 = (n min mbmen (a) O(n
m=me+++
holds where (a) comes from meh [n(11 //8/
Combining the above two lemmas, we conclude that CCESA(a, p²) is private with probability 2 (nn C) for arbitrary C > O. These results on the reliability and the privacy are summarized in Table of the main manuscript.
F DESIGNING THE PARAMETER & FOR THE SECRET SHARING
Here we provide a rule for selecting parameter used in the secret sharing. In general, setting to a smaller number is better for tolerating dropout scenarios. However, when / is excessively small, the system is vulnerable to the unmasking attack adversarial server; the server may request shares of 6; and og to disjoint sets of remaining clients simultaneously, which reveals the local model 0, to the server. The following proposition provides a rule of designing parameter to avoid such unmasking attack.
Proposition 1 (Lower bound on t). For CCESA(n, p). te (n-1)pty(nn-1)oouu Then, the system is asymptotically almost surely secure against the unmasking attack.
be given.
Proof. Let F. be the event that at least one of local models are revealed to the server, and F, be the event that 7th local model 0g revealed the server. Note that 0; revealed to the server if clients send the shares of b, and other t clients send the shares of sf in Step 3. Therefore,
P(E.) S ()) U (0) n V4 2 21)
- P(((Ad(() (0) 2 21) = P(I(Ad((i) 2 21 - 1)
< ((IAdj(i) (n-1) 1)p V(n 1) log(n 1)) (4)
1)2
where (a) comes from Hoeffding's inequality of binomial random variable. As a result, we obtain
P(E) P(Ute(n)
Σ P(E.) nP(Ei) (n 1)²
a 20000 0,
1E|m]
which completes the proof.
As stated above, setting to a smaller number is better to tolerate the dropout of multiple clients. Thus, as in the following remark, we set to be the minimum value avoiding the unmasking attack.
23

---

Under review as a conference paper at ICLR 2021
Remark 4 (Design rule for t). Throughout the paper, we set t = - / (n CCESA(n, p), order to secure a system against the unmasking attack and provide the maximum lolerance against dropout scenarios.
login- 1)+1 for
G DETAILED EXPERIMENTAL SETUP
G.1 AT & FACE DATASET
AT&T Face dataset contains images of 40 members. We allocated the data to 40 clients participating in the federated learning, where each client contains the images of a specific member. This experimental setup is suitable for the practical federated learning scenario where each client has its own image and the central server aggregates the local models for face recognition. Following the previous work (Fredrikson et al. 2015) on the model inversion, we used softmax regression for the classification. Both the number of local training epochs and the number of global aggregation rounds are set to Eiocat =
Egiotal 50, and we used the SGD optimizer with learning rate 7 = 0.05.
G.2 CIFAR-10 DATASET
G.2.1 RELIABILITY EXPERIMENT IN FIG.
We ran experiments under the federated learning setup where 50000 training images are allocated to n = 1000 clients. Here, we considered two scenarios for data allocation: one is partitioning the data in the i.i.d. manner (i.e., each client randomly obtains 50 images), while the other is non-i.i.d allocation scenario. For the non-i.i.d scenario, we followed the procedure of (McMahan et al.) 2017]. Specifically, the data first sorted by its category, and then the sorted data is divided into 2000 shards. Each client randomly chooses 2 shards for its local training data. Since each client has access to at most classes, the test accuracy performance is degraded compared with the i.i.d. setup. For training the classifier, used VGG-11 network and the SGD optimizer with learning rate 7 = 0.1 and momentum / = 0.5. The local training epoch is set to Etocal
G.2.2 PRIVACY EXPERIMENTS TABLE AND TABLE B.1
We conducted experiments under the federated learning setup where Aerrain training images are as- signed to = 10 clients. We considered i.i.d. data allocation setup where each client randomly obtains /urain/ / 110 training images. The network architecture, the optimizer, and the number of local training epochs are set to the options used in Sec. G.2.1
G.3 CONNECTION PROBABILITY SETUP IN FIG.
In Fig. we select different connection probabilities p = p² (n, (uai) for various n and Gotal where The detailed values of connection probability p are provided in Table G.2
p² is defined in 5).
Qooat /
100
200
300
400
500
600
700
800
900
1000
0.636
0.484
0.411
0.365
0.333
0.308
0.289
0.273
0.260
0.248
0.01
0.649
0.494
0.419
0.373
0.340
0.315
0.295
0.280
0.265
0.254
0.05
0.707
0.538
0.457
0.406
0.370
0.344
0.321
0.304
0.289
0.276
0.1
0.795
0.605
0.513
0.456
0.416
0.385
0.361
0.341
0.325
0.311
Table G.2: Connection probability p p=ppppp-- in Fig.
G.4 RUNNING TIME EXPERIMENT IN TABLE
We implemented CCESA algorithm in python. For symmetric authenticated encryption, we AES-GCM with 128-bit keys in Crypto. Cipher package. For the pseudorandom generator, we use randint function (input: random seed, output: random integer in the field of size 2 in numpy, random package. For key agreement, we use Elliptic-Curve Diffie-Hellman over the NIST SP800-56 curve composed with SHA-256 hash function. For secret sharing, we use standard f-out-of-n secret sharing (Shamir 1979.


Reviews:
[{"review_id": "v-D8VRGthFe", "reviewer": "AnonReviewer3", "summary": "", "questions": "", "limitations": "", "rating": 6, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "Summary: \n\nThe paper proposes a secure aggregation framework for federated learning that is communication-computation efficient. Specifically, instead of sharing its public keys and secret shares to all the other clients as done in the existing scheme, each client only shares to a subset of selected clients, which reduces the communication and computational costs. The sufficient condition on the graph topology of the selected pairs (assignment graph) is identified under which the private and reliable learning is guaranteed. Experiments on real-world datasets validate the theory. \n\n\nStrength:\n\nThe paper provides the rigorous theoretical guarantee for the algorithm, including the followings,\n1. Sufficient conditions on the assignment graph are identified under which the federated learning is reliable and private; \n2. For Erdos-Renyi random graph where two nodes are connected with probability $p$, the lower bound of $p$ is given such that the algorithm is asymptotically almost surely reliable and private. The upper bound of error probability is also given for a finite number of nodes such that the algorithm is reliable and private.  \n\n\nWeakness/Comments: \n\n1. My biggest concern is the novelty of the paper, which seems to be not significant. Specifically, the proposed algorithm's main contribution is generalizing the existing secure aggregation framework (Bonawitz et al., 2017) from the complete assignment graph to an arbitrary graph. The only modification is on the assignment graph, while the framework itself is still the same as (Bonawitz et al., 2017). Moreover, the idea of limiting communications over a li\ndistributed learning over the Erdos-Renyi random graph has been studied and analyzed extensively in the literature.\n\n2. In experiments (Fig 4), when p >0.795, the proposed algorithm can achieve the same test accuracy as SA. It seems communication/computational efficiency can be attained \"for free. \" However, intuitively, if the fewer nodes are aggregated each round in update, the convergence rate ought to decrease. Is the same test accuracy because of the generalization property? How does the training accuracy of two algorithms compared to each other? \n\n3. Related work: secure multiparty computation (MPC) has been studied extensively in distributed learning, with or without a central server. Federated learning essentially is a special type of distributed learning. I suggest authors can include more related work about MPC in distributed learning. For example, \n(1) K. Tjell and R. Wisniewski, \"Privacy Preservation in Distributed Optimization via Dual Decomposition and ADMM,\" 2019 IEEE 58th Conference on Decision and Control (CDC), Nice, France, 2019\n(2) C. Zhang, M. Ahmad and Y. Wang, \"ADMM Based Privacy-Preserving Decentralized Optimization,\" in IEEE Transactions on Information Forensics and Security, vol. 14, no. 3, pp. 565-580, March 2019\n(3) Shen, S., Zhu, T., Wu, D., Wang, W. and Zhou, W., \"From distributed machine learning to federated learning: In the view of data privacy and security. Concurrency and Computation: Practice and Experience\", 2020.\n\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "a_RlVX1mFxq", "reviewer": "AnonReviewer1", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 4, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes an efficiency improvement on the \"secure aggregation\" (called SA in this paper) protocol of Bonawitz et al. \n\nFor context: the SA protocol allows a group of clients holding secret values to compute the sum of their values with the help of a reliable server. The computation is \"private\" in the following sense: any adversary that controls the server and at most $t$ out of the $n$ clients learns nothing except the sum of the honest parties' inputs. \n\nMore formally: SA is a multiparty computation protocol for the \"summation\" ideal functionality, that is secure against a *semi-honest* honest adversary. It has the desirable feature of being resilient to failures on the part of many clients (as long as the server remains online). \n\nThe big downsides are that (a) the protocol does not handle malicious behavior on the part of the server and clients and (b) the communication scales poorly with the number $n$ of clients (each client's communication is $\\Theta(n)$, and the server's total communication is $\\Theta(n^2)$).\n\nThis paper aims to alleviate problem (b) by giving a version that uses a reduced communication graph. The paper argues that if the graph has appropriate properties then the resulting protocol is secure (though that argument is problematic, see below). The paper shows that a random Erdos-Renyi graph with density about $1/\\sqrt{n}$ satisfies the properties, leading to a protocol with communication $\\tilde O(\\sqrt{n})$ per client. \n\nI like the approach and idea of the paper, but I don't think the execution is quite there yet—I don't feel the paper, as written, is acceptable for ICLR.  The paper's value hinges on three claims: correctness (the protocol should complete even when some players drop out), low communication, and security. I did not check the arguments for any of these in detail, but correctness and communication look fine. The main issue is the security argument, which is not properly developed (and not obviously correct). The security model is not clearly articulated, the claims don't clearly describe assumptions on the number of corrupted parties, and so forth. For example, the paper makes claims such as that the protocol prevents membership inference. That can't be true because many (most?) membership attacks use only the final trained model (or even just its outputs)—hiding the intermediate gradients doesn't help. \n\nThis paper is about multiparty computation (to be clear, secure summation is a special case of MPC where the ideal functionality is a sum). It should use the language developed over the past thirty+ years in the crypto and security communities to formulate and prove its claims of security. This would allow for clear and refutable claims, and a clear discussion of the new protocols limitations.  In particular, the restriction to semi-honest parties is a huge one, albeit shared with the SA protocol of Bonawitz et al. \n\n\n\n* Modeling the exact security properties of protocols with parties that drop out is a bit subtle. See, for example, this paper for discussion: https://eprint.iacr.org/2018/997\n\n* The idea of replacing the complete graph with a low-degree expander to save communication has been used elsewhere. Some relevant citations are below (though there are others, too):\n\n** Fitzi, M., Franklin, M., Garay, J., Vardhan, H.: Towards optimal and efficientperfectly secure message transmission. In: Vadhan, S.P. (ed.) TCC 2007. LNCS,vol. 4392, pp. 311–322. Springer, Heidelberg (2007)\n\n** Harnik, D., Ishai, Y., Kushilevitz, E.: How many oblivious transfers are neededfor secure multiparty computation? In: Menezes, A. (ed.) CRYPTO 2007. LNCS,vol. 4622, pp. 284–302. Springer, Heidelberg (2007)\n\n* Finally: This type of paper might be a better fit for a security or crypto venue, where its contributions can be better evalauted and appreciated. It is up to the authors where to submit, of course, and I don't generally take conference scope too strictly, but the paper isn't really about learning representations, and isn't clearly a good fit for the ICLR audience.\n\n", "extra_scores": {}, "extra_text": {}}, {"review_id": "EAiwZ9i1fjx", "reviewer": "AnonReviewer2", "summary": "", "questions": "", "limitations": "", "rating": 4, "confidence": 3, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper proposes a secure (or private) algorithm that is communication and computationally efficient for the purpose of federated learning. The main idea is to allow each client to share its public keys and shares them secretly with a subset of its clients. This is a very natural idea. The main theoretical contribution is potentially useful. However, it is based on a very unrealistic model of a graph -- namely the Erdos-Renyi (ER) graph. It is widely acknowledged that in the real world, ER graphs are not realistic and indeed, are too simple to model real world networks. Consequently, the analysis leading to Theorems 3 and 4 are overly simplified and the insights on p^* may not carry over to real-world settings. \n\nThe analytical results illustrated in Fig 3 are also misleading. The authors mention that the privacy error probability is approx 10^{-40}, but this number depends on what p you choose (that is above p^*). If p is only slightly above p^*, this small error probability is unlikely to materialize. Thus, the discussion here is weak. \n\nThere is no impossibility result or any discussion on whether the results in Theorems 3 to 6 are tight in any way. If they were, the illustrations would be more informative. \n\nIn the real-world experiments on CIFAR-10, it is mentioned that p = p^* = 0.795 is the provably minimum connection probably. Isn't this number way too large? Essentially your whole graph is connected and the structure, if any, can't be reasonably exploited. This leads me to think that there is a great deal of looseness in the analyses. ", "extra_scores": {}, "extra_text": {}}, {"review_id": "1qmzpO-bhx_", "reviewer": "AnonReviewer4", "summary": "", "questions": "", "limitations": "", "rating": 3, "confidence": 5, "soundness": null, "presentation": null, "contribution": null, "strengths": "", "weaknesses": "", "quality": null, "clarity": null, "significance": null, "originality": null, "strengths_and_weaknesses": "", "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": "This paper considers the problem of secure aggregation for federated learning, where the goal is to design a protocol that allows the server to aggregate models from clients without learning anything about any individual model. The paper builds up on the secure aggregation scheme of (Bonawitz et al., 2017), and proposes a scheme that requires smaller communication and computation costs. The main idea is to use a sparse random graph as a communication graph as opposed to the complete graph used by (Bonawitz et al., 2017).\n\nStrong points:\n\n1. Reducing communication and computation costs in secure aggregation is indeed an important practical challenge. The idea of using a sparse communication graph is interesting.\n\n2. The paper gives experimental results on CIFAR-10 and compares with (Bonawitz et al., 2017). On the other hand, (Bonawitz et al., 2017) only present results on synthetic vectors and do not consider any machine learning task in their experiments.\n\nMajor concerns:\n\n1. My main concern is that the paper lacks the mathematical rigor required in a theoretical security/privacy paper.\n\n(a) In Definition 2, the eavesdropper model (or threat model) has not been properly defined. In particular, what messages of the protocol the eavesdropper can observe is not explicitly defined. Further, it is not mathematically rigorous to simply say that “an eavesdropper cannot obtain any information on the partial sum”. This needs to be quantified, e.g., by using an information-theoretic or computational expression. \n\n(b) The proof of Theorem 2 in supplementary material simply shows that the eavesdropper cannot compute the sum of local models $\\sum_{i\\in\\mathcal{T}} \\theta_i$ from the sum of the masked models $\\sum_{i\\in\\mathcal{T}} \\tilde{\\theta}_i$. How does this guarantee that the eavesdropper cannot obtain ‘any information’ about the sum of local models? The proof is not rigorous (partially due to the ill-defined privacy requirement).\n\n(c) Sufficient details are not provided in experiments. Specifically, what encryption scheme is used, what PRG is used?\n\n2. From the proof of Theorem 2, it is assumed that the eavesdropper has access to masked local models of a subset $\\mathcal{T} \\subset V_3$ of nodes. This is a much weaker adversary model than (Bonawitz et al., 2017). It does not seem fair to compare costs of protocols that give security guarantees for different threat models. At the very least, it should be explicitly mentioned upfront that  the proposed protocol is secure against a weaker threat model than (Bonawitz et al., 2017).\n\n3. Similarly, the attack considered in experiments (Sec. 5.3) is fairly simple. Secure aggregation schemes in (Bonawitz et al., 2017) and (So et al., 2020) provide security against much stronger attacks — privacy is guaranteed even if a subset of devices collude with each other, or the server colludes with a subset of devices.\n\n4. The following recent paper uses a very similar idea to reduce communication and computation costs of secure aggregation. (This paper gives precise privacy definitions and rigorous mathematical proofs for security.) \n\nJames Bell, K. A. Bonawitz, Adrià Gascón, Tancrède Lepoint, Mariana Raykova, “Secure Single-Server Aggregation with (Poly)Logarithmic Overhead”, Jun 2020. (https://eprint.iacr.org/2020/704)\n\nEven if one considers CCESA as a parallel and independent work, it will be helpful to acknowledge the above paper. \n\nOverall, the paper proposes an interesting idea of using sparse communication graphs for secure aggregation to reduce communication and computation costs. However, the paper seems to lack the mathematical rigor and details.\n\n----------- Post-Rebuttal Comments -----------------\nThanks to the authors for the response and for updating the draft. Some of my queries were clarified. However, I still think the paper lacks the mathematical rigor required for a theoretical security/privacy paper. For instance, in the updated proof of Theorem 2, the authors consider the output of a pseudo-random generator (PRG) as uniformly random and claim information-theoretic (perfect) security. However, PRG output is not uniformly random, and one needs to consider computational security, which is standard in cryptography/security literature. Moreover, the comparison with (Bonawitz et al., 2017) and (Bell et al., 2020) seems a bit unfair since the threat model in the paper is weaker. As an example, for the same threat model in the paper, it is not clear if (Bell et al., 2020) would need the strong assumption on dropouts. For these reasons, I retain my original score. ", "extra_scores": {}, "extra_text": {}}]

Author rebuttal:

Meta-review: This paper presents an efficient secure aggregation algorithm in federated learning scenarios, which employs sparse random secure-sharing clients. Four experienced reviewers left valuable comments on this paper, and three of them are unfortunately negative to this work (4, 4, 3) while one reviewer is slightly on the positive side. 

The reviewers are generally positive about the main idea and the direction for this work, but they are not convinced of its mathematical soundness and practical benefits; the theoretical analysis and mathematical proof has been conducted only for simplified models while their practical advantage is not clear enough. Also, even the most positive reviewer (R3) is concerned about the novelty of the proposed approach.
Although the concerns raised in the original reviews have been partially clarified during the discussion phase, there still remain several critical limitations, which makes this paper require (probably) multiple rounds of revision before publication and this AC has a reservation for accepting this paper.
Decision: Reject