Scalable Robust Federated Learning with Provable Security Guarantees
Authors: Andrew Liu
Jacky Y. Zhang
Nishant Kumar
Dakshita Khurana
Oluwasanmi O Koyejo
Venue: ICLR 2022 Submitted (2022)
Keywords: Federated Learning
Robustness
MPC
Privacy Preserving ML

Abstract: Federated averaging, the most popular aggregation approach in federated learning, is known to be vulnerable to failures and adversarial updates from clients that wish to disrupt training. While median aggregation remains one of the most popular alternatives to improve training robustness, the naive combination of median and secure multi-party computation (MPC) is unscalable. To this end, we propose an efficient approximate median aggregation with MPC privacy guarantees on the multi-silo setting, e.g., across hospitals, with two semi-honest non-colluding servers. The proposed method protects the confidentiality of client gradient updates against both semi-honest clients and servers. Asymptotically, the cost of our approach scales only linearly with the number of clients, whereas the naive MPC median scales quadratically. Moreover, we prove that the convergence of the proposed federated learning method is robust to a wide range of failures and attacks. Empirically, we show that our method inherits the robustness properties of the median while converging faster than the naive MPC median for even a small number of clients.

Under review as a conference paper at ICLR 2022
SCALABLE ROBUST FEDERATED LEARNING WITH PROVABLE SECURITY GUARANTEES
Anonymous authors Paper under double-blind review
ABSTRACT
Federated averaging, the most popular aggregation approach in federated learn- ing, is known to be vulnerable failures and adversarial updates from clients that wish to disrupt training. While median aggregation remains one of the most popular alternatives improve training robustness, relying on secure multi-party computation (MPC) to naïvely compute the median is unscalable. To this end, we propose secure and efficient approximate median aggregation with MPC privacy guarantees in the multi-silo setting, e.g., across hospitals, with two semi-honest non-colluding servers. The proposed method protects the confidentiality of client gradient updates against both semi-honest clients and servers. Asymptotically, the cost our approach scales only linearly with the number of clients, whereas the na've MPC median scales quadratically. Moreover, we prove that the convergence the proposed federated learning method is robust to a wide range of failures show that our method displays similar robustness
and attacks. Empirically, properties as the median while converging faster than the naive MPC median for even small number of clients.
Introduction
Federated Learning (FL) (MeMahan al.) 2017) has emerged as leading approach for training shared models among clients who do not wish to release their datasets publicly. While FL avoids releasing client data, revealing client models the clear creates privacy vulnerabilities, e.g., using model inversion attacks (Fredrikson et al. 2015). To this end, global model aggregation is often implemented using Secure Multi-Party Computation (MPC) to improve privacy (Bonawitz et al.) 2016). MPC (Yao) Goldreich et al. 1987) is cryptographic primitive that makes it possible to evaluate function on encrypted inputs while ensuring that the only information revealed throughout the computation is the final output of the function. Thus, to avoid revealing each client's local weights, clients encrypt their weights before sending them to the central server. MPC allows the central server recover single aggregate update that it sends back to individual clients. Specialized MPC protocols, that allow the server to recover the average of client updates have been widely deployed for Federated Learning.
In addition to privacy, robustness is a major concern in federated learning implementations (Kairouz) al.) 2019). The distributed nature of the computation creates variety of vulnerabilities to ad- versarial training attacks and client failures such as hardware, software, data, and communication errors (Xie al. 2019a 202T). D. One way to improve robustness is to replace an aggregation proce- dure that computes means with more robust aggregate such as the median (Yin et al. 2018). Using the median, up half of inputs can be from a faulty distribution before the median fails as robust average estimator. While median aggregation alone is insufficient to guarantee Byzantine robustness (Xie et al. 2020) - median- based robustness guarantees are sufficient against most published attacks and failures. Unfortunately, the best known approaches for median aggregation with MPC are slow, requiring computation that grows quadratically with the number of clients (Tueno et al. 2019).
Our work is motivated by applications to multi-silo federated learning (Kairouz al. 2019). de- signed for learning across institutions. For example, an individual hospital may be limited to using only their due to privacy and intellectual property concerns. Here, federated learning can provide a mechanism for widely distributed medical institutions jointly train model.
patients' data, and sharing patient information among hospitals is generally difficult

---

Under review as a conference paper at ICLR 2022
The main contribution of this work is new approximate-median aggregation for robust, privacy- preserving federated learning in the multi-silo, two-server setting. Our approach is the first to have all of the following features:
Robustness against failures. By relying on (an approximation of) the median of client updates, we achieve robust estimates even in settings where updates sent by up to half the clients are faulty. addition, we empirically evaluate robustness against noise distributions that take the form of bit flips, label switching, and Gaussian noise in up to half of the clients.
Preserving Client Privacy via Secure Computation. We prove that any subset of clients col- luding with each other and with one of the two servers obtains no information about the private inputs of other clients, beyond the aggregated (approximate) median that is returned at cach step. This provides meaningful privacy every client and is a meaningful defense, e.g., against model- inversion attacks that take advantage of individual client updates.
Scalability. The running time of our protocol increases linearly with the number of clients; match- ing the order-wise scaling (with number of clients) of the standard averaging aggregation. This is in contrast to quadratic factor blowup for a federated learning system that implements me- dian naively in MPC. We empirically evaluate the convergence of our system on various datasets, models and under different types of faults.
2 Related Work
Federated Learning (McMahan et al. data from edge devices. In its plainest form, client updates are sent without encryption to the central server each round, and the global model is sent back to each client. However, this basic imple- mentation of distributed machine learning system is not robust against privacy attacks or failures. For instance, [Wang et al., 2019; Geiping et al.] 2020) show how model inversion attacks can be successful in a federated learning setting. (Bonawitz et al., 2017 2016) provide protocol for cure aggregation of the client updates and computation of the global model in both a coni-honest and malicious setting, with increased runtime and communication overhead. In addition to encryp- tion of client updates, existing work has also considered robustness to failures and Byzantine client attacks, e.g., (Xie et al., 2019a] 2021) prune faulty client updates by assigning each update score, and only aggregating the updates that have the top scores. Other methods of providing byzantine robustness including trimmed mean (Xie et al., 2019b)) Krum (He al.) 2020 (So et al. 2021), and norm-based elimination (Gupta et al. (021]) have been studied. In this paper, we strengthen the re- clients. Although a semi-honest setting may
2017) is widely adopted technique for training models with
striction on client faults and only consider seem restrictive by forcing parties to follow the dictated protocol, it applies to settings where parties are assumed to have no ill intentions. Furthermore, developing semi-honest protocols are a step towards developing protocols in the malicious security model, where more expensive cryptographic primitives such as zero- knowleeeeee proofs are added on top of the existing semi-honest protocol.
Secure Multi-Party Computation (MPC) provides way for multiple parties to compute a function on their individual data and only reveal the final output of the function. (Bonawitz et al. 2016 2017) provide a method for federated learning where client updates have a pairwise additive mask, such that when all the encrypted client updates are summed together, the masks cancel out. In (Tueno) et al. 2019), the authors propose rank computation system where clients send pairwise masked version of their data point to the central server. The central server uses pairwise comparisons in MPC to calculate the desired ranked element in the clients' combined data. However, pairwise compar- isons are expensive in MPC, as additional values for each unique comparison must be generated in advance. Furthermore, agreeing upon pairwise additive masks grows quadratically with the number of parties.
The generalization of a central server to two non-colluding central servers is not a new idea in privacy- preseecing analytics and machine learning. For instance, (Corrigan-Gibe Gibbs & Bonch 2017) introduce a cryptographic protocol called secret-shared non-interactive proofs, and show that these can be used to construct an efficient privacy preserving system for the release of aggregate statis- ties with guarantees on security in the malicious setting. The setting of the paper consists of a small number of servers jointly computing aggregate statistics over private client data. (Mohassel & Zhang 2017) introduce efficient distributed ML protocols that utilize a two server abstraction and MPC versions of ML computations. However they do not seek to provide robustness. To our knowl- edge, (He et al. 2020) is the first work to propose an FL system that combines both robustness and privacy, using private calculation of the distance-base based aggregation. They also make the assumption
2

---

Under review as a conference paper at ICLR 2022
of the central server being two non-colluding central servers, and utilize client side secret sharing of models and server side two party MPC. The two central server setting allows their protocol to scale well with number of parties, compared to a single central server setting. However, their protocol leaks the pairwise distance of client updates to one of the servers, which may be undesirable.
Our proposed approach uses the 2-Party MPC comparison protocols presented in (Rathee et al. 2020). We also adopt a pairwise comparison based computation of the k-th ranked element proposed in (Tueno al., 2019) and bucketing approximate median idea proposed in (Corrigan- Boneh 2017). and apply them to the setting of distributed machine learning. Finally, we note that this work focuses on security and robustness of centralized model training. Existing work has shown that personalization and mitigating data heterogeneity can be addressed by fine-tuning the robust centralized model (Li et 2021). These details are left for future work.
&
3 Preliminaries
Federated Learning. We denote N as the set of positive integers and R, the set of non-negative real numbers. Given n E N. we denote [n] = (I..... n². w R., to denote vectors, and w(k) to denote its value at the h dimension. We consider a two- server multi-client FL system, let So, S₁ denote the two central severs, and C for E [n]] represent the clients, where is the total number of clients. Client e; holds dataset D;. The agreed upon model has d parameters. Wy denotes the global model sent from servers to clients, while w, denotes the local model held by client i. All parties agree beforehand to run r cycles of FL. The loss function for client e₁ is F; I2 + R+. Usually, because clients have different data, the loss functions F, are different. Therefore, the goal of our setting is to minimize the averaged loss across all clients, i.e., arg min w 1 >> (w)
We use bold lowercase letters, e.g.,
We first detail a basic federated learning system with one central server S and clients. Clients are generally considered to be edge nodes and do not communicate with each other. In one iteration, the system follows the following generic protocol:
1. For i E [n]. client 6 receives global model wy from central server S.
2. For i [m]]. client G; performs step(s) of Stochastic Gradient Descent of wy on its dataset
D; to obtain new local model w; They then send this model to S.
3. Upon receiving all client updates, aggregates them obtain the new global model. The new global model is computed as w/g 1i=1 WD;
4. S sends w'J to all the clients.
Secure Multi-Party Computation. Secure Multi-party Computation (MPC) (Goldreich et al.] 1987) is cryptographic primitive which allows n parties, each with input value wi, jointly com- pute a mutually agreed upon function f'(21, 222 #2.. ...2x), ). with the guarantee that no party learns any- thing other than what can be inferred from its own input and the joint output.
One of the most prominent techniques used in MPC is secret sharing. A (t, secret sharing in- volves splitting a secret into n shares, then distributing a share each party, such that any subset of 1 parties cannot learn anything about s, while any f or more parties can jointly reconstruct s. In this paper, we make use of (2, 2) additive secret sharing over pfwer-of-twe sized integer rings, which involves splitting s E Zye into $1, $2 E Znz s.t. $ $2 s, and individually s;, i E {0. 13 has a uniform random distribution. We use (s) to denote secret sharing of over Zzz, and (8)0, (s) to denote the shares of the two parties. We use FComp: Ft Eagul to refer to the "greater than" and "equals to" ideal functionalities respectively, i.e. where parties have access to trusted functionalities computing the said functions and use the same to describe our protocols. To implement the pro- tocols for FComp Equal. we make use of protocols proposed in CrypTFlow2 (Rathee et al. 2020). CrypTFlow2 provides a customized 2- 2-party protocol for solving the millionare's s, and hence also the comparison/equality problems in Ez (more details on all this in Appendix C).
4 Problem Description
In this section, we introduce a baseline solution to secure and robust FL. Median provides well- studied robustness against outliers compared to mean (Xie et al. 2018). In order to make our MPC protocols for this efficient, we abstract the central server in FL to two non-colluding central servers. The servers each receive one of the (2,2) secret shares of the client updates, and perform 2-party based secure median computation. Figure I provides a representation of our model.
3

---

Under review as a conference paper at ICLR 2022
MPC
Computation Median
So
S
(w/70
(W621
(maad
Hospital
Hospital
Figure I: Our proposed two server FL system. Hospitals compute local models wi, and secret share them among the two servers. Servers securely compute the fimension-wise median and end up with the global model. Each hospital receives the global model from So. and repeats the cycle.
4.1 Security Threat Model
We model the adversary using the wammi-honns/hhonst-bt----ooo but-uuroos model, whereby is assumed that the parties controlled by the adversary will follow the protocol specifications, but try to learn more information about other parties' data using the protocol transcript. We also assume static corruption, i.e. that the adversary chooses the parties to corrupt at the beginning of the protocol and cannot change them once protocol execution starts. In addition, we assume the two servers So, S1 do not collude with each other. The adversary is then allowed to corrupt any arbitrary subset of the clients and most one of the servers and once corrupted gets to see their internal state well as the transcript of their communication. Furthermore, we are concerned with the multi-silo setting, where clients are assumed to be large institutions and thus client drop out or limitations on computational resources are not considered.
4.2 Baseline solution
We propose a baseline solution for computing the exact median in our two-server multi-client setting. In order to send their updates to the servers, clients additively secret-share their updates and sends one share to each server. Once all the clients have done so, the two servers now have a (2, 2) additive secret share of all the clients' updates and perform MPC based median computation. We take inspiration from the ideas Tueno et al. (2019) to design a 2-party secure protocol for median computation by breaking it up into pairwise comparisons between all elements and some number equality checks. In Appendix A we provide a formal description of our algorithm in the F Compp F hybrid (described in Algorithm 2 along with correctness sketch and other details for the same. Our final protocol is then obtained by replacing FBmop Fi.uual with CrypTFlow2 (Rathee jet al. 2020) based secure comparison/equality protocols (described in detail in Appendix [.. We refer to this protocol as "pairwise comparison based median" in the rest of the paper.
Complexity. The complexity of this protocol
least dn(n - 1)/2 calls to Fromp in addition to
dn calls to F Equal Note that the number of secure comparisoons/equaliiee grows quadratically with the number of clients n. In the next section, we will introduce our approximate median protocol, whose number of secure operations independent of n. We provide a brief summary in Appendix C on why we use number of secure comparisons as a metric for complexity.
Bucketing based median computation
In this section, we propose an approximate median, which provides increased computational effi ciency, serve as the replacement of the exact median computation. We provide an abridged version of the protocol in Algorithm and a formal description of the protocol in Algorithm 3
Summary of the key idea. Divide the set of possible values that client updates may take into fixed set of buckets. Let designate the number of buckets. Next, instead of sending actual updates to the server, each client will send unit vector that has a 1 in the bucket containing the client's 's update, and 0 everywhere else. U Upon receiving all client updates, the (two) servers build a frequency distribution of client updates and use this to find the bucket which contains the median value. The median is then
4

---

Under review as a conference paper at ICLR 2022
Algorithm 1 Succinct version of our bucketed FL system Input: For i [n]. 6j holds dataset D.. d model size, b number of buckets, p are public parameters.
vi E [m], client a does:
1. Receive global model Wy and bucket ranges B from server Sg.
2. Compute local model w; (GD Di).
3. Compute Bucketize(ug: B, 6, w.) and obtain bucketized local model
4. Creates (2, 2) shares (es)a. (e:)1 of e;
5. Send (es)o to So, send (e:)1 to S1.
Vj E {0, 1), server S, does:
1. Receive share (et) from client C, Vi E [n]].
2. Add shares (ei) ... (en)) obtain (Ei=1 e:)
3. Call 2-party secure protocol Foamp (Ei= e;),
(( and obtain d-length vector m, where m(k) indicates which bucket holds the median for dimension it E [d].
4. So calls Quantice(u; Wg: B, b, m) and obtains new global model w'z-
5. Sy computes new bucket range as 21((w' wgy +
6. So releases w'J and B' to all clients.
approximated by the middle value of the range of this bucket. All this while, servers only obtain 2) additive secret shares of client vectors, and rely on MPC to perform the computation outlined above and find the median. We now describe these steps in additional detail.
We "bucketize" clients' updates by dividing each dimension of the model into b buckets. This enables the servers build secret sharing of the frequency distribution of clients' updates and find the bucket which contains the median value. The approximate median is then chosen the middle value that bucket.
At the beginning of a given round each client receives bucket range B and global model wy from the central servers, and follow by running SGD on its dataset D, to obtain local model w, The bucket range implicitly fixes the buckets around the global model Wg. i.c. in any given dimension (k) with total range of B. The ending buckets are taken represent all the remaining range outside B i.e. the first and the last buckets represent the [,, + 2 +oo). The middle - buckets evenly divide the range 2. c; then creates, Vk E [d]. unit vector (k( E 13 with in place for the bucket which contains un (k)); we refer to this transformation as "bucketizing". e; then sends secret shares of e; to both servers
E [d]. the b buckets are centered around w, (k)
range (-00, (kyk)
(y(k) (k)) + B
The servers add all the client updates to get a secret-sharing of the frequency distribution of clients updates and compute the bucket containing the median value for each dimension. This is done by performing a secure comparison to compare each bucket's share frequency against [_ The comparison result is then revealed to learn which bucket contains the median value and the servers take the middle value that bucket to be the value of the new global model d for that dimension. We refer this transformation of converting bucketed model back to model where each dimension has a numerical value associated with it as "quantizing". The bucket range is then updated as 2 2| w p. where p is parameter agreed by all parties.
Complexity For each dimension, the servers need only perform b calls to F/mmp hence total of db calls. Compared to dn(n - 1)/2 calls for pairwise comparison median computation, we note that if b is constant 10, then while pairwise comparison median needs number of secure comparisons that grows quadratically with the number of clients, the number of calls in our method is independent of the number of clients.
5

---

Under review as a conference paper at ICLR 2022
6 Theoretical guarantees
In this section, we theoretically analyze the proposed method in terms of security, robustness, and convergence guarantees.
6.1 Robustness and Convergence
We first introduce the notation and settings specific to the robustness and convergence analysis. The proof's in this subsection are provided in section D in the appendix. Given a data distribution D, assume data samples {~D are i.id. sampled. Data individual loss function is denoted as f(- :E) Rd R, i.e., f(w:; {) 2 given a parameter
E Rd Based on the individual loss function, we denote the population loss function F = (== and we assume it is differentiable. Draw N i..dd samples for each of the n clients (in total n.V samples): (Er. (en..een Therefore the client
empirical loss function is
N F. Σ
1 1=1
N f(:56)))
for e [n].
(1)
The goal of our setting arg min,. 1
minimize the averaged loss across all clients, i.c.. n Ei= (ww). In the convergence analysis, we consider gradient descent with step size The range of the buckets at iteration is denoted as B2/ B₁ B2) and the model parameter are denoted as w. Rdd As detailed Algorithm we consider the bucket range updated by
Bo + Po. Bg + 7l/w, wi-1lli + P1.
(2)
where P1, > are constants. There is convex parameter set W S Rd such that the pa- rameters during gradient descent for all clients are within W. Given function R. Bd and
p, P.q. E [1, oo], we denote the (p, 4) -norm of g as [|g l0ll..- = (fw ([g()))l du(w)) 1/p In particular, ||ol|so. = supwEw [1g(w))]l.
The coordinate-wise median operator Med(-) takes a set vectors {u, E R and outputs a vector E Rdd such that for each dimension k, vkk is the standard median of (v,(k) E R The bucket median is calculated as described in Algorithm 3 and we denote it as BucketMed(.)) Therefore, in the convergence analysis, we consider the global parameter update be
u+++1 w. BucketMedl (wn:)) se(n]; B,
where the bucket range and is the number of buckets.
We make the following assumptions for the robustness and convergence analysis. Assumption 1 (3 smoothnesss. F is Smooth.. Formally, there exists B 2 0 such that for ww,, We E W we have
IVF(w)) - VF(w2) S sml|es - w2l11,
Note that || 1 is the dual norm of lloo.
Assumption 2 (Weak Law of Large Number). We assume VF = EEaD vf(=:E) exists and the sample mean converges to F in probability I1 Formally, let Ej be i.i.d. sampled,
and denote 8N.c Pr VF 1/ E vf(:EE)
>g}
We assume
20,20
VE > O:
lim
NN.-= = 0.
N -
Therefore, by definition, 8N.,, 2 8N.ez i S 62. Denote 6N,8 = inf 8N, S 8}, and we can see that EN 2 EN,5, if o; 82. Moreover, we have the following proposition.
Proposition 6.1. With Assumption
2 we have v6 > 0: lim EN = 0.
With the above assumptions, the following result shows that the proposed bucket median is robust to some extent ratio of adversarial clients is a < 1/2. We provide similar results for dimension-ver wise median Med(-) in Theorem D.I in the appendix. Note that the previous analysis dimension-winn median in the FL setting (Yin et al. (2018) requires a to be smaller than an easily negative value. We prove the robustness in new way which holds for any < 1/2.

---

Under review as a conference paper at ICLR 2022
Theorem 6.1 (Robustness). With Assumption i& consider nı i.i.d. samples {VF:) (equa- tion 1 and n2 adversarial vectors {wx E R
1= Denote
n1 n2 and a == n2/n being > O, the number of buckets and the gradient
J==1-
the ratio of adversaries. Given the bucket range
descent step size p. Ifa < 1/2 then for de have
-t with probability least 1 - (ŌN..) (1-22)
EN. 1-20
Vaue E )
(m:);; B,b) WVF(w))l S pe + 25
B
for Yw E W satisfying μ u I for all [ng]. With the bucket median being robust, we can prove the convergence guarantee for smooth (possibly non-convex) function.
Note that N + oc, both ,, - 0 and e 0
Theorem 6.2 (Robust Convergence). With Assumption 1 consider n. normal clients with i.i.d. samples ( F (equation ! and nı faulty clients that can send arbitrary vectors following the proposed protocol. Denote == n1 +n2 and a n2/ being the ratio faulty clients. The bucket range adaption is defined by equation 2 where we assume B, S B for all iteration t for a constant B > O, and Po 2 1 l for Vi E [n1]. If a < 1/22, for Ve >> CN. 1-20, and 'V' > 0, the
(N.2(=a)
can achieve proposed method with parameters μ 2 Pi 2 2p + 28' 17 2 1 + 8p and 2
|VF(w)] 23F((w)
min OSEST
T+1 + (c+
with probability at least 1 - (ŌN,e) (1-2n)
Thus, with sufficient number of buckets b and number of data N, the proposed method can converge w.r.t. the true loss function F with high probability, while < 1/2 of clients send incorrect local updates.
6.2 Overview of Security Analysis
We argue the security of our bucketed protocol by means of the standard real/ideal simulation paradigm in cryptography (defined formally Appendix Bj. As stated in section 4.1 we assume a semi-honest adversary statically corrupting up to n - clients and at most one server, and prove the security of one epoch of the FL training using the simulation paradigm. The security of the entire protocol then follows by applying the sequential composition thcorem to the security of each epoch.
We provide a brief overview of the security argument. The use of secure 2-party computation be- tween the servers allows them to compute the desired approximate median without revealing any- thing other than the input/output of the functionality. At the beginning of each round, the clients secret-share their inputs between the two servers and thereafter, the servers use secure 2-party protocols to compute the shares of a unit vector with for the bucket in which the median value lies. Revealing this unit vector allows the servers to learn the median bucket index and find the median value, which is then sent to clients. An adversary corrupting one of the servers only sees random shares throughout the protocol (guaranteed by the secure protocol implementing J Fommp FE F.quaa de- scribed in Appendix C in addition to bucket range (which is computed solely using public values) and median bucket index, which it sees in the clear. Additionally corrupting any number of clients does not allow an adversary to recover any honest client's information, since honest client's data are only secret-shared between the servers and not shared in plain between clients.
We revisit the simulation paradigm and provide the formal security proof in Appendix B
7 Experimental Results
In this section, we evaluate our proposed bucketed median scheme on different models and datasets. First, we compare convergence behaviour over epoch FL. bucketed median, pairwise compari- son median, and mean methods. We also detail the quadratic versus linear relationship the pairwise comparison and bucketed median methods respectively have with the number of clients. In the next subsection, we formally describe the failures that faulty clients can exhibit. We then compare the robustness of median and our bucketed median against mean. In Appendix F we detail a breakdown of one FL cycle and analyze sensitivity of parameters.
Experiments were conducted on an Intel(R) Xeon(R) Platinum 8280 CPU @ 2.70GHz virtual ma- chine with 1 112 cores. All parties involved in the FL process were separate processes on this machine,

---

Under review as a conference paper at ICLR 2022
Phirwise Buckkting
cottiitttiin (M15)
Bocketing
Compotation Time
4.5
1.5
0.5
Number of Clients
Nember of Clients
(b) Communication cost in megabytes per number of clients Figure 3: Single-threaded median computation over 1000 dimensions.
(a) Time taken per number clients
-Bocketing Median
B-uckettigg
Buckering
Training
Median
- Mediam Meen
-Mean
Epoch
(a) MLP, bitflip failure
(b) ML.,, label flip failure (c) MLP, Gaussian noise failure
Figure 4: Training loss convergence behaviour for clients FL system using different server-side methods.
with bandwidth cap of 377 MBps to simulate LAN network. We test on the following combina- tions of (model, dataset): (MLP, MNIST), (CNNMnist, Mnist), and (CNN, CIFAR-10 10). The MLP model has consits of 1 hidden layer with 200 units with ReLu activation for 199, 210 dimensions. We use same CNNMnist as McMahan et al. (017)) which has 1,663,370 dimensions. The CNN model we use consists of two x 5 convolution layers, the first followed by 2 x max pooling, and the second followed by three linear layers for a total of 581 581,866 dimensions. Model training was done using the CPU. Training batch size is set to 20, learning rate is set to 0.01, and client datasets are sampled i.i.d. from the global dataset. Number of buckets b b=b 8.
7.1 Convergence Results
We first test convergence behaviour when all parties are benign. We show that our bucketed median FL system exhibits similar training loss convergence as our baseline: a mean based system. For all three methods, we run the same number of iterations of FL and note the average training loss when all clients are benign.
0.6
27
04
Pairwise
Pairwise
Pairwise
Teining Lees
Buckketing
Training Loos
Bucketing
Bucketing
Mean
Mean
Traiming
Mean
1 4.5
7 101112131411 5166 7161920
2
5
10
2
5
10
Epoch
kpoch
Epach
(a) 20 iter. of (MLP, MNIST)
(b) 10 iter. of (CNN, CIFAR-10) (c) iter. of (CNNMnist, MNIST)
Figure 2: Results of training loss convergence 3 benign parties.
We also show the relationship between number of parties and the time taken for secure median computation in both the bucketing and pairwise median methods. We test for number clients [2, 10] for dimension-wise median when d 1000. Figure 3 depicts the constant and quadratic relationships between time and communication costs with number of clients for both bucketing and pairwise methods. In Appendix F we provide scalability results with larger number of clients.
8

---

Under review as a conference paper at ICLR 2022
2.5
2.5
2.3g
2.5g
Thinnng
Training
1.7
1.7
1.5
Bucketing
--Bokeetngg Median
Backeting
Median
Median
Mean
Mean
Meun
0.
17
11
17
Epoch
Epoch
Epoch
(a) CNN, bitflip failure
(b) CNN, label flip failure
(c) CNN, Gaussian noise failure
Figure 5: Training loss convergence behaviour for clients FL system using different server-side
methods.
0.35
0.3
Rucketing Median
0.3
Mediso
0.25
0.25
Miear
Taining
0.
0.2
Training
in Bucketing
6:15
Mediin
0.15
Mean
0.05
0.05
0.05
19
Epoch
Epoch
Epoch
(c) CNNMnist, Gaussian noise fail-
(a) CNNMnist, bitflip failure
(b) CNNMnist, label flip failure
ure
Figure 6: Training loss convergence behaviour for 3 clients FL system using different server-side methods.
7.2 Client Failure Types
We assume the updates sent from clients can be corrupted with errors arising from machine noise, network transmission errors, data poisoning etc. The failures we test with are:
Bit Flip Failure: The most significant bit, or the bit that controls the sign is flipped. The client
sends the negative gradient instead of the true gradient the servers.
Label Switching Failure: Clients compute gradients with switched labels on the training data. For example, label (0....,9) 9} is replaced by 9 label.
Gaussian Noise Failure: Instead of sending the correct gradient to the server, clients send an update with values sampled from Gaussian distribution with mean of zero and standard deviation of 200.
7.3 Robustness Results
In this subsection, we empirically show that the robustness of our bucketed median FL system behaves similarly to a median based FL system. We show that for bit-flip. label-flip, and Gaussian noise errors, our system still converges. We with three clients, one of which exhibits failures starting from the third epoch. Figures a median and mean method. In our implementation, the training process, while bitflip and Gaussian noise manually computed the local model returned from model training. The mean method results in loss of convergence for both bitflip and Gaussian noise failures, but performs well against label flip failures. However, both the median and bucketed median methods show continued training loss decrease against all three failures.
6 shows results of our bucketed median method versus
faulty client performs label flipping during
8 Conclusion
We presented dual central-server FL system that is robust and private in the semi-honest setting. We propose bucketing approximation technique in order to sacrifice accuracy for computational efficiency, which also leads better scalability with the number of clients. The advantage our work provides are both privacy and robustness in distributed MI..

---

Under review as a conference paper at ICLR 2022
Ethics Statement
Our work focuses theoretically and empirically studying robust federated learning. All the datasets and packages we use are open-sourced. Potential ethical concerns are primarily in the observation that robust federated learning tends to remove outliers, and can be hard to determine data from minority groups are outliers or adversarial.
Reproducibility Statement
We have tried best provide training details to facilitate reproducing results. We pro- vide detailed results on how to train and evaluate our model. We will open-source our code once accepted.
References
Cryptflow2: Practical 2-Party Secure Inference. httpp://ggthuu..co/mm/-ccsss
A.ree/master/SC1 2021.
K. A. Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for federated learning user-held data. In NIPS Workshop Private Multi-Party Machine Learning, 2016.
URL httLhhhtsss///xiii wttpxivv.orr//b//l...11. 04482
abs/
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. Practical secure aggregation for privacy- preserving machine learning. In Proceedings the 2017 ACM SIGSAC Conference Computer and Communications Security, CCS '17, pp. 119,, New York, NY, USA, 2017. Associa- tion for Computing Machinery. ISBN 9781450349468. btttps://dbi.org/ www.o///.............. 11111111/33111.111 3133982
doi: 10.114531139556.133992. URL
Henry Corrigan-Gible and Dan Boneh. Prio: Private, robust, and scalable computation of aggregate statistics. In 14th USENIX Symposium on Nenworked Systems Design and Im- plementation (NSDI 17), pp. 259-282, Boston, MA, March 2017. USENIX Association. ISBN 978-1-931971-37.99 URL httpp:://tw/t wwwn...seeix... www.://nwww....ooooooeeereeomaee
Ivan Damgård, Matthias Fitzi, Eike Kiltz, Jesper Buus Nielsen, and Tomas Toft. Unconditionally secure constant-rounds multi-party computation for equality, comparison, bits and exponentiation. In Shai Halevi and Tal Rabin (cds.). Theory of Cryptography, pp. 285-304, Berlin, Heidelberg, 2006. Springer Berlin Heidelberg. ISBN 978-3-540-32732-55
Matt Fredrikson, Somesh Jha, and Thomas Ristenpart. Model inversion attacks that exploit confi- dence information and basic countermeasures. Proceedings of the 22nd ACM SIGSAC Confer- ence on Computer and Communications Security, CCS '15, pp. 1322-1333, New York, NY, USA, 2015. Association for Computing Machinery. ISBN 9781450338325. doi: 10.1145/2810103. 2813677. URL /ttps: orgg 10. 11t.1.....11111111
28136871777
Jonas Geiping, Hartmut Bauermeister, Hannah Dröge, and Michael Moeller. Inverting gradients how easy is it to break privacy in federated learning?, 2020.
O. Goldreich, S. Micali, and A. Wigderson. How to play any mental game, In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, pp. 218-229, New York, NY, USA. 1987. Association for Computing Machinery. ISBN 0897912217. doi: 10.1 18395.28420 /tRlaattss///oiooo///110
28420
Oded Goldreich. The Foundations of Cryptography Volume 2: Basic Applications. Cambridge University Press, 2004. ISBN Ftt.://////7odddddoooooo.oo.....
doi: Foc-
URLhttp:
//www. wi sdoo. wei peizmann. ac 1t.97//ooddd./////eeeee/
Nirupam Gupta, Shuo Liu, and Nitin H. Vaidya. Byzantine fault-tolerant distributed machine learn ing using stochastic gradient descent (sgd) and norm-based comparative gradient elimination (cge), 2021.
10

---

Under review as a conference paper at ICLR 2022
Lie He, Sai Praneeth Karimireddy, and Martin Jaggi. Secure byzantine-robust machine learning, 2020.
Peter Kairouz, Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista A. Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, Rafael
G. L. D'Oliveira, Salim El Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adrià Gascón, Badih Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaïd Harchaoui, Chaoyang He, Lie He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi, Gauri Joshi, Mikhail Khodak, Jakub Konečný, Aleksandra Korolova, Farinaz Koushanfar, Sanmi Koyejo, Tancrède Lepoint, Yang Liu, Prateek Mittal, Mehryar Mohri, Richard Nock, Ayfer Özgür, Rasmus Pagh, Mariana Raykova, Hang Qi. Daniel Ramage, Ramesh Raskar, Dawn Song, Weikang Song, Se- bastian U. Stich, Ziteng Sun, Ananda Theertha Suresh, Florian Tramèr, Pranecth Vepakomma, Jianyu Wang, Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao. Ad- vances and open problems in federated learning. CoRR, abs/1912.04977, 2019. URL http: //axxiv.org/abs.t
04977
Nishant Kumar, Mayank Rathee, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. Cryptflow: Secure tensorflow inference. In 2020 IEEE Symposium on Security and Privacy (SP).PP pp. 336-353. IEFE, 2020.
Tian Li, Shengyuan Hu, Ahmad Beirami, and Virginia Smith. Ditto: Fair and robust federated learning through personalization, 2021.
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Agüera y Arcas. Communication-effiieen learning of deep networks from decentralized data, 2017.
Payman Mohassel and Peter Rindal. Aby3: A mixed protocol framework for machine learning. In Proceedings of the 2018 ACM SIGSAC Conference on Computer and Communications Security, pp. 32,52, 2018.
Payman Mohassel and Yupeng Zhang. Secureml: A system for scalable privacy-preserving machine learning. In 2017 IEEE Symposium on Security and Privacy (SP), pp. 19-38, 2017. doi: 10.1 109/ SP.2017.12.
Takashi Nishide and Kazuo Ohta. Multiparty computation for interval, equality, and comparison without bit-decomposition protocol. In Tatsuaki Okamoto and Xiaoyun Wang (eds.), Public Key Cryptography PKC 2007, pp. 343-360, Berlin, Heidelberg. 2007. Springer Berlin Heidelberg. ISBN 978-3-540-71677-8.
Deevashwer Rathee, Mayank Rathee, Nishant Kumar, Nishanth Chandran, Divya Gupta, Aseem Rastogi, and Rahul Sharma. Cryptflow2: Practical 2-party secure inference. Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security, Oct 2020. doi: 10. 10.1145/337299..447222
URL //tp:::///x..e
dxx doi 1tt.ooocrr/...11/3337223333 0112297.441222 3417274
Jinhyun So, Basak Guler, and A. Salman Avestimehr. Byzantine-resilient secure federated learning, 2021.
Anselme Tueno, Florian Kerschbaum, Stefan Katzenbeisser, Yordan Boev, and Mubashir Qureshi. Secure computation of the kth-ranked element in a star network, 2019.
Zhibo Wang, Song Mengkai, Zhifei Zhang, Yang Song, Qian Wang, and Hairong Qi. Beyond inferring class representatives: User-level privacy leakage from federated learning. pp. 2512- 2520, 04 2019. doi: 10. 1LL.L//IIIFOOOO.00011987171
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Generalized byzantine-tolerant sgd, 2018.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance. In Kamalika Chaudhuri and Ruslan Salakhutdinov (eds.), Proceedings of the 36th International Conference on Machine Learning, volume 97 of Pro- ceedings of Machine Learning Research, pp. 6893-6901. PMLR, 09-15 Jun 2019a. URL mll. prwss /v97 v97 /xixxi99 9b.. html
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Slsgd: Secure and efficient distributed on-device machine learning, 2019b.
11

---

Under review as a conference paper at ICLR 2022
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta. Fall of empires: Breaking toauntine-toleratt sgd by inner product manipulation. In Uncertainty in Artificial Intelligence, pp. 261-270. PMLR, 2020.
Cong Xie, Sanmi Koyejo, and Indranil Gupta. Zeno++: Robust fully asynchronous sgd, 2021.
Andrew Chi-Chih Yao. How to generate and exchange secrets (extended abstract). In 27th Annual Symposium on Foundations of Computer Science, Toronto, Canada, 27-29 October 1986, pp- 162 167. IEEE Computer Society. 1986. doi: 10.1109/SFCS. 25... URL https://dol. org 10 www.1110999S...1858.8 .5
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett. Byzantine-robust distributed learning: Towards optimal statistical rates. In International Conference on Machine Learning, pp. 5650-5659. PMLR, 2018.
12

---

Under review as a conference paper at ICLR 2022
A Full Description of our algorithms
Here we provide full descriptions of both our median based and approximate bucketed median based FL algorithms (Algorithm
2
along with more details and correctness sketch for the Algorithm
B).
same.
A.1 Median based FL system
This is formally specified in full in Algorithm 2
Correctness sketch. We sketch the idea behind the protocol, which is inspired from similar ideas used in (Tueno et al.] 2019). To compute the median of n values {xi, T2 ...Tr. I. we first com- pute all pairwise comparison results big (x: > Tj), Vi,j E [n], + j. This allows us to compute for each element Tú, its position in the sorted list of { 22... .....Inn J. by computing pos;
Σ Ek{[n],A< bae. Finally, we find element for which pos; [n/2].
In our actual computation, we only compute bij, Vi,j E [n] s.t. j i. Then by: is taken as 1 - bij- The correctness of this median depends on all the values being different, which we assume to happen in our protocol (and abort this not true).
Float-to-fixed conversion. Our protocol for exact median involves mapping the client's local floating point values to integers, since it is well known that most cryptographic protocols are much more efficient when working over integer rings than directly over floating point values (Mohassel & Zhang 2017 Mohassel & Rindal 2018 Kumar et al.) 2020). Previous work in this area (Mo- hassel & Zhang 2017] Mohassel & Rindal 2018, Kumar et al. 2020), has made use of fixed point representation for the same, where real number is mapped to integer Pr [r 2- where is a parameter called the scaling factor. Hence, given a real number r, we map it to its fixed point representation pr, which is then mapped to an integer ring like Zze. In the following, use wiint to denote fixed point version of w.-
F2 and 12Fg,s functions which used for the mapping real numbers (fixed-point) integers and vice versa respectively. In particular, F21 R + Zze. is defined as (2),,((r) = [x 2* 12F Zze + R defined (x) x/2" (where Zzz is first interpreted as signed integer and then the division is performed).
and 32-bit floating point values throughout and which have only 23 bits of precision (and since we are only performing addition over the fixed point values/the values involved at any intermediate stage are small) we don't suffer any accuracy loss/convergence rate loss due to the usage of fixed point values.
Since we use
64, s
A.2 Bucketed median based FL
In Algorithm 3 describe in full our algorithm to compute the bucketed median.
13

---

Under review as a conference paper at ICLR 2022
Algorithm 2 One training epoch of exact median based FL Input: E [n], & holds dataset D;
Parameters: Bitlength fixed point scale
Vi E [m]. client ç does:
1. Receive fixed-point shares of global model (wi"") E Zoz from server Sj.Vje Vj {0, 1}.
2. Compute w = (w=²") + (w))") and wig = r2 (wog
3. Compute local model we SGD( D:)-
4. Convert back to fixed point as w!th F2Ir,,(w;).
5. Create fresh (2, 2) secret shares of wi! by choosing (w!"") at random from Zg and com-
puting (wo!t)) r0! (wo!")).
6. Vj {0, 1), send (w!""), to server Sj.
vj E {0, 1), server Sy performs the following:
1. E [ns]. receive share (w!")), from client C;.
2. Ak [d]. compute shares of median in dimension j across all the clients as follows:
(a) Vo [m].y E [x + 1, n/], compute (zi.g)s where z (w (kk) woth by calling FComp with inputs (mx""(())) (k))) (woli"())) Set (2g.e)s = (2
(b) Vi [m]. compute (post), = E=E(m) (zf.z))-
(c) mid (n + 1)/2 if n is odd, else set mid = n/2.
(d) Vi E [m]. check if pos; = mid by calling Fiiqua with inputs (pos;) mid and receiving output (eq)); in return.
(e) Vi E [n]. send (egi), to server S1-5 and compute eqi (eqi)o + (eq:)
(f) Find i E [ra] s.t. (k) 1 and set (w("'(k)) (k))) (w, (k))
3. Send (wll"") ) each client cs Vi E [n)]
14

---

Under review as a conference paper at ICLR 2022
Algorithm 3 One training epoch of bucketed median based FL
Input: E [n]] clients 6; holds dataset D:
Parameters: Number of buckets b, bitlength E, total epochs r. constant values po. P1. pt F where t is the current epoch number.
[h] Vi E [n], client c; does:
1. Receive global model wa and bucket range B from server So.
2. Compute local model wi SGD(w,, D;).
3. Bucketize w, to get e; {0, 1)dxb, Specifically, for each dimension k in [d], compute the htth row of bucketed model e; as follows:
If w,) I wy (k) 2 set (k) as [1. 0, .........))
If (k) w (k) + 2 set (k) as [0, ................................ . 0, 1].
Else, let = = ( (k) B/2) 1. Set ex(k) as [O,..., 0,0,,, where
B)(6-2)
e, 2) is set to 1.
4. Create (2, 2) secret shares of e; by choosing (e:)o at random from Z and computing
(e:)1 = e; (ei)o.
5. vj {0, 1), send (e:); server Sy-
Vj E (0, 1). server Sj performs the following:
1. Vi E [nl, receive share (e:), from client Cç.
2. Set (h), = Eiem (e:),-
3. For each dimension I: in [d]. calculate the approximate median: set (b) Find the bucket that contains the median:
(a) Vy E [2, b). set (h(k, v)), Exetu/ (h(k; =));
i. Compute (m(k));, where mm))) is of form [0...., 0). by calling FComp
with So input being (h())), [[ and S1 's input being (h())) [0]d*b Set
(m())), = [i]0 (m(())))- ii Sj shares (m), with S1-j.
iii. So computes
(m(k))o @(m(k))
iv. So selects the bucket y that contains the median as min (0,nee00.--))mmml [m(k, y) (1)m-
1].
(c) So quantizes the approximate median value w (k) as follows:
= wy(k) - y b --, w/ wy(() (k) B
If y = 0, w/
(k) (()(
Else, (k) = (w) (k) o + (v 1) (5 + (w)(k) 4 + (15) (x)) /2.
+
4. So creates new bucket range B' = 2/|wrg w
Pl.r. where Pt. is predetermined.
5. So sends w/ B' client e,, Vi [n).
To initialize FL. server So performs the following:
1. Initialize Wy model with parameter values of O.
2. Set B = Po-
3. So sends Wg, B to each client c,, Vi E [n].
B Formal security Proof
In this work, we use the semi-honest or honest-but-curious adversarial model, where it is assumed that the adversary follows the protocol specifications, but tries to glean information about the other party's inputs using the protocol transcript. As stated previously, sary, statically (i.e. before starting the protocol) corrupting up to n - clients and one of the servers, and prove full security of the protocol using the simulation paradigm.
assume semi-honest adver-
15

---

Under review as a conference paper at ICLR 2022
B.1 Defining Secure Multiparty Computation
Here, we provide a formal definition of secure multiparty computation. Parts of this section have been borrowed verbatim from (Goldreich 2004).
A multi-party protocol is cast by specifying a random process that maps pairs of inputs to pairs of outputs (one for each party). We refer to such a process a functionality. The security of a protocol is defined with respect to a functionality f- In particular, let n denote the number of parties. A non-reactive n-party functionality I' is a (possibly randomized) mapping of inputs to n outputs. A multiparty protocol with security parameter À for computing a non-reactive functionalitty I is pro- tocol running in time polynomial in À and satisfying the following correctness requirement: if parties P. Pi..... the joint distribution of the outputs V/.....: Vn of the parties statistically close to f(z,...., A reactive functionality f is sequence of non-reactive functionalities f = (fi...., fe) computed in stateful fashion in series of phases. Let z denote the input of P. in phase j. and let s denote the state of the computation after phase j. Computation of proceeds by setting s" equal to the empty string and then computing (yf...., yi,, 8*) + (,) .....,.......................... .x%) ..,,,.... for j E [c]. where yf denotes the output of P. at the end of phase j. A multi- party protocol computing f also runs in l phases, at the beginning of which each party holds an input and at the end of which each party obtains an output. (Note that parties may wait to decide on their phase-j input until the beginning of that phase.) Parties maintain state throughout the entire execution. The correctness requirement is that, in an honest execution of the protocol, the joint distribution of all the outputs (vi:.... u 2=1 of all the phases statistically close to the joint distribution of all the outputs of all the phases in a computation of f on the same inputs used by the parties.
with inputs (I1....,I,) respectively all run an honest execution of the protocol, then
Defining Security. The security of a protocol (with respect to functionality f) is defined by comparing the real-world execution of the protocol with an ideal-world evaluation of / by a trusted party. More concretely, it is required that for every adversary A, which attacks the real execution of the protocol, there exist an adversary Sim, also referred to as a simulator, which can achieve the same effect in the idcal- world. Next, we specifyy what each of these worlds mean.
The real execution In the real execution of the n-party protocol π for computing ff is executed in the presence of an adversary A. The honest parties follow the instructions of т. The adversary A takes input the security parameter k the set I [n] of corrupted parties, the inputs of the cor- rupted parties, and an auxiliary input z. A obtains the local randomness and the state of all corrupted parties, but all corrupted parties do follow the strategy outlined in the protocol specification.
The interaction of A with protocol π defines a random variable REAL A(=). (A, determined by the coin tosses of the adversary and the honest players. This random variable contains the output of the adversary (which may be an arbitrary function of its view, which includes the state of all corrupted parties) as well as the outputs of the uncorrupted parties. We let REALT..(ss), denote the distribution ensemble (REALT. (2, )EN, (E.. (0.1)
(A, .)) whose value is
The ideal execution security with abort. In this second variant of the ideal model, fairness and output delivery are no longer guaranteed. This is the standard relaxation used when a strict majority of honest parties is not assumed. In this case, an ideal execution for a function f proceeds as follows:
Send inputs to the trusted party: As before, the parties send their inputs to the trusted party, and we let a denote the value sent by P.. Once again, for a semi-honest adversary we require x/ Iz for all i E I.
Trusted party sends output to the adversary: The trusted party computes fa'i...., (v1....,yn, and sends (yileer to the adversary.
This is formalized by having the adversary send either a continue or abort message to the trusted party. (A semi-honest adversary never aborts.) In the latter case, the trusted party sends to each uncorrupted party P; its output value y;. In the former case, the trusted party sends the special symbol 1 to each uncorrupted party.
Adversary instructs trusted party to abort or continue:
Outputs: Sim outputs an arbitrary function of its view, and the honest parties output the values obtained from the trusted party.
16

---

Under review as a conference paper at ICLR 2022
The interaction of Sim with the trusted party defines random variable f.A)),,A(=)AA)) as above,and we let (IDEAL,.AGs) worlds, we now proceed define our notion of security, where semi-honest adversary is defined (intcractive) Turing Machine whose specifications match those of the protocol.
KEN, (E.)))00) Having defined the real and the ideal
Definition 1. Let k be the security parameter. Let be n-party randomized functionality, and be an n-party protocol for n E N. We say that II t-securely computes f in the presence of semi- honest adversaries if for every semi-honest adversary A there exists semi-honest adversary Sim such that for any I C [n]] with [X] S t the following quantity is negligible:
PPr |P,
= 1all-Pr[[DDEES Pr|1DDEAL,,A 1]
where I = (mahee)) E {0, 1)" and = E {0,1}*
B.2
Simulation
Since our model semi-honest and our protocols use secure 2-party computation, the simulator in our case is straightforward. Given the inputs of the adversary and the bucket index containing the median value across clients, the simulator sends random shares to the corrupted server on behalf of the honest clients. Finally, during secure bucketed median computation, it invokes the simulator for the secure protocol implementing Fompp and to this simulator provides as input the bucket index of the median value.
C Protocols implementing F Fompp Fl. Fequal Equal
For exposition purposes, we described our protocols for median computation by writing them in "hybrid" model, where parties have access to trusted functionalities Comp: F Equal- computing secret sharing of comparison and equality of two inputs respectively (described in Figure 7 and Figure S respectively). In this section, we provide protocols implementing the said functionalities. Our final protocol is then obtained by composing these with our own protocols. We then provide reasoning on why we choose secure comparisons the metric for protocol complexity.
F
Comp
Parties Po, P1
vb E 1), Po sends E Zoz to Ft
Comp
Fomp computes r zo 21 Zz = yo + y1 Zze and bit (x > y).
Fomm randomly chooses 2o E Zo and computes
z 20 E En and sends zω to
Po. E 13.
Figure Ideal functionality for 2-party comparisons: given (z), (y) compute (r y).
FL Equal
Parties Po. Pı
vb E {0,1}, P. sends σb, yo E Zze to Ff
Equal-
Ff Equal computes
+ E E Yo + y1 Ez and bit (x 1).
Ft Fégual randomly chooses 2g E Zgt and computes 21 = 2 20 E Zyz and sends 2;
Po. vb E 13.
Figure Ideal functionality for 2-party equality: given (x), (v) compute (r y)-
Notation Before going further, lets setup notation. For boolean variable
notation
1[2} to indicate the indicator variable, which is 1 iff 2 is true. While (z) (x)1 denote (2, 2) additive
secret shares of x over Eze, we use notation (z) (x) denote the (2, 2) additive secret shares of x over Ezz.
Compp Jf Eiquat use and modify bit the protocols proposed in CrypTFlow2 (Rathee et al. 2020). We describe the protocols for these in the following hybrids:
To implement Fl
17

---

Under review as a conference paper at ICLR 2022
Fam This is deseribed in Figure 9 It computes the solution the millionaire's problem over Zne and provides boolean secret shares of the answer bit to the two parties.
B2A This is described in Figure 10 takes boolean shares a bit from the two parties and provides shares of the same over Zze.
Miileg This is described in Figure 11 It is similar to FM except instead of doing comparison, it checks equality of the two received values.
Each of the above hybrids be implemented directly using protocols from CrypTFFow2 (Rathee et al. 2020). In more detail, while protocols for Mun FEZA are described directly in (Rathee et al, 2020. the protocol for FMlll.e can obtained directly by small tweak to the protocol for FM Since these protocols follow directly from (Rathee al. 2020), we skip providing detailed descrip- (Rathee et al. 2020) for the same.
tions and proof's of them here and refer the reader to
Given the above three hybrids, we provide the protocols for implementing FComp: -uquall Algo- rithm 4 Algorithm rrespectivvel.. We then have the following theorems (where "securely" refers to imnulation-based security according to Definition
Theorem C.1. Comp securely implements F'copp in the Fiail Febza hybrid as long as the signed
inputs of the two parties (whose secret-shares they input into the protocol) satisfy |æ]| + ly < 2-11
Theorem C.2. Equal securely implements Fequat in the Filllegg Flzs hybrid.
Composing the corresponding implementation of F Fiz:: Milley (as described above), gives us secure protocols for F Comps
Fl
Equal*
Ft Mill
Parties Po, P1
Po sends x E 1)
1) to Fimm while Pi sends E {0, 1) to Fim-
Fim computes z (a < y). chooses (2) + {0, 1} at random and computes (z)
(2)0 @ z. Fiam sends (=) Ps, vb E {0, 1].
Figure 9: Ideal functionality for solving the Millionaire's 's problem
F
Parties Po.
vb (0, P. sends (z) F F
Jiea computes (x) @ (a) chooses (ar) Ez random and computes (z)1 Ezz
as (z)1 (z)o. It sends (I)) to P., vb {0, 1}.
Figure 10: Ideal functionality converting boolean to arithmetic shares
RRathee al. 2020) provides protocols for Jhm and FiL directly. The protocol for Fi works by breaking up the bits inputs into a balanced binary tree and computing at each level the answer of both comparison and equality checks of the inputs corresponding to that subtree. Hence, while not stated directly in the protocol in (Rathee et al. 2020), protocol for Fimmey can be casily obtained from the protocol for F In addition, the public impiementation of CrypTFlow2 (ery) 202T) contains functions which allow compute the without tweaking anything underlying.
18

---

Under review as a conference paper at ICLR 2022
F
Mill.gg
Parties Po.Pt P1
Po sends E {0, 1] Milllog while Pi sends y E {0, 1) to F Milleq
Millag computes = (x = y), chooses (z)0 t {0, 1] at random and computes (2)
(z)6
Milley sends (z) to Po, vh E {0,
Figure 11: Ideal functionality checking if two parties hold the same value
Algorithm 4 l bit signed comparison protocol, Comp'
Input: vb {0, 1}, P. holds (z)b, b. (y)b.
Pr, Output: vb {0,1}, P. holds (1fx > y})b
1. vb E {0,1), computes (z)o (2)6 (y)6-
2. Compute boolean shares of msb(2) as follows:
(a) vb E [0, Po parses (=)s as msbelly-
(b) Po and P1 invoke F with Po's input 2 yo and Pi's input yı Ab {0. 1),P.
learns (carry)
(c) vb E {0, 1]. Ps computes (4) = msbs @ (carry)
3. Po and P1 invoke FBZa with inputs (t) to learn (t)o-
Algorithm f bit equality protocol, IT
Equal-
Input: vb E {0. PP. P. holds (z)s, (y)6.
Output: vb {0, P, holds (1fx v))b
1. vb {0,1}, computes (2)o (x)) (y)s.
2. Check if by doing the following:
(a) Po and Pi invoke computes F with Po's input (z)o, while Pi's input being
(- mod 2 vb {0, 1}, P, learns (eq)
(b) Po and P1 invoke FéZA with inputs (eq) to learn (eq)s-
C.1 Why we use secure comparison as complexity metric
MPC is efficient on linear operations when using arithmetic shares. The sum of two arithmetic shares (a) + (b) result in share (a + b). However, this is not the case for non-linear operations such
as (a) > (b), since the operation performed and the type of secret sharing are not of the same nature.
These type of non-linear operations such as multiplication, comparisons, and equality require creased computations, such as generation of correlated randomness between parties. There have been many works on improving the efficiency vide secure comparison protocol which uses O log é) secure multiplications, where / log and p is the prime used for the field the secret shares are computed over. (Nishide & Ohta 2007 improved the complexity of secure comparison to ( secure multiplications.
secure comparisons. (Damgárd et al. 2006 pro-
Thus large portion of the evaluation of a function in MPC is due to the computation of non-linear operations. Computing median intuitively involves expensive comparison operations, and therefore we choose the number of secure comparisons needed as a metric for computational complexity of the protocols.
D Detailed Robustness and Convergence Analysis
Proposition D.1 (Proposition 6. Restated),
With Assumption 2 we have
4g > 0: lim
EN,5 0.
N
19

---

Under review as a conference paper at ICLR 2022
Proof. Given a 0, for Ve 0, by Assumption 2 there exists N such that VM M >> N we have 5M, < 5/2. Therefore, C,, I 6M,5/2 = inf O.Me' S 6/2) <.
Theorem D.I. With Assumption 2 consider nı i.i.d. samples {VF:) (equation and m2 adversarial vectors for R Ji=r Denote = n1 + n2 and a == ng/n being the ratio of adversaries. If a < 1/2, then for Ve CN # with probability at least 1 (6N.c) ( (1-2a), have
8(E, E H2 [[ U (b - S. for Ve E W. Note that as N + oc, both ōN, + 0 and EN + O.
Proof. By definition of the median operation, we have VF Med((VE((w)) - VF Ufu
VF(w) Vtt
(3)
Invoking Lemma
2 have
Ved(L)// VF U VF(w))
-
[ VF(w) J (a)))))
(4)
where a; = |/0 F((w)l R.
As we can see, (4) depends on the variance of V N Eラ= Vf( :E(g). where ELs D are
i.idd sampled. Denote
X = 1 V Sch
where 1(.) the indicator function. By Assumption variable with
2 we can see that X; is a Bernoulli random
Pr 1 8N.--
Therefore, X. == mh Xxe forms a binomial distribution. By the Chernoff bound for binomial distribution. for k E N and h & n1(1 - -.N.)) we have
my ((a--o..))
Pr(β. S sk) mn -i.re
(5)
where DEL is the Kullback-Leibler divergence, i.e., for a1, 42 (0,
+ (1 (1) log 1 - 91
Dxz(gillz) == 01 log
42
1 92
2 4ı log
+ (1 q1) log(1 q1) (1 91) log(1 92)
2 (1 )1) log T-qaa
where the first inequality is due to that 42 < 1 and the last inequality is because that qi log 91 + (1
qı) log(1 - Q1) is the entropy which is non-negative.
Combining the above inequality with equation
5 we have
Pr( 5k) Se
-1 log oN. (6N.c) mi
(6)
Denoting event
+ 112
:=:= (X.
we can see that if E, happens then by Lemma of event E, happens. Therefore, when at t
B. we have (4) S It left to show the probability
8N..). we can apply equation to have
2n
Pr(Ee) Pr(X
+ n2
(6x..) (1220)
2
The condition of ny tna < (1-5x.e) esquvavlenn 8N.= S 1-2a and it has sufficient condition 2(1-a)
2n1
of EN, 1. 20.
20

---

Under review as a conference paper at ICLR 2022
Theorem D.2 (Theorem 6.1 Restated). With Assumption 2 consider n. i.i.d. samples { (VF, F (equation I and n2 adversarial vectors {u, R Denote := n₁ To2 and := ruz n being T==
the ratio of adversaries. Given the bucket range > O, the number of buckets and the gradient descent step size p. If < 1/2 then for de EN, 1-20 we have
-tt with probability least 1 (ŌN,e) (1-2a).
B 2b
V(v, R 121
[[BucketNled(((/
(o.)2::Bbb) (VF(w))l I pe
for Vw E W satisfying pll (l)))l 1 B for all i e [n].
Proof. First, by the definition of Bucket.Med()). for any input vector i; E R to the Bucket there exists vector of E R with || I B such that
(ucket)cc(((VVFF(())))
[w:]11: B, b) = BucketMec((//
u (o B,
Denote E, as the event defined in equation 7 By equation 8 we can see that
Pr(E.)
(ŌN..) (1-2a)
Given the event E,, by Theorem D.I we can see that
[[Med([uV] (w) u (w/)))))))))))))) -VF vVF(w) S pe,
for Veu W. Moreover, for Ve W satisfying p (w) s a e [n1]. by Lemma E.3
we have
B
[[BBckeetMed((4V)(())) (o Med Med(f
(o)a))l S
26
(10)
Therefore, combining equation 9 and equation 10 gives the theorem.
With Assumption 2 consider nı normal clients with i.i.d. samples { F; 1a (equation and n22 faulty clients that can send arbitrary vectors following the proposed protocol. Denote == nı +22 and a := n2/n n being the ratio of faulty clients. The bucket range adaption is defined by equation where we assume B, S B for all iteration t for a constant m3 ||V F; (1 for Vi E [n1]. If a < 1/2 for Ve >
Theorem D.3 (e2
B > and po
1-20 and Vc' > 0, the (N.
proposed method with parameters μ
dBg can achieve d3 Pı 2 2pc + 26" 2 + 3p and b 2 2e'
B
2,F((wo)
min USEST
T + (c ()
with probability at least 1 (ŌN.e) ) 2 (1-2a)
Proof. Denote E. = (X, +1 } as the event defined in equation 7 where
8 1 Villooo,o se).
By equation we have
Pr(E.) (ŌN.c) ) (1-2a)
Now condition on the event E., and denote the of clients
:= {i E [m]] ||FF v Filloc, S c),
(II)
and we can see that
[[]
+2
Recall that the training procedure of Algorithm is
w: = w;-1 - BucketMed ( U (v Bt-,,)).
where v are sent from the faulty clients at iteration L. In the following, for notational ease we denote
9:-1 := Bucket.Med( (w:-))) U (u..-172 b.)
Moreover recall the bucket range B, at iteration is updated by
B, = 17| n/| w || + P1 nl1g.-1l11 +PI. P1.
Now, given any i make the following claim.
21

---

Under review as a conference paper at ICLR 2022
Claim 1. Conditioned on event E., for any iteration step 2 0 have
p V (wr)))l Be,
(12)
B
[/VF((.))) gelloo yee +
(13)
2h
Proof of Claim 7 Note that equation 12 is true for t = 0 by assumption, and we prove the claim by induction. Assuming equation [2 holds for iteration 1, we prove equation 12 for iteration t, and prove equation
13
for iteration 1 by the way. We begin by
14 | F3 (w:)ll
14 V F3 (wx) VF(w)) + VF((:) VF(ww-1) VF(W:-1) gt- 9t-1/1 9t-1/Allo
(w:(w:)
VF(w)))lo> + (l).)) VF(wi-))ll>
IDFF(W-1) g 1
(14)
a3
4
where the last step is by triangle inequality. We will show that aı, 42, have straight-forward upper bounds, respectively. For the 01 by equation II
we have
a1 pec
By Assumption 1 have
a2 S u w1-1ll1 -
For a4, by definition of the & norm and lo norm, directly have
|1:--111-
Note that is exactly we want to prove for equation 13 For ag need to prove slightly different version of Theorem 6.1 however, using similar techniques. Recall the definition of g:-1
and I S [n1], we have
a3 = (w:-) BucketMiel((/VV/(((==)))) U (0. B b)
|IVFF(w - BucketWedl(d U he)mm (1ic-1) B B,-1, b)llo
Note that we have assumed that (w: < B For (n (uV
U (0: 1m2
there exists n1 + n2 vectors v/ Rd satisfying ||0/||0o B for i [nq ne [7] such that
Bucket
Bacceceee(((AAAA/eeooaaaaa/////a B)
(Vir-1) 1 B B,
= Bbeecthee(((T////oooo))e1111/11 B,
(15)
Therefore, denoting := (IVF((()==)))) by Lemma
R.3
we have
Budcket B Med(V)ll - B
B
<
(16)
2b
2b"
Moreover, since |T] int and we have
VF(w;-1)loo S for any E 1, by Lemma
E.1
[[Mod(V) V F (1)
[MMdd ( ( -m [F(
< j.c.
(17)
Combining equation 16 and equation
by triangle inequality, we have
B
[BuckettMedd) B) /V F S μe +
2b
( ( - we apply equation Noting that 1> (uV
15 to have
B
(BucketMel((AVV/(((:==))) Uo. b) (VW S
2h
22

---

Under review as a conference paper at ICLR 2022
which proves equation 13 for iteration - 1, and equivalently as S pc bounds for d1, a2, ag and a1, we finally have
+
B 26-
Collecting our upper
B
14
01
02
0g
a4 S pue 1.33lgt-11 + pe
l1
1//1
2b
B
2p
+
+ + (1+13))
2h
Recall the condition that p1 2 2μ1
+ 36
and 17 2 1 3p. We can see that
14
- M 1 + p1 Bt.
By induction, it concludes the claim.
Given the Claim [ we continue the proof of Theorem 6.2 By the smoothness assumption (Assump- tion I and given that the parameter domain W is defined to be convex, it is known that F (wi++1) F(w,)
I (VF(w,), W441 w.) + ||0,+1 welli
8
(VF(w,) 91) glggeli
d3 19
(VF(w;)) 9.)
(VF(w;)) 9: 1 F(w:) VVF(w,)) + d3 l1g (VF(w,) (VF(w)))
- (VF( mVF
d3 VVF(w::) ||g. /V ( ) x 2 (w:)))
V
2
(18)
Substituting into μ
d3 we can continue as
d3
18
VF(ww))1
11g (VW(w:))
2d3
2
d3
s
VF (w:))11
11g:
FVF
2d3
2
By Claim I we have
d3
B
2
18
<
|
[F(w)))
NE
2d3
2
2b
B dB
V (w:)
)
+
2d3
V28
2 2b
Therefore, rearranging the inequality, and denote
dd
2
dB3 2
23
V23
25
2b
we have
V (., ) < (3(F((w)) - F(W++1)) + +.p.
Accordingly, for number iterations 7 1:
T
28 (F(wo) F(wr+11) +
VF w. )12 <
T ++1
d
T +
2 (wo)
+ p. 19 implics
(19)
T
Given any > and choosing b b>
dB3 2d
equation
F (wo))
min OStST
VF((w:)l <
+ (e +
d
T +
23

---

Under review as a conference paper at ICLR 2022
E
Auxiliary Lemmas
Lemma E.1. Given of real number A {or (R..= and interval (a, bj R. IAn la, b] > IAn [a, b] then we have Mod(.A) E [a, b).
Proof. Without loss of generality, assume A is sorted, i.c, 2, S I++1 for Vi [n 1]. By the definition median, there are at least [ numbers A that are less or equal to Med(.A). Therefore, if Med(AA) < a, (a, b). which contradicts to the condition of [A n [a, bll > [A in [a, b]%. Hence, Med(A) 2 a Similarly, we can show Med(AA) b. That being said, Med(AA) [a, bj.
that there are least [ numbers in A that are outside
Lemma E.2. Given n vectors {or E (RO we have
[Med((o))2=ille>> I Mo
Proof. Denoting (k) as the htth dimension of E RR, we have
((ied(((;))=))ll max
max Med({ Med(( kefml
(20)
kE(m]
Denote k" E arg [| (cd(( and we have
20 Med(() S Med({ max
[u,(k)] Med((])
kE
Lemma E.3. Given the bucket range B > the number of buckets for any n vectors J in
Rd if ll B for all i E (n], then have
B
[BucketMedd(o:) B, Med(fu;) S
Proof. Since |/ < B for all [ni] are within the bucket range, the Bucket ((v)) B, is the same as Med((v))) for some of e Rd satisfying
B
100 villo -
2h
Denote
B
B
w
:.
+
2b
26"
where the + 26 is done every dimension of v. We that w I v S w/', where the I is also dimension-win wise. Noting that
B 25
( 26
Med( (W < Med((u/)E s Med([w]]
= Med( +
can conclude that
B
Med((f((] - Mcd([v;] < 26
Replacing the Med((v)) by BucketMed((o:)]1 B) gives the lemma.
Computation Breakdown and Parameter Sensitivity
In this subsection, we detail a temporal breakdown of a round of federated learning in our approach and the pairwise comparison median. We show the relationship between server-side computation time and increasing number of clients. In the bucketing technique, parameters are agreed upon at the start of the FL protocol to initiate values for the bucketing ranges. We empirically show that these parameters are not sensitive, and that convergence still holds while varying the order magnitude of these parameter values.
24

---

Under review as a conference paper at ICLR 2022
16000
-4000
Server Computation Time
12000
10000
6000
4000
Total Server-side Computation
2000
Median Computation Only
130
160
Number of Clients
Figure 12: Relationship between number of clients and 1. total server-side computation time after receiving all client updates, 2. bucketed median computation time.
Computation Breakdown for one round of FL
Insecure
Me-
Time
Pairwise Compar-
Time
Bucketed Median
Time
dian
(s)
ison Median
(s)
(s)
Clients train local model
24
Clients train local 24
Clients train
local 24
model
model
Clients bucketize 5
model
Clients
compute
Clients compute
shares
shares
Server insecurely computes median
Servers calls C++
500
Servers calls C++
125
backend to compute median
backend compute
median buckets
Server quantizes
5
median buckets
Total
Total
525
Total
160
Table 1: CNNMnist, 8 clients, simulated LAN network
detail the time in seconds each part of the FL process takes for both the pairwise com- parison based median method, and our proposed bucketed median method. The bucketed method had the additional overhead client and server side of converting and from bucketed format, and this takes around 5 seconds per transformation for a CNNMnist model. The time for both methods are dominated by the two server secure computation of median. We see that the pairwise comparison based median FL system increases by factor of 17.5, and the bucketed median FL system increases by factor of 5.5.
In T
In Figure we show the scalability of our protocol when the number of clients range from 10 to 160 in increments of We detail the number of clients on the x-axis and the server-side computation time (after receiving all client updates) in milliseconds on the y-axis. The server-side computation consists of the following parts: adding client shares to compute histogram for each dimension, 2. performing MPC computation of the bucketed median for each dimension, 3. converting the chosen median buckets to a global model. Steps 2. and 3. are independent of the number of clients. We test the MLP model. We see that the time for bucketed median computation stays constant, yet the time taken for steps 1-3 roughly increases when number of clients increase due to the time taken for step 1.
In Figure 13 we show the performance of our bucketed protocol with different parameter values. In protocol, determine bucket range as B {po, [ww, wtyl1 p1.t), where po chosen during the initial epoch, and I|// Wy + P1.e is chosen in subsequent epochs. In convergence analysis,
Pi and prove convergence for this choice. In experiments, where t is the current epoch count. Both choices empirically result decreasing training loss per epoch, albeit slightly different rates. We note that in our implementation, set both Pn and p1 as
25

---

Under review as a conference paper at ICLR 2022
100
++1
++.0.8
0.008
++0.008
+00.0008
10
Training Loss
0.01
10
Epoch
Figure 13: Variable parameter values for bucket range tested on a three client FL system and CNN- Mnist model.
equivalent values, and use the CNNMnist model. For parameter values less than we see that our bucketed mechanism results in similar rate of training loss convergence. For each model, one can solve for specific Po. Pi values for the best convergence rate, but as the convergence behaviour does not strictly depend on the parameter values, we do not focus our attention towards this optimization.
26


Reviews:
[{"review_id": "tldh2bWBZgf", "reviewer": "Reviewer_6dep", "summary": "", "questions": "", "limitations": "", "rating": 3, "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": "\n\nThe paper is understandable but contains quite a few language mistakes and suboptimal formulations.\n\nThe technical details (often in appendix) contain quite a few mistakes, it is unclear whether it is possible to fix them all while sticking to the current results.\n\nFor example, the robustness theorem (6.1) looks suspicious to me.  As it is formulated, there is no specification of how the adversarial vectors are generated.  There may exist schemes to generate these adversarial vectors which are compatible with the theorem formulation but cause a deviation in the median much larger than what the theorem promises.\n\n\n\nA few details:\n\n* Sec 4.2: In order to send their updates to the servers, clients additively secret-share their updates and sends one share to each server. -> send (plural)\n\n* Algorithm 2, part 2, step 2. (d) : where is b defined ?  Or do you mean j instead of b ?\n\n* In algorithm 1, 'b' is the number of buckets (a different meaning than the symbol 'b' in algorithm 2, it is preferable to avoid the same symbol having different meanings at different places).\n\n* In Section 5, \"instead of sending actual updates to the server, each client will send a unit vector that has a 1 in the bucket containing the client’s update, a\": it therefore seems that as soon as the actual update has fewer bits than the number of buckets the original non-bucketed version may be cheaper from a communication point of view?\n\n* Section 6.1: \"Data individual loss function is denoted\" -> an article is missing\n* \"if ratio of adversarial clients is\" -> an article is missing for \"ratio\"\n\n* We provide similar result -> a similar result\n\n* Equation (3): I would have expected \\|Med(\\{\\nabla {\\hat F}_i(w) \\}_{i=1}^{n_1} \\cup \\{v_i\\}_{i_1}^{n_2}) - \\nabla F(w) \\|_\\infty = \\|Med(\\{\\nabla {\\hat F}_i(w) - \\nabla F(w) \\}_{i=1}^{n_1} \\cup \\{v_i - \\nabla F(w) \\}_{i_1}^{n_2}) \\|_\\infty, but in Eq (3) in the paper the rightmost term of the righthandside of the equation doesn't have \"- \\nabla F(w)\".\n\n* Equation (4), please define (or remind the definition of) a_i.\n\n", "summary_of_the_paper": "\nThe paper proposes to use the median of model updates instead of the average of model updates in federated learning, and proposes an algorithm to perform the computation in a secret-sharing fashion by two independent servers.\n", "summary_of_the_review": "\nWhile the topic is interesting and the paper may have a valuable contribution, I don't succeed to verify the proofs of its theorems, and the way in which the theorems are stated lets me believe it is possible they are not correct.  ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "2: Several of the paper’s claims are incorrect or not well-supported.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "p5-LoBXuPSL", "reviewer": "Reviewer_SNQM", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "Strengths\n\n1. The topic is interesting. Achieving privacy and robustness is an important goal for federated learning. \n\n2. An approximate median aggregation rule is proposed. The proposed approximate median is crypto-friendly.\n\n3. Some theoretical analysis about the approximate median is proposed. \n\nWeaknesses\n\n1. The proposed crypto method assumes two non-colluding servers. This assumption may be unrealistic. \n\n2. The compared baseline seems too simple. Basically pairwise comparison is adopted as a baseline for implementing the standard median. How about median of median? We can divide the clients into groups, calculate median in each group, and then take median of median. This is another approximate method and is more efficient.\n\n3. The evaluated Byzantine failures are too simple. Basically,  bit flips failure, label flip failure, and Gaussian noise failure are considered. I suggest the authors to consider more advanced attacks, e.g., the following:\n\na. A Little Is Enough: Circumventing Defenses For Distributed Learning. In NeurIPS, 2019.\n\nb. Local Model Poisoning Attacks to Byzantine-Robust Federated Learning. In Usenix Security Symposium, 2020. \n\nIf my comments, especially 2 and 3 are addressed, I'm happy to increase my rating score.  Overall, I think this is a promising direction. We can pick a robust federated learning method and then use cryptography to make it privacy preserving. However, we need to pick a really robust federated learning method. The paper picks Median, which shows some robustness but is not really robust. I think picking a method with provable robustness guarantee would make the paper stronger, e.g., the following:\n\nc. Provably Secure Federated Learning against Malicious Clients. In AAAI, 2021.\n\nd. CRFL: Certifiably Robust Federated Learning against Backdoor Attacks. In ICML, 2021.\n\n", "summary_of_the_paper": "This paper aims to build privacy-preserving and robust federated learning systems. The proposed method includes two key ideas. The first idea is to propose an approximate, crypto-friendly median aggregation rule, which aims to achieve robustness. The second idea is to use cryto methods to implement this aggregation rule. Experiments were conducted to show that the proposed method is more efficient than cryto-based standard median implementation.  ", "summary_of_the_review": "The paper studies privacy-preserving and robust federated learning. I think the paper would be stronger if my comments are addressed. ", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}, {"review_id": "Pjb9IbL8RDI", "reviewer": "Reviewer_mthn", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The problem of achieving security as well as Byzantine robustness in federated learning is challenging, and there are only a few papers on this topic. In this sense, the paper is timely and relevant. However, the threat model considered in the paper is non-standard (and also a bit confusing). Furthermore, the novelty seems to be limited as the paper mainly combines two ideas from the literature: bucketing (from [Corrigan-Gibbs and Boneh 2017]) and secure median ([Tueno et al. 2019]). The detailed comments are as follows:\n\nMajor comments:\n\n1. In the majority of papers that consider robust federated/distributed learning, it is assumed that Byzantine/adversarial clients can arbitrarily deviate from the protocol. The paper mentions in the abstract about adversarial updates, but also assumes that all clients honestly follow the protocol. This is somewhat non-standard threat model. Is it assumed that errors occur due to external factors such as hardware faults etc? If this is the case, then errors may occur while computing secret shares of the model as well. It is assumed that secret shares are computed perfectly, which does not seem practical. Also, first mentioning adversarial updates and then mentioning semi-honest clients can be a bit confusing. It would be important to add a discussion on this model, and explicitly mention how this differs from Byzantine or malicious setup considered in prior works.\n\n2. The title of the paper says scalable robust federated learning, however experiments are performed with just 3 clients. This seems to be a bit too limited. Since MPC primitives will mainly be used between the two servers and clients simply secret share their updates, it is not clear why not to scale the protocol to a larger number of clients in the experiments. At the very least, can the authors comment on how would the bucketed median perform (without security constraints) for a larger number of clients, when a constant fraction of clients can be faulty?\n\n3. Assumption 2 seems to require that each client has a very large dataset, and computes gradient descent on the entire dataset. Can the authors elaborate on this? This seems to limit the practicality. How the assumptions in the paper differ from typical assumptions, say those in [Yin et al. 2018]?\n\nTaking this point further, the paper says (before Theorem 6.1) that [Yin et al. 2018] requires \\alpha to be \"smaller than an easily negative value\". Can the authors give more details on what this means? Further, the authors say that they prove the robustness in a new way.  It will be helpful to elaborate what new techniques are used, and how they differ from [Yin et al. 2018].\n\n4. In Algorithm 1, it is not at all clear how F^l_{Comp}(<\\sum_{i}e_i>_j, n/2) can compute the median on buckets. Specifically, why does  the comparison algorithm take sum of shares as input? In general, it is a bit unclear how the frequency distribution of client updates is computed, or even how it is defined. It is important to give sufficient details here.\n\n5. In Experimental Results, it would be important to give more details about the models considered. For instance, in the CNN for CIFAR-10, how many convolutional layers, what pooling etc.\n\nOther comments:\n\n1. The authors mention that best known approaches for median aggregation with MPC are slow, having quadratic computation cost (in terms of the number of clients). There are no citations given. Can the authors provide some references to support this claim?\n\n2. The paper cites [Konecny et a. 2017] for MPC in federated learning at two instances in the first paragraph. This is incorrect as [Konecny et a. 2017] deals with reducing communication costs, and does not consider MPC.\n\n3. Can the proposed protocol handle client dropouts? It would be helpful to mention this explicitly.\n\n4. Secure comparison is a significantly complex computation. The complexity of the proposed algorithm is characterized in terms of number of calls to secure comparison. It would be helpful to elaborate on the complexity of secure comparison to give a fair idea to readers (who are less aware of MPC primitives).\n\n5. The paper claims in the title that the proposed algorithm has provable security guarantees, but spends only a paragraph in the main paper about the security analysis. It would be helpful to add more details, as security considerations are important for the problem setup. \n\n6. For label flipping, computing mean seems to perform better than computing median. It would be helpful to add a comment on why this is the case.", "summary_of_the_paper": "The paper considers federated learning with two non-colluding honest-but-curious servers and honest-but-curious clients, where a subset of clients can be faulty. It proposes a protocol to securely compute approximate median. The main idea is to use secure median algorithm from [Tueno et al. 2019] along with a bucketing trick proposed in [Corrigan-Gibbs and Boneh 2017] to reduce complexity. The paper gives convergence analysis for bucketed median under some strict assumptions.", "summary_of_the_review": "The novelty seems to be fairly limited as the paper mainly combines two known ideas: bucketing and secure median. The threat model is somewhat non-standard, and experiments are conducted on only 3 clients.", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "3: Some of the paper’s claims have minor issues. A few statements are not well-supported, or require small changes to be made correct.", "technical_novelty_and_significance": "2: The contributions are only marginally significant or novel.", "empirical_novelty_and_significance": "1: The contributions are neither significant nor novel."}, "extra_text": {}}, {"review_id": "L9gptgcwY9", "reviewer": "Reviewer_moZd", "summary": "", "questions": "", "limitations": "", "rating": 5, "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": "The paper considers the two-server federated learning setting and proposes an interesting and simple approach for tolerating malicious users. The protocol is efficient as its complexity grows only linearly in the number of the users, whereas it grows quadratically in prior works.  The approximation is based on bucketing, which divides each dimension of the model into buckets and sends a unit vector that has a 1 in the bucket containing the client’s update and the median is approximated as the middle value of the range of this bucket. My main concern is that the paper does not consider some closely related works. Hence, it is not clear if the proposed approach is better. Below, I provide my detailed comments.\n\n1- It is not clear for me how the proposed approach of this paper compares to other related works that are not mentioned as [1, 2]. The authors should make sure to include all relevant works along with comparisons that show the effectiveness of the proposed approach compared to these works. \n\n2- Typo in Page 2: \"showe\" -> show\n\n3- Page 4: I find the static corruption model in Section 4.1 to be unrealistic as it assumes that the adversary chooses the parties to corrupt at the beginning of the protocol and cannot change them. In general, the corrupted parties may change dynamically while the protocol is running.  \n\n4- Page 6: The convergence analysis only considers the IID case, how about the non-IID case?\n\n5-  The following sentence should be illustrated more perhaps by providing numerical examples.  \n\"Note that the previous analysis on dimension-wise median in the FL setting (Yin et al., 2018) requires α to be smaller than an easily negative value\"\n\n6- The number of users considered in the experiments is too small to claim scalability. More experiments with large number of users need to be performed to show the effectiveness of the proposed approach in large-scale systems. \n\n7- Fig. 5 shows large gap between the proposed approach and the median approach, why this is the case?\n\nReferences \n\n[1] Y. Khazbak et al. \"MLGuard: Mitigating Poisoning Attacks in Privacy Preserving Distributed Collaborative Learning.\" , IEEE ICCCN, 2020.\n\n[2] H. Fereidooni, et al. \"SAFELearn: secure aggregation for private federated learning.\" 2021 IEEE Security and Privacy Workshops (SPW).", "summary_of_the_paper": "This paper proposes a fast, secure, private and scalable approximate median aggregation approach for federated learning with two semi-honest non-colluding servers. The convergence analysis of the proposed approach for the IID case has been also provided under certain assumptions, which shows that the proposed approach converges with high probability if less than 1/2 of the clients are malicious. Finally, the experiments show that the proposed approach achieves similar robustness performance compared to the exact median based approach. ", "summary_of_the_review": "The paper proposes an interesting approach approach for tolerating malicious users in FL, but it does not consider some prior works. Hence, I recommend revising the paper to include all relevant works and adding the comparisons. \n\n-- Post Rebuttal  --\n\nI still do not see how the proposed approach in this paper compares to the related works I mentioned. While [1] does not provide server side running times, you should still evaluate their protocol and compare with your work. The responses to the non-IID issue and the scalability issue that I raised are not satisfying neither. Hence, I am keeping my score. \n", "strength_and_weaknesses": "", "limitations_and_societal_impact": "", "review_text": "", "extra_scores": {"correctness": "4: All of the claims and statements are well-supported and correct.", "technical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work.", "empirical_novelty_and_significance": "3: The contributions are significant and somewhat new. Aspects of the contributions exist in prior work."}, "extra_text": {}}]

Author rebuttal:

Meta-review: There were concerns that the paper has a fairly limited novelty, being based on the combination of two known ideas: bucketing and 2-party secure median for distributed learning. Also, the scale of experiments is quite limited. Other issues include the lack of comparison to relevant related work, some doubts on correctness, and issues with independence and scalability that weren't fully resolved. Overall the reviewers felt that the paper shoud not be accepted in its current form.
Decision: Reject