\section{Introduction}\label{sec:introduction}

\IEEEPARstart{F}{ederated learning} (FL, \cite{mcmahan2017communication, konevcny2015federated}) enables multiple participants to jointly train a machine learning (ML) model without sending their data to a central server. In FL, participants compute model updates based on their local data and a global model received from a coordination server, to whom they send the resulting updates. The server aggregates the received updates to obtain a new global model, which is redistributed among the participants. This collaboration entails mutual benefits for all parties: i) the participants and the server obtain more accurate models due to learning from joint training data, ii) participants keep their private local data in their devices, and iii) the server distributes the computational load of training across the participants' devices ({\em e.g.}, smartphones) \cite{bonawitz2019towards}. Since training data do not leave the participants' devices, FL is a suitable option for scenarios dealing with personal data, such as facial recognition~\cite{xu2017end}, voice assistants~\cite{bhowmick2018protection}, healthcare~\cite{brisimi2018federated}, next-word prediction~\cite{hard2018federated} and intrusion detection in IoT
networks~\cite{mothukuri2021federated}, or in case data collection and processing are restricted due to privacy protection laws such as the GDPR~\cite{voigt2017eu}.
Despite these advantages, FL is vulnerable to privacy and security attacks~\cite{kairouz2019advances, mothukuri2021survey}.

Regarding privacy, several works \cite{mcmahan2017learning, nasr2019comprehensive, melis2019exploiting} have demonstrated that a \emph{semi-honest} server can analyze individual updates to infer sensitive information on a participant's local training data. 
Recent powerful privacy attacks show that
it is possible to reconstruct the original training data by inverting the gradients of updates \cite{zhu2020deep, zhao2020idlg, geiping2020inverting}.
Regarding security, FL is vulnerable to poisoning attacks~\cite{blanco2021achieving}.
Since the server has no control over the behavior of participants, any of them may deviate from the prescribed training protocol to attack the model by conducting either untargeted poisoning ({\itshape i.e.} Byzantine) attacks~\cite{blanchard2017machine, wu2020federated} or targeted poisoning attacks~\cite{biggio2012poisoning, fung2020limitations, bagdasaryan2020backdoor}. 
In the former type of attacks, the attacker aims to degrade the model's overall performance, whereas in the latter, he aims to cause the global model to misclassify some attacker-chosen inputs.

Some solutions have been proposed to prevent the server from analyzing individual updates or linking them to their originators. These involve well-known privacy-enabling methods: differential privacy (DP) \cite{dwork2014algorithmic}, homomorphic encryption (HE) \cite{gentry2009fully} and secure multiparty computation (SMC) \cite{yao1982protocols}. 
DP-based methods protect the participants' data by injecting random noise into the parameters of updates at the cost of sa\-cri\-ficing the accuracy of the global model \cite{domingo2020limits}.
Unfortunately, this conflicts with a key motivation of FL, namely improving the accuracy of the trained mo\-dels. On the other hand, HE- and SMC-based methods securely aggregate the updates of participants before sending them to the server. This brings privacy to the participants and provides perfectly accurate aggregate updates to the server. 
Yet, HE and SMC have a high computational cost 
and they prevent the server from inspecting individual updates, which makes approaches based on these techniques 
vulnerable to security attacks. 
Note that countermeasures against security attacks require direct access by the server 
to the individual updates in order to detect and/or filter out those that are poisoned 
\cite{yin2018byzantine, blanchard2017machine, fung2018mitigating}.

Simultaneously achieving privacy, security and accuracy is a tough challenge for FL \cite{li2020federated, kairouz2019advances, blanco2021achieving}.
In fact, this is one of several challenges in ML due to contradicting requirements; see~\cite{liu2020machine} about other conflicts.

Our goal in this paper is to address the following puzzle: \emph{``Can we prevent a semi-honest server from performing privacy attacks on individual updates while learning an accurate global model and ensuring protection against security attacks?''}. 
To this end, we propose \emph{fragmented federated learning} (FFL), a framework that can prevent the server from performing privacy attacks, can counter security attacks and can maintain the accuracy of the learned global model. In FFL, participants randomly exchange fragments of updates among them before sending them to the server. We make the following contributions:
\begin{itemize}
    \item We design a novel lightweight protocol that i) allows participants to privately exchange and mix random fragments of their updates, ii) enables the server to correctly aggregate the global model from the mixed updates, and iii) prevents the server from recovering the complete original updates or linking them to their originators.
    \item We propose a new reputation-based defense tailored to FFL against security attacks. 
    Specifically, the server selects participants for training and adaptively aggregates their mixed updates according to their global reputations. 
    Also, honest participants do not exchange fragments with participants with low local reputations.
    Reputations are computed based on the quality of the updates
    the participants send and the fragments they exchange. 
    \item We demonstrate the effectiveness of our proposal through an extensive theoretical and empirical analysis to assess the accuracy, privacy and security offered by FFL, and we quantify the computation overhead and communication cost it incurs.
\end{itemize}
The rest of this paper is organized as follows. 
Section~\ref{sec:related} discusses related works.
Section~\ref{sec:prelim} introduces preliminary notions. Section~\ref{sec:attack_model} describes the attacks being considered.
Section~\ref{sec:meth} presents the fragmented federated learning framework. 
Section~\ref{sec:setup} details the experimental setup and evaluates our approach w.r.t. accuracy, robustness against attacks and runtime. Finally, Section~\ref{sec:conclusion} gathers conclusions and proposes several lines of future research. 
Appendices (A-C) contain privacy, security, convergence and complexity analyses.

\section{Related Work}
\label{sec:related}

Most works in the FL literature tackle either robustness versus attacks against privacy or robustness versus attacks against security (poisoning attacks), but they do not consider both types of robustness simultaneously. 

\textbf{Private FL.}
On the privacy side, several works have been proposed to prevent the server from seeing individual updates. \cite{bonawitz2017practical, so2021turbo} use secret sharing to hide individual updates. \cite{aono2017privacy, hardy2017private, zhang2020batchcrypt} encrypt the local updates and use homomorphic encryption to compute the global model from the encrypted updates. However, both approaches are vulnerable to poisoning attacks because they hinder the analysis of individual updates by the server. 
Other works adopt differential privacy (DP) \cite{mcmahan2017learning, bhowmick2018protection, geyer2017differentially}, which adds noise to local updates before sending them to the server. DP is practical and offers strong privacy guarantees for small values of $\epsilon$ but, due to the added noise, it significantly hampers the accuracy of the global model~\cite{domingo2020limits}. 


\textbf{Secure FL.}
On the security side, several attack-resistant aggregation defenses have been proposed. Multi-Krum~\cite{blanchard2017machine}, Bulyan~\cite{mhamdi2018hidden}, FoolsGold~\cite{fung2020limitations} and DRACO~\cite{chen2018draco} are well known in the FL literature. However, they generally require direct access to the original individual updates, which interferes with protecting 
the privacy of participants.
Although the median and the trimmed mean~\cite{yin2018byzantine} can be applied on mixed updates, they are not suitable for high-dimensional models because their estimation error scales up with the size of the model in a square-root manner~\cite{chang2019cronus}.

\textbf{Private and secure FL.}
Recently, the literature has witnessed a growing interest in achieving FL that is both privacy-preserving and secure.
\cite{naseri2020toward} uses DP to address both privacy and robustness against backdoor attacks. However, it does not deal with the trade-off between privacy and accuracy, and it does not consider poisoning attacks different from backdoor attacks. 
PEFL~\cite{privacy_enhanced9524709} tries to address both privacy and security, but assumes there are two \emph{non-colluding} servers that collaborate to filter out malicious updates while preventing each other from seeing individual updates. 
However, the curiosity of those servers may eventually lead them to collusion. 
Moreover, PEFL builds on linear homomorphic encryption and a packing technique, which involves exchanging the encrypted updates in four interacting protocols between the two servers for filtering and aggregation, which causes high communication and computation overheads. 
ShieldFL~\cite{ma2022shieldfl} also assumes two \emph{non-colluding} servers, and uses a two-trapdoor HE scheme based on the Paillier cryptosystem to achieve both secure and privacy-preserving FL.
In ShieldFL, the two servers execute three interactive protocols to compute the cosine similarity of the local updates in ciphertext. They then use the computed cosine similarities to filter out potential poisoned updates. Unfortunately, this also imposes significant computation and communication costs on the participating entities.
BREA~\cite{so2020byzantine} proposes a single-server framework where each participant secret-shares her local update with all the other participants in the system. 
Also, each participant locally computes the participant-wise Euclidean distances to the shares of all participants, and then sends the computed distances to the server, which uses them to filter out potential poisoned updates. 
The server then selects the potential good updates and asks the participants to locally aggregate the selected good shares and upload the aggregates to the server. Finally, the server reconstructs the global model from the received aggregates and sends it to the participants in the next training round. 
Although this work has the advantage of being single-server, it imposes high computation and communication overheads on the participating parties. This makes it impractical for large-scale FL systems. 
\cite{ma2022differentially} integrate local DP on the participant's side with an intermediate shuffler between the participants and the aggregator server to achieve privacy.  
Besides, they use a Byzantine-robust stochastic aggregation algorithm at the server side to achieve security.
However, this work is subject to the inevitable trade-off between privacy and accuracy due to the use of DP. 
In addition, the shuffler is a third party, and hence its honesty is not guaranteed.
SAFELearning \cite{zhang2021safelearning} is based on the work of \cite{bonawitz2017practical} to support backdoor detection and privacy-preserving aggregation simultaneously. To this end, it randomly divides participants into subgroups, securely aggregates a sub-model for each subgroup and filters out malicious sub-models instead of individual models. However, this approach faces a trade-off of another kind: the smaller the number of participants in a subgroup, the less privacy for these participants; conversely, the larger the number of participants, the easier it is for the attacker to hide her malicious model amid honest ones. The paper proposes to disclose part of the parameters of the aggregated sub-models, leading to another privacy/security trade-off. The authors of~\cite{domingo2021secure} propose a co-utile FL to solve the accuracy-privacy-security conflict. The proposed solution preserves the global model accuracy and allows defending against security attacks, but its privacy is limited to only breaking the link between local updates and their originators. Although this provides a level of privacy protection, a semi-honest server still has direct access to original unlinked updates. Hence, it can use them to perform several privacy attacks, such as membership inference attacks and reconstruction attacks. ~\cite{chen2020training, zhang2021shufflefl} employ Trusted Execution Environments (TEEs) on the participants (for local training) and on the servers (for secure aggregation) in order to achieve accurate and privacy-preserving FL. However, the limited memory size of current TEEs makes them impractical for large DL models or large-scale FL systems.
Besides, the authors of those papers do not consider data poisoning attacks such as label-flipping attacks, and assume trust in the manufacturers of the TEEs, which seems too strong an assumption.

In contrast to previous works, FFL offers a single-server and practical solution to simultaneously achieve accurate, privacy-preserving and secure FL. FFL does not add noise to updates (and thus preserves the accuracy of the global model), and it prevents the server from obtaining individual updates (thus thwarting successful server-side attacks against privacy). At the same time, FFL enables the server to neutralize security attacks through a novel defense that outperforms many of the state-of-the-art defenses against security attacks. 
Furthermore, FFL incurs very minor communication and computation overheads for the involved parties, which makes it suitable for large-scale FL systems.


\section{Preliminaries}
\label{sec:prelim}

\subsection{Deep neural networks}
A deep neural network (DNN) is a function $F(x)$, obtained by composing $L$ functions $f_l, l\in [1, L]$, that maps an input $x\in \mathbb{R}^n$ to an output $y\in \mathbb{R}^z$. Each $f_l$ is a layer that is parameterized by a weight matrix $w_l$, a bias vector $b_l$ and an activation function $\sigma_l$. $f_l$ takes as input the output of the previous layer $f_{l-1}$. The output of $f_l$ on an input $x$ is computed as 
\begin{equation}
    \label{eq:layer_activation}
    f_l(x) = \sigma_l(w_l \cdot x + b_l)
\end{equation}
Therefore, a DNN can be expressed as 
\begin{equation}
    \label{eq:dnn}
    F(x) = \sigma_L(w_L \cdot \sigma_{L-1}(w_{L-1} \dots \sigma_1(w_1 \cdot x + b_1) \dots + b_{L-1} )+ b_L)
\end{equation}
In this paper we use predictive DNNs as $z$-class classifiers. The output of $F(x)$ is a vector of $z$ dimensions containing the probabilities of $x$ belonging to each class $c_j$ for $j\in[1, z]$. The final predicted 
class $\hat{F}(x)$ is taken to be the class with the highest probability. 

\subsection{Federated learning}
In federated learning (FL), $K$ participants and an aggregator server $A$ collaboratively build a global model $W$. In each training round $t\in[1, T]$,
the aggregator randomly selects a subset of participants $S$ of size $n = C \cdot K \ge 1$ where $K$ is the total number of participants in the system, and $C$ is the fraction of participants that are selected in $t$. After that, $A$ distributes the current global model $W^{t}$ to all participants in $S$. Besides $W^{t}$, $A$ sends a set of hyper-parameters to be used to train the local models, which includes the number of local epochs $E$, the local batch size $BS$ and the learning rate $\eta$. After receiving $W^t$, each participant $k$ divides her local data into batches of size $BS$ and performs $E$ local training epochs on her data to compute her local update $W^{t+1}_{k}$. Finally, participants upload their updates to $A$, which aggregates them into a new global model $W^{t+1}$.
The federated averaging algorithm (\textit{FedAvg})\cite{mcmahan2017communication} is usually employed to perform the aggregation, and it is defined as 
\begin{equation}
\label{eq:fedavg}
   W^{t+1} = \sum_{k=1}^{K} \frac{d_{(k)}}{d} W^{t+1}_{(k)},
\end{equation}
where $d_{(k)}$ is the number of data points locally held by worker $k$, and $d$ is the total number of data points locally held by the $K$ workers, that is, $d=\sum_{k=1}^{K} d_{(k)}$.
Note that FedAvg is the standard way to aggregate updates in FL and is not meant to counter security attacks.


\section{Attack Models}
\label{sec:attack_model}
We consider two attack models: privacy attacks by a \emph{semi-honest} server 
or participant, and security attacks by \emph{malicious} participants.

\textbf{Privacy attack model.} We focus on a \emph{semi-honest} server $A^s$, who follows the protocol honestly, but tries to infer information about the private local data used by participants for training. Even though privacy attacks may also be orchestrated by participants based on the successive global models, the performance of such attacks is quite limited and degrades significantly as the number of participants increases \cite{melis2019exploiting}. Server-side attacks are much stronger, especially when the server sees local updates individually and can link them to their originators.  

 In particular, membership inference attacks aim to determine if a specific example is part of the training data set \cite{melis2019exploiting, nasr2019comprehensive}. Property inference attacks try to infer specific properties about the training data \cite{ganju2018property, melis2019exploiting}. Distribution estimation attacks aim to obtain examples from the same distribution of the participants' training data \cite{hitaj2017deep}. 

 Finally, reconstruction attacks are the most ambitious in that they attempt to extract the original training data from a participant's local update \cite{zhu2020deep, zhao2020idlg, geiping2020inverting}. To mount any of these attacks, the server needs to access individual local updates. Therefore, our goal is to disable privacy attacks by preventing the server from obtaining the participants' original updates.

\textbf{Security attack model.} Since the server has no control over the participants' behavior, a \emph{malicious} participant may deviate from the prescribed training protocol and attack the global model. Depending on the attacker's objective, security attacks can be divided into untargeted attacks \cite{fang2020local, biggio2012poisoning, jagielski2018manipulating}, and targeted attacks \cite{bagdasaryan2020backdoor, bhagoji2019analyzing, shafahi2018poison}. 
The former are attacks against model availability 
({\em e.g.} to prevent the model from converging), whereas the 
latter are against model integrity ({\em e.g.} to fool the global model into making incorrect predictions on some attacker-chosen inputs). Security attacks can be performed in two ways: model poisoning and data poisoning. In model poisoning \cite{blanchard2017machine, wu2020federated, bagdasaryan2020backdoor}, the attacker manipulates the model parameters before sending her update to the server. In data poisoning \cite{biggio2012poisoning, fung2018mitigating}, the attacker injects bad or biased data into her training data set before training her local model. 
In our work, we consider a number of attackers $K'\leq K/5$, that is, no more than $20\%$ of the $K$ participants in the system. 
Although some works in the literature assume larger percentages of attackers, finding more than $20\%$ of attackers in real-world FL scenarios is highly unlikely.
For example, with the millions of users~\cite{davenport_corbin} of Gboard~\cite{hard2018federated}, controlling even a small percentage of user devices requires the attacker(s) to compromise a large number of devices, which demands huge effort and resources and is therefore impractical. 
We assume the $K'$ attackers carry out two types of attacks: (1) untargeted attacks based on Gaussian noise \cite{li2019rsa, wu2020federated} and (2) targeted attacks based on label-flipping \cite{biggio2012poisoning,fung2018mitigating}. Furthermore, we assume that the attacker(s) have no control over the server or the honest participants.

\section{Fragmented Federated Learning}
\label{sec:meth}
In this section, we present \emph{fragmented federated learning} (FFL), a framework that aims at overcoming the drawbacks of the previous works reviewed in Section~\ref{sec:related} and solving the accuracy-privacy-security conflict. First, we give an overview of our framework and then present its design and protocols in detail. Table~\ref{tab:notation} summarizes the notation used in this paper.

\begin{table}[ht]
\centering
\caption{Notation used in this paper}
\label{tab:notation}
\begin{tabular}{|l|l|}
\hline
Notation & Description \\ \hline
$W$                 &   Federated learning model or update \\
$W^t$ & Model or update at round $t$\\ 
$|W|$ & Number of model parameters\\
$\lambda$ & Bitlength of a parameter\\
$w_l$               &  Weight matrix of layer $l$ \\
$b_l$               &  Bias vector of layer $l$            \\
$\sigma_l$           &  Activation function of layer $l$ \\
$D$ & Dimensionality of the model\\
$L$ & Number of layers of the model\\
$D_L$ & Last-layer dimensionality\\
$K$                 &  Number of participants \\
$A$                 &  Aggregator server \\ 
$T$                 &   Number of training rounds \\
$C$                 &  Fraction of selected participants \\
$n$                 & Number of selected participants     \\
$S$                 &  Set of selected participants\\
$Sc$                & Set of candidate participants\\
$E$                 &  Number of local epochs \\
$BS$                & Size of local batch size \\ 
$\eta$              &   Local learning rate \\
$W_k$ & Participant $k$'s update\\
$W_{k,i}$           &  $i$-th parameter of $W_k$\\
$K'$                & Number of malicious participants     \\
$\gamma^t$            & Global reputation vector held by the server at time $t$\\
$\gamma_k^t$            & Global reputation given by the server to participant $k$ at time $t$ \\
$Q1_x$            & First quartile of the values of magnitude $x$ \\
$\zeta^t_k$         & Local reputation vector held by participant $k$ at time $t$\\
$\zeta_{k, j}^t$         & Local reputation given by participant $k$ to participant $j$ at time $t$\\
$p$ & Large prime (2048-bit long)\\
$\mathbb{G}_p$ & Multiplicative group of integers mod $p$\\
$g$ & Generator of $\mathbb{G}_p$\\
$PRNG(.)$           & Public pseudo-random number generator \\
$Enc_{{pk}_{A}}(\cdot)$ & Encryption under $A$'s public key \\ 
$Dec_{{sk}_{A}}(\cdot)$    & Decryption under $A$'s private key \\
$(W_k)_{mix}$ & Participant $k$'s mixed update\\
$(W_k)^{'}_{mix}$   &  Participant $k$'s encrypted mixed update\\
$s_{r_k}$           & Seed to generate $k$'s one-time pad (OTP) \\
$r_k$               & OTP used to encrypt $k$'s fragments \\
$m$                 & Binary mask: vector of 0's and 1's \\ 
$\lnot{m}$           & 1's complement of $m$ \\
\hline
\end{tabular}
\end{table}

\subsection{Overview}
\label{sec:overview}

 \begin{figure}[!ht]
    \centering
      \includegraphics[width=0.6\linewidth]{figures/ffl_framework_adaptive.pdf}
      \caption{Overview of the fragmented federated learning framework}
      \label{ffl_framework}
\end{figure}
Fig.\ref{ffl_framework} shows an overview of the FFL framework. The key idea of FFL is to have the participants randomly fragment and mix their updates before sending them to the server. Specifically, two participants agree on some symmetric random indices in their update vectors and exchange the parameters of those indices after they are encrypted. The participants then send the encrypted mixed updates to the server instead of their original updates. 
Since exchanging parameters between participants is done without changing their original coordinate positions, the server can calculate the average of the mixed updates after decrypting the encrypted mixed updates and obtain the same updated global model that would result from averaging the original updates. 
Sending mixed updates instead of the original ones breaks the link between the updates and their originators, and does not give the server direct access to individual updates. Thus, FFL  prevents a semi-honest server from mounting powerful privacy attacks.
Also, the global model's accuracy is preserved because the parameters of the exchanged fragments are kept unaltered. 
Yet, exchanging fragments between participants should neither impose significant communication or computation overheads nor protect against server-side privacy attacks at the price of facilitating participant-side privacy attacks. Thus, we design a fragment exchanging protocol based on lightweight cryptographic tools to:
i) allow the participants to exchange and mix random fragments of their updates while incurring 
very minor communication and computation overheads,
ii) prevent participants from seeing each other's original fragments,
and iii) allow the server to correctly compute the updated global model from the mixed updates without being able to recover the individual original updates or link them to their originators. 
However, averaging updates to compute the global model goes against countering security attacks.
Also, the design of the exchange protocol gives $n'$ attackers the chance of poisoning $2n'$ coordinates.
We tackle both issues by designing a novel reputation-based defense tailored for FFL that builds trust in participants based on the quality of the mixed updates they send and the fragments they exchange.
Specifically, the server holds a global reputation vector and uses it to select participants for training and adaptively aggregate their mixed updates. A participant who repeatedly sends poisoned mixed updates will have a lower global reputation, and thus will not be selected in future training rounds.
Also, the mixed updates she sends will have little to no influence on the global model aggregation.
On the other hand, each participant holds a local reputation vector and uses it to decide whether to exchange fragments with the other participants.
The local reputation increases or decreases based on the quality of the fragments exchanged by participants.
An attacker who exchanges poisoned fragments with honest participants will eventually find no honest participant to exchange with.
The similarity between the mixed updates and their centroid is used to measure their quality.


\subsection{FFL design}
\label{sec:design}
There are $K + 1$ parties in the FFL framework: $K$ participants and an aggregator server $A$. 
We assume that $K'$ participants (with $K'\leq K/5$) may be malicious and attack the global model's availability or integrity by sending poisoned updates to $A$. 
Also, we assume that the aggregator server is semi-honest and may use the participants' updates to infer information about their local private data. 
Before starting any training task, $A$ generates a public/private key pair $(pk_A, sk_A)$ and broadcasts $pk_A$ to the $K$ participants.
Then, the server uses the metadata of the participants' devices (like IP or MAC addresses) to register them into the system. 
After that, $A$ assigns each participant a unique pseudonym. 
All parties are assumed to possess pairwise secure communication channels using communication protocols such as TLS or HTTPS and communicate with each other using pseudonyms.
Protocol~\ref{protocol1} formalizes the framework we propose.
At the first global training round, $A$ starts a federated learning task by initializing the global model $W^0$ and the global reputation vector $\gamma^0 \in \mathbb{R}^{K}$. The global reputation vector $\gamma$ is used to select participants for training and re-weight their mixed updates in the global model aggregation. 
Also, each participant $k$ initializes a local reputation vector $\zeta_k^0 \in \mathbb{R}^{K-1}$ that is used to store a local reputation value for each participant in the system different from $k$. 
In the first global training round, both $\gamma^0$ and $\zeta_k^0$ are initialized with zero vectors.
Later in this section, we explain how $\gamma$ and $\zeta_k$ are calculated and used in our framework.

\textbf{Adaptive selection of participants.}
At each round $t$, $A$ uses Procedure~\ref{proc1} to select a set $S$ of potential honest participants.
First, the first quartile of the global reputation $Q1_{\gamma^t}$ is computed.
Then, participants with a global reputation greater than or equal to $Q1_{\gamma^t}$ are assigned to the candidate set $Sc$.
Finally, the server selects a random set $S$ of 
$n=\max(C \cdot |Sc|, 2)$ participants from $Sc$.
As we explain later in this section, we expect the attackers 
(up to 20\%) to have global reputations less than $Q1_{\gamma^t}$. 
Note that, in the standard FL setting, $n = \max(C \cdot K, 1)$, but we replace $1$ by $2$ because FFL needs at least $2$ participants to be applicable. 
After that, $A$ sends the global model $W^t$ to the participants in $S$ through a secure channel. 
The server also adds the pseudonyms of the selected participants to a public board seen by all participants.

\textbf{Local training.}
Each participant $k\in S$ trains the received model on her private local data to obtain her local update $W_k$. 
Then, $k$ scales her computed local update by the number of data points she holds, $d_k$. 
The next step is for $k$ to randomly select another participant $j$ from the public board to exchange a fragment of her encrypted update $W_k$ with her.


\textbf{Participant selection for exchange.}
To avoid making herself a bridge for poisoning the global model, $k$ uses her local reputation vector $\zeta_k^t$ to decide whether to exchange fragments with any other participant $j$.
To do so, $k$ computes the first quartile of her local reputation vector $Q1_{\zeta_k^t}$ and assigns the participants in the public board that have local reputations greater than $Q1_{\zeta_k^t}$ to the set $Sc_k$.
Then, $k$ selects a random participant $j$ from $Sc_k$ and asks her to exchange fragments.
When $j$ receives the request from $k$ for fragment exchange, she checks the local reputation of $k$, 
$\zeta_{j, k}^t$, and if $\zeta_{j, k}^t<Q1_{\zeta_j^t}$, $j$ rejects $k$'s request for exchange.
Otherwise, $j$ accepts to exchange fragments with $k$, and they call protocol EXCHANGE\_FRAGMENTS. 
At the end of the protocol, both $k$ and $j$ obtain two encrypted mixed updates with their corresponding encrypted one-time pad (OTP) seeds: $({W_k})'_{mix}$ and $Enc_{{pk}_A}(s_{r_j})$ for participant $k$, and $({W_j})'_{mix}$ and $Enc_{{pk}_A}(s_{r_k})$ for participant $j$, and send them to $A$. Note that the seeds to generate the mixed updates' OTPs are encrypted under $A$'s public key and swapped between $k$ and $j$.
Later in this section, we detail how local reputations are computed.

\begin{algorithm}[!ht]
\SetKwProg{Fn}{Function}{}{end}
\caption{Fragmented federated learning}
\label{protocol1}
\SetAlgoLined
\KwInput{$K, C, BS, E, \eta, T$}
\KwOutput{$W^T$, the global model after $T$ training rounds}

$A$ initializes $W^{0}, \gamma^0 = \{\gamma_k^0 = 0\}_{k = 1}^{K}$;

\For{each participant $k \in [1, K]$}
{
    $k$ initializes $\zeta_k^0 = \{\zeta_{k, j \ne k}^0 = 0\}$;
}

\For{each round $t \in [0, T-1]$}
{
     $S \leftarrow$\FuncSty{SELECT\_PARTICIPANTS($C, \gamma^t)$};
        
    
    $A$ sends $W^t$ to all participants in $S$
    
    \For{each participant $k \in S$ \textbf{in parallel }} 
        {
            $k$ calls $(W_{k}^{t+1})'_{mix}, Enc_{{pk}_A}(s_{r_j}) \leftarrow$
            \FuncSty{PARTICIPANT\_UPDATE($k, W^{t})$};
            
            $k$ sends $(W_{k}^{t+1})'_{mix}, Enc_{{pk}_A}(s_{r_j})$ to $A$;
    
            $A$ decrypts $Enc_{{pk}_A}(s_{r_j})$ with its private key to obtain $s_{r_j}$;
            
            $A$ generates $r_j \leftarrow PRNG(s_{r_j})$;
             
            $A$ decrypts $(W_{k}^{t+1})'_{mix}$ with $r_j$ as
            $(W_{k}^{t+1})_{mix} \leftarrow
            (W_{k}^{t+1})'_{mix} \oplus r_j$;
        }
        
    \FuncSty{COMPUTE\_SIMILARITY()};
    
    \FuncSty{UPDATE\_REPUTATIONS()};
        
    Let $\nu^{t}$ be the computed trust vector from Expression~(\ref{normalize_gr});
        
    $A$ aggregates 
    $W^{t} \leftarrow \frac{1}{\sum_{k \in S} d_k} \sum \nu_k^{t} (W_{k}^{t+1})_{mix}$\label{lin18};
    
}

\Fn{\FuncSty{PARTICIPANT\_UPDATE}($k, W^{t}$)}{
    {
        
        $W_k \leftarrow W^{t}$; 
     
        \For{each local epoch $e \in [1, E]$}
        {
	    \For {each batch $\beta$ of size $BS$}
            {
                $W_k \leftarrow W_k-\eta\nabla \mathcal{L}(W_k, \beta)$; 
            }
        }
        
         $W_k\leftarrow d_k W_k$;
         
         exchanged=false;
         
         Let $Q1_{\zeta_k^t}$ be the first quartile in $\zeta_k^t$;
         
         Let $Sc_k$ be the set of participants with local reputations greater than $Q1_{\zeta_k^t}$;
        
   
         \While{not exchanged}
         {
         $j \leftarrow$ select a random participant of $Sc_k$;
         
         \If {$\zeta_{j, k}^t \geq Q1_{\zeta_j^t}$} {
         
            $(W_{mix})', Enc_{{pk}_A}(s_{r_j})\leftarrow\FuncSty{EXCHANGE\_FRAGMENTS}(k,j)$;
         
         exchanged=true; 
         
            \Return  $(W_{mix})', Enc_{{pk}_A}(s_{r_j})$;
         }
       }
    }    
}
\end{algorithm}

\setcounter{algocf}{0}
\renewcommand*{\algorithmcfname}{Procedure}
\begin{algorithm}[!ht]
  \DontPrintSemicolon
  \SetKwFunction{FMain}{SELECT_PARTICIPANTS}
  \caption{Adaptive selection of participants}
  \label{proc1}
  \SetKwProg{Fn}{}{:}{}
  \Fn{\FMain{$C, \gamma^t$}}{
  
            $Sc\leftarrow [ \ ]$; 
            
            Let $Q1_{\gamma^t}$ be the first quartile of $\gamma^t$;
            
            
            \For{each global reputation $\gamma_k^t \in \gamma^t$}
            {
            \If{$\gamma_k^t \geq Q1_{\gamma^t}$}{
                Add($k, Sc$);
            }
            }
            
        $n \leftarrow \max(C \cdot |Sc|, 2)$;
        
        $S\leftarrow$ select a random set of $n$ participants from $Sc$;
            
     
    \KwRet $S$;
}
\end{algorithm}


\textbf{Fragments exchanging and mixing.}
The protocol for exchanging fragments is key in our approach. 
We design this protocol to privately and efficiently exchange fragments of updates between participants. Specifically, a participant $k$ (the \emph{Initiator}) seeks to exchange a random fragment of her update with another participant $j$ (the \emph{Acceptor}). 
Both participants leverage a key exchange protocol to jointly generate two
complementing masks used to fragment their updates. The fragments are then
encrypted using one-time pads,
that is, random sequences added to the fragments, that allow {\em Initiator}
and {\em Acceptor} to combine
their updates but prevent each other from accessing their counterpart's update
parameters.
These one-time pads can only be removed by the central server after they
have been mixed
using the secret information provided by both participants.

Let $PRNG(\cdot)$ be a public pseudo-random number generator that takes an
integer as a seed.
Let $\mathbb{G}_p$ be the multiplicative group of integers modulo a large prime $p$ (2048-bit long), and $g$ a
generator of the group. 
All subsequent operations with vectors are performed coordinate-wise. Protocol EXCHANGE\_FRAGMENTS is as follows: 
\begin{enumerate}
    \item Participant $k$ randomly generates integers $a$, $s_{r_k}$ and $s_{\rho_k}$, 
    and sends $g^a \mod p$ and $Enc_{pk_{A}}(s_{r_k})$ to $j$. 
    
    \item Participant $j$ generates integers $b$, $s_{r_j}$ and $s_{\rho_j}$ and computes $g^b \mod p$, $r_j = PRNG(s_{r_j})$ and 
    $\rho_j = PRNG(s_{\rho_j})$, with the last two numbers 
   
   
   
    having bitlength $|W|\lambda$ (the bitlength of an update, that is, number of parameters times the bitlength of a parameter).  $j$ generates a mask $m=PRNG(g^{ab} \mod p)$ of 
    $0$'s and $1$'s of bitlength $|W|$ (equal to the number of update parameters) and its
   
    1-complement inverse mask $\lnot{m}$ such that $m \oplus \lnot{m} = \mathbf{1}_{|W|}$ (adding modulo 2 a mask to its 1-complement inverse yields the all ones mask). Then, $j$ sends $g^b \mod p$, $Enc_{pk_{A}}(s_{r_j})$, 
   
    $W_j \oplus r_j \oplus \rho_j$, 
   
   
    and $(W_j \odot \lnot{m}) \oplus \rho_j$ to $k$, where $\odot$ is an operator between an update and a mask that preserves the $i$-th update parameter if the $i$-th mask bit is 1, and clears to 0 the $i$-th update parameter if the $i$-th mask bit is 0.\\
 The random uniform binary mask $m$ will be used to fragment both $j$'s and $k$'s updates. 
    Also, both $r_j$ and $\rho_j$ are OTPs known to $j$ only,
   
    and used by $j$ to hide her original fragments from $k$. 
    \item $k$ computes $r_k = PRNG(s_{r_k})$ and $\rho_k = PRNG(s_{\rho_k})$ both of length $|W|\lambda$. $k$ generates $m=PRNG(g^{ab} \mod p)$ 
    and its inverse $\lnot{m}$. Then, $k$ computes her encrypted mixed update as follows:
    \begin{align}
    \label{exp1}
(W_k)^{'}_{mix} &= (W_k)_{mix} \oplus {r_j} \nonumber\\
                        &= W_k \oplus (W_k \odot m) \nonumber\\
                        &\oplus (W_j \oplus r_j \oplus \rho_j) \oplus ((W_j \odot \lnot{m}) \oplus \rho_j).
    \end{align}
   
    In Expression (\ref{exp1}), the result of subexpression $W_k \oplus (W_k \odot m)$ is to clear to 0 all parameters of $W_k$ at coordinates where the mask $m$ has a 1. On the other hand, subexpression $W_j \oplus (W_j \odot \lnot{m})$ clears to 0 all parameters of $W_j$ where the mask $m$ has a 0. Bitwise adding both subexpressions yields the mixed update $(W_k)_{mix}$. Note that the two appearances of $\rho_j$ cancel each other and $r_j$ encrypts the mixed update into $(W_k)^{'}_{mix}$.
   
    Since the mask $m$ is random, the mixed update can be expected to contain the same number of 1s and 0s. Hence, $(W_k)_{mix}$ can be expected to contain half of the coordinates from $W_j$
    and the other half from $W_k$. Another important remark is that the mixed update is encrypted using $r_j$, whereas $k$ has only $Enc_{pk_{A}}(s_{r_j})$, so $k$ cannot obtain the full cleartext mixed update. \\
    
    After that, $k$ sends $(W_k \oplus r_k \oplus \rho_k)$, and $(W_k \odot \lnot{m}) \oplus \rho_k$ to $j$. She
   
    also sends $(W_k)^{'}_{mix}, Enc_{pk_{A}}(s_{r_j})$ to the server.\\
    
Receiving $Enc_{pk_{A}}(s_{r_j})$ 
allows the server to decrypt the encrypted mixed update but does not allow it to extract any original fragment separately or link it to the fragment's originator, as we show in Appendix~\ref{sec:privacy}. Moreover, the use of the Diffie-Hellman key exchange method~\cite{diffie1976new} to generate seed  $g^{ab}$ ensures that no one but $k$ and $j$ knows the generated mask $m$. 
    
    \item Similarly, $j$ computes her encrypted mixed update as: 
    \begin{equation}
    \begin{aligned}
    (W_j)^{'}_{mix} &= (W_j)_{mix} \oplus {r_k} \\
                        &= W_j \oplus (W_j \odot m) \\
                        &\oplus (W_k \oplus r_k \oplus \rho_k) \oplus ((W_k \odot \lnot{m}) \oplus \rho_k).
    \end{aligned}
     \end{equation}
    Finally, $j$ sends  $(W_j)^{'}_{mix}, Enc_{pk_{A}}(s_{r_k})$ to the server.
\end{enumerate}
A naive and simpler way to exchange fragments would be to encrypt the updates coordinate by coordinate by using the server public key before exchanging fragments. 
However, this would cause significant communication and computation overheads for both the server and the par\-ti\-ci\-pants. Instead, our protocol uses OTPs as a means to encrypt the mixed updates. In other words, we rely on symmetric-key encryption, which is much more efficient when dealing with models that may contain millions of parameters. 

\textbf{Decryption of encrypted mixed updates.}
When at training round $t$ the server receives a mixed encrypted update $(W_{k}^{t+1})'_{mix}$ and its corresponding encrypted seed $Enc_{pk_{A}}(s_{r_j})$, it uses its private key to obtain the clear seed $s_{r_j} = Dec_{{sk}_{A}}(Enc_{pk_{A}}(s_{r_j}))$. 
Then $A$ regenerates $r_j$ using $s_{r_j}$ as a seed to $PRNG(\cdot)$
and bitwise adds $r_j$ to $(W_{k}^{t+1})'_{mix}$ to obtain $(W_{k}^{t+1})_{mix}$. 
$A$ does the same for all $k \in S$ to get the plain mixed updates $\{(W_{k}^{t+1})_{mix}|k\in S\}$. 

\textbf{Computation of reputation and trust values.} 
We explain how reputations are computed and used to neutralize potential attackers in the system.
First, the similarity between the mixed updates and their centroid are computed to measure their quality. Second, the global and local reputations are updated based on the computed similarities. Third, 
the global reputations are used to compute the trust values for the senders of the mixed updates, and these trust values finally weight the mixed updates when aggregating them to obtain 
the new global model. The above three steps
are detailed next:

{\em 1. Compute similarity.} 
In this procedure, the server computes the corresponding mixed gradients of the set $\{(W_{k}^{t+1})_{mix}|k\in S\}$. 
For a mixed update $(W_{k}^{t+1})_{mix}$, $A$ computes its corresponding gradient as
\begin{equation}
    \label{extract_gradient}
     (\nabla_{k}^{t})_{mix} = (W^t - (W_{k}^{t+1})_{mix})/\eta.
\end{equation}
The impact of untargeted attacks is expected to be evident in the magnitudes of whole poisoned updates, whereas the impact of the targeted attacks is expected to be more evident in the last-layer gradients that carry the indicative features and map directly to the prediction probability~\cite{fung2020limitations}.
Therefore, we independently analyze the whole mixed gradients and the last layer of mixed gradients and then combine the results to simultaneously counter both untargeted and targeted attacks. 
To do so, $A$ first computes the magnitude of each mixed gradient 
and obtains $\{||(\nabla_{k}^{t})_{mix}|||k\in S\}$. 
Then, it computes the median of the computed magnitudes, $med_{mix}^{t}$. 
Since most mixed updates are good, $med_{mix}^{t}$ is expected to fall amid good mixed updates.
After that, $A$ computes the distance between $med_{mix}^{t}$ and each magnitude $||(\nabla_{k}^{t})_{mix}||$ as
\begin{equation}
    \label{dist_sim}
    ds_k^{t} = |med_{mix}^{t} - ||(\nabla_{k}^{t})_{mix}|||.
\end{equation}
For each participant $k$, $ds_k^{t}$ represents how far the magnitude of the participant's mixed update is from $med_{mix}^{t}$. 
In the case of untargeted attacks, poisoned mixed updates are expected to deviate more from $med_{mix}^{t}$ and thus result in 
larger $ds^{t}$ values. 
It would also be possible to compute distances
based on the updates themselves and the median update rather
than their magnitudes, but this would 
cause a higher computational overhead on the server.
To capture the behavior of targeted attacks, $A$ extracts the mixed gradients of the last layer $L$ and obtains the set $\{(\nabla_{k}^{t})_{mix, L}|k\in S\}$. 
Then, $A$ computes $med_{mix, L}^{t}$ as the coordinate-wise 
median of the previous
set. Since honest participants share the same objective and are a majority, the median of the mixed last-layer gradients is expected to lie in the same direction as the honest participants' last-layer gradients. 
Thus, $A$ computes the cosine similarity between $med_{mix, L}^{t}$ and each $(\nabla_{k}^{t})_{mix, L}$ as
\begin{equation}
    \label{cos_sim}
    cs_k^{t} = \cos \varphi = \frac{(\nabla_{k}^{t})_{mix, L} \cdot med_{mix, L}^{t}}{||(\nabla_{k}^{t})_{mix, L}|| \cdot || med_{mix, L}^{t}||}.
\end{equation}
This yields a cosine similarity value $cs_k^{t+1} \in [-1, 1]$ for each participant's mixed update. 
Note that poisoned mixed updates, being a minority,
can be expected to have lower cosine similarity with $med_{mix, L}^{t}$ than good mixed updates. 

To compute a combined similarity value that captures the behaviors of both untargeted and targeted attacks, $A$ performs the following steps:
\begin{enumerate}
\item Normalize and invert the computed distances into the range $[0, 1]$ as
 $ds_k^{t} = 1 - ds_k^{t}/\max_{j\in S}(ds_j^{t}).$
\item Normalize the cosine similarity vector $cs^{t}$ into 
the range $[0, 1]$ as
    $cs_k^{t} = (cs_k^{t} + 1)/2.$
\item Compute the aggregated similarity value of $k$ as
        $sim_k^{t} = \alpha ds_k^{t} + (1 - \alpha) cs_k^{t}.$
\end{enumerate}
In this way, smaller $sim_k^{t}$ values are likely to correspond to potential poisoned mixed updates.
The hyperparameter $\alpha \in [0,1]$ is used to tune the simultaneous detection of untargeted and targeted attacks. 

{\em 2. Update reputations.} After computing the vector $sim^{t}$
containing similarities for all participants $k\in S$, $A$ updates the global reputations of those participants as
\begin{equation}
    \label{update_gr}
    \gamma_k^{t+1} = \gamma_k^{t} +  (sim_k^{t} - Q1_{sim^{t}}),
\end{equation}
where $Q1_{sim^t}$ is the first quartile of similarity values.
Based on its computed similarity $sim_k^{t}$, $k$'s global reputation increases or decreases: a similarity less than  $Q1_{sim^t}$
causes a reputation decrease and may lead to negative reputation.
If $k$ is an attacker and always sends poisoned mixed updates, its global reputation will get smaller and smaller and thus he will be excluded by the server from future selection for training.
However, an honest participant $k$ could also experience
a reputation decrease if she sent an update with a poisoned fragment during the exchange.
Therefore, $A$ also sends $sim_k^{t}- Q1_{sim^{t}}$ to $k$, who uses it to update the local reputation of the participant $j$ with whom $k$ has exchanged fragments in training round $t$:
\begin{equation}
    \label{update_lr}
    \zeta_{k, j}^{t+1} = \zeta_{k, j}^{t} + (sim_k^{t} - Q1_{sim^{t}}).
\end{equation}
This ensures that, when $k$ obtains a small similarity value because of $j$'s poisoned fragment, she reduces $j$'s local reputation.
As a result, if $j$ exchanges poisoned fragments with the other participants, she will get a bad local reputation among all honest participants and thus become an outcast, so that no honest participant will accept to exchange fragments with him in the future.

{\em 3. Adaptive model aggregation.} The server adaptively aggregates the received mixed updates using the global reputations of their senders. 
First, $A$ computes the trust vector $\nu^{t}$ as
\begin{equation}
    \label{normalize_gr}
    \nu^{t} = \max(\tanh{(\gamma^{t+1} - Q1_{\gamma^{t+1}})},0).
\end{equation}
The hyperbolic tangent function ($\tanh$) squashes its negative inputs into the range $[-1, 0[$,  and its positive inputs into the range $]0, 1]$.
Since the attackers are expected to have values lower than $Q1_{\gamma^{t+1}}$, $\tanh$ will make their trust scores in $\nu^{t}$ less than $0$. The maximum in Expression (\ref{normalize_gr}) sets the attackers' trust values to 0.
Note that, since the reputations of honest participants are likely to increase in every training round, their trust scores will converge to $1$ as training evolves, due to the use of $\tanh$.
Finally, the server uses the values in the computed trust vector $\nu^{t}$ to re-weight and aggregate the mixed updates 
(line~\ref{lin18} of Protocol~\ref{protocol1}). Since the 
attackers' trust values are 0, their updates are neutralized
in the aggregation.

\section{Experimental Analysis}
\label{sec:setup}

In this section, we report empirical results on three real data sets for the most relevant security and privacy attacks discussed above.  
We used the PyTorch framework to implement the experiments on a computer with an AMD Ryzen 5 3600 6-core CPU, 32 GB RAM, an NVIDIA GTX 1660 GPU with 6 GB RAM, and Windows 10 OS. 
As said above, with PyTorch, the parameter bitlength is $\lambda=32$.  
Our code and data are available for reproducibility purposes\footnote{\url{https://github.com/anonymized30/FFL}}.

In all the experiments, the {\em Acceptor}, respectively the {\em Initiator}, looped through all the layers of her update and generated a random binary $mask_{l}$ for each layer $l\in [1, L]$, where $L$ is the total number of layers in the global model $W$. At the end, the {\em Acceptor}, resp. the {\em Initiator}, set
$mask=mask_{l}||\ldots||mask_L$, where $||$ is the concatenation operator, and used $mask$ to exchange a random fragment.

We used the Diffie-Hellman key exchange protocol with the secure 2048-bit MODP group~\cite{rfc5114} to generate the secret shared seeds of the fragments' masks, and we used~\cite{pycryptodome} to encrypt and decrypt the OTP seeds with the recommended 3072-bit key size.
We used a value of $\alpha = 0.2$ because we found it gives better simultaneous detection of untargeted and targeted attacks. 
That is because targeted attacks are stealthier than untargeted ones.


\subsection{Data sets and models}
We tested the proposed method on three ML tasks: tabular data classification, image classification and sentiment analysis. Table~\ref{tab:datasets_models} summarizes the data sets and models we used. 
To evaluate the effectiveness of FFL at defeating reconstruction attacks, we used the code provided by the authors of \cite{geiping2020inverting}, who perform reconstruction attacks with the \emph{ConvNet64} model described in their paper (with about 3 million parameters) and some images from the \emph{CIFAR10} validation set.

\begin{table}[ht]
\centering
\caption{Data sets and models used in the experiments}
\label{tab:datasets_models}
\resizebox{0.5\textwidth}{!}{%
\begin{tabular}{|l|c|c|c|c|}
\hline
\multicolumn{1}{|c|}{Task}      & Data set & \# Examples & Model  & \# Parameters \\ \hline
Tabular classif.                & Adult    & 48,842      & MLP    & $\sim$5K            \\ \hline
\multirow{2}{*}{Image classif.} & MNIST    & 70K         & CNN    & $\sim$22K           \\ \cline{2-5} 
                                & CIFAR10  & 60K         & VGG16  & $\sim$15M           \\ \hline
Sent. analysis                  & IMDB     & 50K         & BiLSTM & $\sim$13M           \\ \hline
\end{tabular}%
}
\end{table}

\textbf{Tabular data classification.} We used the Adult tabular data set\footnote{\url{https://archive.ics.uci.edu/ml/datasets/adult}} that contains $48,842$ records of census income information with 14 numerical and categorical attributes. 
The class label is the attribute \emph{income} that classifies records into either $> 50$K or $\leq 50$K.
We used $80\%$ of the data as training data and the remaining $20\%$ as validation data.
We randomly and uniformly split the $80\%$ training examples among $20$ FL participants. 
We used a multi-layer perceptron (MLP) with one input layer, one hidden layer and one output layer that contains about $5$K learnable parameters.
The output layer is followed by a Sigmoid function to produce the final predicted class for an input record. 
The MLP was trained during $100$ rounds. In each round, the FL server selected $10$ participants and asked them to train the model for $1$ local epoch and a local batch size $64$. 
The participants used the binary cross-entropy with logit loss function and the Adam optimizer with a learning rate = $0.001$ to train their models.

\textbf{Image classification.} We used two data sets for the
image classification task:
\begin{itemize}
\item MNIST data set. It contains $70$K handwritten digit images from $0$ to $9$ ({\em i.e.}, $10$ classes) \cite{lecun1999object}. 
The images are in grayscale with size $28\times28$ pixels, and they are divided into a training set ($60$K examples) and a testing set ($10$K examples). 
We randomly and uniformly split the $60$K training examples among $100$ simulated participants of an FL setting. 
We used a two-layer convolutional neural network (CNN) with two fully connected layers. 
The CNN model was trained during $200$ rounds. In each round, the FL server randomly chose $50$ participants and asked them to train the model for $3$ local epochs and a local batch size $64$. 
The participants used the cross-entropy loss function and the stochastic gradient descent (SGD) optimizer with a learning rate = $0.001$ and momentum = $0.9$ to train their models.

\item CIFAR10 data set. It consists of $60$K colored images of $10$ different classes \cite{krizhevsky2009learning}. 
The data set is divided into $50$K training examples and $10$K testing examples. 
We randomly and uniformly split the $50$K training examples among $20$ FL participants.
We used the VGG16 CNN model with one fully connected layer \cite{simonyan2014very}. 
The VGG16 model was trained during $100$ rounds. 
In each round, the FL server randomly chose $10$ participants and asked them to train the model for $3$ local epochs and a local batch size $32$. 
The participants used the cross-entropy loss function and the SGD optimizer with a learning rate = $0.01$ and momentum = $0.9$ to train their models.
\end{itemize}

{\bf Sentiment analysis.} We used the IMDB Large Movie Review data set \cite{maas2011learning} for this binary sentiment classification task. 
This data set is a collection of $50$K movie reviews and their corresponding sentiment binary labels (either positive or negative). 
We divided the data set into $40$K training examples and $10$K testing examples. 
We randomly and uniformly split the $40$K training examples among $20$ FL participants. 
We used a Bidirectional Long/Short-Term Memory (BiLSTM) model, which has an embedding layer of $100$ dimensions for each token. 
The model ends with a linear layer followed by a Sigmoid function to produce the final predicted sentiment for an input review. 
The BiLSTM was trained during $100$ rounds. In each
round, the FL server randomly chose $10$ participants and asked them to train the model for $1$ local epoch and a local batch size $32$. 
The participants used the binary cross-entropy with logit loss function and the Adam optimizer with a learning rate = $0.001$ to train their models.

\textbf{Evaluation metrics.}
\label{metrics} We used the following evaluation metrics on the test set examples to assess the impact of the attacks on the learned model and the performance of the proposed framework w.r.t. the state of the art:
\begin{itemize}
\item \emph{Test error (TE)}. This is the error resulting from the loss functions used in training. The lower the test error, the more robust the method is against the attack.
\item \emph{Overall accuracy (All-Acc)}. This is the number of correct predictions divided by the total number of predictions. 
\item \emph{Source class accuracy (Src-Acc)}. We evaluated the 
accuracy for the subset of test examples belonging to the source class. Note that one may achieve a good overall accuracy while degrading the accuracy of the source class. 
\item \emph{Attack success rate (ASR)}. This is the proportion of targeted examples (with the source label) that are incorrectly classified into the label desired by the attacker.
\end{itemize}
An effective defense against the attacks needs to retain the benign performance of the global model on the main task while reducing ASR. 

\subsection{Robustness against security attacks}

\label{exp:robustness}
We next report results on the robustness of FFL against two security
attack strategies: in {\em Strategy 1}, the attacker generates two poisoned fragments, one of which he exchanges with 
another participant $k$, and he sends to the server a mixed update
consisting of his other poisoned fragment and the good fragment of $k$; in {\em Strategy 2}, the attacker exchanges a poisoned fragment with $k$ and sends a fully poisoned update to the server. 

Also, we compare the performance of FFL with the performance of FedAvg\cite{mcmahan2017communication}, the median~\cite{yin2018byzantine}, the trimmed mean~\cite{yin2018byzantine}, multi-Krum~\cite{blanchard2017machine}, and FoolsGold~\cite{fung2020limitations} on standard FL. 
Notice that FedAvg does nothing to counter security attacks (it systematically aggregates all received updates).

We evaluated TE and All-Acc under the Gaussian noise untargeted attack, and TE, Src-Acc and ASR under the label-flipping targeted attack. 
We used standard FL with FedAvg when no attacks were performed as a baseline to show the impact of attacks on the model performance. 
In our experiments, the percentage of attackers was $20\%$ for all four benchmarks.

\textbf{Gaussian noise attack.} The attackers added Gaussian noise to their local updates to prevent the model from converging \cite{li2019rsa, wu2020federated}. Specifically, they added noise with $0$ mean and $0.5$ standard deviation for the MLP and CNN model parameters, and $0.2$ standard deviation for VGG16 and BiLSTM parameters.
\begin{table*}[t]
\centering
\caption{Robustness against Gaussian noise attacks. Best scores are in bold.}
\label{tab:robustness_gn}
\begin{tabular}{|cl|cc|cc|cc|cc|}
\hline
\multicolumn{2}{|c|}{\multirow{2}{*}{\textbf{\begin{tabular}[c]{@{}c@{}}Benchmark/ \\ Method\end{tabular}}}} & \multicolumn{2}{c|}{Adult-MLP}          & \multicolumn{2}{c|}{MNIST-CNN}         & \multicolumn{2}{c|}{CIFAR10-VGG16}      & \multicolumn{2}{c|}{IMDB-BiLSTM}       \\ \cline{3-10} 
\multicolumn{2}{|c|}{}                                                                                       & \multicolumn{1}{c|}{TE}     & All-Acc\% & \multicolumn{1}{c|}{TE}    & All-Acc\% & \multicolumn{1}{c|}{TE}     & All-Acc\% & \multicolumn{1}{c|}{TE}    & All-Acc\% \\ \hline
\multicolumn{1}{|c|}{\multirow{6}{*}{FL}}                        & FedAvg (no attacks)                       & \multicolumn{1}{c|}{0.349}  & 82.56     & \multicolumn{1}{c|}{0.112} & 96.69     & \multicolumn{1}{c|}{0.881}  & 80.77     & \multicolumn{1}{c|}{0.475} & 88.63     \\ \cline{2-10} 
\multicolumn{1}{|c|}{}                                           & FedAvg                                    & \multicolumn{1}{c|}{1.198}  & 75.08     & \multicolumn{1}{c|}{2.322} & 9.65      & \multicolumn{1}{c|}{10.324} & 10.0      & \multicolumn{1}{c|}{0.618} & 67.7      \\ \cline{2-10} 
\multicolumn{1}{|c|}{}                                           & Median                                    & \multicolumn{1}{c|}{0.349}  & \textbf{82.87}     & \multicolumn{1}{c|}{0.115} & 96.62     & \multicolumn{1}{c|}{1.020}  & 78.91     & \multicolumn{1}{c|}{0.524} & 88.33     \\ \cline{2-10} 
\multicolumn{1}{|c|}{}                                           & Trimmed mean                              & \multicolumn{1}{c|}{0.350}  & 82.61     & \multicolumn{1}{c|}{0.114} & 96.64     & \multicolumn{1}{c|}{1.046}  & \textbf{80.23}     & \multicolumn{1}{c|}{\textbf{0.457}} & \textbf{88.79}     \\ \cline{2-10} 
\multicolumn{1}{|c|}{}                                           & Multi-Krum                                & \multicolumn{1}{c|}{0.350}  & 82.69     & \multicolumn{1}{c|}{0.126} & 96.18     & \multicolumn{1}{c|}{0.998}  & 78.86     & \multicolumn{1}{c|}{0.565} & 87.72     \\ \cline{2-10} 
\multicolumn{1}{|c|}{}                                           & FoolsGold                                 & \multicolumn{1}{c|}{44.051} & 69.47     & \multicolumn{1}{c|}{2.741} & 8.92      & \multicolumn{1}{c|}{12.813} & 9.02      & \multicolumn{1}{c|}{2.694} & 51.61     \\ \hline
\multicolumn{1}{|c|}{\multirow{2}{*}{FFL}}                       & Strategy 1                                & \multicolumn{1}{c|}{\textbf{0.349}}  & 82.84     & \multicolumn{1}{c|}{\textbf{0.112}} & \textbf{96.67}     & \multicolumn{1}{c|}{\textbf{0.931}}  & 79.74     & \multicolumn{1}{c|}{0.536} & 88.15     \\ \cline{2-10} 
\multicolumn{1}{|c|}{}                                           & Strategy 2                                & \multicolumn{1}{c|}{0.350}  & 82.86     & \multicolumn{1}{c|}{0.113} & 96.61     & \multicolumn{1}{c|}{0.938}  & 79.26     & \multicolumn{1}{c|}{0.542} & 87.48     \\ \hline
\end{tabular}%
\end{table*}

Table~\ref{tab:robustness_gn} shows the results under this attack.
First, we can see the significant negative impact of the attack on the performance of FedAvg regarding both the test error and the overall accuracy. 
The case was even worse with FoolsGold because it considered participants with similar last-layer gradients to be attackers and it removed their contributions.
Conversely, it considered participants with dissimilar last-layer 
gradients to be honest and it preserved their contributions 
in the model aggregation. 
The rest of the methods, including FFL, achieved comparable results to the baseline.
Since the added noise made the magnitudes of the poisoned updates different from those of good updates, we observe that i) the median and the trimmed mean were able to neutralize the poisoned parameters in model aggregation, ii) multi-Krum was able to exclude the poisoned updates due to the larger Euclidean distances they had, and iii) FFL was able to exclude poisoned mixed updates because their deviations from their medians were larger than those of good mixed updates.
We can also see that, in most cases (Adult-MLP, MNIST-CNN and CIFAR10-VGG16), FFL achieved the lowest test error among all methods.
As the training evolved, FFL set the trust values of honest participants to $1$ and thus fully considered their contributions. 
Note that FFL achieved similar performance under attack strategies 1 and 2. 


\textbf{Label-flipping attack.} In the label-flipping attack, attackers flip the labels of correct training examples from one class (a.k.a. the source class) to another class and train their models according to the latter~\cite{biggio2012poisoning,fung2018mitigating}. 
For Adult, the attackers flipped each example with the label ''$>50$K'' to ''$\leq 50$K'', while they flipped each example with the label ''$7$'' to ''$1$'' for MNIST.
For CIFAR10, the attackers flipped each example with the label ''Cat'' to ''Dog''.
For IMBD, they flipped the ''positive'' reviews to ''negative''.

\begin{table*}[t]
\centering
\caption{Robustness against label-flipping attacks. Best scores are in bold.}
\label{tab:robustness_lf}
\begin{tabular}{|cl|ccc|ccc|ccc|ccc|}
\hline
\multicolumn{2}{|c|}{\multirow{2}{*}{\textbf{\begin{tabular}[c]{@{}c@{}}Benchmark/ \\ Method\end{tabular}}}} & \multicolumn{3}{c|}{Adult-MLP}                                      & \multicolumn{3}{c|}{MNIST-CNN}                                      & \multicolumn{3}{c|}{CIFAR10-VGG16}                                  & \multicolumn{3}{c|}{IMDB-BiLSTM}                                    \\ \cline{3-14} 
\multicolumn{2}{|c|}{}                                                                                       & \multicolumn{1}{c|}{TE}    & \multicolumn{1}{c|}{Src-Acc\%} & ASR\% & \multicolumn{1}{c|}{TE}    & \multicolumn{1}{c|}{Src-Acc\%} & ASR\% & \multicolumn{1}{c|}{TE}    & \multicolumn{1}{c|}{Src-Acc\%} & ASR\% & \multicolumn{1}{c|}{TE}    & \multicolumn{1}{c|}{Src-Acc\%} & ASR\% \\ \hline
\multicolumn{1}{|c|}{\multirow{6}{*}{FL}}                        & FedAvg (no attacks)                       & \multicolumn{1}{c|}{0.349} & \multicolumn{1}{c|}{38.5}      & 61.46 & \multicolumn{1}{c|}{0.112} & \multicolumn{1}{c|}{95.43}     & 0.49  & \multicolumn{1}{c|}{0.881} & \multicolumn{1}{c|}{70.7}      & 14.5  & \multicolumn{1}{c|}{0.519} & \multicolumn{1}{c|}{87.16}     & 12.84 \\ \cline{2-14} 
\multicolumn{1}{|c|}{}                                           & FedAvg                                    & \multicolumn{1}{c|}{0.371} & \multicolumn{1}{c|}{11.7}      & 88.28 & \multicolumn{1}{c|}{0.130} & \multicolumn{1}{c|}{93.39}     & 1.26  & \multicolumn{1}{c|}{0.913} & \multicolumn{1}{c|}{53.8}      & 29.3  & \multicolumn{1}{c|}{0.562} & \multicolumn{1}{c|}{63.61}     & 36.39 \\ \cline{2-14} 
\multicolumn{1}{|c|}{}                                           & Median                                    & \multicolumn{1}{c|}{0.352} & \multicolumn{1}{c|}{33.6}      & 66.4  & \multicolumn{1}{c|}{0.117} & \multicolumn{1}{c|}{93.48}     & 1.07  & \multicolumn{1}{c|}{0.943} & \multicolumn{1}{c|}{58.0}      & 24.8  & \multicolumn{1}{c|}{0.643} & \multicolumn{1}{c|}{59.92}     & 40.08 \\ \cline{2-14} 
\multicolumn{1}{|c|}{}                                           & Trimmed mean                              & \multicolumn{1}{c|}{0.350} & \multicolumn{1}{c|}{34.73}     & 65.27 & \multicolumn{1}{c|}{0.118} & \multicolumn{1}{c|}{93.58}     & 1.07  & \multicolumn{1}{c|}{0.943} & \multicolumn{1}{c|}{58.4}      & 25.5  & \multicolumn{1}{c|}{0.649} & \multicolumn{1}{c|}{58.2}      & 41.8  \\ \cline{2-14} 
\multicolumn{1}{|c|}{}                                           & Multi-Krum                                & \multicolumn{1}{c|}{\textbf{0.349}} & \multicolumn{1}{c|}{\textbf{39.98}}     & \textbf{60.02} & \multicolumn{1}{c|}{0.113} & \multicolumn{1}{c|}{\textbf{95.33}}     & \textbf{0.39}  & \multicolumn{1}{c|}{0.896} & \multicolumn{1}{c|}{42.6}      & 39.3  & \multicolumn{1}{c|}{0.886} & \multicolumn{1}{c|}{39.05}     & 60.95 \\ \cline{2-14} 
\multicolumn{1}{|c|}{}                                           & FoolsGold                                 & \multicolumn{1}{c|}{0.350} & \multicolumn{1}{c|}{39.37}     & 60.63 & \multicolumn{1}{c|}{\textbf{0.111}} & \multicolumn{1}{c|}{95.14}     & \textbf{0.39}  & \multicolumn{1}{c|}{0.989} & \multicolumn{1}{c|}{67.4}      & 16.6  & \multicolumn{1}{c|}{0.549} & \multicolumn{1}{c|}{\textbf{86.86}}     & \textbf{13.14} \\ \hline
\multicolumn{1}{|c|}{\multirow{2}{*}{FFL}}                       & Strategy 1                                & \multicolumn{1}{c|}{0.350} & \multicolumn{1}{c|}{39.59}     & 60.41 & \multicolumn{1}{c|}{\textbf{0.111}} & \multicolumn{1}{c|}{\textbf{95.33}}     & \textbf{0.39 } & \multicolumn{1}{c|}{\textbf{0.849}} & \multicolumn{1}{c|}{\textbf{68.90}}      & \textbf{13.20}  & \multicolumn{1}{c|}{\textbf{0.544}} & \multicolumn{1}{c|}{86.64}     & 13.36 \\ \cline{2-14} 
\multicolumn{1}{|c|}{}                                           & Strategy 2                                & \multicolumn{1}{c|}{\textbf{0.349}} & \multicolumn{1}{c|}{39.90}      & 60.10  & \multicolumn{1}{c|}{0.112} & \multicolumn{1}{c|}{95.04}     & 0.49  & \multicolumn{1}{c|}{0.892} & \multicolumn{1}{c|}{68.80}      & 15.00  & \multicolumn{1}{c|}{0.524} & \multicolumn{1}{c|}{86.16}     & 13.84 \\ \hline
\end{tabular}%
\end{table*}

Table~\ref{tab:robustness_lf} shows the results under the label-flipping attack.
For the Adult-MLP benchmark, the FedAvg performance significantly degraded for  Src-Acc and ASR.
However, TE slightly increased and kept close to that of the baseline. The reason for that is the Adult data set is highly imbalanced, with a skew toward the ''$\leq 50$K'' class label.
The median and the trimmed mean achieved low TE and slightly degraded the performance on Src-Acc and ASR because they discarded a large number of coordinates in the global model aggregation.
The other methods, including FFL, achieved similar results to the baseline in the three metrics used.
For MNIST-CNN, the performance of FedAvg, median and trimmed mean slightly degraded compared to the baseline.
An interesting note is that FedAvg was not highly affected by the attack. The reasons for that are the small size of the model and the simple and balanced distribution of the data set. That was also observed in~\cite{shejwalkar2021back}, where the authors argued that, in some cases, FedAvg could be robust against poisoning attacks.
For CIFAR-VGG16, Src-Acc degraded from $70.7\%$ to $53.8\%$, and ASR increased from $14.5\%$ to $29.3\%$ with FedAvg.
On the other hand, FedAvg achieved TE lower than that of the median, the trimmed median and FoolsGold.
That is because the attackers flipped the labels on the examples of only one class and kept the labels of the other classes unchanged.
The median and the trimmed mean decreased Src-Acc and increased ASR because of the large size of the VGG16 model. \cite{chang2019cronus} have shown that the estimation error of the median and the trimmed mean scales up with the size of the model in a square-root manner.
Multi-Krum achieved the worst performance regarding Src-Acc and ASR because the small impact of the attack was not detectable in the large model.
Therefore, multi-Krum identified some attackers as honest while identifying 
some honest participants as attackers, which led to its poor performance.
FFL achieved the best performance among all the methods for all three metrics. 
FoolsGold scored the second-best after FFL regarding Src-Acc and ASR.
FFL and FoolsGold achieved such good performance because they analyzed the 
last-layer gradients, which contain more useful information for detecting the behavior of targeted poisoning attacks.
However, FoolsGold achieved the greatest TE among the other methods because it did not consider the full contributions of the honest participants.
FFL, however, considered almost all the full contributions of the honest participants and thus achieved the lowest TE. 

For the IMDB-BiLSTM benchmark, FFL and FoolsGold achieved the 
best performance among all methods, most of which were negatively 
impacted by the large size of the BiLSTM model.
FFL and FoolsGold outperformed the other methods by a large margin in
achieving good values for all metrics.
FoolsGold performed well in this benchmark because it was its ideal setting: updates from honest participants were somewhat different due to the different reviews they gave, whereas updates for attackers became very close to each other because they shared the same objective. 

To summarize, the results show that FFL can effectively defend against untargeted and targeted poisoning attacks while preserving the benign model performance. Moreover, FFL outperforms the state-of-the-art defenses in achieving good 
model performance while preventing the attackers from mounting successful security attacks and hindering the semi-honest server from mounting privacy attacks. 

\subsection{Protection against the reconstruction privacy attack}
\label{exp:rec_attack}

We next report results on the protection offered by FFL against the most powerful privacy attack, namely the reconstruction attack proposed in \cite{geiping2020inverting}. Notice that this attack does not require auxiliary data and 
can estimate the private training data by inverting their corresponding gradients. 

Fig.~\ref{fig:one_image_construction} shows the results when two participants, $k$ and $j$, sent their updates computed on 
just their private images (left column of the figure) to the server. In the FL setting (middle column of the figure), the server was able to reconstruct their private images with high accuracy. However, when they mixed fragments of their updates before sending them (FFL setting, right column of the figure), the server was only able to obtain noise instead of the original images.
\begin{figure}[htbp]
    \centering
    \begin{subfigure}{0.15\textwidth}
      \centering
      \includegraphics[width=\linewidth]{figures/input11.png}
    \end{subfigure
    \begin{subfigure}{0.15\textwidth}
      \centering
      \includegraphics[width=\linewidth]{figures/output11.png}
    \end{subfigure
    \begin{subfigure}{0.15\textwidth}
      \centering
      \includegraphics[width=\linewidth]{figures/output11_mixed.png}
    \end{subfigure}%
    \vspace{0.1\baselineskip}
    \begin{subfigure}{0.15\textwidth}
      \centering
      \includegraphics[width=\linewidth]{figures/input21.png}
    \end{subfigure
    \begin{subfigure}{0.15\textwidth}
      \centering
      \includegraphics[width=\linewidth]{figures/output21.png}
    \end{subfigure
    \begin{subfigure}{0.15\textwidth}
      \centering
      \includegraphics[width=\linewidth]{figures/output21_mixed.png}
    \end{subfigure}%
    \caption{Reconstruction of two input images from the gradients of two participants.  Left: Two input images. Middle: Reconstruction from original gradients (FL). Right: Reconstruction from mixed gradients (FFL).}
    \label{fig:one_image_construction}
\end{figure}

Similarly, Fig.~\ref{fig:batch_construction_peerkj} shows the results when two participants $k$ and $j$ sent their updates computed on a batch of $8$ images to the server. The figure exemplifies on two different batches of input images; the first example is given in the three upper rows and the second one in the three lower rows. In the FL setting, the server was able to recover a lot of information about the participants' training data. However, when they mixed their updates before sending them to the server (FFL setting), the latter just got a totally random batch of images. 


\begin{figure}[htbp]
    \centering
    \begin{subfigure}{0.5\textwidth}
      \centering
      \includegraphics[width=\linewidth]{figures/input18.png}
    \end{subfigure
    \vspace{0.1\baselineskip}
    \begin{subfigure}{0.5\textwidth}
      \centering
      \includegraphics[width=\linewidth]{figures/output18.png}
    \end{subfigure
    \vspace{0.1\baselineskip}
    \begin{subfigure}{0.5\textwidth}
      \centering
      \includegraphics[width=\linewidth]{figures/output18_mixed.png}
    \end{subfigure}%
    \vspace{0.5\baselineskip}
    \begin{subfigure}{0.5\textwidth}
      \centering
      \includegraphics[width=\linewidth]{figures/input28.png}
    \end{subfigure
    \vspace{0.1\baselineskip}
    \begin{subfigure}{0.5\textwidth}
      \centering
      \includegraphics[width=\linewidth]{figures/output28.png}
    \end{subfigure
    \vspace{0.1\baselineskip}
    \begin{subfigure}{0.5\textwidth}
      \centering
      \includegraphics[width=\linewidth]{figures/output28_mixed.png}
    \end{subfigure}%
   
   
    \caption{The three upper rows show the reconstruction by the server of a batch of 8 input images based on the gradients of a participant. The first row shows the input private images, the second row shows the reconstructions from the FL original gradients of the participant, and the third row the reconstructions from the FFL mixed gradients of the participant. The three lower rows report another analogous example with a different batch of input images.}
    \label{fig:batch_construction_peerkj}
\end{figure}

\subsection{Runtime of FFL}
\label{sec:runtime}

\begin{table*}[t]
\centering
\caption{CPU runtime in seconds of FFL in comparison with standard FL for one training round. Columns Dec. and Aggr. contain the decryption runtime of encrypted mixed updates, and the global reputation calculation and aggregation runtime on the server side (S). 
Column Mix. reports the overhead (extra runtime) on the participant side (P)
with respect to standard FL; this overhead results from local reputation calculation and the EXCHANGE\_FRAGMENTS protocol of FFL.}
\label{tab:runtime}
\resizebox{\textwidth}{!}{%
\begin{tabular}{|cl|ccc|ccc|ccc|ccc|}
\hline
\multicolumn{2}{|c|}{Benchmark}                                                                     & \multicolumn{3}{c|}{Adult-MLP}                                                            & \multicolumn{3}{c|}{MNIST-CNN}                                                            & \multicolumn{3}{c|}{CIFAR10-VGG16}                                                         & \multicolumn{3}{c|}{IMDB-BiLSTM}                                                           \\ \hline
\multicolumn{1}{|l|}{\multirow{2}{*}{\# of updates}} & \multicolumn{1}{c|}{\multirow{2}{*}{Method}} & \multicolumn{2}{c|}{S}                                               & P                  & \multicolumn{2}{c|}{S}                                               & P                  & \multicolumn{2}{c|}{S}                                                & P                  & \multicolumn{2}{c|}{S}                                                & P                  \\ \cline{3-14} 
\multicolumn{1}{|l|}{}                               & \multicolumn{1}{c|}{}                        & \multicolumn{1}{c|}{Dec.}               & \multicolumn{1}{c|}{Aggr.} & Mix.               & \multicolumn{1}{c|}{Dec.}               & \multicolumn{1}{c|}{Aggr.} & Mix.               & \multicolumn{1}{c|}{Dec.}               & \multicolumn{1}{c|}{Aggr.}  & Mix.               & \multicolumn{1}{c|}{Dec.}               & \multicolumn{1}{c|}{Aggr.}  & Mix.               \\ \hline
\multicolumn{1}{|c|}{\multirow{6}{*}{10}}            & FedAvg (FL)                                  & \multicolumn{1}{c|}{\multirow{5}{*}{0}} & \multicolumn{1}{c|}{0.001} & \multirow{5}{*}{0} & \multicolumn{1}{c|}{\multirow{5}{*}{0}} & \multicolumn{1}{c|}{0.001} & \multirow{5}{*}{0} & \multicolumn{1}{c|}{\multirow{5}{*}{0}} & \multicolumn{1}{c|}{0.064}  & \multirow{5}{*}{0} & \multicolumn{1}{c|}{\multirow{5}{*}{0}} & \multicolumn{1}{c|}{0.071}  & \multirow{5}{*}{0} \\ \cline{2-2} \cline{4-4} \cline{7-7} \cline{10-10} \cline{13-13}
\multicolumn{1}{|c|}{}                               & Median (FL)                                  & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.002} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.002} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.858}  &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.816}  &                    \\ \cline{2-2} \cline{4-4} \cline{7-7} \cline{10-10} \cline{13-13}
\multicolumn{1}{|c|}{}                               & TMean (FL)                                   & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.003} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.007} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{1.201}  &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.843}  &                    \\ \cline{2-2} \cline{4-4} \cline{7-7} \cline{10-10} \cline{13-13}
\multicolumn{1}{|c|}{}                               & MKrum (FL)                                   & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.004} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.013} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.822}  &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.690}  &                    \\ \cline{2-2} \cline{4-4} \cline{7-7} \cline{10-10} \cline{13-13}
\multicolumn{1}{|c|}{}                               & FGold (FL)                                   & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.01}  &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.017} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.497}  &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.256}  &                    \\ \cline{2-14} 
\multicolumn{1}{|c|}{}                               & FFL                                          & \multicolumn{1}{c|}{0.064}              & \multicolumn{1}{c|}{0.021} & 0.231              & \multicolumn{1}{c|}{0.113}              & \multicolumn{1}{c|}{0.016} & 0.578              & \multicolumn{1}{c|}{0.372}              & \multicolumn{1}{c|}{2.308}  & 1.106              & \multicolumn{1}{c|}{0.321}              & \multicolumn{1}{c|}{1.773}  & 1.081              \\ \hline
\multicolumn{1}{|c|}{\multirow{6}{*}{50}}            & FedAvg (FL)                                  & \multicolumn{1}{c|}{\multirow{5}{*}{0}} & \multicolumn{1}{c|}{0.002} & \multirow{5}{*}{0} & \multicolumn{1}{c|}{\multirow{5}{*}{0}} & \multicolumn{1}{c|}{0.002} & \multirow{5}{*}{0} & \multicolumn{1}{c|}{\multirow{5}{*}{0}} & \multicolumn{1}{c|}{0.194}  & \multirow{5}{*}{0} & \multicolumn{1}{c|}{\multirow{5}{*}{0}} & \multicolumn{1}{c|}{0.275}  & \multirow{5}{*}{0} \\ \cline{2-2} \cline{4-4} \cline{7-7} \cline{10-10} \cline{13-13}
\multicolumn{1}{|c|}{}                               & Median (FL)                                  & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.007} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.008} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{6.843}  &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{4.135}  &                    \\ \cline{2-2} \cline{4-4} \cline{7-7} \cline{10-10} \cline{13-13}
\multicolumn{1}{|c|}{}                               & TMean (FL)                                   & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.015} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.045} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{7.097}  &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{4.267}  &                    \\ \cline{2-2} \cline{4-4} \cline{7-7} \cline{10-10} \cline{13-13}
\multicolumn{1}{|c|}{}                               & MKrum (FL)                                   & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.014} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.015} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{7.044}  &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{5.657}  &                    \\ \cline{2-2} \cline{4-4} \cline{7-7} \cline{10-10} \cline{13-13}
\multicolumn{1}{|c|}{}                               & FGold (FL)                                   & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.042} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.035} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{1.609}  &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{1.129}  &                    \\ \cline{2-14} 
\multicolumn{1}{|c|}{}                               & FFL                                          & \multicolumn{1}{c|}{0.263}              & \multicolumn{1}{c|}{0.04}  & 0.239              & \multicolumn{1}{c|}{0.509}              & \multicolumn{1}{c|}{0.033} & 0.583              & \multicolumn{1}{c|}{1.875}              & \multicolumn{1}{c|}{4.726}  & 1.188              & \multicolumn{1}{c|}{1.612}              & \multicolumn{1}{c|}{3.536}  & 1.174              \\ \hline
\multicolumn{1}{|c|}{\multirow{6}{*}{100}}           & FedAvg (FL)                                  & \multicolumn{1}{c|}{\multirow{5}{*}{0}} & \multicolumn{1}{c|}{0.004} & \multirow{5}{*}{0} & \multicolumn{1}{c|}{\multirow{5}{*}{0}} & \multicolumn{1}{c|}{0.004} & \multirow{5}{*}{0} & \multicolumn{1}{c|}{\multirow{5}{*}{0}} & \multicolumn{1}{c|}{0.341}  & \multirow{5}{*}{0} & \multicolumn{1}{c|}{\multirow{5}{*}{0}} & \multicolumn{1}{c|}{0.517}  & \multirow{5}{*}{0} \\ \cline{2-2} \cline{4-4} \cline{7-7} \cline{10-10} \cline{13-13}
\multicolumn{1}{|c|}{}                               & Median (FL)                                  & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.015} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.013} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{16.582} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{8.926}  &                    \\ \cline{2-2} \cline{4-4} \cline{7-7} \cline{10-10} \cline{13-13}
\multicolumn{1}{|c|}{}                               & TMean (FL)                                   & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.035} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.111} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{16.645} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{8.929}  &                    \\ \cline{2-2} \cline{4-4} \cline{7-7} \cline{10-10} \cline{13-13}
\multicolumn{1}{|c|}{}                               & MKrum (FL)                                   & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.028} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.031} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{27.875} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{16.893} &                    \\ \cline{2-2} \cline{4-4} \cline{7-7} \cline{10-10} \cline{13-13}
\multicolumn{1}{|c|}{}                               & FGold (FL)                                   & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.086} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{0.063} &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{6.180}  &                    & \multicolumn{1}{c|}{}                   & \multicolumn{1}{c|}{2.273}  &                    \\ \cline{2-14} 
\multicolumn{1}{|c|}{}                               & FFL                                          & \multicolumn{1}{c|}{0.359}              & \multicolumn{1}{c|}{0.043} & 0.249              & \multicolumn{1}{c|}{1.01}               & \multicolumn{1}{c|}{0.035} & 0.594              & \multicolumn{1}{c|}{3.675}              & \multicolumn{1}{c|}{4.883}  & 1.319              & \multicolumn{1}{c|}{3.236}              & \multicolumn{1}{c|}{3.583}  & 1.282              \\ \hline
\end{tabular}%
}
\end{table*}

Table~\ref{tab:runtime} reports the CPU runtimes in seconds per training round for mixed update decryption, global reputation calculation and model aggregation on the server side, and local model computation, fragment exchanging and mixing on the participants' side. 
Note that the reported runtimes for exchanging and mixing fragments are the average for a single participant.
We computed the runtime for the three benchmarks with 10, 50 and 100 updates per training round to illustrate how the runtime scales with the number of updates.
On the server side,
we report the total runtime for all methods; in contrast,
on the participant side, we report 
the overhead (extra runtime)  with respect to standard FL. 

It can be seen that, as the number of updates and
the  model size increase, the FFL server's runtime 
grows less than for the other methods, which confirms 
our computation cost analysis
 of Appendix S.II-A in the supplementary materials. In particular, with CIFAR10-VGG16, 
FFL achieved the lowest runtime among all non-baseline methods. 
Furthermore, unlike FFL, the 
other methods are unable to thwart privacy attacks or provide adequate protection against security attacks. 

Regarding the runtime overhead incurred by each participant, the maximum runtime overhead resulting from exchanging and mixing fragments was 
about 1.319 seconds for the largest model we used, which was VGG16. Also, it is worth noting that the increase in the number of updates had little impact on the overhead of the participants because their computations 
essentially depend on the model dimensionality. 

Nevertheless, the FFL runtime is very small if we compare it with that of ~\cite{zhang2020batchcrypt}, which provides a level of privacy similar to ours but without being able to neutralize poisoned updates. Specifically, for an LSTM model containing only $4.02$ million parameters, ~\cite{zhang2020batchcrypt} report a runtime overhead for each participant of about $176$ seconds and a total runtime for the server of $174$ seconds to aggregate $50$ local updates. Note also that the hardware specifications of the computers employed by ~\cite{zhang2020batchcrypt} for the participants and the server are superior to ours. 
Therefore, the participants in FFL can turn a blind eye to the computational overhead they incur in exchange for protecting their privacy, countering security attacks and learning a more accurate global model.


\section{Conclusions and Future Work}
\label{sec:conclusion}

In this paper, we have presented \emph{fragmented federated learning} (FFL), a novel approach based on cooperation between participants in federated learning systems to preserve their privacy without renouncing robust and accurate aggregation of their updates to the global model. FFL offers a practical solution where participants privately and efficiently exchange random fragments of their updates before sending them to the server. We have also proposed a novel reputation-based defense tailored for FFL that builds trust in the participants based on the quality of the mixed updates they send and the fragments they exchange.
We have demonstrated that the proposed framework can effectively counter privacy and security attacks.
All the above is achieved while obtaining a global model's accuracy similar to that of standard FL (when no attack is performed) and imposing affordable communication cost and computation overhead on the participating parties.  
The efficiency of FFL makes it applicable to large-scale FL systems.

As future work, we plan to evaluate the robustness of FFL against backdoor attacks. Also, we plan to test its performance when working with non-identical and independently distributed (non-iid) data.


\section*{Acknowledgments}

Thanks go to Ashneet Singh for help with some figures. This research was funded by the European Commission (projects H2020-871042 ``SoBigData++'' and H2020-101006879 ``MobiDataLab''), the Government of Catalonia (ICREA Acad\`emia Prizes to J.
Domingo-Ferrer, and D. S\'anchez, FI grant to N. Jebreel), and the Spanish
Government (project RTI2018-095094-B-C21 ``Consent''). The authors are with the UNESCO Chair in Data Privacy, but the views in this paper are their own and are not necessarily shared by UNESCO.

\ifCLASSOPTIONcaptionsoff
  \newpage
\fi


