Year: 2021

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, relying on secure multi-party computation (MPC) to naı̈vely compute the median is unscalable. To this end, we propose a 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 of our approach scales only linearly with the number of clients, whereas the naı̈ve 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 displays similar robustness properties as the median while converging faster than the naı̈ve MPC median for even a small number of clients.

text: 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, relying on secure multi-party computation (MPC) to naı̈vely compute the median is unscalable. To this end, we propose a 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 of our approach scales only linearly with the number of clients, whereas the naı̈ve 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 displays similar robustness properties as the median while converging faster than the naı̈ve MPC median for even a small number of clients.

heading: 1 Introduction
text: Federated Learning (FL) (McMahan et al., 2017) has emerged as a 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 in 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, 1986; Goldreich et al., 1987) is a cryptographic primitive that makes it possible to evaluate a 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 to recover a 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 et al., 2019). The distributed nature of the computation creates a variety of vulnerabilities to adversarial training attacks and client failures such as hardware, software, data, and communication errors (Xie et al., 2019a; 2021). One way to improve robustness is to replace an aggregation procedure that computes means with a more robust aggregate such as the median (Yin et al., 2018). Using the median, up to half of inputs can be from a faulty distribution before the median fails as a 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 et al., 2019), designed for learning across institutions. For example, an individual hospital may be limited to using only their own patients’ data, and sharing patient information among hospitals is generally difficult due to privacy and intellectual property concerns. Here, federated learning can provide a mechanism for widely distributed medical institutions to jointly train a model.
The main contribution of this work is a new approximate-median aggregation for robust, privacypreserving 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. In 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 colluding 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 each step. This provides meaningful privacy to every client and is a meaningful defense, e.g., against modelinversion attacks that take advantage of individual client updates. • Scalability. The running time of our protocol increases linearly with the number of clients; matching the order-wise scaling (with number of clients) of the standard averaging aggregation. This is in contrast to a quadratic factor blowup for a federated learning system that implements median naı̈vely in MPC. We empirically evaluate the convergence of our system on various datasets, models and under different types of faults.

heading: 2 Related Work
text: Federated Learning (McMahan et al., 2017) is a widely adopted technique for training models with data from edge devices. In its plainest form, client updates are sent without encryption to the central server at each round, and the global model is sent back to each client. However, this basic implementation of a 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 a protocol for secure aggregation of the client updates and computation of the global model in both a semi-honest and malicious setting, with increased runtime and communication overhead. In addition to encryption 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 a 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 et al., 2020; So et al., 2021), and norm-based elimination (Gupta et al., 2021) have been studied. In this paper, we strengthen the restriction on client faults and only consider semi-honest clients. Although a semi-honest setting may 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-knowledge proofs are added on top of the existing semi-honest protocol.
Secure Multi-Party Computation (MPC) provides a 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 a rank computation system where clients send a 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 comparisons 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-preserving analytics and machine learning. For instance, (Corrigan-Gibbs & Boneh, 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 statistics 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 knowledge, (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-based aggregation. They also make the assumption
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 et al., 2019) and a bucketing approximate median idea proposed in (Corrigan-Gibbs & 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 al., 2021). These details are left for future work.

heading: 3 Preliminaries
text: Federated Learning. We denote N as the set of positive integers and R+ as the set of non-negative real numbers. Given n ∈ N, we denote [n] = {1, . . . , n}. We use bold lowercase letters, e.g., w ∈ Rd, to denote vectors, and w(k) to denote its value at the kth dimension. We consider a twoserver multi-client FL system, let S0, S1 denote the two central severs, and ci for i ∈ [n] represent the clients, where n is the total number of clients. Client ci holds datasetDi. The agreed upon model has d parameters. wg denotes the global model sent from servers to clients, while wi denotes the local model held by client i. All parties agree beforehand to run r cycles of FL. The loss function for client ci is F̂i : Rd → R+. Usually, because clients have different data, the loss functions F̂i are different. Therefore, the goal of our setting is to minimize the averaged loss across all clients, i.e., arg minw 1 n ∑n i=1 F̂i(w).
We first detail a basic federated learning system with one central server S and n 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 ∈ [n], client ci receives global model wg from central server S . 2. For i ∈ [n], client ci performs step(s) of Stochastic Gradient Descent of wg on its dataset
Di to obtain new local model wi. They then send this model to S. 3. Upon receiving all client updates, S aggregates them to obtain the new global model. The
new global model is computed as w′g = 1 n ∑n i=1 wi.
4. S sends w′g to all the clients.
Secure Multi-Party Computation. Secure Multi-party Computation (MPC) (Goldreich et al., 1987) is a cryptographic primitive which allows n parties, each with input value xi, to jointly compute a mutually agreed upon function f(x1, x2 . . . xn), with the guarantee that no party learns anything 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, n) secret sharing involves splitting a secret s into n shares, then distributing a share to each party, such that any subset of t− 1 parties cannot learn anything about s, while any t or more parties can jointly reconstruct s. In this paper, we make use of (2, 2) additive secret sharing over power-of-two sized integer rings, which involves splitting s ∈ Z2` into s1, s2 ∈ Z2` s.t. s1 + s2 = s, and individually si, i ∈ {0, 1} has a uniform random distribution. We use 〈s〉 to denote secret sharing of s over Z2` , and 〈s〉0, 〈s〉1 to denote the shares of the two parties. We use F`Comp,F`Equal 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 protocols for F`Comp,F`Equal, we make use of protocols proposed in CrypTFlow2 (Rathee et al., 2020). CrypTFlow2 provides a customized 2-party protocol for solving the millionaire’s, and hence also the comparison/equality problems in Z2` (more details on all this in Appendix C).

heading: 4 Problem Description
text: In this section, we introduce a baseline solution to secure and robust FL. Median provides wellstudied 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 1 provides a representation of our model.

heading: 4.1 Security Threat Model
text: We model the adversary using the semi-honest/honest-but-curious model, whereby it 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 S0, S1 do not collude with each other. The adversary is then allowed to corrupt any arbitrary subset of the clients and at most one of the servers - and once corrupted gets to see their internal state as 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.

heading: 4.2 Baseline solution
text: 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 a MPC based median computation. We take inspiration from the ideas in 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 of equality checks. In Appendix A, we provide a formal description of our algorithm in the F`Comp,F`Equal hybrid (described in Algorithm 2), along with a correctness sketch and other details for the same. Our final protocol is then obtained by replacing F`Comp,F`Equal with CrypTFlow2 (Rathee et al., 2020) based secure comparison/equality protocols (described in detail in Appendix C). We refer to this protocol as “pairwise comparison based median” in the rest of the paper.
Complexity. The complexity of this protocol is at least dn(n − 1)/2 calls to F`Comp, in addition to dn calls to F`Equal. Note that the number of secure comparisons/equalities grows quadratically with the number of clients n. In the next section, we will introduce our approximate median protocol, whose number of secure operations is independent of n. We provide a brief summary in Appendix C on why we use number of secure comparisons as a metric for complexity.

heading: 5 Bucketing based median computation
text: In this section, we propose an approximate median, which provides increased computational efficiency, to serve as the replacement of the exact median computation. We provide an abridged version of the protocol in Algorithm 1 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 a fixed set of buckets. Let b designate the number of buckets. Next, 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, and 0 everywhere else. 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
Algorithm 1 Succinct version of our bucketed FL system Input: For i ∈ [n], ci holds dataset Di. d = model size, b = number of buckets, p are public parameters. ∀i ∈ [n], client ci does:
1. Receive global model wg and bucket ranges B from server S0. 2. Compute local model wi as SGD(wg, Di). 3. Compute Bucketize(wg, B, b,wi) and obtain bucketized local model ei. 4. Creates (2, 2) shares 〈ei〉0, 〈ei〉1 of ei. 5. Send 〈ei〉0 to S0, send 〈ei〉1 to S1.
∀j ∈ {0, 1}, server Sj does: 1. Receive share 〈ei〉j from client ci,∀i ∈ [n]. 2. Add shares 〈e1〉j . . . 〈en〉j to obtain 〈 ∑n i=1 ei〉j .
3. Call 2-party secure protocol F`Comp(〈 ∑n i=1 ei〉j , d n 2 e) and obtain d-length vector m, where
m(k) indicates which bucket holds the median for dimension k ∈ [d]. 4. S0 calls Quantize(wg, B, b,m) and obtains new global model w′g . 5. S0 computes new bucket range B′ as 2‖(w′g −wg)‖1 + p. 6. S0 releases w′g and B ′ to all clients.
approximated by the middle value of the range of this bucket. All this while, servers only obtain (2, 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 to build a secret sharing of the frequency distribution of clients’ updates and find the bucket which contains the median value. The approximate median is then chosen as the middle value in that bucket.
At the beginning of a given round each client ci receives bucket range B and global model wg from the central servers, and follow by running SGD on its dataset Di to obtain local model wi. The bucket range implicitly fixes the buckets around the global model wg , i.e. in any given dimension k ∈ [d], the b buckets are centered around wg(k) with total range of B. The ending buckets are taken to represent all the remaining range outside B - i.e. the first and the last buckets represent the range (−∞,wg(k) − B2 ], [wg(k) + B 2 ,+∞). The middle b − 2 buckets evenly divide the range wg(k) ± B2 . ci then creates, ∀k ∈ [d], a unit vector ei(k) ∈ {0, 1} b with 1 in place for the bucket which contains wi(k); we refer to this transformation as “bucketizing”. ci then sends secret shares of ei to both servers
The servers add all the client updates to get a secret-sharing of the frequency distribution of the 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 of frequency against dn2 e. The comparison result is then revealed to learn which bucket contains the median value and the servers take the middle value of that bucket to be the value of the new global model g′w for that dimension. We refer to this transformation of converting a bucketed model back to a model where each dimension has a numerical value associated with it as “quantizing”. The bucket range is then updated as 2‖w′g −wg‖1 + p, where p is a parameter agreed by all parties.
Complexity For each dimension, the servers need to only perform b calls to F`Comp - hence a total of db calls. Compared to dn(n−1)/2 calls for pairwise comparison median computation, we note that if b is a 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.

heading: 6 Theoretical guarantees
text: In this section, we theoretically analyze the proposed method in terms of security, robustness, and convergence guarantees.

heading: 6.1 Robustness and Convergence
text: We first introduce the notation and settings specific to the robustness and convergence analysis. The proofs in this subsection are provided in section D in the appendix. Given a data distribution D, we assume data samples ξ∼D are i.i.d. sampled. Data individual loss function is denoted as f(· ; ξ) : Rd → R+, i.e., f(w; ξ) ≥ 0 given a parameter w ∈ Rd. Based on the individual loss function, we denote the population loss function F = Eξ∼D[f(· ; ξ)], and we assume it is differentiable. Draw N i.i.d. samples for each of the n clients (in total nN samples): {ξi,j}i∈[n],j∈[N ]. Therefore the client empirical loss function is
F̂i = 1
N N∑ j=1 f(· ; ξi,j) for i ∈ [n]. (1)
The goal of our setting is to minimize the averaged loss across all clients, i.e., arg minw 1 n ∑n i=1 F̂i(w). In the convergence analysis, we consider gradient descent with step size µ. The range of the buckets at iteration t is denoted as [−Bt/2, Bt/2], and the model parameter are denoted as wt ∈ Rd. As detailed in Algorithm 3, we consider the bucket range updated by
B0 ← p0, Bt ← η‖wt −wt−1‖1 + p1, (2)
where p0, p1, η > 0 are constants. There is a convex parameter set W ⊆ Rd such that the parameters during gradient descent for all clients are within W . Given a function g : Rd → Rd and p, q ∈ [1,∞], we denote the (p, q)-norm of g as ‖g‖p,q = (∫ W ‖g(w)‖ p q dµ(w) )1/p . In particular, ‖g‖∞,q = supw∈W ‖g(w)‖q.
The coordinate-wise median operator Med(·) takes a set of vectors {vi ∈ Rd}ni=1 and outputs a vector v ∈ Rd such that for each dimension k, v(k) is the standard median of {vi(k) ∈ R}ni=1. 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
wt+1 ← wt − BucketMed({µ∇F̂i(wt)}i∈[n];B, b), where B is the bucket range and b is the number of buckets.
We make the following assumptions for the robustness and convergence analysis.
Assumption 1 (β∞-smoothness). F is β∞-smooth. Formally, there exists β ≥ 0 such that for ∀w1,w2 ∈ W we have
‖∇F (w1)−∇F (w2)‖∞ ≤ β‖w1 −w2‖1, Note that ‖ · ‖1 is the dual norm of ‖ · ‖∞. Assumption 2 (Weak Law of Large Number). We assume ∇F = Eξ∼D[∇f(· ; ξ)] exists and the sample mean converges to ∇F in probability in ‖ · ‖∞,∞. Formally, let ξj ∼ D be i.i.d. sampled,
and denote δN, := Pr {∥∥∥∇F − 1N ∑Nj=1∇f(· ; ξj)∥∥∥∞,∞ > } . We assume
∀ > 0 : lim N→∞ δN, = 0.
Therefore, by definition, δN, 1 ≥ δN, 2 if 1 ≤ 2. Denote N,δ = inf{ : δN, ≤ δ}, and we can see that N,δ1 ≥ N,δ2 if δ1 ≤ δ2. Moreover, we have the following proposition. Proposition 6.1. With Assumption 2, we have ∀δ > 0 : limN→∞ N,δ = 0.
With the above assumptions, the following result shows that the proposed bucket median is robust to some extent if ratio of adversarial clients is α < 1/2. We provide similar results for dimension-wise median Med(·) in Theorem D.1 in the appendix. 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. We prove the robustness in a new way which holds for any α < 1/2.
Theorem 6.1 (Robustness). With Assumption 1&2, consider n1 i.i.d. samples {∇F̂i}n1i=1 (equation 1) and n2 adversarial vectors {vi ∈ Rd}n2i=1. Denote n := n1 + n2 and α := n2/n being the ratio of adversaries. Given the bucket range B > 0, the number of buckets b and the gradient descent step size µ. If α < 1/2 then for ∀ > N, 1−2α
2(1−α) with probability at least 1− (δN, )
n 2 (1−2α),
we have ∀{vi ∈ Rd}n2i=1 : ‖BucketMed({µ∇F̂i(w)} n1 i=1 ∪ {vi} n2 i=1;B, b)− µ∇F (w)‖∞ ≤ µ + B2b , for ∀w ∈ W satisfying µ‖∇F̂i(w)‖∞ ≤ B for all i ∈ [n1]. With the bucket median being robust, we can prove the convergence guarantee for smooth (possibly non-convex) function.
Note that as N →∞, both δN, → 0 and N,δ → 0. Theorem 6.2 (Robust Convergence). With Assumption 1&2, consider n1 normal clients with i.i.d. samples {∇F̂i}n1i=1 (equation 1) and n2 faulty clients that can send arbitrary vectors following the proposed protocol. Denote n := n1 +n2 and α := n2/n being the ratio of faulty clients. The bucket range adaption is defined by equation 2, where we assume Bt ≤ B for all iteration t for a constant B > 0, and p0 ≥ 1mβ ‖∇F̂i(w0)‖∞ for ∀i ∈ [n1]. If α < 1/2, for ∀ > N, 1−2α2(1−α) and ∀ ′ > 0, the proposed method with parameters µ = 1dβ , p1 ≥ 2µ + B 2b , η ≥ 1 + βµ and b ≥ dBβ 2 ′ can achieve
min 0≤t≤T
1 m ‖∇F (wt)‖22 ≤ 2βF (w0) T + 1 + ( + ′)2,
with probability at least 1− (δN, ) n 2 (1−2α).
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.

heading: 6.2 Overview of Security Analysis
text: We argue the security of our bucketed protocol by means of the standard real/ideal simulation paradigm in cryptography (defined formally in Appendix B). As stated in section 4.1, we assume a semi-honest adversary statically corrupting up to n− 1 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 theorem to the security of each epoch.
We provide a brief overview of the security argument. The use of secure 2-party computation between the servers allows them to compute the desired approximate median without revealing anything 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 two servers use secure 2-party protocols to compute the shares of a unit vector with 1 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 F`Comp,F`Equal, described 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.

heading: 7 Experimental Results
text: In this section, we evaluate our proposed bucketed median scheme on different models and datasets. First, we compare convergence behaviour over epoch of FL of bucketed median, pairwise comparison 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 machine with 112 cores. All parties involved in the FL process were separate processes on this machine,
with a bandwidth cap of 377 MBps to simulate a LAN network. We test on the following combinations of (model, dataset): (MLP, MNIST), (CNNMnist, Mnist), and (CNN, CIFAR-10). The MLP model has consits of 1 hidden layer with 200 units with ReLu activation for 199, 210 dimensions. We use the same CNNMnist as McMahan et al. (2017), which has 1,663,370 dimensions. The CNN model we use consists of two 5 × 5 convolution layers, the first followed by a 2 × 2 max pooling, and the second followed by three linear layers for a total of 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 = 8.

heading: 7.1 Convergence Results
text: 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 FL 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.
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 of clients n ∈ [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.

heading: 7.2 Client Failure Types
text: 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 to the servers. • Label Switching Failure: Clients compute gradients with switched labels on the training data. For example, label ∈ {0, ..., 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 a Gaussian distribution with mean of zero and standard deviation of 200.

heading: 7.3 Robustness Results
text: 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 test with three clients, one of which exhibits failures starting from the third epoch. Figures 4, 5, 6 shows results of our bucketed median method versus a median and mean method. In our implementation, the faulty client performs label flipping during the training process, while bitflip and Gaussian noise are manually computed on 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.

heading: 8 Conclusion
text: We presented a dual central-server FL system that is robust and private in the semi-honest setting. We propose a bucketing approximation technique in order to sacrifice accuracy for computational efficiency, which also leads to better scalability with the number of clients. The advantage our work provides are both privacy and robustness in distributed ML.
Ethics Statement Our work focuses on 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 it can be hard to determine if data from minority groups are outliers or adversarial.
Reproducibility Statement We have tried our best to provide training details to facilitate reproducing our results. We provide detailed results on how to train and evaluate our model. We will open-source our code once accepted.

heading: A Full Description of our algorithms
text: Here we provide full descriptions of both our median based and approximate bucketed median based FL algorithms (Algorithm 2, Algorithm 3), along with more details and correctness sketch for the 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 - {x1, x2 . . . xn}, we first compute all pairwise comparison results - bij = (xi > xj),∀i, j ∈ [n], i 6= j. This allows us to compute for each element xi, its position in the sorted list of {x1, x2 . . . xn}, by computing posi = ∑ k∈[n],k 6=i bik. Finally, we find element for which posi = dn/2e.
In our actual computation, we only compute bij ,∀i, j ∈ [n] s.t. j > i. Then bji 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 if this is 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 (Mohassel & Zhang, 2017; Mohassel & Rindal, 2018; Kumar et al., 2020), has made use of fixed point representation for the same, where real number r is mapped to integer ρr = br ∗ 2sc, where s is a parameter called the scaling factor. Hence, given a real number r, we map it to its fixed point representation ρr, which is then mapped to an integer ring like Z2` . In the following, we use wiInt to denote fixed point version of wi.
F2I`,s and I2F`,s are functions which are used for the mapping real numbers to (fixed-point) integers and vice versa respectively. In particular, F2I`,s : R → Z2` , is defined as F2I`,s(x) = bx ∗ 2sc. I2F`,s : Z2` → R is defined as I2F`,s(x) = x/2s (where x ∈ Z2` is first interpreted as a signed integer and then the division is performed).
Since we use ` = 64, s = 24 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.
A.2 Bucketed median based FL
In Algorithm 3 we describe in full our algorithm to compute the bucketed median.
Algorithm 2 One training epoch of exact median based FL Input: ∀i ∈ [n], ci holds dataset Di Parameters: Bitlength `, fixed point scale s ∀i ∈ [n], client ci does:
1. Receive fixed-point shares of global model 〈wIntg 〉j ∈ Z2` from server Sj ,∀j ∈ {0, 1}.
2. Compute wIntg = 〈wIntg 〉0 + 〈wIntg 〉1 and wg = I2F`,s(wIntg ). 3. Compute local model wi = SGD(wg, Di).
4. Convert back to fixed point as wInti = F2I`,s(wi).
5. Create fresh (2, 2) secret shares of wInti by choosing 〈wInti 〉0 at random from Zd2` and computing 〈wInti 〉1 = wInti − 〈wInti 〉0.
6. ∀j ∈ {0, 1}, send 〈wInti 〉j to server Sj . ∀j ∈ {0, 1}, server Sj performs the following:
1. ∀i ∈ [n], receive share 〈wInti 〉j from client ci. 2. ∀k ∈ [d], compute shares of median in dimension j across all the n clients as follows:
(a) ∀x ∈ [n], y ∈ [x + 1, n], compute 〈zkx,y〉j where zkx,y = (wIntx (k) > wInty (k)) by calling F`Comp with inputs 〈wIntx (k)〉j , 〈wInty (k)〉j . Set 〈zky,x〉j = j − 〈zkx,y〉j .
(b) ∀i ∈ [n], compute 〈posi〉j = ∑ x∈[n],x 6=i〈zki,x〉j .
(c) Set mid = (n+ 1)/2 if n is odd, else set mid = n/2. (d) ∀i ∈ [n], check if posi = mid by calling F`Equal with inputs 〈posi〉j , j ∗ mid and
receiving output 〈eqi〉j in return. (e) ∀i ∈ [n], send 〈eqi〉j to server S1−j and compute eqi = 〈eqi〉0 + 〈eqi〉1. (f) Find i ∈ [n] s.t. eqi(k) = 1 and set 〈wIntg ′ (k)〉j = 〈wInti (k)〉j .
3. Send 〈wIntg ′〉j to each client ci,∀i ∈ [n].
Algorithm 3 One training epoch of bucketed median based FL Input: ∀i ∈ [n], clients ci holds dataset Di Parameters: Number of buckets b, bitlength `, total epochs r, constant values p0, p1, pt = p1t , where t is the current epoch number. [h] ∀i ∈ [n], client ci does:
1. Receive global model wg and bucket range B from server S0. 2. Compute local model wi = SGD(wg, Di).
3. Bucketize wi to get ei ∈ {0, 1}d×b. Specifically, for each dimension k in [d], compute the kth row of bucketed model ei as follows:
• If wi(k) ≤ wg(k)− B2 , set ei(k) as [1, 0, . . . , 0]. • If wi(k) ≥ wg(k) + B2 , set ei(k) as [0, . . . , 0, 1]. • Else, let z = bwi(k)−(wg(k)−B/2)B/(b−2) c + 1. Set ei(k) as [0, . . . , 0, 1, 0, . . . , 0], where ei(k, z) is set to 1.
4. Create (2, 2) secret shares of ei by choosing 〈ei〉0 at random from Zd×b2` and computing 〈ei〉1 = ei − 〈ei〉0.
5. ∀j ∈ {0, 1}, send 〈ei〉j to server Sj . ∀j ∈ {0, 1}, server Sj performs the following:
1. ∀i ∈ [n], receive share 〈ei〉j from client ci. 2. Set 〈h〉j = ∑ i∈[n]〈ei〉j .
3. For each dimension k in [d], calculate the approximate median: (a) ∀y ∈ [2, b], set 〈h(k, y)〉j = ∑ z∈[y]〈h(k, z)〉j .
(b) Find the bucket that contains the median: i. Compute 〈m(k)〉j , where m(k) is of form [0, . . . , 1, . . . , 0], by calling F`Comp
with S0’s input being 〈h(k)〉0, [dn2 e] d×b and S1’s input being 〈h(k)〉1, [0]d×b. Set
〈m(k)〉j = [j]b − 〈m(k)〉j . ii. Sj shares 〈m〉j with S1−j .
iii. S0 computes m = 〈m(k)〉0 ⊕ 〈m(k)〉1.
iv. S0 selects the bucket y that contains the median as miny∈[0,b−1])[m(k, y) ≡ 1]. (c) S0 quantizes the approximate median value w′g(k) as follows:
• If y == 0, w′g(k) = wg(k)− B2 • If y == b− 1, w′g(k) = wg(k) + B2 • Else, w′g(k) = ( (wg(k)− B2 + (y − 1) ∗ ( B b−2 )) + (wg(k)− B 2 + y ∗ ( B b−2 )) ) /2.
4. S0 creates new bucket range B′ = 2‖w′g −wg‖1 + p1,t, where p1,t is predetermined. 5. S0 sends w′g , B
′ to client ci,∀i ∈ [n]. To initialize FL, server S0 performs the following:
1. Initialize wg as model with parameter values of 0. 2. Set B = p0. 3. S0 sends wg , B to each client ci,∀i ∈ [n].

heading: B Formal security Proof
text: 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, we assume a semi-honest adversary, statically (i.e. before starting the protocol) corrupting up to n−1 clients and one of the servers, and prove full security of the protocol using the simulation paradigm.
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 as 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 f is a (possibly randomized) mapping of n inputs to n outputs. A multiparty protocol with security parameter λ for computing a non-reactive functionality f is a protocol running in time polynomial in λ and satisfying the following correctness requirement: if parties P1, . . . , Pn with inputs (x1, . . . , xn) respectively all run an honest execution of the protocol, then the joint distribution of the outputs y1, . . . , yn of the parties is statistically close to f(x1, . . . , xn). A reactive functionality f is a sequence of non-reactive functionalities f = (f1, . . . , f`) computed in a stateful fashion in a series of phases. Let xji denote the input of Pi in phase j, and let s
j denote the state of the computation after phase j. Computation of f proceeds by setting s0 equal to the empty string and then computing (yj1, . . . , y j n, s j) ← fj(sj−1, xj1, . . . , xjn) for j ∈ [`], where y j i denotes the output of Pi at the end of phase j. A multi-party protocol computing f also runs in ` 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 {yj1, . . . , yjn}`j=1 of all the phases is 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.
Defining Security. The security of a protocol (with respect to a functionality f ) is defined by comparing the real-world execution of the protocol with an ideal-world evaluation of f 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 ideal-world. Next, we specify what each of these worlds mean.
The real execution In the real execution of the n-party protocol π for computing f is executed in the presence of an adversary A. The honest parties follow the instructions of π. The adversary A takes as input the security parameter k, the set I ⊂ [n] of corrupted parties, the inputs of the corrupted 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 ofA with a protocol π defines a random variable REALπ,A(z),I(λ, ~x) whose value is 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 REALπ,A(z),I denote the distribution ensemble {REALΠ,A(z),I(λ, ~x)}k∈N,〈~x,z〉∈{0,1}∗ .
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 x′i denote the value sent by Pi. Once again, for a semi-honest adversary we require x′i = xi for all i ∈ I .
• Trusted party sends output to the adversary: The trusted party computes f(x′1, . . . , x ′ n) = (y1, . . . , yn) and sends {yi}i∈I to the adversary.
• Adversary instructs trusted party to abort or continue: 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 Pi its output value yi. In the former case, the trusted party sends the special symbol ⊥ to each uncorrupted party.
• Outputs: Sim outputs an arbitrary function of its view, and the honest parties output the values obtained from the trusted party.
The interaction of Sim with the trusted party defines a random variable IDEALf,A(z)(λ, ~x) as above,and we let {IDEALf,A(z),I(λ, ~x)}k∈N,〈~x,z〉∈{0,1}∗ . Having defined the real and the ideal worlds, we now proceed to define our notion of security, where a semi-honest adversary is defined as an (interactive) Turing Machine whose specifications match those of the protocol.
Definition 1. Let k be the security parameter. Let f be an n-party randomized functionality, and Π be an n-party protocol for n ∈ N. We say that Π t-securely computes f in the presence of semihonest adversaries if for every semi-honest adversary A there exists a semi-honest adversary Sim such that for any I ⊂ [n] with |I| ≤ t the following quantity is negligible:
|Pr[REALΠ,A(z),I(λ, ~x) = 1]− Pr[IDEALf,A(z),I(λ, ~x) = 1]|
where ~x = {xi}i∈[n] ∈ {0, 1}∗ and z ∈ {0, 1}∗.
B.2 Simulation
Since our model is 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 F`Comp, and to this simulator it provides as input the bucket index of the median value.
C Protocols implementing F `Comp, F `Equal For exposition purposes, we described our protocols for median computation by writing them in a “hybrid” model, where parties have access to trusted functionalities F`Comp,F`Equal, computing secret sharing of comparison and equality of two inputs respectively (described in Figure 7 and Figure 8 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 as the metric for protocol complexity.
Notation Before going further, lets setup some notation. For a boolean variable z, we use notation 1{z} to indicate the indicator variable, which is 1 iff z is true. While 〈x〉0, 〈x〉1 denote (2, 2) additive secret shares of x over Z2` , we use notation 〈x〉B0 , 〈x〉B1 to denote the (2, 2) additive secret shares of x over Z2.
To implementF`Comp,F`Equal, we use and modify a bit the protocols proposed in CrypTFlow2 (Rathee et al., 2020). We describe the protocols for these in the following hybrids:
• F`Mill: This is described in Figure 9. It computes the solution to the millionaire’s problem over Z2` and provides boolean secret shares of the answer bit to the two parties.
• F`B2A: This is described in Figure 10. It takes in boolean shares of a bit from the two parties and provides shares of the same over Z2` .
• F`Mill,eq: This is described in Figure 11. It is similar to F`Mill, except instead of doing comparison, it checks equality of the two received values.
Each of the above hybrids can be implemented directly using protocols from CrypTFlow2 (Rathee et al., 2020). In more detail, while protocols for F`Mill,F`B2A are described directly in (Rathee et al., 2020), the protocol for F`Mill,eq can be obtained directly by a small tweak1 to the protocol for F`Mill. Since these protocols follow directly from (Rathee et al., 2020), we skip providing detailed descriptions and proofs of them here and refer the reader to CrypTFlow2 (Rathee et al., 2020) for the same.
Given the above three hybrids, we provide the protocols for implementing F`Comp,F`Equal in Algorithm 4, Algorithm 5 respectively. We then have the following theorems (where “securely” refers to simulation-based security according to Definition 1).
Theorem C.1. Π`Comp securely implements F`Comp in the F `−1 Mill ,F`B2A hybrid as long as the signed inputs of the two parties x, y (whose secret-shares they input into the protocol) satisfy |x| + |y| < 2`−1.
Theorem C.2. Π`Equal securely implements F`Equal in the F`Mill,eq,F`B2A hybrid.
Composing the corresponding implementation of F`Mill,F`B2A,F`Mill,eq (as described above), gives us secure protocols for F`Comp,F`Equal.
1(Rathee et al., 2020) provides protocols for F`Mill and F`B2A directly. The protocol for F`Mill works by breaking up the ` bits of 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), a protocol for F`Mill,eq can be easily obtained from the protocol for F`Mill. In addition, the public implementation of CrypTFlow2 (cry, 2021), contains functions which allow us to compute the same without tweaking anything underlying.
Algorithm 4 ` bit signed comparison protocol, Π`Comp. Input: ∀b ∈ {0, 1}, Pb holds 〈x〉b, 〈y〉b. Output: ∀b ∈ {0, 1}, Pb holds 〈1{x > y}〉b
1. ∀b ∈ {0, 1}, Pb computes 〈z〉b = 〈x〉b − 〈y〉b. 2. Compute boolean shares of msb(z) as follows:
(a) ∀b ∈ {0, 1}, Pb parses 〈z〉b as msbb||yb. (b) P0 and P1 invoke F`−1Mill with P0’s input 2`−1 − y0 and P1’s input y1. ∀b ∈ {0, 1}, Pb
learns 〈carry〉Bb . (c) ∀b ∈ {0, 1}, Pb computes 〈t〉Bb = msbb ⊕ 〈carry〉Bb .
3. P0 and P1 invoke F`B2A with inputs 〈t〉Bb to learn 〈t〉b.
Algorithm 5 ` bit equality protocol, Π`Equal. Input: ∀b ∈ {0, 1}, Pb holds 〈x〉b, 〈y〉b. Output: ∀b ∈ {0, 1}, Pb holds 〈1{x = y}〉b
1. ∀b ∈ {0, 1}, Pb computes 〈z〉b = 〈x〉b − 〈y〉b. 2. Check if z = 0 by doing the following:
(a) P0 and P1 invoke computes F`Mill,eq with P0’s input 〈z〉0, while P1’s input being (−〈z〉1) mod 2`. ∀b ∈ {0, 1}, Pb learns 〈eq〉Bb . (b) P0 and P1 invoke F`B2A with inputs 〈eq〉Bb to learn 〈eq〉b.
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 increased computations, such as generation of correlated randomness between parties. There have been many works on improving the efficiency of secure comparisons. (Damgård et al., 2006) provide a secure comparison protocol which uses O(` log `) secure multiplications, where ` = log p 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 O(`) secure multiplications.
Thus a 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.

heading: D Detailed Robustness and Convergence Analysis
text: Proposition D.1 (Proposition 6.1 Restated). With Assumption 2, we have
∀δ > 0 : lim N→∞ N,δ = 0.
Proof. Given a δ > 0, for ∀ > 0, by Assumption 2 there exists N such that ∀M : M > N we have δM, < δ/2. Therefore, M,δ ≤ M,δ/2 = inf{ ′ : δM, ′ ≤ δ/2} ≤ .
Theorem D.1. With Assumption 1&2, consider n1 i.i.d. samples {∇F̂i}n1i=1 (equation 1) and n2 adversarial vectors {vi ∈ Rd}n2i=1. Denote n := n1 + n2 and α := n2/n being the ratio of adversaries. If α < 1/2, then for ∀ > N, 1−2α
2(1−α) with probability at least 1 − (δN, )
n 2 (1−2α), we
have ∀{vi ∈ Rd}n2i=1 : ‖Med({∇F̂i(w)} n1 i=1 ∪ {vi} n2 i=1)−∇F (w)‖∞ ≤ , for ∀w ∈ W . Note that as N →∞, both δN, → 0 and N,δ → 0.
Proof. By definition of the median operation, we have
‖Med({∇F̂i(w)}n1i=1 ∪ {vi} n2 i=1)−∇F (w)‖∞
=‖Med({∇F̂i(w)−∇F (w)}n1i=1 ∪ {vi −∇F (w)} n2 i=1)‖∞. (3)
Invoking Lemma E.2, we have
(3) ≤ Med({‖∇F̂i(w)−∇F (w)‖∞}n1i=1 ∪ {‖vi −∇F (w)‖∞} n2 i=1)
= Med({‖∇F̂i(w)−∇F (w)‖∞}n1i=1 ∪ {ai} n2 i=1), (4)
where ai = ‖vi −∇F (w)‖∞ ∈ R. As we can see, (4) depends on the variance of ∇F̂i = 1N ∑N j=1∇f(· ; ξi,j), where ξi,j ∼ D are i.i.d. sampled. Denote
X̂i, := 1{‖∇F −∇F̂i‖∞,∞ ≤ }, where 1(·) is the indicator function. By Assumption 2, we can see that X̂i is a Bernoulli random variable with
Pr { X̂i, = 1 } = 1− δN, .
Therefore, X̂ := ∑n1 i=1 X̂i, forms a binomial distribution. By the Chernoff bound for binomial distribution, for k ∈ N and k ≤ n1(1− δN, ), we have
Pr(X̂ ≤ k) ≤ e −n1DKL
( k n1 ∥∥(1−δN, )) , (5)
where DKL is the Kullback–Leibler divergence, i.e., for q1, q2 ∈ (0, 1) DKL(q1‖q2) := q1 log ( q1 q2 ) + (1− q1) log ( 1− q1 1− q2 ) ≥ q1 log q1 + (1− q1) log(1− q1)− (1− q1) log(1− q2) ≥ (1− q1) log 11−q2 , where the first inequality is due to that q2 < 1 and the last inequality is because that q1 log q1 + (1− q1) log(1− q1) is the entropy which is non-negative. Combining the above inequality with equation 5, we have
Pr(X̂ ≤ k) ≤ e −n1(1− k n1 ) log 1 δN, = (δN, ) n1−k . (6)
Denoting event
E := {X̂ > n1 + n2
2 }, (7)
we can see that if E happens then by Lemma E.1 we have (4) ≤ . It left to show the probability of event E happens. Therefore, when n1+n22n1 ≤ (1− δN, ), we can apply equation 6 to have
Pr(E ) = 1− Pr(X̂ ≤ n1 + n2
2 ) ≥ 1− (δN, )
n 2 (1−2α). (8)
The condition of n1+n22n1 ≤ (1−δN, ) is equivalent to δN, ≤ 1−2α
2(1−α) , and it has a sufficient condition of > N, 1−2α
2(1−α) .
Theorem D.2 (Theorem 6.1 Restated). With Assumption 1&2, consider n1 i.i.d. samples {∇F̂i}n1i=1 (equation 1) and n2 adversarial vectors {vi ∈ Rd}n2i=1. Denote n := n1 +n2 and α := n2/n being the ratio of adversaries. Given the bucket range B > 0, the number of buckets b and the gradient descent step size µ. If α < 1/2 then for ∀ > N, 1−2α
2(1−α) with probability at least 1− (δN, )
n 2 (1−2α),
we have
∀{vi ∈ Rd}n2i=1 : ‖BucketMed({µ∇F̂i(w)} n1 i=1 ∪ {vi} n2 i=1;B, b)− µ∇F (w)‖∞ ≤ µ +
B 2b ,
for ∀w ∈ W satisfying µ‖∇F̂i(w)‖∞ ≤ B for all i ∈ [n].
Proof. First, by the definition of BucketMed(·), for any input vector vi ∈ Rd to the BucketMed(·), there exists a vector v′i ∈ Rd with ‖v′i‖∞ ≤ B such that BucketMed({µ∇F̂i(w)}n1i=1 ∪ {vi} n2 i=1;B, b) = BucketMed({µ∇F̂i(w)} n1 i=1 ∪ {v ′ i} n2 i=1;B, b).
Denote E as the event defined in equation 7 By equation 8 we can see that
Pr(E ) ≥ 1− (δN, ) n 2 (1−2α).
Given the event E , by Theorem D.1 we can see that ‖Med({µ∇F̂i(w)}n1i=1 ∪ {v ′ i} n2 i=1)− µ∇F (w)‖∞ ≤ µ , (9)
for ∀w ∈ W . Moreover, for ∀w ∈ W satisfying µ‖∇F̂i(w)‖∞ ≤ B for all i ∈ [n1], by Lemma E.3 we have
‖BucketMed({µ∇F̂i(w)}n1i=1 ∪ {v ′ i} n2 i=1;B, b)−Med({µ∇F̂i(w)} n1 i=1 ∪ {v ′ i} n2 i=1)‖∞ ≤
B 2b .
(10) Therefore, combining equation 9 and equation 10 gives the theorem.
Theorem D.3 (Theorem 6.2 Restated). With Assumption 1&2, consider n1 normal clients with i.i.d. samples {∇F̂i}n1i=1 (equation 1) and n2 faulty clients that can send arbitrary vectors following the proposed protocol. Denote n := n1 +n2 and α := n2/n being the ratio of faulty clients. The bucket range adaption is defined by equation 2, where we assume Bt ≤ B for all iteration t for a constant B > 0, and p0 ≥ 1mβ ‖∇F̂i(w0)‖∞ for ∀i ∈ [n1]. If α < 1/2, for ∀ > N, 1−2α2(1−α) and ∀ ′ > 0, the proposed method with parameters µ = 1dβ , p1 ≥ 2µ + B 2b , η ≥ 1 + βµ and b ≥ dBβ 2 ′ can achieve
min 0≤t≤T
1 m ‖∇F (wt)‖22 ≤ 2βF (w0) T + 1 + ( + ′)2,
with probability at least 1− (δN, ) n 2 (1−2α).
Proof. Denote E := {X̂ > n1+n22 } as the event defined in equation 7, where
X̂ := n1∑ i=1 1{‖∇F −∇F̂i‖∞,∞ ≤ }.
By equation 8 we have
Pr(E ) ≥ 1− (δN, ) n 2 (1−2α).
Now condition on the event E , and denote the set of clients I := {i ∈ [n1] : ‖∇F −∇F̂i‖∞,∞ ≤ }, (11)
and we can see that |I| > n1+n22 . Recall that the training procedure of Algorithm 3 is
wt = wt−1 − BucketMed({µ∇F̂i(wt−1)}n1i=1 ∪ {vi,t−1} n2 i=1;Bt−1, b),
where vi,t−1 are sent from the faulty clients i at iteration t. In the following, for notational ease we denote
gt−1 := BucketMed({µ∇F̂i(wt−1)}n1i=1 ∪ {vi,t−1} n2 i=1;Bt−1, b).
Moreover recall the bucket range Bt at iteration t is updated by Bt = η‖wt −wt−1‖1 + p1 = η‖gt−1‖1 + p1. Now, given any i ∈ I , we make the following claim.
Claim 1. Conditioned on event E , for any iteration step t ≥ 0 we have µ‖∇F̂i(wt)‖∞ ≤ Bt, (12)
‖µ∇F (wt)− gt‖∞ ≤ µ + B
2b . (13)
Proof of Claim 1. Note that equation 12 is true for t = 0 by assumption, and we prove the claim by induction. Assuming equation 12 holds for iteration t− 1, we prove equation 12 for iteration t, and prove equation 13 for iteration t− 1 by the way. We begin by
µ‖∇F̂i(wt)‖∞ =µ‖∇F̂i(wt)−∇F (wt) +∇F (wt)−∇F (wt−1) +∇F (wt−1)− gt−1/µ+ gt−1/µ‖∞ ≤µ‖∇F̂i(wt)−∇F (wt)‖∞︸ ︷︷ ︸
a1
+µ‖∇F (wt)−∇F (wt−1)‖∞︸ ︷︷ ︸ a2
+ ‖µ∇F (wt−1)− gt−1‖∞︸ ︷︷ ︸ a3 + ‖gt−1‖∞︸ ︷︷ ︸ a4 , (14)
where the last step is by triangle inequality. We will show that a1, a2, a4 have straight-forward upper bounds, respectively. For the a1, by equation 11 we have
a1 ≤ µ . By Assumption 1, we have
a2 ≤ µβ‖wt −wt−1‖1 = µβ‖gt−1‖1. For a4, by definition of the `1 norm and `∞ norm, we directly have
a4 ≤ ‖gt−1‖1. Note that a3 is exactly we want to prove for equation 13. For a3, we need to prove a slightly different version of Theorem 6.1, however, using similar techniques. Recall the definition of gt−1 and I ⊆ [n1], we have
a3 = ‖µ∇F (wt−1)− BucketMed({µ∇F̂i(wt−1)}n1i=1 ∪ {vi,t−1} n2 i=1;Bt−1, b)‖∞
= ‖µ∇F (wt−1)− BucketMed({µ∇F̂i(wt−1)}i∈I ∪ {µ∇F̂i(w)}i∈[n1]\I ∪ {vi,t−1} n2 i=1;Bt−1, b)‖∞.
Note that we have assumed that ‖µ∇F̂i(wt−1)‖ ≤ Bt−1. For {µ∇F̂i(w)}i∈[n1]\I ∪ {vi,t−1} n2 i=1, there exists n1 + n2 − |I| vectors v′i ∈ Rd satisfying ‖v′i‖∞ ≤ Bt−1 for i ∈ [n1 + n2 − |I|] such that
BucketMed({µ∇F̂i(wt−1)}n1i=1 ∪ {vi,t−1} n2 i=1;Bt−1, b)
= BucketMed({µ∇F̂i(wt−1)}i∈I ∪ {µ∇F̂i(w)}i∈[n1]\I ∪ {vi,t−1} n2 i=1;Bt−1, b) = BucketMed({µ∇F̂i(wt−1)}i∈I ∪ {v′i} n1+n2−|I| i=1 ;Bt−1, b) (15)
Therefore, denoting V := {µ∇F̂i(wt−1)}i∈I ∪ {v′i} n1+n2−|I| i=1 , by Lemma E.3, we have
‖BucketMed(V;Bt−1, b)−Med(V)‖∞ ≤ Bt−1 2b ≤ B 2b . (16)
Moreover, since |I| > n1+n22 and ‖∇F (wt−1)−∇F̂ (wt−1)‖∞ ≤ for any i ∈ I , by Lemma E.1 we have
‖Med(V)−∇F (wt−1)‖∞ = ‖Med({µ∇F̂i(wt−1)}i∈I ∪ {v′i} n1+n2−|I| i=1 )−∇F (wt−1)‖∞
≤ µ . (17) Combining equation 16 and equation 17 by triangle inequality, we have
‖BucketMed(V;Bt−1, b)− µ∇F (wt−1)‖∞ ≤ µ + B
2b .
Noting that V = {µ∇F̂i(wt−1)}i∈I ∪ {v′i} n1+n2−|I| i=1 , we apply equation 15 to have
‖BucketMed({µ∇F̂i(wt−1)}n1i=1 ∪ {vi,t−1} n2 i=1;Bt−1, b)− µ∇F (wt−1)‖∞ ≤ µ +
B 2b ,
which proves equation 13 for iteration t − 1, and equivalently a3 ≤ µ + B2b . Collecting our upper bounds for a1, a2, a3 and a4, we finally have
(14) = a1 + a2 + a3 + a4 ≤ µ + µβ‖gt−1‖1 + µ + B
2b + ‖gt−1‖1
= 2µ + B
2b + (1 + µβ)‖gt−1‖1.
Recall the condition that p1 ≥ 2µ + B2b and η ≥ 1 + βµ. We can see that (14) ≤ η‖gt−1‖1 + p1 = Bt. By induction, it concludes the claim.
Given the Claim 1, we continue the proof of Theorem 6.2. By the smoothness assumption (Assumption 1), and given that the parameter domainW is defined to be convex, it is known that F (wt+1)− F (wt)
≤ 〈∇F (wt),wt+1 −wt〉+ β
2 ‖wt+1 −wt‖21
= −〈∇F (wt), gt〉+ β
2 ‖gt‖21
≤ −〈∇F (wt), gt〉+ dβ
2 ‖gt‖22
= −〈∇F (wt), gt − µ∇F (wt) + µ∇F (wt)〉+ dβ
2 ‖gt − µ∇F (wt) + µ∇F (wt)‖22
= −µ‖∇F (wt)‖22 − 〈∇F (wt), gt − µ∇F (wt)〉
+ dβ
2 (µ2‖∇F (wt)‖22 + ‖gt − µ∇F (wt)‖22 + µ〈∇F (wt), gt − 2µ∇F (wt)〉).
(18) Substituting into µ = 1dβ , we can continue as
(18) = − 1 2dβ ‖∇F (wt)‖22 + dβ 2 ‖gt − µ∇F (wt)‖22
≤ − 1 2dβ ‖∇F (wt)‖22 + dβ 2 ‖gt − µ∇F (wt)‖2∞.
By Claim 1, we have
(18) ≤ − 1 2dβ ‖∇F (wt)‖22 + dβ 2
( µ + B
2b )2 = − 1
2dβ ‖∇F (wt)‖22 + ( √ 2β + √ β 2 dB 2b )2 .
Therefore, rearranging the inequality, and denote
ρ := 2β ( √ 2β + √ β 2 dB 2b )2 = ( + dBβ 2b )2 ,
we have 1
d ‖∇F (wt)‖22 ≤ 2β(F (wt)− F (wt+1)) + ρ.
Accordingly, for number of iterations T ≥ 1: 1
T + 1 T∑ t=0 1 d ‖∇F (wt)‖22 ≤ 2β T + 1 (F (w0)− F (wT+1)) + ρ
≤ 2βF (w0) T + 1 + ρ. (19)
Given any ′ > 0 and choosing b > dBβ2 ′ , equation 19 implies
min 0≤t≤T
1 d ‖∇F (wt)‖22 ≤ 2βF (w0) T + 1 + ( + ′)2.

heading: E Auxiliary Lemmas
text: Lemma E.1. Given a set of real number A = {xi ∈ R}ni=1 and an interval [a, b] ⊂ R, if |A ∩ [a, b]| > |A ∩ [a, b]c| then we have Med(A) ∈ [a, b].
Proof. Without loss of generality, we assume A is sorted, i.e, xi ≤ xi+1 for ∀i ∈ [n − 1]. By the definition of median, there are at least dn2 e numbers in A that are less or equal to Med(A). Therefore, if Med(A) < a, we can see that there are at least dn2 e numbers in A that are outside [a, b], which contradicts to the condition of |A ∩ [a, b]| > |A ∩ [a, b]c|. Hence, Med(A) ≥ a. Similarly, we can show Med(A) ≤ b. That being said, Med(A) ∈ [a, b].
Lemma E.2. Given n vectors {vi ∈ Rd}ni=1, we have ‖Med({vi}ni=1)‖∞ ≤ Med({‖vi‖∞}ni=1).
Proof. Denoting vi(k) as the kth dimension of vi ∈ Rd, we have ‖Med({vi}ni=1)‖∞ = max
k∈[m] |Med({vi(k)}ni=1)| ≤ max k∈[m] Med({|vi(k)|}ni=1). (20)
Denote k? ∈ arg maxk∈[m] Med({|vi(k)|}ni=1), and we have
(20) = Med({|vi(k?)|}ni=1) ≤ Med({max k∈[m] |vi(k)|}ni=1) = Med({‖vi‖∞}ni=1).
Lemma E.3. Given the bucket range B > 0, the number of buckets b, for any n vectors {vi}ni=1 in Rd, if ‖vi‖∞ ≤ B for all i ∈ [n], then we have
‖BucketMed({vi}ni=1;B, b)−Med({vi}ni=1)‖∞ ≤ B
2b .
Proof. Since ‖vi‖∞ ≤ B for all i ∈ [n] are within the bucket range, the BucketMed({vi}ni=1;B, b) is the same as Med({v′i}ni=1) for some v′i ∈ Rd satisfying
‖v′i − vi‖∞ ≤ B
2b .
Denote
wli = vi − B
2b , wri = vi +
B 2b ,
where the ±B2b is done on every dimension of v. We can see that w l i ≤ v′i ≤ wri , where the ≤ is also dimension-wise. Noting that
Med({vi}ni=1)− B
2b = Med({wli}ni=1) ≤ Med({v′i}ni=1) ≤ Med({wri }ni=1) = Med({vi}ni=1) +
B 2b ,
we can conclude that
‖Med({v′i}ni=1)−Med({vi}ni=1)‖ ≤ B
2b .
Replacing the Med({v′i}ni=1) by BucketMed({vi}ni=1;B, b) gives the lemma.

heading: F Computation Breakdown and Parameter Sensitivity
text: 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 of magnitude of these parameter values.
In Table 1, we detail the time in seconds each part of the FL process takes for both the pairwise comparison based median method, and our proposed bucketed median method. The bucketed method had the additional overhead on client and server side of converting to and from a 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 a factor of 17.5, and the bucketed median FL system increases by a factor of 5.5.
In Figure 12, we show the scalability of our protocol when the number of clients range from 10 to 160 in increments of 30. 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: 1. adding client shares to compute a 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 on 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 our protocol, we determine bucket range as B = {p0, ‖w′g − wg‖1 + p1,t}, where p0 is chosen during the initial epoch, and ‖w′g −wg‖1 + p1,t is chosen in subsequent epochs. In our convergence analysis, we use p1 and prove convergence for this choice. In our experiments, we use pt = p1t , where t is the current epoch count. Both choices empirically result in decreasing training loss per epoch, albeit at slightly different rates. We note that in our implementation, we set both p0 and p1 as
equivalent values, and use the CNNMnist model. For parameter values less than 1, we see that our bucketed mechanism results in a similar rate of training loss convergence. For each model, one can solve for specific p0, p1 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.

Review summaries:
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.

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. 

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.