Byzantine-Resilient Secure Federated Learning

I Introduction

Federated learning is a distributed training framework that has received significant interest in the recent years, by allowing machine learning models to be trained over the vast amount of data collected by mobile devices . In this framework, training is coordinated by a central server who maintains a global model, which is updated by the mobile users through an iterative process. At each iteration, the server sends the current version of the global model to the mobile devices, who update it using their local data and create a local update. The server then aggregates the local updates of the users and updates the global model for the next iteration .

Security and privacy considerations of distributed learning are mainly focused around two seemingly separate directions: 1) ensuring robustness of the global model against adversarial manipulations and 2) protecting the privacy of individual users. The first direction aims at ensuring that the trained model is robust against Byzantine faults that may occur in the training data or during protocol execution. These faults may result either from an adversarial user who can manipulate the training data or the information exchanged during the protocol, or due to device malfunctioning. Notably, it has been shown that even a single Byzantine fault can significantly alter the trained model . The primary approach for defending against Byzantine faults is by comparing the local updates received from different users and removing the outliers at the server . Doing so, however, requires the server to learn the true values of the local updates of each individual user. The second direction aims at protecting the privacy of the individual users, by keeping each local update private from the server and the other users participating in the protocol . This is achieved through what is known as a secure aggregation protocol . In this protocol, each user masks its local update through additive secret sharing using private and pairwise random keys before sending it to the server. Once the masked models are aggregated at the server, the additional randomness cancels out and the server learns the aggregate of all user models. At the end of the protocol, the server learns no information about the individual models beyond the aggregated model, as they are masked by the random keys unknown to the server. In contrast, conventional distributed training frameworks that perform gradient aggregation and model updates using the true values of the gradients may reveal extensive information about the local datasets of the users, as shown in .

This presents a major challenge in developing a Byzantine-resilient, and at the same time, privacy-preserving federated learning framework. On the one hand, robustness against Byzantine faults requires the server to obtain the individual model updates in the clear, to be able to compare the updates from different users with each other and remove the outliers. On the other hand, protecting user privacy requires each individual model to be masked with random keys, as a result, the server only observes the masked model, which appears as a uniformly random vector that could correspond to any point in the parameter space. Our goal is to reconcile these two critical directions. In particular, we want to address the following question, “How can one make federated learning protocols robust against Byzantine adversaries while preserving the privacy of individual users?”.

In this paper, we propose the first single-server Byzantine-resilient secure aggregation framework, BREA, towards addressing this problem. Our framework is built on the following main principles. Given a network of $N$ mobile users with up to $A$ adversaries, each user initially secret shares its local update with the other users, through a verifiable secret sharing protocol . However, doing so requires the local updates to be masked by uniformly random vectors in a finite field , whereas the model updates during training are performed in the domain of real numbers. In order to handle this problem, BREA utilizes stochastic quantization to transfer the local updates from the real domain into a finite field.

Verifiable secret sharing allows the users to perform consistency checks to validate the secret shares and ensure that every user follows the protocol. However, a malicious user can still manipulate the global model by modifying its local update or private dataset. BREA handles such attacks through a robust gradient descent approach, enabled by secure computations over the secret shares of the local updates. To do so, each user locally computes the pairwise distances between the secret shares of the local updates belonging to other users, and sends the computation results to the server. Since these computations are carried out using the secret shares, users do not learn the true values of the local updates belonging to other users.

In the final phase, the server collects the computation results from a sufficient number of users, recovers the pairwise distances between the local updates, and performs user selection for model aggregation. The user selection protocol is based on a distance-based outlier removal mechanism , to remove the effect of potential adversaries and to ensure that the selected models are sufficiently close to an unbiased gradient estimator. After the user selection phase, the secret shares of the models belonging to the selected users are aggregated locally by the mobile users. The server then gathers the secure computation results from the users, reconstructs the true value of the aggregate of the selected user models, and updates the global model. Our framework guarantees the privacy of individual user models, in particular, the server learns no information about the local updates, beyond their aggregated value and the pairwise distances.

In our theoretical analysis, we demonstrate provable convergence guarantees for the model and robustness guarantees against Byzantine adversaries. We then identify the theoretical performance limits in terms of the fundamental trade-offs between the network size, user dropouts, number of adversaries, and privacy protection. Our results demonstrate that, in a network with $N$ mobile users, BREA can theoretically guarantee: i) robustness of the trained model against up to $A$ Byzantine adversaries, ii) tolerance against up to $D$ user dropouts, iii) privacy of each local update, against the server and up to $T$ colluding users, as long as $N\geq 2A+1+\max\{m+2,D+2T\}$, where $m$ is the number of selected models for aggregation.

We then numerically evaluate the performance of BREA and compare it to the conventional federated learning protocol, the federated averaging scheme of . To do so, we implement BREA in a distributed network of $N=40$ users with up to $A=12$ Byzantine users who can send arbitrary vectors to the server or to the honest users. We demonstrate that BREA guarantees convergence against Byzantine users and its convergence rate is comparable to the convergence rate of federated averaging. BREA also has comparable test accuracy to the federated averaging scheme while BREA entails quantization loss to preserve the privacy of individual users.

Finally, while BREA provides the first distributed training framework that is both Byzantine-resilient and privacy-preserving, there are several directions for further improvements. The first is that our theoretical analysis for convergence needs the assumption of an independent and identically distributed (i.i.d.) data distribution over the users. Second, we rely on distance-based outlier removal mechanisms, which make it difficult to distinguish whether a large distance between local updates is due to a non-i.i.d. data distribution or a Byzantine attack. Providing theoretical performance guarantees for non-i.i.d. data in the Byzantine-robust training setups is an important and interesting direction for future research. However, one should also note that even without the privacy requirements, this is still an open problem and an active area of research in the literature . Other open questions include whether it is possible to break the quadratic communication and computation complexity of Byzantine-resilient secure aggregation in the current work, and investigating the fundamental performance limits of Byzantine-resilient distributed learning with multiple local updates.

II Related Work

In the non-Byzantine federated learning setting, secure aggregation is performed through a procedure known as additive masking , . In this setup, users first agree on pairwise secret keys using a Diffie-Hellman type key exchange protocol , and send a masked version of their local update to the server, where the masking is done using pairwise and private secret keys. When the masked models are aggregated at the server, additive masks cancel out, allowing the server to learn the aggregate of the local updates. This process works well if no users drop during the execution of the protocol. In wireless environments, however, users may drop from the protocol anytime due to the variations in channel conditions. Such user dropouts are handled by letting each user secret share their private and pairwise keys through Shamir’s secret sharing . The server can remove the additive masks by collecting the secret shares from the surviving users. This approach leads to a quadratic communication overhead in the number of users. More recent approaches have focused on reducing the communication overhead, by training in a smaller parameter space , autotuning the parameters, or by utilizing coding techniques .

Another line of work has focused on differentially-private federated learning approaches , to protect the privacy of personally-identifiable information against inference attacks. Although our focus is not on differential-privacy, our approach may in principle be combined with differential privacy techniques , which is an interesting future direction. Another important direction in federated learning is the study of fairness and how to avoid biasing the model towards specific users . The convergence properties of federated learning models are investigated in .

Distributed training protocols have been extensively studied in the Byzantine setting using clear (unmasked) model updates . The main defense mechanism to protect the trained model against Byzantine users is by comparing the model updates received from different users, and removing the outliers. Doing so ensures that the selected model updates are close to each other, as long as the network has a sufficiently large number of honest users. A related line of work is model poisoning attacks, which are studied in .

In concurrent work, a Byzantine-robust secure gradient descent algorithm has been proposed for a two-server model in , however, unlike federated learning (which is based on a single-server architecture) , this work requires two honest (non-colluding) servers who both interact with the mobile users and communicate with each other to carry out a secure two-party protocol, but do not share any sensitive information with each other in an attempt to breach user privacy. In contrast, our goal is to develop a single-server Byzantine-resilient secure training framework, to facilitate robust and privacy-preserving training architectures for federated learning. Compared to the two-server models, single server models carry the additional challenge where all information has to be collected at a single server, while still being able to keep the individual models of the users private.

The remainder of the paper is organized as follows. In Section III, we provide background on federated learning. Section IV presents our system model along with the key parameters used to evaluate the system performance. Section V introduces our framework and the details of the specific components. Section VI presents our theoretical results, whereas our numerical evaluations are provided in Section VII, to demonstrate the convergence and Byzantine-resilience. The paper is concluded in Section VIII. The following notation is used throughout the paper. We represent a scalar variable with $x$, whereas $\mathbf{x}$ represents a vector. A set is denoted by $\mathcal{X}$, whereas $[N]$ refers to the set $\{1,\ldots,N\}$.

III Background

The global model is updated locally by mobile users on sensitive private datasets, by letting

where $N$ is the total number of mobile users, $C_{i}(\mathbf{w})$ denotes the local objective function of user $i$, $B_{i}$ is the number of data points in user $i$’s private dataset $\mathcal{D}_{i}$, and $B:=\sum_{i=1}^{N}B_{i}$. For simplicity, we assume that users have equal-sized datasets, i.e., $B_{i}=\frac{B}{N}$ for all $i\in[N]$.

Training is performed through an iterative process where mobile users interact through the central server to update the global model. At each iteration, the server shares the current state of the global model, denoted by $\mathbf{w}^{(t)}$, with the mobile users. Each user $i$ creates a local update,

where $g$ is an estimate of the gradient $\nabla C(\mathbf{w}^{(t)})$ of the cost function $C$ and $\xi^{(t)}_{i}$ is a random variable representing the random sample (or a mini-batch of samples) drawn from $\mathcal{D}_{i}$. We assume that the private datasets $\{\mathcal{D}_{i}\}_{i\in[N]}$ have the same distribution and $\{\xi^{(t)}_{i}\}_{i\in[N]}$ are i.i.d. $\xi^{(t)}_{i}\sim\xi$ where $\xi$ is a uniform random variable such that each $\mathbf{w}_{i}^{(t)}$ is an unbiased estimator of the true gradient $\nabla C(\mathbf{w}^{(t)})$, i.e.,

The local updates are aggregated at the server in a privacy-preserving protocol, such that the server only learns the aggregate of a large fraction of the local updates, ideally the sum of all user models $\sum_{i\in[N]}\mathbf{w}_{i}^{(t)}$, but no further information is revealed about the individual models beyond their aggregated value. Using the aggregate of the local updates, the server updates the global model for the next iteration,

where $\gamma^{(t)}$ is the learning rate, and sends the updated model $\mathbf{w}^{(t+1)}$ to the users. This process is illustrated in Figure 1.

Conventional secure aggregation protocols require each user to mask its local update using random keys before aggregation . This is typically done by creating pairwise keys between the users through a key exchange protocol . Using the pairwise keys, each pair of users $i,j\in[N]$ agree on a pairwise random seed $a_{ij}^{(t)}$. User $i$ also creates a private random seed $b_{i}^{(t)}$, which protects the privacy of the local update in case the user is delayed instead of being dropped, in which case the pairwise keys are not sufficient for privacy, as shown in . User $i\in[N]$ then sends a masked version of its local update $\mathbf{w}_{i}^{(t)}$, given by

to the server, where PRG is a pseudo random generator. User $i$ then secret shares $b_{i}^{(t)}$ and $\{a_{ij}^{(t)}\}_{j\in[N]}$ with the other users, via Shamir’s secret sharing . For computing the aggregate of the user models, the server collects either the secret shares of the pairwise seeds belonging to a dropped user, or the shares of the private seed belonging to a surviving user (but not both). The server then recovers the private seeds of the surviving users and the pairwise seeds of the dropped users, and removes them from the aggregate of the masked models,

and obtains the aggregate of the local updates, where $\mathcal{U}\subseteq[N]$ and $\mathcal{D}\subseteq[N]$ denote the set of surviving and dropped users, respectively. In (III), $\sum_{i\in\mathcal{U}}\text{PRG}(b_{i}^{(t)})$ corresponds to the reconstructed private seeds belonging to the surviving users. On the other hand, \sum_{i\in\mathcal{D}}\Big{(}\sum_{j:i<j}\text{PRG}(a_{ij}^{(t)})-\sum_{j:i>j}\text{PRG}(a_{ji}^{(t)})\Big{)} corresponds to the reconstructed pairwise seeds belonging to the dropped users. Both of these terms are reconstructed by the server to remove the random masks in the aggregate of the masked versions of the surviving users, $\sum_{i\in\mathcal{U}}\mathbf{y}_{i}^{(t)}$. At the end, all of the random masks cancel out, and the server recovers the summation of the original models belonging to all of the surviving users, i.e., $\sum_{i\in\mathcal{U}}\mathbf{w}_{i}^{(t)}$.

IV Problem Formulation

In this section, we describe the Byzantine-resilient secure aggregation problem, by extending the conventional secure aggregation scenario from Section III to the case when some users, known as Byzantine adversaries, can manipulate the trained model by modifying their local datasets or by sharing false information during the protocol.

We consider a distributed network with $N$ mobile users and a single server. User $i\in[N]$ holds a local updateFor notational clarity, throughout Sections IV and V, we omit the iteration number $(t)$ from $\mathbf{w}_{i}^{(t)}$. $\mathbf{w}_{i}$ of dimension $d$. The goal is to aggregate the local updates at the server, while protecting the privacy of individual users. However, unlike the non-Byzantine setting of Section III, the aggregation operation in the Byzantine setting should be robust against potentially malicious users. To this end, we represent the aggregation operation by a function,

where $\mathcal{S}$ is a set of users selected by the server for aggregation. The role of $\mathcal{S}$ is to remove the effect of potentially Byzantine adversaries on the trained model, by removing the outliers. Similar to prior works on federated learning, our focus is on computationally-bounded parties, whose strategies can be described by a probabilistic polynomial time algorithm .

We evaluate the performance of a Byzantine-resilient secure aggregation protocol according to the following key parameters:

Robustness against Byzantine users: We assume that up to $A$ users are Byzantine (malicious), who manipulate the protocol by modifying their local datasets or by sharing false information during protocol execution. The protocol should be robust against such Byzantine adversaries.

Privacy of local updates: The aggregation protocol should protect the privacy of any individual user from the server and any collusions between up to $T$ users. Specifically, the local update of any user should not be revealed to the server or the remaining users, even if up to $T$ users cooperate with each other by sharing information.Collusions that may occur between the server and the users are beyond the scope of our paper.

Tolerance to user dropouts: Due to potentially poor wireless channel conditions, we assume that up to $D$ users may get dropped or delayed at any time during protocol execution. The protocol should be able to tolerate such dropouts, i.e., the privacy and convergence guarantees should hold even if up to $D$ users drop or get delayed.

In this paper, we present a single-server Byzantine-resilient secure aggregation framework (BREA) for the computation of (8). BREA consists of the following key components:

Verifiable secret sharing of the user models: Users then secret share their quantized models using a verifiable secret sharing protocol. This ensures that the secret shares created by the mobile users are valid, i.e., Byzantine users cannot cheat by sending invalid secret shares.

Secure distance computation: In this phase, users compute the pairwise distances between the secret shares of the local updates, and send the results to the server. Since this computation is performed using the secret shares of the models instead of their true values, users do not learn any information about the actual model parameters.

User selection at the server: Upon receiving the computation results from the users, the server recovers the pairwise distances between the local updates and selects the set of users whose models will be included in the aggregation, by removing the outliers. This ensures that the aggregated model is robust against potential manipulations from Byzantine users. The server then announces the list of the selected users.

Secure model aggregation: In the final phase, each user locally aggregates the secret shares of the models selected by the server, and sends the computation result to the server. Using the computation results, the server recovers the aggregate of the models of the selected users, and updates the model.

In the following, we describe the details of each phase.

V The BREA Framework

In this section, we present the details of the BREA framework for Byzantine-resilient secure federated learning.

Quantization requires a challenging task as it should be performed in a way to ensure the convergence of the model. Moreover, the quantization function should allow the representation of negative integers in the finite field, and facilitate computations to be performed in the quantized domain. Therefore, we cannot utilize well-known gradient quantization techniques such as in , which represents the sign of a negative number separately from its magnitude. BREA addresses this challenge with a simple stochastic quantization strategy as follows. For any integer $q\geq 1$, we define a stochastic rounding function:

V-B Verifiable Secret Sharing of the User Models

BREA protects the privacy of individual user models through verifiable secret sharing. This is to ensure that the individual user models are kept private while preventing the Byzantine users from breaking the integrity of the protocol by sending invalid secret shares to the other users.

To do so, user $i\in[N]$ secret shares its quantized model $\overline{\mathbf{w}}_{i}$ with the other users through a non-interactive verifiable secret sharing protocol . Our framework leverages Feldman’s verifiable secret sharing protocol from , which combines Shamir’s secret sharing with homomorphic encryption. In this setup, each party creates the secret shares, then broadcasts commitments to the coefficients of the polynomial they use for Shamir’s secret sharing, so that other parties can verify that the secret shares are constructed correctly. To verify the secret shares from the given commitments, the protocol leverages the homomorphic property of exponentiation, i.e., $exp(a+b)=exp(a)exp(b)$, whereas the privacy protection is based on the assumption that computation of the discrete logarithm in the finite field is intractable.

To make these shares verifiable, user $i$ also broadcasts commitments to the coefficients of $f_{i}$, given by

Upon receiving the commitments in (14), each user $j\in[N]$ can verify the secret share $\mathbf{s}_{ij}=f_{i}(\theta_{j})$ by checking

where all arithmetic is taken modulo $\lambda$. This commitment scheme ensures that the secret shares are created correctly from the polynomial in (12), hence they are valid. On the other hand, as we assume the intractability of computing the discrete logarithm , the server or the users cannot compute the discrete logarithm $\log_{\psi}(\mathbf{c}_{it})$ and reveal the quantized model $\overline{\mathbf{w}}_{i}$ from $\mathbf{c}_{i0}$ in (14).

V-C Secure Distance Computation

Verifiable secret sharing of the model parameters, as described in Section V-B, ensures that the users follow the protocol correctly by creating valid secret shares. However, malicious users can still try to manipulate the trained model by modifying their local updates instead. In this case, the secret shares will be created correctly but according to a false model. In order to ensure that the trained model is robust against such adversarial manipulations, BREA leverages a distance-based outlier detection mechanism, such as in . The main principle behind these mechanisms is to compute the pairwise distances between the local updates and select a set of models that are sufficiently close to each other. On the other hand, the outlier detection mechanism in BREA has to protect the privacy of local updates, and performing the distance computations on the true values of the model parameters would breach the privacy of individual users.

We address this by a privacy-preserving distance computation approach, in which the pairwise distances are computed locally by each user, using the secret shares of the model parameters received from the other users. In particular, upon receiving the secret shares of the model parameters as described in Section V-B, user $i$ computes the pairwise distances,

between each pair of users $j,k\in[N]$, and sends the result to the server. Since the computations in (16) are performed over the secret shares, user $i$ learns no information about the true values of the model parameters $\overline{\mathbf{w}}_{j}$ and $\overline{\mathbf{w}}_{k}$ of users $j$ and $k$, respectively. Finally, we note that the computation results from (16) are scalar values.

V-D User Selection at the Server

Upon receiving the computation results in (16) from a sufficient number of users, the server reconstructs the true values of the pairwise distances. During this phase, Byzantine users may send incorrect computation results to the server, hence the reconstruction process should be able to correct the potential errors that may occur in the computation results due to malicious users. Our decoding procedure is based on the decoding of Reed-Solomon codes.

for $\theta\in\{\theta_{i}\}_{i\in[N]}$ and $j,k\in[N]$. Accordingly, $h_{jk}$ can be viewed as the encoding polynomial of a Reed-Solomon code with degree at most $2{T}$, such that the missing computations due to the dropped users correspond to the erasures in the code, and manipulated computations from Byzantine users refer to the errors in the code. Therefore, the decoding process of the server corresponds to decoding an $[N,2{T}+1,N-2{T}]_{p}$ Reed-Solomon code with at most $D$ erasures and at most $A$ errors. By utilizing well-known Reed-Solomon decoding algorithms , the server can recover the polynomial $h_{jk}$ and obtain the true value of the pairwise distances by using the relation $h_{jk}(0)=\lVert f_{j}(0)-f_{k}(0)\rVert^{2}=\lVert\overline{\mathbf{w}}_{j}-\overline{\mathbf{w}}_{k}\rVert^{2}$. At the end, the server learns the pairwise distances

between the models of users $j,k\in[N]$. Then the server converts (18) from the finite field to the real domain as follows,

We assume the field size $p$ is large enough to ensure the correct recovery of the pairwise distances,

where $Q_{q}$ is the stochastic rounding function defined in (9) and (21) holds if

By utilizing the pairwise distances in (22), the server carries out a distance-based outlier removal algorithm to select the set of users to include in the final model aggregation. The outlier removal procedure of BREA follows the multi-Krum algorithm from . The main difference is that our framework considers the multi-Krum algorithm in a quantized stochastic gradient setting, as BREA utilizes quantized gradients instead of the true gradients, in order to enable privacy-preserving computations on the secret shares. We present the theoretical convergence guarantees of this quantized multi-Krum algorithm in Section VI, and numerically demonstrate its convergence behaviour in our experiments in Section VII.

In this setup, the server selects $m$ users through the following iterative process. At each iteration $k\in[m]$, the server selects one user, denoted by $i^{(k)}$, by finding

where $\mathcal{S}^{(k)}$ denotes the index set of the users selected in up to $k$ iterations and $s^{(k)}(j)$ is a score function assigned to user $j$ at iteration $k$. The score function of user $j$ is defined as

where $\mathcal{I}^{(k-1)}_{j}\subseteq[N]\setminus\mathcal{S}^{(k-1)}$ denotes the set of $(N-k+1)-A-2$ users whose models are closest to the model of user $j$. After selecting $i^{(k)}$, the server updates the selected index set as $\mathcal{S}^{(k)}=\{\mathcal{S}^{(k-1)},i^{(k)}\}$ where $\mathcal{S}^{(0)}=\emptyset$. After $m$ iterations, the server obtains the index set $\mathcal{S}=\mathcal{S}^{(m)}$.

V-E Secure Model Aggregation

The final phase of BREA is to securely aggregate the local updates of the selected users, without revealing the individual models to the server. To do so, the server initially announces the list of selected users via broadcasting. We denote the set of selected users by $\mathcal{S}$. Then, each user locally aggregates the secret shares belonging to the selected users,

and sends the result to the server. Upon receiving the computation results from a sufficient number of users, the server can decode the aggregate of the models $\sum_{j\in\mathcal{S}}\overline{\mathbf{w}}_{j}$ through the decoding of Reed-Solomon codes.

One can then observe that $h$ is the encoding polynomial of a Reed-Solomon code with degree at most $T$, the missing computations due to the dropped users correspond to the erasures in the code, and manipulated computations from Byzantine users correspond to the errors in the code. Therefore, the decoding process of the server corresponds to decoding an $[N,{T}+1,N-{T}]_{p}$ Reed-Solomon code with at most $D$ erasures and at most $A$ errors. Hence, by using a Reed-Solomon decoding algorithm, the server can recover the polynomial $h$ and obtain the true value of the aggregate of the selected user models by using the relation $h(0)=\sum_{j\in\mathcal{S}}f_{j}(0)=\sum_{j\in\mathcal{S}}\overline{\mathbf{w}}_{j}$. We note that the total number of users selected by the server for aggregation, i.e., $|\mathcal{S}|=m$, should be sufficiently large, which can be agreed offline between the users and the server. Then, if the set announced by the server is too small (e.g., consisting of a single user), the honest users may opt to not send the computation results.

Upon learning the aggregate of the user models, the server updates the global model for the next iteration as follows,

where $\phi^{-1}$ is the demapping function defined in (20) and $q$ is the integer parameter in (9). We assume that the field size $p$ is large enough to avoid wrap-around in $\sum_{j\in\mathcal{S}}\overline{\mathbf{w}}_{j}^{(t)}$ such that

where (29) follows from (10). Finally, it follows from (30) that the update equation in (28) is equivalent to

where $Q_{q}$ is the stochastic rounding function defined in (9).

Having all above steps, the overall BREA framework can now be presented in Algorithm 1.

VI Theoretical Analysis

In this section, we analyze the fundamental performance limits of BREA. The global model update equation of BREA can be expressed as follows,

where $f$ is the aggregation operation from (8) and represents the user selection and model aggregation procedures from Sections V-D and V-E, respectively, while $Q_{q}$ is the stochastic rounding function defined in (9).

where $\sigma^{\prime}(\mathbf{w})=\sqrt{\frac{1}{4q^{2}}+\sigma^{2}(\mathbf{w})}$.

(Unbiasedness) Given $Q_{q}$ in (9) and any random variable $x$, it follows that,

from which we obtain the unbiasedness condition in (34),

(Bounded variance) Next, we observe that,

from which one can obtain the bounded variance condition in (35) as follows,

where (39) follows from the triangle inequality and (40) follows form (38). ∎

As discussed in Section IV, Byzantine users can manipulate the training protocol via two means, either by modifying their local update (directly or by modifying the local dataset), or by sharing false information during protocol execution. In this section, we demonstrate how BREA provides robustness in both cases. We first focus on the former case and study the resilience of the global model, i.e., conditions under which the trained model remains close to the true model, even if some users modify their local updates adversarially. The second case, i.e., robustness of the protocol when some users exchange false information during the protocol execution, will be considered in Theorem 1.

In order to evaluate the resilience of the global model against Byzantine adversaries, we adopt the notion of $(\alpha,A)$-Byzantine resilience from .

Lemma 2 below states that if the standard deviation caused by random sample selection and quantization is smaller than the norm of the true gradient, and $2A+2<N-m$, then the aggregation function $f$ from (32) is $(\alpha,A)$-Byzantine resilient where $\alpha$ depends on the ratio of the standard deviation over the norm of the gradient .

Assume that $2A+2<N-m$ and $\eta(N,A)\sqrt{d}\sigma^{\prime}<\lVert\nabla C(\mathbf{w})\rVert$ where

We now state our main result for the theoretical performance guarantees of BREA.

(Robustness against Byzantine users) The protocol executes correctly against up to $A$ Byzantine users and the trained model is $(\alpha,A)$-Byzantine resilient.

(Convergence) The sequence of the gradients $\nabla C(\mathbf{w}^{(t)})$ converges almost surely to zero,

(Privacy) The server or any group of up to $T$ users cannot compute an unknown local update. For any set of users $\mathcal{T}\subset[N]$ of size at most $T$,

for all $i\in[N]\setminus\mathcal{T}$ where $\text{view}_{\mathcal{T}}$ denotes the messages that the members of $\mathcal{T}$ receive.

for any $N\geq 2A+1+\max\{m+2,D+2T\}$, where $m$ is the number of selected models for aggregation.

The two conditions $\sum_{t=1}^{\infty}\gamma^{(t)}=\infty$ and $\sum_{t=1}^{\infty}({\gamma^{(t)}})^{2}<\infty$ are instrumental in the convergence of stochastic gradient descent algorithms . Condition $\sum_{t=1}^{\infty}({\gamma^{(t)}})^{2}<\infty$ states that the learning rates decrease fast enough, whereas condition $\sum_{t=1}^{\infty}\gamma^{(t)}=\infty$ bounds the rate of their decrease, to ensure that the learning rates do not decrease too fast.

We consider a general (possibly non-convex) objective function $C$. In such scenarios, proving the convergence of the model directly is challenging, and various approaches have been proposed instead. Our approach follows and , where we prove the convergence of the gradient to a flat region instead. We note, however, that such a region may refer to any stationary point, including the local minima as well as saddle and extremal points.

(Robustness against Byzantine users) The $(\alpha,A)$-Byzantine resilience of the trained model follows from Lemma 2. We next provide sufficient conditions for BREA to correctly evaluate the update function (32), in the presence of $A$ Byzantine users. Byzantine users may send any arbitrary random vector to the server or other users in every step of the protocol in Section V. In particular, Byzantine users can create and send incorrect computations in three attack scenarios: i) sending invalid secret shares $\mathbf{s}_{ij}$ in (13), ii) sending incorrect secure distance computations $d_{jk}^{(i)}$ in (16), and iii) sending incorrect aggregate of the secret shares $\mathbf{s}_{i}$ in (26).

The first attack scenario occurs when the secret shares $\mathbf{s}_{ij}$ in (13) do not refer to the same polynomial from (12). BREA utilizes verifiable secret sharing to prevent such attempts. The correctness (validity) of the secret shares can be verified by testing (15), whenever the majority of the surviving users are honest, i.e., $N>2A+D$ .

The second attack scenario can be detected and corrected by the Reed-Solomon decoding algorithm. In particular, as described in Section V-D, given $j,k\in[N]$, $\{d_{jk}^{(i)}\}_{i\in[N]}$ can be viewed as $N$ evaluation points of the polynomial $h_{jk}$ given in (17) whose degree is at most $2T$. The decoding process at the server then corresponds to the decoding of an $[N,2T+1,N-2T]_{p}$ Reed-Solomon code with at most $D$ erasures and at most $A$ errors. As an $[n,k,n-k+1]_{p}$ Reed-Solomon code with $e$ erasures can tolerate a maximum number of $\lfloor\frac{n-k-e}{2}\rfloor$ errors , the server can recover the correct pairwise distances as long as $A\leq\lfloor\frac{N-(2T+1)-D}{2}\rfloor$, i.e. $N\geq D+2A+2T+1$.

The third attack scenario can also be detected and corrected by the Reed-Solomon decoding algorithm. As described in Section V-E, $\{\mathbf{s}_{i}\}_{i\in[N]}$ are evaluation points of polynomial $h$ in (27) of degree at most $T$. This decoding process corresponds to the decoding of an $[N,T+1,N-T]_{p}$ Reed-Solomon code with at most $D$ erasures and at most $A$ errors. As such, the server can recover the desired aggregate model $h(0)=\sum_{j\in{\mathcal{S}}}\overline{\mathbf{w}}_{j}$ as long as $N\geq D+2A+T+1$. Therefore, combining with the condition of Lemma 2, the sufficient conditions under which BREA guarantees robustness against Byzantine users is given by

(Convergence) We now consider the update equation in (32) and prove the convergence of the random sequence $\nabla C(\mathbf{w}^{(t)})$. From Lemma 2, the quantized multi-Krum function $f$ in (32) is $(\alpha,A)$-Byzantine resilient. Hence, from Proposition $2$ of , $\nabla C(\mathbf{w}^{(t)})$ converges almost surely to zero,

(Privacy) As described in Section V-B, we assume the intractability of computing discrete logarithms, hence the server or any user cannot compute $\overline{\mathbf{w}}_{i}$ from $\mathbf{c}_{i0}$ in (14). It is therefore sufficient to prove the privacy of each individual model against a group of $T$ colluding users, in the case where $\mathcal{T}$ has size $T$. If $T$ users cannot get any information about $\overline{\mathbf{w}}_{i}$, then neither can fewer than $T$ users. Without loss of generality, let $\mathcal{T}=\{1,\ldots,T\}=[T]$ and \text{view}_{\mathcal{T}}=\big{\{}(\mathbf{s}_{kj})_{k\in[N]},\big{(}d^{j}_{kl}\big{)}_{k,l\in[N]},\mathbf{s}_{j}\big{\}}_{j\in[T]} where $\mathbf{s}_{kj}$ in (13) is the secret share of $\overline{\mathbf{w}}_{k}$ sent from user $k$ to user $j$, $d^{j}_{kl}$ in (16) is the pairwise distance of the secret shares sent from users $k$ and $l$ to user $j$, and $\mathbf{s}_{j}$ in (26) is the aggregate of the secret shares. As \big{\{}\big{(}d^{j}_{kl}\big{)}_{k,l\in[N]}\big{\}}_{j\in[T]} and \big{\{}\mathbf{s}_{j}\big{\}}_{j\in[T]} are determined by \big{\{}\big{(}\mathbf{s}_{kj}\big{)}_{k,l\in[N]}\big{\}}_{j\in[T]}, we can simplify the left hand side (LHS) of (46) as

where (51) follows from the fact that any $T+1$ evaluation points define a unique polynomial of degree $T$, which completes the proof of privacy. ∎

In this section, we analyze the complexity of BREA with respect to the number of users, $N$, and model dimension $d$.

Complexity Analysis of the Users: User $i$’s computation cost can be broken into three parts: 1) generating the secret shares $\mathbf{s}_{ij}$ in (12) for $j\in[N]$, 2) computing the pairwise distances $d^{(i)}_{jk}$ in (16) for $j,k\in[N]$, and 3) aggregating the secret shares belonging to the selected users from (26). First, generating $N$ secret shares of a vector with dimension $d$ has a computation cost of $O(dN\log^{2}N)$ . Second, as there are $O(N^{2})$ pairwise distances, computing the pairwise distances has a computation cost of $O(dN^{2})$ in total. Third, when the number of selected users $m=|\mathcal{S}|$ is $O(N)$, aggregating the secret shares belonging to the selected users has a computation cost of $O(dN)$. Therefore, the overall computation cost of each user is $O(dN\log^{2}N+dN^{2})$.

User $i$’s communication cost can be broken to three parts: 1) sending the secret share $\mathbf{s}_{ij}$ to user $j\in[N]$, 2) sending the secret shares of the pairwise distances $d^{(i)}_{jk}$ to the server for $j,k\in[N]$, and 3) sending the aggregate of secret the shares $\mathbf{s}_{i}$ in (26) to the server. The communication cost of the three parts are $O(dN)$, $O(N^{2})$, and $O(d)$, respectively. Therefore, the overall communication cost of each user is $O(dN+N^{2})$.

Complexity Analysis of the Server: Computation cost of the server can be broken into three parts: 1) decoding the pairwise distances by recovering $h_{jk}(0)$ in (17) for $j,k\in[N]$, 2) carrying out the multi-Krum algorithm to select the $m$ users for aggregation, and 3) decoding the aggregate of the selected models by recovering $h(0)$ in (27). As described in Section V-D, recovering the polynomial $h_{jk}$ corresponds to decoding an $[N,2T+1,N-2T]_{p}$ Reed-Solomon code with at most $D$ erasures and at most $A$ errors, which has an $O(N\log^{2}N\log\log N)$ computation cost . As there are $O(N^{2})$ pairs and each pair is embedded in a single polynomial, the computation cost of the first part is $O(N^{3}\log^{2}N\log\log N)$ in total. The computation cost of the second part is $O(dN^{2}+N^{2}\log N)$ . As the dimension of $h(0)$ is $d$, the computation cost of the third part is $O(dN\log^{2}N\log\log N)$. Overall, the computation cost of the server is $O((N^{3}+dN)\log^{2}N\log\log{N})$.

Communication cost can be broken into two parts: 1) receiving the secret shares of the pairwise distances $d^{(i)}_{jk}$ from users $i\in[N]$ for $j,k\in[N]$ and 2) receiving the aggregate of secret shared models $\mathbf{s}_{i}$ from users $i\in[N]$. The communication cost of the two parts are $O(N^{3})$ and $O(dN)$, respectively. Overall, the communication cost of the server is $O(dN+N^{3})$.

We summarize the complexity analysis in Table I. As can be observed in Table I, the server has a communication cost of $O(N^{3})$ and a computation cost of $O(N^{3}\log^{2}{N}\log\log{N})$, which is due to the recovery of $N^{2}$ pairwise distances. Although the distances are scalar valued, the overhead can become a limitation for very large-scale networks. In the next subsection, we propose a generalized framework to reduce the communication cost from $O(N^{3})$ to $O(N^{2})$ as well as to reduce the computation cost from $O(N^{3}\log^{2}{N}\log\log{N})$ to $O(N^{2}\log^{2}{N}\log\log{N})$.

VI-B The Generalized BREA Framework

The key idea of the generalized framework is to partition the set of $N(N-1)/2$ pairwise distances into sets of size $K$, and embed the $K$ distances in a single polynomial. Consequently, the number of polynomials to embed the $N(N-1)/2$ pairwise distances can be reduced from $O(N^{2})$ to $O(N^{2}/K)$. Each user then sends a single evaluation point of each polynomial to the server, which has an $O(N^{3}/K)$ communication cost in total. By setting $K=O(N)$, the generalized BREA framework can achieve $O(N^{2})$ communication complexity.

We now present the details of the generalized BREA framework. In the stochastic quantization phase, the generalized BREA framework follows the same steps as in Section V-A. In the verifiable secret sharing phase, user $i\in[N]$ generates secret shares of the quantized model $\overline{\mathbf{w}}_{i}$ by modifying the random polynomial $f_{i}$ in (12) as,

where the degree of $f_{i}$ is increased from $T$ to $K+T-1$. User $i$ then sends a secret share of $\overline{\mathbf{w}}_{i}$ to user $j\in[N]$, denoted by $\mathbf{s}_{ij}=f_{i}(\theta_{j})$.

As the coefficients from the first degree to the $(K-1)$-th degree terms in (52) are zero, the coefficient of the $(k-1)$-th degree term in (53) corresponds to the pairwise distance of the $k$-th pair in $\mathcal{P}_{1}$, i.e., $\lVert\mathbf{f}_{1}(0)-\mathbf{f}_{k+1}(0)\rVert^{2}=\lVert\overline{\mathbf{w}}_{1}-\overline{\mathbf{w}}_{k+1}\rVert^{2}$ for all $k\in[K]$. User $i$ then sends ${u}_{\mathcal{P}_{1}}(\theta_{i})$ to the server. Upon receiving the computation results from a sufficient number of users, the server can decode the pairwise distances of all pairs in $\mathcal{P}_{1}$ by reconstructing the polynomial ${u}_{\mathcal{P}_{1}}(\theta_{i})$. As the degree of ${u}_{\mathcal{P}_{1}}$ is $3K+2T-3$, the minimum number of results the server needs to collect from the users to recover the pairwise distances, i.e., the recovery threshold, is $3K+2T-2$. The decoding process of the polynomial corresponds to decoding an $[N,3K+2T-3,N-3K-2T+2]_{p}$ Reed-Solomon code with at most $D$ erasures and at most $A$ errors. In a similar way, we can define polynomials ${u}_{\mathcal{P}_{k}}$ for $k\in\{2,\ldots,G\}$ where user $i$ computes and sends ${u}_{\mathcal{P}_{k}}(\theta_{i})$ to the server. The server can then decode all of the $N(N-1)/2$ pairwise distances by reconstructing the $G$ polynomials.

After the server learns the pairwise distances, the generalized protocol follows the same steps as in Sections V-D and V-E. The overall algorithm of the generalized BREA framework is presented in Algorithm 2.

The generalized BREA framework achieves a communication cost of $O(N^{2})$ and computation cost of $O(N^{2}\log^{2}{N}\log\log{N})$ by setting $K=O(N)$, which follows from the following observations. First, user $i$ sends an evaluation point of each polynomial $u_{\mathcal{P}_{k}}$ to the server for $k\in[G]$, and there are $N$ users and $G=O(N^{2}/K)=O(N)$ polynomials, which has $O(N^{2})$ communication overhead in total. Second, the computation cost to decode the polynomial $u_{\mathcal{P}_{k}}$ is $O(N\log^{2}{N}\log\log N)$ and there are $G=O(N)$ polynomials, which has a computation cost of $O(N^{2}\log^{2}{N}\log\log N)$ in total. We summarize the complexity of the generalized BREA protocol in Table II.

VII Experiments

In this section, we demonstrate the convergence and resilience properties of BREA compared to conventional federated learning, i.e., the federated averaging scheme from , which is termed FedAvg throughout the section. We measure the performance in terms of the cross entropy loss evaluated over the training samples and the model accuracy evaluated over the test samples, with respect to the iteration index, $t$.

Network architecture: We consider an image classification task with 10 classes on the MNIST dataset , and train a convolutional neural network with 6 layers including two $5\times 5$ convolutional layers with stride 1, where the first and the second layers have 32 and 64 channels, respectively, and each is followed by ReLu activation and $2\times 2$ max pooling layer. It also includes a fully connected layer with $1024$ units and ReLu activation followed by a final softmax output layer.

Convergence and robustness against Byzantine users: Figure 2 shows the test accuracy of BREA and FedAvg for different number of Byzantine users. We can observe that BREA with $0\%$ and $30\%$ Byzantine users is as efficient as FedAvg with $0\%$ Byzantine users, while FedAvg does not tolerate Byzantine users. Figure 3 presents the cross entropy loss for BREA versus FedAvg for different number of Byzantine users. We omit the FedAvg with $30\%$ Byzantine users as it diverges. We observe that BREA with $30\%$ Byzantine users achieves convergence with comparable rate to FedAvg with $0\%$ Byzantine users, while providing robustness against Byzantine users and being privacy-preserving. For all cases of BREA in Figures 2 and 3, we set the quantization value in (9) to $q=1024$. Figure 4 further illustrates the cross entropy loss of BREA for different values of quantization parameter $q$. We can observe that BREA with a larger value of $q$ has better performance because the variance caused by the quantization function $Q_{q}$ defined in (9) gets smaller as $q$ increases. On the other hand, given the field size $p$, the quantization parameter $q$ should be less than a certain threshold to ensure (23) holds.

CIFAR-10 dataset: To investigate the performance of BREA with a larger dataset, we additionally experiment with CIFAR-10 , by using the same model architecture of (about $10^{6}$ model parameters). We use the same setting for parameters $N,A,m,p$ as the setting of i.i.d MNIST dataset. Figure 6 shows that the BREA algorithm (with $30\%$ Byzantine users) has comparable test accuracy to the FedAvg algorithm (with no Byzantine users).

VIII Conclusion

This paper presents the first single-server solution for Byzantine-resilient secure federated learning. Our framework is based on a verifiable secure outlier detection strategy to guarantee robustness of the trained model against Byzantine faults, while protecting the privacy of the individual users. We provide the theoretical convergence guarantees and the fundamental performance trade-offs of our framework, in terms of the number of Byzantine adversaries and the user dropouts the system can tolerate. In our experiments, we have implemented our system in a distributed network by using two ways of partitioning the MNIST dataset over up to $N=100$ users: i.i.d. and non-i.i.d. data distribution. For both settings, we numerically demonstrated the convergence behaviour while providing robustness against Byzantine users and being privacy-preserving. Future directions include developing single-server Byzantine-resilient secure learning architectures considering the heterogeneous environments in terms of computation and communication resources, developing efficient communication architectures, and quantization techniques.

In this paper, we utilize the distance based outlier detection approach to guarantee the robustness against Byzantine users. There have been many outlier detection approaches for Byzantine resilient SGD methods (or federated learning). Existing works can be roughly classified into two main categories: 1) geometric median and 2) coordinate-wise median . Our framework utilizes the geometric median based approach because it is more efficient in the secure domain. In order to preserve the privacy of local updates, the coordinate-wise median based approaches require a multiparty secure comparison protocol to find the median value of each coordinate. On the other hand, in our framework, the server compares the pairwise distances in plaintext, which is much more efficient than the secure comparison protocol. Extending the coordinate-wise median based algorithms to the secure domain would be a very interesting future direction.

Acknowledgement

This material is based upon work supported by Defense Advanced Research Projects Agency (DARPA) under Contract No. HR001117C0053, ARO award W911NF1810400, NSF grants CCF-1703575 and CCF-1763673, ONR Award No. N00014-16-1-2189, and research gifts from Intel and Facebook. The views, opinions, and/or findings expressed are those of the author(s) and should not be interpreted as representing the official views or policies of the Department of Defense or the U.S. Government.

References

-A The BREA Framework with Local Updating Schemes

In this section, we present how BREA framework can work with local updating schemes where each user locally takes multiple-steps of stochastic gradient descent using its local data before sending the updated model to server.

The BREA framework with local updating schemes follows the same steps from Section V-A to Section V-E by changing the local update $\mathbf{w}_{i}^{(t)}$ of user $i$ from a gradient estimate to the updated model by using multiple-steps of stochastic gradient descent (SGD). Then, the update equation of a benign user $i$ can be expressed as follows,