text:
\section*{Acknowledgements}
We thank Mathieu Andreux and Jean du Terrail whose comments helped improve and clarify this manuscript.

\section{Neural Networks Architectures}
\label{appendix:network_architecture}

In this appendix, we present the LeNet architecture used for experiments on MNIST (see Table~\ref{tab:LeNetArchitecture})
and the AlexNet architecture used for experiments on CIFAR-10
(see Table~\ref{tab:AlexNetArchitecture}).

\begin{table}[h!]
\centering
\begin{tabular}{lccccc}
\toprule
Layer Type & Filters & Kernel & Stride & Padding & Output Shape \\
\midrule
Conv2D+ReLU & 6 & (5,5) & (1,1) & (2,2) & $28 \times 28 \times 6$ \\
Max Pooling & & (2,2) & & & $14 \times 14 \times 6$ \\
Conv2D+ReLU & 16 & (5,5) & (1,1) &  & $10 \times 10 \times 16$ \\
Max Pooling & & (2,2) & & & $5 \times 5 \times 16$ \\
Flatten & & & & & $400$ \\
FC+ReLU & & & & & $120$ \\
FC+ReLU & & & & & $84$ \\
FC & & & & & $10$ \\
\bottomrule
\end{tabular}
\caption{Architecture of the LeNet used for experiments on MNIST.
\label{tab:LeNetArchitecture}}
\end{table}

\begin{table}[h!]
\centering
\begin{tabular}{lccccc}
\toprule
Layer Type & Filters & Kernel & Stride & Padding & Output Shape \\
\midrule
Conv2D+ReLU & 64 & (5,5) & (1,1) & (2,2) & $32 \times 32 \times 64$ \\
Max Pooling & & (3,3) & (2,2) & (1,1) & $16 \times 16 \times 64$ \\
\multicolumn{2}{l}{LocalResponseNorm} & & & & $16 \times 16 \times 64$ \\
Conv2D+ReLU & 64 & (5,5) & (1,1) & (2,2) & $16 \times 16 \times 64$ \\
\multicolumn{2}{l}{LocalResponseNorm} & & & & $16 \times 16 \times 64$ \\
Max Pooling & & (3,3) & (2,2) & (1,1) & $8 \times 8 \times 64$ \\
Flatten & & & & & $4096$ \\
FC+ReLU & & & & & $384$ \\
FC+ReLU & & & & & $192$ \\
FC & & & & & $10$ \\
\bottomrule
\end{tabular}
\caption{Architecture of the AlexNet used for experiments on CIFAR-10. The LocalResponseNorm layers have the following parameters: $size=4$, $\alpha=0.001/9$, $\beta=0.75$, $k=1$.
\label{tab:AlexNetArchitecture}}
\end{table}

\section{Privacy Proof of Secure Sum Algorithm}
\label{appendix:privacy-proof}

The privacy proof of the Secure Sum Algorithm (see Algorithm~\ref{algo:secure-sum})
is mainly based on the following lemma.

\begin{lemma}
Let $b \in \mathbb{Z}_m$. If $r$ is a uniform random element in $\mathbb{Z}_m$,
then $b+r$ is also a uniform random element in $\mathbb{Z}_m$
(even if $b$ is not a uniform random element in $\mathbb{Z}_m$).
\label{lemma:uniformly-random}
\end{lemma}

We will now prove Theorem~\ref{th:privacy}.

\begin{proof}
Let $A$ be an adversary controlling $p<S$ servers,
$Server_{j_1}$, \dots, $Server_{j_p}$, and
$q \leq C$ clients, $Client_{i_1}$, \dots, $Client_{i_q}$.
In this proof, we will use the following notations for
different sets of servers and clients,
\begin{align*}
    J &= \{j_1, ..., j_p\} \\
    \overline{J} &= \{j~|~ j \in [1, S] \text{ and } j \notin J\} \\
    I  &= \{i_1, ..., i_q\} \\
    \overline{I} &= \{i~|~i \in [1,C] \text{ and } i \notin I\}
\end{align*}
We will prove the privacy of our protocol in the ideal-real paradigm.
We will first describe the simulator $S_A$, who simulates the
view of the adversary $A$ in the ideal world.
Then, we will prove that the views of the adversary $A$
in the ideal world and in the real world are indistinguishable.
We will split the proof in three cases, depending on the number of
clients the adversary controls,
\begin{itemize}
    \item[I.] no clients ($q = 0$),
    \item[II.] at least one and up to $C-2$ clients ($1 \leq q \leq C-2$),
    \item[III.] all clients, or all clients except one ($C-1 \leq q \leq C$).
\end{itemize}

\vspace{1em}

\centerline{\textsc{Case I: $q = 0$}}

\noindent \textbf{Simulation}

$S_A$ picks $p \times C$ uniformly random vectors $\tilde{R}_{i,j}, \forall  (i,j) \in [1,C] \times J$ into  $\mathbb{Z}_m^n$ and sends them to the adversary $A$.

\noindent \textbf{Indistinguishability of Views}

We will now prove that the views of $A$ in the real world and in the ideal world are indistinguishable.
In the real world, the adversary $A$ receives from honest parties the following messages
$$\forall (i,j) \in [1,C] \times J, R_{i,j}$$
If $S \notin J$, then by construction,
$\forall (i,j) \in [1, C] \times J, R_{i,j}$
are independently and uniformly random in $\mathbb{Z}_m^n$
(see L.2 in Alg.~\ref{algo:secure-sum}).
Thus, the views of the adversary $A$ in the real world and in the ideal world are indistinguishable.

If $S \in J$, since $J \subsetneq [1, S]$, then $[1, S-1] \bigcap \overline{J}$ is not empty.
Let $j^*$ be one element of $[1, S-1] \bigcap \overline{J}$, and
with it rewrite $R_{i, S}$ as
\begin{equation}
    R_{i,S} = \left( X_i - \sum_{j \in [1, S-1] \backslash j^*} R_{i,j} \right)  - R_{i,j^*} \mod m.
\end{equation}
By construction, $ \forall i \in [1,C]$, the values $R_{i, j^*}$
are uniformly random in $\mathbb{Z}_m^n$
(see L.2 in Alg.~\ref{algo:secure-sum}).
By applying Lemma~\ref{lemma:uniformly-random},  $\forall i \in [1,C]$,
the values $R_{i, S}$ are uniformly random in $\mathbb{Z}_m^n$.

This proves that all messages received by $A$ are
independently and uniformly random in $\mathbb{Z}_m^n$, and
thus, the views of the adversary $A$ in the real world and
in the ideal world are indistinguishable.

\vspace{1em}

\centerline{ \textsc{Case II: $1 \leq q \leq C-2$} }

\noindent \textbf{Simulation}

$S_A$ picks $(C-q) \times p + (S-p)$ uniformly random vectors
into  $\mathbb{Z}_m^n$ noted
$\tilde{R}_{i,j}, \forall (i,j) \in \overline{I} \times J$
and $\tilde{R}_j, \forall j \in \overline{J}$
and sends them to the adversary $A$.

\noindent \textbf{Indistinguishability of Views}

In the real world, the adversary $A$ receives from honest parties the following messages:
$$\begin{cases}
R_{i,j}, \quad \forall (i,j) \in \overline{I} \times J \\
R_j, \quad \forall j \in \overline{J}
\end{cases}$$
With a similar proof to \textsc{Case I}, we can demonstrate that
$\forall (i,j) \in \overline{I} \times J$, the values $R_{i,j}$
are independently and uniformly random in $\mathbb{Z}_m^n$.
Now, let $i^*$ be an element in $\overline{I}$, where $\overline{I}$
is not empty because the adversary controlled at most $(C-2)$ clients.
Then, $\forall j \in \overline{J}$, we can rewrite $R_j$ as
\begin{equation}
    R_j = \left(\sum_{i \in [1,C] \backslash i^*} R_{i,j}\right) + R_{i^*,j} \mod m.
\end{equation}
By construction, for all $j \in \overline{J}$, $R_{i^*, j}$ are independently and uniformly random in $\mathbb{Z}_m^n$
(see L.2 in Alg.~\ref{algo:secure-sum}).
By applying Lemma~\ref{lemma:uniformly-random},
$\forall j \in \overline{J}$, the values
$R_j$ are uniformly random in $\mathbb{Z}_m^n$.

This proves that all messages received by $A$ are independently and
uniformly random in $\mathbb{Z}_m^n$, and
thus, the views of the adversary $A$ in the real world and in
the ideal world are indistinguishable.

\vspace{1em}

\centerline{\textsc{Case III: $C-1 \leq q \leq C$}}

Assume that the adversary controls all the clients ($q=C$).
Then, the adversary knows all inputs and outputs.
Thus, our protocol is private according to the privacy definition
outlined in Sec.~\ref{subsec:SMC}.

Now assume that the adversary controls all clients \emph{except}
the client $i^*$.
Then, the inputs of the parties controlled by the adversary are
$\{X_i\}_{i \in [1,C] \backslash i^*}$ and the outputs of the parties
controlled by the adversary are $X = \sum_{i \in [1, C]} X_i$.
The adversary can easily infer the input of the client $i^*$ as
$$X_{i^*} = X - \sum_{i \in [1,C] \backslash i^*} X_i \mod m.$$
Thus, the adversary cannot learn anything more, because they already know
everything.
Thus, our protocol is private according to the privacy definition in
Sec.~\ref{subsec:SMC}.

\end{proof}

\section{Practical Secure Aggregation \cite{PracticalSA_GIKM17} Communication Cost}
\label{appendix:PSA-CommCost}

The communication cost of the Practical Secure Aggregation protocol is presented in Section 7.1 of \cite{PracticalSA_GIKM17}.
For each federated round, each client transmits to the Server
$$2n \cdot a_K + (5n-4) \cdot a_S+m \lceil \log_2 R  \rceil \text{ bits},$$
where $n$ is the number of clients, $m$ is the number of trainable parameters, $a_K= 256$
is the number of bits in a public key, $a_S=256$ is the number of bits in an encrypted share,
and $\mathbb{Z}_R$ is the field in which all operations are evaluated.
And at the end of the federated round, the server transmits the aggregated model parameters to each client
at a cost of $m \lceil \log_2 R  \rceil \text{ bits}$.
Thus, the total communication cost for one federated round is equal to
$$n \cdot (2n \cdot a_K + (5n-4) \cdot a_S+ 2m \lceil \log_2 R  \rceil) \text{ bits}.$$

Using our notation, the total communication cost for a single federated round is thus given as
$$C \cdot (2C \cdot a_K + (5C-4) \cdot a_S+ 2N \lceil \log_2 R  \rceil) \text{ bits},$$
where $C$ is the number of clients, $N$ is the number of trainable parameters and $\mathbb{Z}_R$ is the field in which all operations are evaluated.

\section{Further details on \texttt{SecureUnion} protocol}
\label{appendix:secure_union}

Let us first recall the setup of the \texttt{SecureUnion} protocol (Alg.~\ref{algo:secure-union}).
Each client $i$ owns a list of indices $V_i \subset [1,N]$, and together
they would like to securely evaluate the union of the list of indices $\bigcup_{i=1}^C V_i$.
To accomplish this, each client $i$ creates a vector $A_i$ representing $V_i$
such that $\forall k \in [1,N]$,
\begin{equation}
    A_i[k]=\begin{cases}
        R_{i,k}, & \text{ if } k \in V_i, \text{ where } R_{i,k} \in_R \mathbb{Z}_{2^q}^*, \\
        0, & \text{ otherwise }.
    \end{cases}
\end{equation}
The clients and the servers then securely evaluate $A = \sum_{i=1}^C A_i \mod 2^q$.
Finally, each client infers the union of indices from $A$ as
\begin{equation}
    V = \{k \in [1, N] | A[k] \neq 0\}
\end{equation}
As we will explore in the following sections, this inference of the union
of indices for the \texttt{SecureUnion} is only an approximation $V \approx \bigcup_{i=1}^C V_i$.

For the analysis of the \texttt{SecureUnion} protocol, let us assume that
each client $i$ has selected independently and uniformly at random their
list of $k$ indices $V_i \subset [1,N]$,
then, for each client the probability of selecting the index $x \in [1, N]$ is
equal to $\nicefrac{k}{N}$ and the probability of not selecting the index $x$ is equal
to $\nicefrac{N-k}{N}$.
Thus, under these assumptions, the probability that exactly $t$ clients have
selected the index $x \in [1,N]$ is
\begin{equation}
    P(N, k, C, t) = \binom{C}{t} \left( \frac{k}{N} \right)^t \left( \frac{N-k}{N} \right)^{C-t}.
\end{equation}

\subsection{Expected number of false negatives}

When using the \texttt{SecureUnion} protocol, the resulting union is approximate as it
may contain a number of false-negatives.
Specifically, when at least two clients have selected the same index
$x$, $\sum_{i=1}^C A_i[x] \mod 2^q$ will be equal to 0 with probability $\nicefrac{1}{2^q}$,
causing the index $k$ to be omitting from $V$ whereas it should be present.

Let us analyze the average number of false negatives caused by the \texttt{SecureUnion} protocol.
False negatives occur only when at least 2 clients have selected the same index.
The probability that at least 2 clients have selected the same index $x \in [1,N]$ is equal to
\begin{equation}
    \text{Pr}[t \geq 2 | N, k, C] = 1 - P(N, k, C, 0) - P(N, k, C, 1).
\end{equation}

When one index is selected by at least 2 clients, the probability to obtain a false negative
for this index is equal to $\nicefrac{1}{2^q}$.
Thus, the expected number of false negatives in $V$ is given by
\begin{equation}
    N \times P[t \geq 2 | N, k, C] \times \frac{1}{2^q}.
\end{equation}

The Table~\ref{tab:false_negatives} presents the average amount of false negatives in the \texttt{SecureUnion} protocol for different parameters.

\begin{table}[!h]
    \centering
    \begin{tabular}{S[table-format=7.0]S[table-format=1.2]S[table-format=6.0]S[table-format=1.0]S[table-format=1.0]S[table-format=3.0]}
        \toprule
        {$N$} & {$\rho$} & {$k=\lfloor N \cdot \rho \rfloor$} & {$C$} & {$q$} & {$\mathbb{E}~(\text{\# false negatives})$}\\
        \midrule
        61706 & 0.1 & 6170 & 5 & 1 & 2513 \\
        61706 & 0.1 & 6170 & 5 & 5 & 157 \\
        61706 & 0.1 & 6170 & 5 & 10 & 5 \\
        \midrule
        61706 & 0.02 & 1234 & 5 & 1 & 119 \\
        61706 & 0.02 & 1234 & 5 & 5 & 7 \\
        61706 & 0.02 & 1234 & 5 & 10 & 0 \\
        \midrule
        1756426 & 0.1 & 175642 & 5 & 1 & 71539 \\
        1756426 & 0.1 & 175642 & 5 & 5 & 4471 \\
        1756426 & 0.1 & 175642 & 5 & 10 & 140\\
        \bottomrule
    \end{tabular}
    \caption{Average amount of false negatives in the \texttt{SecureUnion} protocol.
    \label{tab:false_negatives}}
\end{table}

\subsection{One client learns that he alone has selected a given index}

When using the \texttt{SecureUnion} protocol, one client can learn that with high probability
that he alone has selected one index.
Specifically, if one client $i$ observes that $A[x] = R_{i,x}$, then the client
can infer with very high probability he alone has selected this index $x$.

Let us assume the client $i$ observes that $A[x] = R_{i,x}$ for one index $x \in [1,N]$.
The client $i$ is not alone to have selected this index $x$, when at least two other
clients have selected this index $x$ and the sum of the random values
$R_{i,x}$ selected by these other clients is equal to 0 in $\mathbb{Z}_{2^q}$.

The probability that at least two other clients have selected this index $x$
is equal to $\text{Pr}[t\geq 2 | N, k, C-1]$.
When several clients have selected this index $x$,
the sum of their random values $R_{i,x}$ will be equal to 0 with probability $1/2^q$.
Finally, if one client $i$ observes that $A[x] = R_{i,x}$, then the client can
infer that with probability $1 - \frac{1}{2^q}~\text{Pr}[t \geq 2 | N, k, C-1]$ that he alone has selected this index $x$.
This probability is evaluated for some parameters in Table~\ref{tab:alone_select_index}.

\begin{table}[!h]
    \centering
    \begin{tabular}{S[table-format=7.0]S[table-format=1.2]S[table-format=6.0]S[table-format=1.0]S[table-format=1.0]S[table-format=2.2]}
        \toprule
        {$N$} & {$\rho$} & {$k=\lfloor N \cdot \rho \rfloor$} & {$C$} & {$q$} &  {Probability}\\
        \midrule
        61706 & 0.1 & 6170 & 5 & 1 & 97.39\% \\
        61706 & 0.1 & 6170 & 5 & 5 & 99.84\% \\
        61706 & 0.1 & 6170 & 5 & 10 & 99.99\% \\
        \midrule
        61706 & 0.02 & 1234 & 5 & 1 & 99.88\% \\
        61706 & 0.02 & 1234 & 5 & 5 & 99.99\% \\
        61706 & 0.02 & 1234 & 5 & 10 & 99.99\% \\
        \midrule
        1756426 & 0.1 & 175642 & 5 & 1 & 97.39\% \\
        1756426 & 0.1 & 175642 & 5 & 5 & 99.84\% \\
        1756426 & 0.1 & 175642 & 5 & 10 & 99.99\% \\
        \bottomrule
    \end{tabular}
    \caption{If one client $i$ observes that $A[x] = R_{i,x}$, we evaluate the probability that this client alone has selected this index $x$.
    \label{tab:alone_select_index}}
\end{table}

\section{Further details on \texttt{TopBinary} Aggregation}
\label{appendix:separate-aggregation}
Let us first recall the setup  for the aggregation.
Let us proceed by assuming that we want to
operate on the aggregation of some real-valued vectors
$X_i \in \mathbb{R}^N$, of which we have $C$ different
realizations. From each of these vectors, we calculate one
new vector and one scalar value,
\begin{align}
    D_i &= {\rm sgn}\circ\text{Top-}k(X_i) ,\\
    \alpha_i &= \frac{||X_i||_2}{||D_i||_2},
\end{align}
such that $||\alpha_i D_i||_2 = ||X_i||_2$.
Because of the ${\rm sgn}\circ\text{Top-}k$ operation, the result \emph{sign} vector belongs
to the space $D_i \in \{-1, 0, 1\}^{N}$, as each entry can only take
one of these three values. Now, since the value of $k$ is fixed for the entire
federated optimization across all workers,
we know, trivially, the number of non-zero entries: $k$.  And, since
the non-zero entries are $\pm 1$, we know
$||D_i||_2 = \sqrt{k} \quad \forall i$,
thus
\begin{equation}
    \alpha_i = \frac{1}{\sqrt{k}} ||X_i||_2.
\end{equation}

Let us now define the different variants of the aggregation again,
\begin{align}
    \bar{D} &= \frac{1}{C}\sum_{i=1}^C \alpha_i D_i  \notag \\
            &= \frac{1}{C\sqrt{k}} \sum_{i=1}^C L_i D_i, \tag{\texttt{DirectAgg}}\\
    \tilde{D} &= \frac{1}{C^2}\sum_{i=1}^C \alpha_i \sum_{i=1}^C D_i \notag \\
                  &= \frac{1}{C \sqrt{k}}\cdot\frac{1}{C}\sum_{i=1}^C L_i \cdot \sum_{i=1}^C D_i, \tag{\texttt{SepAgg}}
\end{align}
where $L_i \triangleq ||X_i||_2$ is the Euclidean norm of the original
vector $X_i$. Our desire is to compute the value of $\bar{D}$,
however, for the efficiency of SMC, we may only make use of
the estimate $\widetilde{D}$.
Given this, how far off will we be,
and what are the effects of using such an estimate?

Let $\widetilde{L} \triangleq \frac{1}{C}\sum_{i=1}^C L_i$, i.e. the average norm
of all of the original vectors $X_i$, then
\begin{align}
    \widetilde{D}
        &= \frac{\widetilde{L}}{\sqrt{k}} \cdot \frac{1}{C} \sum_{i=1}^C D_i, \\
        &= \frac{1}{C\sqrt{k}} \sum_{i=1}^C \widetilde{L} D_i,
\end{align}
where we can see that the average norm $\widetilde{L}$ serves as an approximation
for the individual norms $L_i$. When using this norm, we can see the MSE difference
between the \texttt{SepAgg} and \texttt{DirectAgg} as
\begin{align}
||\bar{D} - \widetilde{D}||_2^2 &=
    \frac{1}{C^2 k} \sum_{j=1}^N \left( \sum_{i=1}^C(L_i - \widetilde{L}) D_i[j]\right)^2,
\end{align}
which shows us that if the expectation of the difference $L_i - \widetilde{L}$ is small,
we can expect that the \texttt{SepAgg} will be an adequate estimation of the
direct aggregation.

\section{Background}
\label{sec:background}

\subsection{Federated Learning}

\subsubsection{Collaborative (or Cross-Silo) Setting}
Many current FL works in the growing body of literature, such as~\cite{BEG2019},
study massive-scale use cases where a multitude of different mobiles
participate to the training.
In contrast, in this manuscript, we focus on collaborative FL applied to
medical use cases, e.g. clinical research.
In this context, we assume the following settings:
\begin{itemize}
    \item A small number of participants (generally less than 10) takes part in the federated training.
    \item Participants are able to obtain useful trained models from only their own local dataset, but they would like to augment their performance through collaboration.
    \item Unlike the mobile device use-case, all clients are able to participate in each round with
    robust connectivity to the system.
    This robustness obviates the need for secure protocols designed specifically to be dropout-resilient, such as the ones proposed in~\cite{PracticalSA_GIKM17}.
\end{itemize}

\subsubsection{Federated Optimization}
When approaching machine learning through the lens of empirical risk minimization, we desire to train a
model parameterized by the set of its coefficients $\theta$, so as to minimize a loss over available
training data samples $\mathcal{D}$,
\begin{equation}
    \mathcal{L}(\mathcal{D}, \theta) = \frac{1}{|\mathcal{D}|} \sum_{(x,y)\in\mathcal{D}} \ell(x, y, \theta),
    \label{eq:erm}
\end{equation}
where $\ell(\cdot,\cdot, \cdot)$ is a sample-specific loss, $(x, y)$ represents the model inputs and outputs,
respectively, and $|\mathcal{D}|$ is a count of the number of data samples.

In FL, we would like to obtain a single trained model from some datasets
held by $C$ clients, $\mathcal{D}_i~\forall i \in [1,C]$, without moving
these datasets to a single location for training.
When training a single model over this set of datasets,
the \emph{federated} loss can be written simply as
\begin{equation}
    \mathcal{F}(\left\{  D_i \right\}, \theta) =
        \sum_{i=1}^C \frac{|\mathcal{D}_i|}{N}~\mathcal{L}_i(\mathcal{D}_i, \theta),
\label{eq:federated-loss}
\end{equation}
where $\mathcal{L}_i$ is the loss of client $i$ defined as in \eqref{eq:erm},
and $N \triangleq \sum_{i=1}^C |\mathcal{D}_i|$ is the number of data samples in
all datasets, which is used to weigh the per-client losses according to the
relative size of participant datasets\footnote{%
    This approach was proposed in~\cite{FL_MMRA16}, however, such weightings can
    be adapted according to the application.
}. Critically, \eqref{eq:federated-loss} can be evaluated locally at each client $i$,
and then aggregated to obtain the federated loss.

While \eqref{eq:federated-loss} can be easily optimized via a batch-distributed
stochastic gradient descent, this is not commonly applied in practical federated
systems, owing to the high degree of communication required for
per-batch synchronization.
The Federated Averaging (\texttt{FedAvg}) introduced by~\cite{FL_MMRA16},
also known as local SGD,
is the most commonly
used strategy in practice, which instead proposes a synchronized averaging of client models (or their updates)
after a pre-determined number of local update steps.
In this algorithm, within each \emph{federated round}, denoted by $r$,
each selected participating client $i$ is provided with the current global model state
$\theta^{(r)}$, and the following steps are carried out at each client, where
$\text{Opt}_E(\cdot)$ represents an $E$-step optimization procedure minimizing \eqref{eq:erm},
\begin{align}
    &\theta_i^{(0)} \gets \theta^{(r)} \tag{Local Initial State}, \\
    &\theta_i^{(E)} \gets \text{Opt}_E(\theta_i^{(0)}, \mathcal{D}_i) \tag{Local Training}\\
    &U_i^{(r)} \gets \theta_i^{(E)} - \theta_i^{(0)} \tag{Local Update},
\end{align}
with thes final updates being transmitted to a central \emph{aggregator} who is responsible
for maintaining and updating the global model state,
\begin{align}
    \theta^{(r+1)} \gets  \theta^{(r)} + \sum_{i=1}^{C}\frac{|\mathcal{D}_i|}{N}~U_i^{(r)}. \tag{Aggregate \& Update}
\end{align}
Many federated rounds are computed in sequence until the global model state converges or
meets some desired performance metric.
Because multiple local update steps are used, \texttt{FedAvg}
does not optimize \eqref{eq:federated-loss} for $E>1$.
Thus, there is no guarantee that such an algorithm converges, or provides an acceptable solution,
in general~\cite{heterogeneity_SLSZ18,SCAFFOLD_KKMRSS19}.
The trade-off for \texttt{FedAvg}, then, is to select a large enough $E$ so as to reduce
the number of federated rounds required (and therefore communication and coordination overhead) to
reach a desired performance metric, but not so large that the algorithm fails to converge.

\subsubsection{Communication-Efficient FL}
While \texttt{FedAvg} addresses communication-efficiency by reducing the number of required data exchanges,
it does not address the size of the model update messages communicated within that round.
In computer vision and natural language tasks, neural architectures can often be quite large,
comprising many tens of thousands, or millions of parameters.
In the application of FL to problems in medical imaging (e.g. volumetric segmentation), such large model sizes are ubiquitous
~\cite{UNet_SLBR16}.
During one aggregation phase, each participant sends its local model update to the aggregator and the aggregator sends back to each participant the aggregated model update.
Since the size of a local model update is of the same dimensionality as the original model,
the aggregation phase of federated rounds represents a significant bandwidth cost,
and therefore a limitation in the practicality of conventional \texttt{FedAvg}
for such use cases.

Over the past several years, speeding distributed large model training has been a topic of focus of works such as
\cite{SFD2014, Sto2015, SparseBinaryCompression_SWMS18, DoubleSqueeze_TYLZ19}.
These approaches show that there exists an
inherent compressibility in model updates which can be exploited to reduce the communication costs
of distributed training while retaining the predictive accuracy of the final model.
In the case of
~\cite{SFD2014}, this was evidenced by the ability to encode gradients using only the direction
(sign) of each coefficient.
In~\cite{Sto2015}, this approach was further enhanced by demonstrating that very
few of these components carry significant information, and many can be discarded, resulting
in a so-called \emph{ternary} coding of the model update~\cite{TernGrad_WXYW17}.
Both of these approaches made use of an \emph{error compensation} (EC) scheme to stabilize training with quantized and compressed model updates.
EC has been studied analytically in~\cite{ErrorFeedback_KRSJ19,SparsifiedSGD_SCJ18}, where it is shown that even when used
in conjunction with arbitrary biased lossy compression schemes,
the convergence rate of the optimization remains the same as uncompressed stochastic gradient descent.
Recent works such as~\cite{SparseBinaryCompression_SWMS18, DoubleSqueeze_TYLZ19}
have demonstrated the utility of such model update compression schemes in practical federated settings.

\subsubsection{Privacy Risks of Sharing Local Updates}
Even if the training data are not shared in FL, the training data are not safe during an FL training due to the sharing of intermediate model parameters, which may leak sensitive information.
There exist many attacks based on the knowledge of the model parameters such as membership inference \cite{MembershipInference_SZM19,MembershipInference_SDSO19} or data reconstruction attacks \cite{DLG_ZLH19,iDLG_ZMB20} and new attacks are regularly created.
Membership inference attack consists to create an oracle that given a sample, answers whether this sample has been used during the training.
In data reconstruction attacks, the goal of the attacker is to reconstruct the data used to train the model.
To conclude, it is essential to restrict the amount of visible intermediate
training information, through techniques such as secure aggregation, to reduce the
effectiveness of such attacks in revealing sensitive or identifying information
about the training data.

\subsection{Secure Multiparty Computation}
\label{subsec:SMC}

SMC is a subfield of cryptography which allows several parties to jointly
evaluate a function over their inputs while keeping these inputs private.
Many protocols exist in this field, such as Yao garbled circuit \cite{Yao86} and secret sharing \cite{SS_RST79}.
These protocols have different trade-offs between the computation cost,
the communication costs,  and the number of required communication rounds.
The computation cost is dominated by the number of expensive cryptographic operations.

\subsubsection{Security Definitions}
A SMC protocol is determined to be secure if the two following requirements are met.
\begin{itemize}
\item \emph{Correctness}. The output of the protocol is correct for the desired secure operation.
\item \emph{Privacy}. Each party will learn their output and nothing else, except what they can infer from
their own input and their own output.
\end{itemize}

Different kinds of adversaries are traditionally considered:
\begin{itemize}
    \item \emph{Semi-honest adversaries} follow the protocol but try to infer as much information as possible from
the observed messages,
    \item \emph{Malicious adversaries} can use any kind of strategy to learn information,
    \item \emph{Covert adversaries} are malicious but do not wish to be caught,
    \item \emph{Static adversaries} select the parties to corrupt at the beginning of the protocol execution. The set of corrupted parties is fixed for the whole protocol execution,
    \item \emph{Adaptive adversaries} may select the corrupted parties during the protocol execution. The selection of the corrupted parties may be based on what the adversary learns during the protocol execution.
\end{itemize}
In this paper, we only take into account semi-honest or malicious, \emph{static} adversaries.

\subsubsection{Real-world/ideal-world simulation}

A real-world/ideal-world simulation game~\cite{SimulationGame_L17} is traditionally used to prove the privacy of a SMC protocol.
The goal is to prove that whatever can be computed by an adversary $A$ during the protocol can also be computed
from only the inputs and outputs of the parties controlled by this adversary noted $Inputs_A$ and $Outputs_A$.
To do that, we have to define a simulator $S_A$ who only knows $Inputs_A$ and $Outputs_A$
and who generates the view of all parties controlled by the adversary in the execution.
The protocol is private if for all adversarial behaviors in a real execution, there exists a simulator such that
the view of the adversary in the real execution and in the simulated execution called ideal execution are indistinguishable.

As we later show in Section~\ref{subsec:secure_aggregation}, our proposed method is private against malicious adversaries and correct against semi-honest adversaries.
Thus, a malicious adversary cannot learn information
about the input data of honest parties,
but they can modify messages such that the output is incorrect.
A malicious adversary may also abort during the protocol and then,
the protocol will be stopped and no party will obtain the final trained model.
In collaborative FL use cases, data owners benefit from the trained global model and therefore
do not want to reduce their own performance.
Therefore, semi-honest correctness is sufficient for our use case.
In addition, all participants have an incentive to try to obtain information about data held by other participants.
Hence, our protocol must be private against malicious adversaries.

\subsection{Notation}
In this paper, $[a,b]$ represents the set of integers $\{a, a+1, ..., b\}$.
$\mathbb{Z}_m$ (resp. $\mathbb{Z}_m^*$) is isomorphic to $[0, m-1 ]$ (resp. $[1, m-1]$).
The space of vectors of length $n$ whose components belong to $\mathbb{Z}_m$
is represented by $\mathbb{Z}_m^n$.
The notation $x \in_R S$ indicates that $x$ is sampled uniformly at random from the finite set $S$.
And when $x \in_R \mathbb{Z}_m ^n$, all coordinates of $x$ are sampled independently and uniformly at random from $\mathbb{Z}_m$.
The notation $S \backslash i$ represents the set $S$ deprived of the element $i$
$$S \backslash i = \{k \in S~|~ k \neq i\}$$

We also introduce some notations related to the federated system:
\begin{itemize}
\item $N$ --  number of trainable parameters of the neural network, equivalent to the length of the vector of updates
sent by each client to the aggregation server,
\item $C$ -- number of clients participating in the federated system,
\item $R$ -- number of federated rounds, which is equal to the number of aggregations.
\end{itemize}

\subsection{Fixed-Point Representation}
While ML models are very often parameterized by floating-point values, SMC protocols do not support floating-point values for computation.
Thus, a fixed-point representation is required to represent these real values into integers.
Furthermore, SMC operations are applied in a finite field (e.g. $\mathbb{Z}_q$).
Parameters of the fixed-point representation and the finite field should be selected with attention in order to avoid overflows during secure computation.

In our secure aggregation protocol, the fixed point representation is only used to convert \emph{positive} real values into integers.
In this manuscript, we use an adaptation of the fixed-point representation presented in~\cite{FixedPoint_CDNR20} to \emph{positive} real values.
Each \emph{positive} real value $x \in \mathbb{R}^+$ is converted into $Q(x) \in \mathbb{Z}_{2^{\lambda}}$ such that
\begin{equation}
    Q(x) = \lfloor 2^a \cdot x \rfloor \mod 2^{\lambda}.
\label{eq:fixed-point-represention}
\end{equation}
The integer $\lambda$ corresponds to the number of bits used to represent $x$ and the integer $a$ corresponds to the number of bits used to represent only the fractional part of $x$.
With this approach, larger is the value of $a$, the more accurate is the fixed-point representation, but
also the more bits are required to store all possible states.

In practice, all values $x$ (inputs, intermediate results and outputs) belong to a finite interval.
The integer $a$ is selected according to the wanted floating point precision.
To avoid overflow issues, the value of $\lambda$ is set according to the largest value resulting from any step in the secure computation.

\section{Conclusion}

In this article, we design a secure and efficient protocol for federated learning.
This protocol is based on quantization to highly reduce the communication cost of the aggregation
without compromising accuracy.
We adapt quantizated federated learning techniques to secure computation in order to be able
to efficiently and securely evaluate the aggregation steps during a federated training.
Thanks to these adaptations, our secure aggregation protocol relies only on
additions (no expensive cryptographic operations are used) and thus has a
very low computation cost.
Given that our secure aggregations is only based on additions, it can
be easily implemented by non-cryptographic experts.
We also prove that our protocol is private against malicious
adversaries and correct against semi-honest adversaries.
Finally, our experiments show the efficiency of our protocol in real use cases.
Compared to prior works, our protocol has a lower computation cost
(because no expensive operations are used)
and has a lower communication cost thanks to model update compression and lightweight SMC protocols.

Future works could study in detail the different compression approaches
to further reduce the communication cost.
Moreover, our work does not investigate  information leakage from aggregated compressed
updates, which remains for future works. Finally, we note that there still exist large
communication differences between the different security profiles of the secure
union techniques we propose. It would be of interest for future works to find
better trade-offs in the security perimeter of such protocols against communication
requirements.

\section{Experiments}
\label{sec:experiments}

For our experimental evaluation, we chose $C = 5$ and $S = 2$ to demonstrate
a moderately sized collaborative federated system.

\subsection{Datasets and Model Architectures}
To demonstrate the utility of our proposed approaches, we conduct a series
of image classification experiments on MNIST~\cite{MNISTdatabse}
and CIFAR-10~\cite{CIFAR10database}. For client data, we use
i.i.d. dataset partitions to mimic clients holding data samples from
the same data distribution\footnote{%
    While such homogeneity cannot be expected in practice, we control for inter-client
    heterogeneity as this aspect is out of the scope of the current work.
}. Both of these datasets represent basic image recognition tasks, namely,
handwritten digit and natural image classification, respectively.
For MNIST experiments, the 70,000 image dataset is randomly shuffled
and then partitioned into a training dataset of 50,000 samples,
a test dataset of 10,000 samples, and a validation dataset of 10,000 samples.
Then, the training dataset is partitioned into five sets, and each is given to one
of the $C=5$ clients, thus we have 10,000 samples per client.
We conduct the same dataset partition procedure for CIFAR-10,
however as the training dataset contains 40,000 samples,
each client is given only 8,000 samples.

For our MNIST experiments, we train a simple LeNet-5 network~\cite{LeNet_LBBH98} for
the task of digit classification.
This architecture is detailed in Table~\ref{tab:LeNetArchitecture} in Appendix~\ref{appendix:network_architecture} and
consists of  $N = 61,706$ trainable parameters.
For CIFAR-10, we train the same AlexNet~\cite{AlexNet_KSH17} architecture as demonstrated in the original
\texttt{FedAvg} work~\cite{CommEfficient_MMRH17}.
We also utilize the same image preprocessing
pipeline as was proposed in this work, e.g.
random flipping,
and normalization.
This AlexNet CNN is detailed in Table~\ref{tab:AlexNetArchitecture}
in Appendix~\ref{appendix:network_architecture} and consists of $N = 1,756,426$ trainable parameters.

The goal of our experiments is to demonstrate that with our proposed method,
compared to \texttt{FedAvg}~\cite{FL_MMRA16} with no compression,
we obtain a computation and communication efficient secure aggregation
without compromising accuracy. We note that more modern neural architectures could be
utilized, as well as larger datasets across more varied tasks. However, as our approach
is agnostic to the underlying task, we utilize these simpler ML experiments for the sake of
clarity of our demonstration.

\subsection{Hyperparameter Selection}
Before conducting federated training on our partitioned MNIST and CIFAR-10 datasets,
we must first select the local model training parameters to use at each client.
To find appropriate settings for these hyperparameters,
we performed a grid search on the entire training dataset without FL (i.e. a single client),
evaluating performance on the held-out validation dataset.
While this approach cannot be utilized in a practical FL use-case, it represents a best-case
hyperparameter selection technique, and we fix the hyper-parameter setting across all
approaches. We consider optimal hyperparameter tuning across federated data out of the scope of this work.
Table~\ref{tab:parameters_without_FL} presents the selected model training hyperparameters used for
experimentation.

\begin{table}[h!]
\centering
\begin{tabular}{ccS[table-format=1.2]S[table-format=2.0]S[table-format=0.1]S[table-format=2.1]}
\toprule
Dataset & Network & {LR} & {Batch} & {Momentum} & {Acc. (\%)}\\
\midrule
   MNIST & LeNet-5      & 0.01 & 64 & 0.9 & 99.2 \\
CIFAR10 & AlexNet &  0.10  & 64 &   0.0 & 80.6 \\
\bottomrule
\end{tabular}
\caption{%
    Selected hyperparameters obtained with grid search for classical
    single-dataset training~\label{tab:parameters_without_FL}.
}
\end{table}

\subsection{Targeted accuracy}
One of main constraints is to not compromise the prediction performance obtained using our
proposed techniques in comparison to non-secure non-compressed \texttt{FedAvg}.
Table~\ref{tab:FedAvg_baseline} presents the accuracy obtained with non-secure non-compressed \texttt{FedAvg}
training on five clients with the selected hyperparameters from Table~\ref{tab:parameters_without_FL}.
Here, $E$ represents the number of local updates performed within each federated round, i.e.
between two successive aggregations.
From this table, we selected a desired performance level to achieve:
$98\%$ accuracy for MNIST and $80\%$ accuracy for CIFAR-10.

\begin{table}[h!]
\centering
\begin{tabular}{ccS[table-format=3.0]S[table-format=3.0]S[table-format=2.1]}
    \toprule
    Dataset & Network & {$E$} & {Epochs} & {Acc. (\%)} \\
    \midrule
    MNIST & LeNet-5 &  10 & 50 & 98.9 \\
    MNIST & LeNet-5 & 100 & 50 & 99.0 \\
    \midrule
    CIFAR-10 & AlexNet &  10 & 150 & 81.2 \\
    CIFAR-10 & AlexNet & 100 & 150 & 81.3 \\
    \bottomrule
\end{tabular}
\caption{%
    Accuracy reached on MNIST and CIFAR-10 with
    \texttt{FedAvg} over five clients with the selected hyperparameters.
    \label{tab:FedAvg_baseline}
}
\end{table}

\subsection{Results}
\begin{table*}[t!]
\centering
\begin{tabular}{lcS[table-format=3.0]S[table-format=3.0]S[table-format=2.1]S[table-format=5.0]S[table-format=4.2]l}
    \toprule
    {Strategy} & {Sec. Agg.} & {E} & {$R$} & {$\rho$} & {$\mathbb{E}~|V|$} & {Comm. (MB)} & {Expensive Operations} \\
    \midrule
    \texttt{FedAvg} & {\xmark} &  10 &   129 & {-} &  {-}  & 303.65 & Additions \\
    \midrule
    \cite{PracticalSA_GIKM17} & {\cmark} & 10 & 129 & {-} & {-} & 304.16 & Asymmetric encryption, PRG \\

    \cite{EaSTLy_DCSW20} with TSS & {\cmark} & 10 &  478 & {-} &  {-}  & 281.29 & Polynomial interpolation \\

    \cite{EaSTLy_DCSW20} with HE  & {\cmark} & 10 & 478 & {-} &  {-}  & 2250.33 & Paillier HE \\

    \midrule
    Our method w/  \texttt{NoUnion} & {\cmark} & 10 & 478 & 0.02 & {-}  & 281.33 & Additions \\

    Our method w/ \texttt{SecureUnion} (q=5) & {\cmark} & 10 & 396 & 0.02 & 4804  & 309.47 & Additions \\
    Our method w/ \texttt{SecureUnion} (q=10) & {\cmark} & 10 & 436 & 0.02 & 4856  & 661.66 & Additions \\

    Our method w/ \texttt{PartialSecureUnion} & {\cmark} & 10 & 478 & 0.02 & 4865  & 233.18 & Additions \\

    Our method w/  \texttt{PlaintextUnion} & {\cmark}  & 10 & 478 & 0.02  & 4865 & 57.38 & Additions \\

    \midrule
    \midrule
    \texttt{FedAvg} & {\xmark}  & 100 &  15 &   {-} &     {-} & 35.31 & Additions \\

    \midrule
    \cite{PracticalSA_GIKM17} & {\cmark} & 100 &   15 & {-}  &  {-} & 35.37 & Asymmetric encryption, PRG \\

    \cite{EaSTLy_DCSW20} with TSS & {\cmark} & 100 & 17 &  {-} &  {-} & 10.00 & Polynomial interpolation \\

    \cite{EaSTLy_DCSW20} with HE & {\cmark} & 100 &   17 &  {-} &  {-}  & 80.03 & Paillier HE \\

    \midrule
    Our method w/ \texttt{NoUnion} & {\cmark} & 100 &    17 & 0.10 &  {-} & 10.01 & Additions \\

    Our method w/ \texttt{SecureUnion} (q=1) & {\cmark} & 100 &    22 & 0.10 & 14344  & 6.25 & Additions \\
    Our method w/ \texttt{SecureUnion} (q=5) & {\cmark} & 100 &    17 & 0.10 &  18037 & 15.43 & Additions \\
    Our method w/ \texttt{SecureUnion} (q=10) & {\cmark} & 100 &    17 & 0.10 & 18127  & 27.95 & Additions \\

    Our method w/ \texttt{PartialSecureUnion} & {\cmark} & 100 & 17 & 0.10 & 18253 & 10.46 & Additions \\

    Our method w/ \texttt{PlaintextUnion} & {\cmark} & 100 &    17 & 0.10 & 18253 & 4.21 & Additions \\

   \bottomrule
\end{tabular}\\
\vspace{1ex}
(a) LeNet on MNIST (98\% Acc. Target) \\
\vspace{3ex}
\begin{tabular}{lcS[table-format=3.0]S[table-format=3.0]S[table-format=2.1]S[table-format=6.0]S[table-format=4.2]l}
    \toprule
    {Strategy} & {Sec. Agg.} & {E} & {$R$} & {$\rho$} & {$\mathbb{E}~|V|$} & {Comm. (GB)} & {Expensive Operations} \\

    \midrule
    \texttt{FedAvg} & {\xmark} & 100 &  101 &   {-} &  {-} & 6.61 & Additions \\

    \midrule
    \cite{PracticalSA_GIKM17} & {\cmark} & 100 & 101 &  {-} &  {-} & 6.61 & Asymmetric encryption, PRG \\

    \cite{EaSTLy_DCSW20} with TSS & {\cmark} & 100 & 110 &  {-} &  {-} & 1.80 & Polynomial interpolation \\

    \cite{EaSTLy_DCSW20} with HE & {\cmark} & 100 &   110 &  {-} &  {-} & 14.40 & Paillier HE \\

    \midrule
    Our method w/ \texttt{NoUnion} & {\cmark} & 100 &  110 & 0.10 & {-} & 1.80 & Additions \\

    Our method w/ \texttt{SecureUnion} (q=1) & {\cmark} & 100 &  114 & 0.10 & 574599 & 1.08 & Additions \\
    Our method w/ \texttt{SecureUnion} (q=5) & {\cmark} & 100 &  110 & 0.10 & 657164 & 2.92 & Additions \\
    Our method w/ \texttt{SecureUnion} (q=10) & {\cmark} & 100 &  105 & 0.10 & 660793 & 4.94 & Additions \\

    Our method w/ \texttt{PartialSecureUnion} & {\cmark} & 100 &  110 & 0.10 & 663630 & 2.03 & Additions \\

    Our method w/ \texttt{PlaintextUnion} & {\cmark} & 100 &  110 & 0.10 & 663630 &   0.90 & Additions \\

    \bottomrule
\end{tabular}\\
\vspace{1ex}
(b) AlexNet on CIFAR-10 (80\% Acc. Target) \\
\vspace{2ex}
\caption{%
    Number of rounds and total communication cost required
    to reach the targeted accuracy with \texttt{FedAvg} strategy and our
    approach on five clients.\label{tab:all_xps}}
\end{table*}

We conduct several ML training experiments to define the number of federated rounds $R$
required to obtain the targeted accuracy defined above ($98\%$ for MNIST and $80\%$ for CIFAR-10)
for two strategies, the \texttt{FedAvg} without model update compression, and the
approach of using \texttt{FedAvg} in conjunction with \texttt{TopBinary} coding of the
model updates for $\rho \in \{0.1, 0.02\}$. We subsequently analytically estimate
the communication costs associated with using these two FL approaches in conjunction with different
secure aggregation protocols (see Tables~\ref{tab:related_works} and \ref{tab:comm-cost-estimations}),
the results of which are detailed in Table~\ref{tab:all_xps}.

For experiments on \texttt{FedAvg} with \texttt{TopBinary} model update coding, we
also report the mean size of the aggregated union of indices over the course of federated
training, $\mathbb{E}~|V|$.
This value gives us an idea of the scale of the union of
indices operation for the different ML training experiments.

In table~\ref{tab:all_xps}, we also present an evaluation of communication cost for methods presented in \cite{PracticalSA_GIKM17,EaSTLy_DCSW20}.
We see that the methods proposed in~\cite{EaSTLy_DCSW20}
have a total communication cost close to some of our proposed techniques. The
lower costs associated with these techniques is natural since they make use of
\emph{TernGrad} as a model-update compression technique.
Since the compression approaches are so similar, we assume that these
techniques with \emph{TernGrad} compression require a similar number of
federated rounds to obtain the same level of accuracy as our proposed techniques.
Hence, to evaluate the total communication cost of these methods,
we use the same number of rounds than our approach.
We recall that these approaches introduced in~\cite{EaSTLy_DCSW20} cannot be used in practice because at the end of the FL training, each client obtains a different trained models and we do
not know how to aggregate these models into one
model without compromising accuracy.

These results showcase the low total communication cost of our
proposed compressed secure aggregation approach compared to other
techniques with or without secure aggregation.
This communication cost can be further reduced with more fine tuning, as
higher compression rates (i.e. $\rho < 0.02$) may be achievable for the
same performance level \cite{SparseBinaryCompression_SWMS18}.
The higher the compression rate, the lower the communication cost of our
method compared to other secure aggregation techniques.

From our experiments, we observed that when the number of
local updates is too high (e.g. 100)
and the compression rate is too low (e.g. $\rho \leq 0.01$),
federated training does not converge in a reasonable number of federated rounds,
and it is not possible to reach the target model performance.
Such findings confirm the communication analysis presented in~\cite{SparseBinaryCompression_SWMS18}:
there exists a lower bound on communication which is reflected by
a trade-off between the number of rounds of communication
(which depends of the number of local updates between two consecutive aggregations)
and the communication cost at each round (which depends of the compression rate).

We recall that our \texttt{SecureUnion} protocol is not correct, since some indices are missing in the union result.
In this protocol, the parameter $q$ is used to manage this amount of false negatives:
higher is $q$, smaller is the amount of false negatives.
From our experiments, we observed that when the compression rate is too low ($\rho=0.02$) and when $q=1$, it is not possible to reach the targeted accuracy.
With $q=1$, many selected gradients are not used during the secure aggregation due to the incorrectness of the \texttt{SecureUnion} protocol.
This high amount of false negatives reduces the amount of information used for each aggregation and thus, prevents a robust training.
Among all our experiments, our method with \texttt{SecureUnion} ($q=1$) and parameters $E=100$ and $\rho=0.01$ achieves the best trade-off between privacy and communication cost.
In addition, this strategy has a lower communication cost than \cite{PracticalSA_GIKM17,EaSTLy_DCSW20}.

\section{Introduction}
Today, the common machine learning (ML) paradigm requires the collection of
large volumes of data in order to train robust predictive models
used across a wide range of contexts.
As more data often begets improved predictive power, generally one would
like to bring together as much data as possible for a given ML task.
However, in many contexts, such data are often of a sensitive and personal nature,
and due to regulations (e.g. GDPR),
it may be forbidden to centrally collect such data for ML purposes, irrespective
of the societal or business interest in doing so.
Ideally, one would like to be able to securely train an ML model
over sensitive datasets while ensuring privacy guarantees to the data owners.
For instance, training on medical data across different,
geographically distant, hospitals can be beneficial for the treatment of
rare diseases, but such collaborations are blocked without a system that
properly attends to the interests of data owners, and the regulators that
oversee them.

Three core privacy-preserving ML (PPML) techniques are commonly proposed in
such settings to secure model training and protect training data, namely,
Secure Multiparty Computation (SMC)~\cite{SMC_EKR18},
Homomorphic Encryption (HE)~\cite{HE_AAUC17},
and Differential Privacy (DP)~\cite{DP_DR14}.
SMC~\cite{SMC_EKR18} enables multiple clients to jointly evaluate
a function over their input data while keeping this data private
(except what can be inferred from the output).
With HE~\cite{HE_AAUC17}, one is able to perform computations
directly on encrypted data.

The goal of DP mechanisms~\cite{DP_DR14,DP_DSNS06} applied
to model training is to reduce the statistical likelihood
of any individual data sample being identified as a training sample,
and thus associated with the trained model,
all while attempting to retain the utility of the model in identifying the
data-wide patterns and correlations desired.
When DP mechanisms are applied to the training of deep learning models
via stochastic gradient descent (SGD), these mechanisms often come via
an extra noise term added to each mini-batch gradient~\cite{ACG2016}.
If too much noise is applied,
the privacy guarantees will increase and at the same time,
the overall predictive performance of the model will decrease,
thus putting the goals of privacy and utility at opposition.
However, this trade-off can be controlled through the
parameterization of the DP mechanism selected.
We note that the utility of DP is orthogonal to secured model
training, and it is often of interest to \emph{pair} DP
training with secure training to ensure the privacy of training
data w.r.t. the final trained model.

When we look to \emph{distributed} model training over
sensitive datasets, we see two main approaches proposed in the literature:
secure function evaluation based on cryptographic techniques,
and distributed privacy-aware machine learning.
The first approach attempts to secure the entire training process
and only reveals the final trained model~\cite{%
SecureML_MZ17,ABY3_MR18,SecureNN_WGC18,SecureNN3_WGC19,FALCON_WTBK20,ARIANN_RPB20}.
This approach is often based on either SMC protocols
(e.g. garbled circuits, secret sharing, etc.) or HE.
However, the currently proposed solutions based on SMC or HE techniques are
often too inefficient for secure deep neural network training,
owing to the high communication and computational costs associated with
the application of these protocols to modern, massive deep learning models.
For example,
HE is currently only applied on computationally limited tasks,
e.g.~training linear models, neural network inference, etc.,
due to its high computational cost.

The second approach is federated learning (FL),
a technique first introduced~\cite{shokri2015privacy, FL_MMRA16}.
FL is a paradigm to train
a model that benefits
from all available datasets
while keeping training data in place.
By aggregating model parameters, or the updates thereof,
after short local training steps,
FL permits one to train a global model over previously unobtainable
datasets.
While the technique is promising, according to~\cite{FL_chaellenges_LSTS20}, four main challenges limit the large-scale
adoption of FL techniques in real-world use cases, namely,
    i) expensive communication,
    ii) system heterogeneity,
    iii) statistical heterogeneity, and
    iv) privacy concerns.
In this paper, we will focus on communication and privacy challenges, simultaneously.

In particular,
while leaving data at its source is a significant step in improvement for
the rights of data owners, both in terms of control and in privacy,
sharing intermediate model updates has been demonstrated to
leak sensitive information~\cite{privacy_BDFK18,privacy_CLKE18,privacy_MSCS19}.
To combat this, federated approaches often couple together DP model training as well
as HE- or SMC-based secure aggregation techniques
to ensure that transmitted model information is privacy preserving.
SMC techniques can be used to securely aggregate the local model updates without revealing them.
This functionality is commonly used for federated systems~\cite{PracticalSA_GIKM17}, and can ensure that individual
contributions remain hidden from federated system operators.
The main bottleneck for the application of SMC techniques is the additional computation and communication costs.

Using the knowledge of existing PPML techniques, and in light of their limitations,
the challenge for privacy-preserving distributed ML consists in building a protocol which provides meaningful privacy guarantees
while also being computation and communication efficient,  all without significantly compromising accuracy.
In this paper, we propose a novel FL approach
which combines neural network update compression
techniques~\cite{Sto2015, SparseBinaryCompression_SWMS18, DoubleSqueeze_TYLZ19}
with secure computation.
Thanks to SMC, this approach provides privacy guarantees on model update exchanges,
along with a significant reduction in
transmission costs. As evidenced in earlier works, when using compression with the proper error compensation techniques~\cite{ErrorFeedback_KRSJ19},
such improvements in communication efficiency can be gained without loosing performance.

More precisely, we propose the following novel contributions:
\begin{enumerate}
    \item We introduce a new protocol for secure aggregation in collaborative FL in Sec.~\ref{sec:proposed-method}. This protocol is based on the adaptation of a federated strategy with model update compression to secure computation.
    \item In our protocol, secure aggregation is performed across several servers. We prove in Theorem~\ref{th:privacy} that the privacy is guarantee when at most all servers except one collude.
    \item In Section~\ref{subsec:total_comm_cost},
    we demonstrate that this protocol has a very low communication cost.
    \item Our experiments on MNIST and CIFAR10 presented in
    Sec.~\ref{sec:experiments} prove that our protocol obtains
    similar accuracy than non-secure uncompressed FL training with
    a lower communication cost.
    Compared to secure FL training \cite{PracticalSA_GIKM17}, our protocol has a lower computation and communication costs.
\end{enumerate}

\section{Proposed Method}
\label{sec:proposed-method}

In this paper, we focus on collaborative FL, a context often
encountered in medical applications of federated techniques.
Within this context, we assume that our participants are a ``small'' ($<20$) set of
hospitals which possess robust and consistent network connections, as well as
a desire to train large computer vision models for medical imaging data.
The aim of this work is to present a secure FL technique which answers
to the following four design constraints:
\begin{itemize}
    \item[\emph{i})]
        \textbf{Perform the model update aggregation in a secure way}.
        Nothing will be
        revealed to the aggregation servers, only the clients who are engaged
        in model training will learn the aggregated updates, and thus whatever
        information can be inferred from these updates in conjunction with their
        local data and model updates.
        Specifically, our protocol must be:
        \begin{itemize}
            \item[\emph{a})]
                \textbf{Private in malicious settings.}
                Clients and servers may want to obtain information about
                other clients training data.
                They may deviate from the defined protocol to obtain as
                much information as possible.
                Thus, our protocol must be private against malicious adversaries.
            \item[\emph{b})]
                \textbf{Correct in semi-honest setting.}
                Participants would like to improve their local model performance
                through collaboration. Therefore, they have an incentive to behave
                correctly in order to obtain a trained model with better
                performance than their local model.
                Thus, correctness in the semi-honest model is sufficient.
        \end{itemize}
    \item[\emph{ii})]
        \textbf{No compromise on accuracy.}
        Our method must obtain a similar accuracy than
        non-secure \texttt{FedAvg}.
    \item[\emph{iii})]
        \textbf{Computation Efficient.}
        Our method must not use expensive cryptographic operations.
    \item[\emph{iv})]
        \textbf{Communication Efficient.}
        Our method must have a smaller communication cost
        than non-secure uncompressed \texttt{FedAvg}.
\end{itemize}

In this section, we will first describe a communication-efficient FL algorithm
which is amenable to efficient secure aggregation in
Sec.~\ref{subsec:comm-efficient-fl}.
Then, we will present an efficient and
secure sum of vectors protocol
in Sec.~\ref{subsec:secure-sum};
this secure sum algorithm is the main block of our efficient secure
aggregation protocol described in Sec.~\ref{subsec:secure_aggregation}.
Our method is summarized in Alg.~\ref{alg:smc-friendly-fl}.

\subsection{Communication-Efficient FL}
\label{subsec:comm-efficient-fl}
\subsubsection{Updates Compression with Error Compensation}
Our method is based on the compression of the updates sent from clients to the aggregation server
with an error compensation to ensure convergence \cite{Sto2015, ErrorFeedback_KRSJ19, SparseBinaryCompression_SWMS18}.
Over the past few years, it has been demonstrated that compressing updates with
error compensation permits one to reduce the communication costs of distributed model training
without compromising predictive performance of the final model.  Notably, both the empirical
and theoretical work in this area have shown that even very biased and severe model update
quantization and compression techniques can be used while still producing a convergent model
training.

Recently, the \texttt{DoubleSqueeze} technique~\cite{DoubleSqueeze_TYLZ19} was introduced. In this technique, the model updates sent to the server are compressed and the aggregated updates returned from the server to the clients are also compressed.
While this additional compression step would be welcomed, we recall from our design
requirements that we would like to
\emph{securely} evaluate all computations performed on the server.
Unfortunately, the recompression of the aggregated
updates would require either knowledge of the aggregated update in the clear, or the ability to
securely and efficiently perform a Top-$k$ selection~\cite{SparsifiedSGD_SCJ18}, an operation which cannot be efficiently evaluated in a secure way.
Thus, we choose to only compress updates sent from the clients to the server and not those
returned from the server back to the clients.
See Alg.~\ref{alg:smc-friendly-fl} for further details on the federated training procedure
with compressed updates with error compensation.

\subsubsection{\texttt{TopBinary} Coding}
For the compression method, we used a combination of the
Top-$k$ sparsification~\cite{SparsifiedSGD_SCJ18} as well as 1-bit quantization~\cite{SignSGD_BWAA18}
which we note here as \texttt{TopBinary} coding.
The Top-$k$ sparsification jointly compresses a vector $X$
by retaining only the $k$ components with largest magnitude,
and assuming all other components are zero magnitude.
More precisely, let $X \in \mathbb{R}^N$, then $\forall i \in [1,N]$,
\begin{equation}
    \text{Top-}k(X)[\pi_i] =
    \begin{cases}
        X[\pi_i], & \text{if}~ \pi_i \leq k,\\
        0, & \text{otherwise}.
    \end{cases}
\end{equation}
where $\pi$ is a sorting permutation of $[1, N]$ such that $\forall i \in [1, N-1]$,
$| X[\pi_i] | \geq | X[\pi_{i+1}] |$.
In order to speak about the same relative
compression rate between models of varying architectures, we will introduce the
term $\rho \triangleq \frac{k}{N}$, which is interpreted as a desired model update
sparsity level selected as a hyper-parameter of model training.

To further reduce communication costs, we also employ the one-bit quantization
to the $k$ significant model update coefficients \cite{SparseBinaryCompression_SWMS18,Sto2015}.
This scalar quantization maps each non-zero element of a vector $X$
to the binary set $\{-\alpha_{\rm lo}, \alpha_{\rm hi}\}$ according to their signs.
The selection of these two magnitude values varies from work to work, with some suggesting the use
of the average magnitude of the negative and positive coefficients,
respectively~\cite{OneBit_SFDL14,SparseBinaryCompression_SWMS18},
while others suggest a constant factor chosen as a training hyper-parameter~\cite{Sto2015}.
As in~\cite{Sto2015,TernGrad_WXYW17}, we propose a uniform magnitude level, e.g.
$\alpha_{\rm lo} = \alpha_{\rm hi} = \alpha$. Together with Top-$k$ sparsification,
we obtain the \texttt{TopBinary} coder,
\begin{equation}
    \texttt{TopBinary}(X; k) = \alpha \cdot \text{sgn}\circ\text{Top-}k(X),
\end{equation}
where
\begin{equation}
    \alpha \triangleq \frac{|| X ||_2}{||\text{sgn}\circ\text{Top-}k(X)||_2} = \frac{1}{\sqrt{k}} ||X||_2
\end{equation}
is a scaling factor used to preserve the Euclidean norm of $X$.
We note that the implementation of the proposed secure protocol does not depend tightly
on this construction of $\alpha$, and other definitions could be chosen, as well.

The \texttt{TopBinary} coded vector can be split into two components: the scalar
factor $\alpha$ and the vector of signs $D = \text{sgn} \circ \text{Top-}k(X)$. Furthermore,
when $\rho$ is small, the ternary-valued $D$ can instead be represented by two
$k$-length vectors, namely, the list of non-zero indices, $V = [\pi_1, \dots, \pi_k ]$,
and the signs of the coefficients at those non-zero locations,
$(D)_{|V} = [D[\pi_1], \dots, D[\pi_k] ]$.

These sequences can be coded into
binary representations easily for transmission. In the case of $(D)_{|V}$, the
sign sequence can be represented with $k$ bits, however, as we expect the sign
sequence to be essentially random, there is no expected gain in applying an
entropy coding to this sequence. The support sequence $V$ is compressible,
and can be efficiently represented with adaptive run-length codes, as proposed
in~\cite{Sto2015,SparseBinaryCompression_SWMS18}. We can estimate the lower-bound
on the required number of bits to represent $V$ according to its entropy,
$H_\rho = -(1-\rho)\log_2(1-\rho) - \rho\log_2\rho$. Assuming a 32-bit
floating-point representation for $\alpha$, we can calculate the size if the
\texttt{TopBinary}-coded model updates as
\begin{equation}
    32 + H_{\rho}N + \rho N \quad\text{bits}.
\end{equation}

\subsubsection{Separate Aggregation}
To reduce complexity in secure computation (and thus to reduce computational cost),
we suggest an alternative to aggregate compressed model updates called
\emph{separate aggregation} (\texttt{SepAgg}).
This approach separately aggregates the scaling factors and the vector of signs of the
\texttt{TopBinary}-coded model updates.
Let $\alpha_i \cdot D_i$ the updates of the client $i$.
In \texttt{SepAgg}, the aggregated update is given as
\begin{equation}
    U = \frac{1}{C^2} \left(\sum_{i=1}^C \alpha_i\right) \left(\sum_{i=1}^C D_i\right)
\label{eq:separate_aggregation}
\end{equation}
whereas usually a \emph{direct aggregation} (\texttt{DirectAgg}) is performed and
the aggregated updates is defined as
    $\frac{1}{C} \sum_{i=1}^C \alpha_i D_i$.
We contrast these two approaches in Appendix~\ref{appendix:separate-aggregation}, where
we show the derivation of the scaling term for \texttt{SepAgg} as well as demonstrate
the contexts in which it serves as an appropriate proxy for \texttt{DirectAgg}.

With  \texttt{SepAgg}, the convergence of the federated training is not proved.
However in our experiments, federated training with this \texttt{SepAgg} provides
 similar trained model predictive performance than \texttt{FedAvg} training with \texttt{DirectAgg}.
The main advantage of this \texttt{SepAgg} is to be SMC-friendly
without compromising accuracy.

\begin{algorithm}[t!]
\caption{SMC-friendly Compressed Update FL}\label{alg:smc-friendly-fl}
\DontPrintSemicolon
\KwInput{
    Number of rounds $R$,
    number of local updates $E$,
    initial global model state $\theta^{(0)}$,
    local datasets $\mathcal{D}_i$,
    desired compression factor $\rho$.
}
\textbf{Initialization}\;
\Indp
    $\delta_i^{(0)} \gets \mathbf{0}, \quad \forall i \in [1,C]$\;
    $\theta_i^{(0)} \gets \theta^{(0)} \quad \forall i \in [1,C]$\;
\Indm
\For{$r=0, 1, ..., R-1$}{
    \textbf{Locally on each Client $i$}\;
    \Indp
        \tcc{Local Model Update}
        $U_i \gets {\rm Opt}_E\left(\theta_i^{(r)}, \mathcal{D}_i \right)  - \theta_i^{(r)}$ \;
        \tcc{Coding of EC Update}
        $(\alpha_i, D_i) \gets \mathtt{TopBinary}(U_i + \delta_i^{(r)})$ \;
        \tcc{Update Error Accumulator}
        $\delta_i^{(r+1)} \gets \delta_i^{(r)} + (U_i - \alpha_i \cdot D_i$ )\;
    \Indm
    \textbf{Via SMC between clients and servers} \;
    \Indp
        $D \leftarrow \mathtt{SecurelySum}(D_1, \dots, D_C)$ \;
        $\alpha \leftarrow \mathtt{SecurelySum}(\alpha_1, \dots, \alpha_C)$ \;
    \Indm
    \textbf{Locally on each Client $i$} \;
    \Indp
        \tcc{Update the local weights}
        $\theta_i^{(r+1)} \gets \theta_i^{(r)} + \frac{1}{C^2} \alpha \cdot  D$
}
\end{algorithm}

\subsection{Core Secure Sum Protocol}
\label{subsec:secure-sum}

In this section, we propose an MPC protocol to efficiently
sum a set of vectors in $\mathbb{Z}_m^n$ and evaluate its
costs in terms of both communication and computation.
This protocol will serve as a core building block for the
set of higher-level protocols we will propose in the next
sections for the specific case of secure aggregation of
sparse vectors.

\subsubsection{Protocol Architecture}
\label{subsubsec:architecture}
For our secure computations, we will use a classical architecture
comprised of parties of two kinds:
\begin{itemize}
\item $C$ data owners (\emph{clients}) who transmit secret shares of their data to the servers,
\item and $S\geq 2$ servers who securely evaluate a function on these shares
      and transmit back the shares of the result to each client.
\end{itemize}
Finally, the clients combine their received result shares to obtain the
final expected result of the computation.
The proposed protocol does not require that the parties playing the
role of the server are mutually exclusive from the client parties,
and so creates an opportunity for a completely decentralized construction
of the architecture (e.g. $S = C$).
No matter the architecture, the proposed protocol will only reveal
to the clients the result of the secure function evaluation, with
the caveat that if a client is \emph{also} a server, then this party will
observe the result by virtue of being a client, themselves.
The privacy of our proposed protocol relies only on the fact that at most $S-1$ malicious
servers collude. If it is likely that a few servers might collude, then the decentralized
nature of this protocol allows one to grow the number of servers so that the
collusion of $S$ servers becomes unlikely.

\subsubsection{Protocol}
\label{subsubsec:secure_sum}
Each client possesses a vector $X_i \in \mathbb{Z}_m^n$, and desires to
know the sum of all client vectors,
$X = \sum_{i=1}^C X_i \mod m$, but each client does not wish to reveal
their own vector to other parties.
To accomplish this, we propose a secure sum of vectors protocol based solely on
additive masked vectors.
More precisely, each client sends some additive masks of his vector to $S \geq 2$ servers,
then the servers add all received masked data and send back the result to each client.
The clients obtain the aggregated vectors by adding the received result shares.
See Alg.~\ref{algo:secure-sum} for a detailed presentation of this protocol.

\begin{algorithm}[t!]
\caption{Secure Sum Protocol}\label{algo:secure-sum}
\DontPrintSemicolon
\KwInput{Each client has a vector $X_i \in \mathbb{Z}_m^n$}
\textbf{Locally on each Client $i$} \;
\Indp
    \tcc{Create \& Transmit Shares}

    $R_{i,j} \gets \mathtt{sample}(\mathbb{Z}_m^n) \quad \forall j \in [1, S-1] $\;

    $R_{i, S} \gets X_i - \sum_{j=1}^{S-1} R_{i,j} \mod m$ \;
    Transmit $R_{i,j}$ to $Server_j$,  $\forall j \in [1, S]$ \;
\Indm
\textbf{Locally on each Server $j$} \;
\Indp
    \tcc{Aggregate received shares}

    $R_j \gets \sum_{i=1}^C R_{i,j} \mod m$\;
    Broadcast $R_j$ to all clients \;
\Indm
\textbf{Locally on each Client $i$} \;
\Indp
    \tcc{Aggregate received shares}

    $X \gets \sum_{j=1}^S R_j \mod m$ \;
\Indm
\KwOutput{$\begin{cases}
                \text{Clients: } X = \sum_{i=1}^C X_i \mod m\\
                \text{Servers: } \varnothing \end{cases}$

                }
\end{algorithm}

\subsubsection{Correctness \& Privacy}
We now turn our attention to both the correctness of the proposed protocol, in
the semi-honest setting, as well as the privacy of the protocol in the case of
malicious parties.

\begin{theorem}
The Secure Sum Protocol is correct against semi-honest adversaries.
\label{th:correctness}
\end{theorem}
\begin{proof}
    The correctness of our secure sum protocol against semi-honest adversaries
    is straightforward and follows directly via substitution from the protocol
    description in Alg.~\ref{algo:secure-sum}. Working backwards from the
    local addition of result shares,

    \begin{align*}
        X &= \sum_{j=1}^S R_j \mod m, \tag{L.9}\\
          &= \sum_{j=1}^{S}\sum_{i=1}^C R_{i,j} \mod m, \tag{L.6}\\
          &= \sum_{i=1}^C \left( R_{i,S} + \sum_{j=1}^{S-1} R_{i,j} \right) \mod m, \\
          &= \sum_{i=1}^C X_i \mod m, \tag{L.3}
    \end{align*}
    where the line numbers refer to the lines of Alg.~\ref{algo:secure-sum}.
\end{proof}

The correctness in the malicious settings is not required
if the clients and servers have the same incentive to obtain
a trained model with good prediction performance. We make this
assumption due to the collaborative FL context we put in
place in Sec.~\ref{sec:background}, and under this assumption we
do not include extra features into the protocol to protect against
poisoning attacks from malicious parties who intend to break
its correctness.
Instead, we focus on what a malicious adversary controlling multiple parties could
learn from the observation of the protocol.

\begin{theorem}
    The Secure Sum Protocol is private against a
    malicious adversary controlling at most $S-1$ servers and any number of clients.
    \label{th:privacy}
\end{theorem}
\begin{proof}
    Given in Appendix~\ref{appendix:privacy-proof}.
\end{proof}

Since our secure sum protocol is private against a malicious adversary controlling at
most $(S-1)$ servers and any number of clients,
the malicious adversary cannot learn more than what he can infer from the inputs and outputs of
the parties they control.
In practice, if the adversary controls \emph{all} clients, the adversary already knows everything.
If the adversary controls all clients \emph{except one}, he can deduce the inputs of this honest client
from the inputs and outputs of the clients that are under his control.
If the adversary controls at most $(C-2)$ clients, the adversary can infer the sum of the inputs
of the honest clients from the inputs and outputs of the clients that he controls,
but not the individual inputs of the honest parties. In this manner, the security of the
individual clients is preserved, however the sum of vectors of honest parties is not.

\subsubsection{Computation \& Communication Costs}

Owing to the construction of the secure sum protocol, the computation incurred by
all parties to execute the secure sum protocol is quite minimal, as it involves
only additions modulo $m$ at all parties. Clients have an additional burden to
produce $S-1$ random vectors in $\mathbb{Z}_m^n$, but the computational cost
of producing such batches of random values is also minimal. Notably, the
proposed secure sum protocol also does not require any external coordination steps,
as in~\cite{PracticalSA_GIKM17}, to coordinate mask generation, but instead all
client parties may act independently when producing data shares.
The simplicity of the proposed protocol offers an ability to reduce the
overall round-time required for ensuring the secure aggregation of model
updates, thus allowing for more federated rounds to be executed within
a fixed time interval.

The communication cost can be calculated as the number of bits required
to transmit all shares to the servers and subsequently for all servers
to transmit shares back to the clients. Specifically,
each client sends to each server a single vector in $\mathbb{Z}_m^n$ of
$n \cdot \lceil \log_2 m \rceil$ bits. Subsequently,
each server sends back to each client one vector in $\mathbb{Z}_m^n$
of $n\cdot \lceil \log_2 m \rceil$ bits.
Thus, the \emph{total} communication cost required to execute this
protocol is
\begin{equation}
    \label{eq:secure_sum_comm_cost}
    2 \cdot S \cdot C \cdot n \cdot \lceil \log_2 m \rceil \text{ bits}.
\end{equation}

\subsection{Compressed Secure Aggregation Protocol}
\label{subsec:secure_aggregation}
Now that we have a decentralized, secure, and computationally-efficient sum
protocol in hand to use as a building block, we will demonstrate how to construct a
protocol for the efficient aggregation of \emph{sparse} quantized vectors, namely, the ones
produced by the \texttt{TopBinary} coding described in Sec.~\ref{subsec:comm-efficient-fl}.
Our proposed secure aggregation protocol for compressed model updates can be
described in three steps:
\begin{enumerate}
    \item a union of the list of indices of each client,
    \item a sum of the signs restricted on the union of the list of indices,
    \item and finally, a sum of the scalar factors.
\end{enumerate}
These steps are described in more details in Alg.~\ref{algo:separate-secure-agg}.

In the next sections we will detail why the intermediate steps of this
protocol are secure (Sec.~\ref{subsubsec:revealing-info}), then we
will provide a number of different approaches for the efficient
computation of the secure union (Sec.~\ref{subsubsec:secure-unions}), the protocol for
a secure sum of sign vectors (Sec.~\ref{subsubsec:secure-sign-sum}), and finally the
protocol for the secure sum of scalar factors (Sec.~\ref{subsubsec:secure-factor-sum}).

\begin{algorithm}[t!]
    \caption{Compressed Secure Aggregation}\label{algo:separate-secure-agg}
    \DontPrintSemicolon
    \KwInput{Each client $i$ has a vector $X_i = \alpha_i D_i \in \mathbb{R}^N$}

    \textbf{Via SMC between clients and servers} \;
    \Indp
        \tcc{Union of Indices (Algs.~\ref{algo:partial-secure-union}, \ref{algo:secure-union})}
        $V \gets \bigcup_{i=1}^C V_i = \bigcup_{i=1}^C \{k \in [1,N]~|~D_i[k] \neq 0\} $\;
        \tcc{Sum of Signs (Alg.~\ref{algo:secure-sum-signs})}
        $D \gets \sum_{i=1}^C (D_i)_{|V}$\;
        \tcc{Sum of Factors (Alg.~\ref{algo:secure-sum-factors})}
        $\alpha \gets \sum_{i=1}^C \mathcal{Q}(\alpha_i)$\;
    \Indm
    \textbf{Locally on each Client $i$} \;
    \Indp
        $U \gets \frac{1}{C^2} \cdot \alpha \cdot D$\;
    \Indm
    \KwOutput{$\begin{cases}
                \text{Clients: } &U = \texttt{SepAgg}(X_1, \dots, X_C) \\
                                 &V, D, \alpha \\
                \text{Servers: } &\varnothing \end{cases}$}
\end{algorithm}

\subsubsection{Security of Intermediate Outputs}
\label{subsubsec:revealing-info}
At the end of the secure aggregation round,
each client obtains the separate aggregated updates $U$
(see Eq.~\ref{eq:separate_aggregation}).
From $U$, the client can easily infer the following pieces of
information:
\begin{itemize}
    \item the union of the list of indices via
          $$\tilde{V} = \{k \in [1,N]~|~U[k] \neq 0\},$$
    where $\tilde{V} \subset V = \bigcup_{i=1}^C \{k \in [1, N]~|~D_i[k] \neq 0 \}$ and
    $V  \backslash \tilde{V} = \{k \in V~|~\sum_{i=1}^C D_i[k] = 0\}$

    \item the sum of the scalar factors via
          $$\widetilde{\alpha} = C^2 \cdot \min_{k \in  V}~\left|U[k]\right|,$$
    where $\widetilde{\alpha} = \alpha$ if at least one index of the sum of the signs
    is equal to $-1$ or $1$, which is the case when one index has been selected by
    exactly one client, an occurrence we expect to be highly likely,
    \item and the sum of the signs via
          $$D = \left(\frac{C^2}{\alpha} \right)U.$$
\end{itemize}
Notably, each of these pieces of information is an intermediate output of the generic
compressed secure aggregation protocol we propose (Alg.~\ref{algo:separate-secure-agg}).
Thus, revealing to the clients these intermediate outputs over the course of the protocol
does not provide any \emph{additional} information than what they could learn simply from
their knowledge of their own inputs and result of the secure protocol at its completion.
Hence, the proposed stepwise approach is secure as long as its individual steps is secure,
which we will show in the following sections.

\subsubsection{Secure Union Protocols}
\label{subsubsec:secure-unions}
Now, we will define a set of protocols, each with a different secure perimeter and
communication cost trade-off, for finding the union of non-zero indices of
\texttt{TopBinary}-coded vectors between clients.
We compare these different approaches in Table~\ref{tab:comp-secure-union}.
In each protocol, each client $i$ has a list of indices $V_i$ whose components
belong to $[1,N]$.
The clients would like to securely evaluate the union
of the lists of indices $V = \bigcup_{i=1}^C V_i$.

\begin{table*}[!t]
    \centering
    \begin{tabular}{lcll}
        \toprule
        Protocol & Communication Cost (bits)& Clients Learn (besides $V$)  & Servers Learn \\
        \midrule
        \texttt{PlaintextUnion} & $2 \cdot C \cdot N$ & Nothing & Clients' list of indices \\
        \texttt{PartialSecureUnion} & $2 \cdot S \cdot C \cdot N \cdot \lceil \log_2 (C+1) \rceil $ & How many clients have selected each index & Nothing\\
        \texttt{SecureUnion} & $2 \cdot S \cdot C \cdot N \cdot q$ & If they alone selected each index & Nothing\\
        \bottomrule
    \end{tabular}
    \caption{Comparison of secure union protocols}
    \label{tab:comp-secure-union}
\end{table*}

\paragraph{\texttt{PartialSecureUnion}}
In this protocol,
each client will create a Boolean vector $B_i$ representing their list of indices $V_i$ such that,
$\forall k \in [1,N]$,
\begin{equation}
    B_i[k]=\begin{cases}
        1, & \text{ if } k \in V_i, \\
        0, & \text{ otherwise }.
    \end{cases}
\end{equation}
Using this representation, the clients can securely calculate the union of indices through
the use of Alg.~\ref{algo:secure-sum} by evaluating the sum of their Boolean vectors $B_i$
in $\mathbb{Z}_{C+1}^N$.
At the end of the secure sum evaluation, each client will obtain $B=\sum_{i=1}^C B_i \mod (C+1)$,
from which they may easily infer the union of indices $V$ by
selecting the positions of non-zero values in $B$.
In this protocol, client learns the union of indices and also the number of clients having each index.
See Alg.~\ref{algo:partial-secure-union} for a detailed presentation of this
\texttt{PartialSecureUnion} algorithm.

In terms of privacy and security, the simplicity of the
\texttt{PartialSecureUnion} is gained by permitting the knowledge of $B$ at each
client.
Here, $B$ reveals to the clients \emph{how many} clients have non-zero values at a
given index, however it does not reveal \emph{which} clients. Though correlated,
such information is somewhat stronger than what is available via $U$,
which can only be used to measure the relative frequency of a certain
location being positive or negative in the sign vector.

\begin{algorithm}[t!]
\caption{\texttt{PartialSecureUnion}}\label{algo:partial-secure-union}
\DontPrintSemicolon
\KwInput{Each client $i$ has a list of indices $V_i \subset [1, N]$}
\textbf{Locally on each Client $i$}\;
\tcc{Create vector $B_i$ representing $V_i$}
\Indp

$\forall k \in [1,N], B_i[k]= \begin{cases} 1, & \text{ if } k \in V_i \\
0, & \text{ otherwise} \end{cases}$ \;
\Indm
\textbf{Via Secure Sum between clients and servers (Alg.~\ref{algo:secure-sum})}\;
\Indp
    $B = \sum_{i=1}^C B_i \mod (C+1)$\;
\Indm
\textbf{Locally on each Client $i$}\;
\Indp
    \tcc{Compute the union of indices}
    $V = \{k \in [1, N] | B[k] \neq 0\}$\;
\KwOutput{$\begin{cases}
                \text{Clients: } V=\bigcup_{i=1}^C V_i \\
                \text{Servers: } \varnothing \end{cases}$}
\end{algorithm}

\paragraph{\texttt{SecureUnion}}
In this protocol, each client will create a vector $A_i$ representing
its list of indices $V_i$ such that $\forall k \in [1,N]$,
\begin{equation}
    A_i[k]=\begin{cases}
        R_{i,k}, & \text{ if } k \in V_i \text{ where } R_{i,k} \in_R \mathbb{Z}_{2^q}^*, \\
        0, & \text{ otherwise }.
    \end{cases}
\end{equation}
Subsequently, the clients will securely evaluate the sum of the vectors $A_i$ in $\mathbb{Z}^N_{2^q}$
using Alg.~\ref{algo:secure-sum}.
At the end of the secure sum evaluation, each client will obtain $A=\sum_{i=1}^C A_i \mod 2^q$
from which each client can easily infer the union of indices by
selecting the positions of non-zero values in $A$.
A detailed description of the \texttt{SecureUnion} protocol is given in Alg.~\ref{algo:secure-union}.

When using the \texttt{SecureUnion} protocol,
the resulting union of indices may have some false negatives, as there is potential for the masked
entries of $A$ to cancel out, thus impacting the correctness of this protocol.
Specifically, when more than two clients have the same index, the sum
of random values $R_{i,k}$ will be equal to 0 with probably $1 / 2^q$,
causing $k$ to be omitted from $V$ when it should be present.
Increasing $q$ can make the probability of such false negatives increasingly rare, but at
the cost of increased working space, and therefore, increased communication cost.
We refer to Appendix~\ref{appendix:secure_union} for an analysis of the average amount of false negatives.
This potential error is in contrast with \texttt{PartialSecureUnion}, which will always be correct.
We note that, in experimentation, the proposed communication-efficient FL in
Alg.~\ref{alg:smc-friendly-fl} is observed empirically to be quite robust to such
dropped support.

In terms of information leakage, if one client observes that the component
$A[k]$ in the sum result is equal to
their random component $R_{i,k}$, then the client can infer that with very high
probability he is alone to have this index $k$.
We refer to Appendix~\ref{appendix:secure_union} for an analysis of this probability.

\begin{algorithm}[t!]
\caption{\texttt{SecureUnion}}\label{algo:secure-union}
\DontPrintSemicolon
\KwInput{Each client $i$ has a list of indices $V_i \subset [1, N]$}
\textbf{Locally on each Client $i$}\;
\tcc{Create vector $A_i$ representing $V_i$}
\Indp

$    A_i[k]=\begin{cases}
        R_{i,k}, & \text{ if } k \in V_i \text{ where } R_{i,k} \in_R \mathbb{Z}_{2^q}^*, \\
        0, & \text{ otherwise }.
    \end{cases}$\;
\Indm
\textbf{Via Secure Sum between clients and servers (Alg.~\ref{algo:secure-sum})}\;
\Indp
    $A=\sum_{i=1}^C A_i \mod 2^q$\;
\Indm
\textbf{Locally on each Client $i$}\;
\Indp
    \tcc{Compute the union of indices}
    $V = \{k \in [1, N] | A[k] \neq 0\}$\;
\Indm
\KwOutput{$\begin{cases}
                \text{Clients: } V \approx \bigcup_{i=1}^C V_i \\
                \text{Servers: } \varnothing \end{cases}$}
\end{algorithm}

\paragraph{\texttt{PlaintextUnion}}
In this protocol, the clients will only learn the union of indices, however
the first server will learn the list of indices of each client.
In this protocol, each client sends to the first server
the Boolean vector $B_i$ representing their list of indices.
The first server evaluates the union of indices by OR-ing the
received Boolean vectors and transmitting back the resulting
Boolean vector to each client.

While such a protocol is not advisable for every setting, especially for
NLP tasks or recommender systems, where the knowledge of support locations
can be indicative of training features,
the effectiveness of many white-box privacy attacks on distributed ML systems
has only been demonstrated for exact, real-valued model updates, and not for
model update support.
In the case of large computer-vision models, such a security perimeter may
be acceptable to the system designer.

\paragraph{\texttt{NoUnion}}
If the compression rate is very low, the split of the sum of signs into a
union of indices and a sum on restricted signs vectors is not beneficial.
Then, it is more efficient to perform the secure aggregation in two steps:
\begin{itemize}
    \item the secure sum of signs vectors $D_i$ directly, as $V=[1, N]$,
    \item and the secure sum of scalar factors.
\end{itemize}

\subsubsection{Secure Sum of Signs}
\label{subsubsec:secure-sign-sum}
In the second step of the compressed secure aggregation protocol (see Alg.~\ref{algo:separate-secure-agg}),
each client restricts their dense vector of ternary values $D_i$
to the support resulting from the secure union of indices $V$, and
then together they securely evaluate the sum of these binary vectors of signs, $(D_i)_{|V}$.
More precisely, the parties would like to securely evaluate the sum of
$C$ vectors of length equal to the size of
the union of indices $|V|$,  each component belongs to $\{-1, 0, 1\}$.
The resulting vector will be a vector of size $|V|$
whose components belong to $[-C, C]$.

To define a protocol for the secure sum of signs,
first, each client will convert each component of its restricted
vector from $[-C, C]$ to $[0, 2C]$ via
\begin{equation}
    \text{Convert}(x) = \begin{cases}
    x, & \text{ if } x \in [0, C], \\
    x + (2C+1), & \text{ if } x \in [-C,-1].
    \end{cases}
\label{eq:signs-convert}
\end{equation}
Subsequently, the clients will securely evaluate the sum of these converted vectors in $\mathbb{Z}_{2C+1}$
using the secure sum protocol of Alg.~\ref{algo:secure-sum}.
Finally, after obtaining the result of this secure sum,
each client will convert the components of the result vector from $[0, 2C]$ back to $[-C, C]$
via
\begin{equation}
    \text{Convert}^{-1}(x) = \begin{cases}
    x, & \text{ if } x \in [0, C], \\
    x - (2C+1), & \text{ if } x \in [C+1,2C].
    \end{cases}
\label{eq:signs-inverse-convert}
\end{equation}
This protocol is detailed in Alg.~\ref{algo:secure-sum-signs}.

\begin{algorithm}[t!]
\caption{Secure Sum of Signs}\label{algo:secure-sum-signs}
\DontPrintSemicolon
\KwInput{Each client $i$ has a vector of signs $D_i \in \{-1, 0, 1\}^N$ and a common list of indices $V \subset [1, N]$}
\textbf{Locally on each Client $i$}\;
\Indp
    \tcc{Convert $(D_i)_{|V}$ into $[0, 2C]$}
    $\forall k \in V, (\tilde{D}_i)_{|V}[k] = \text{Convert}((D_i)_{|V}[k])$\;
\Indm
\textbf{Via Secure Sum between clients and servers (Alg.~\ref{algo:secure-sum})}\;
\Indp
    $\tilde{D}_ {|V} = \sum_{i=1}^C (\tilde{D}_i)_{|V} \mod (2C+1)$\;
\Indm
\textbf{Locally on each Client $i$}\;
\Indp
    \tcc{Convert $\tilde{D}_ {|V}$ into $[-C, C]$}
    $\forall k \in V, D_{|V}[k] = \text{Convert}^{-1}(\tilde{D}_{|V}[k])$\;
    \tcc{Create the full signs vector}
    $\forall j \in [1, N], D[j] = \begin{cases}
    D_{|V}[j], &\text{ if } j \in V \\
    0, &\text{ otherwise}
    \end{cases}$\;
\Indm
\KwOutput{$\begin{cases}
                \text{Clients: } D=\sum_{i=1}^C D_i \\
                \text{Servers: } \varnothing \end{cases}$}
\end{algorithm}

\subsubsection{Secure Sum of Factors}
\label{subsubsec:secure-factor-sum}
In the third step of the compressed secure aggregation protocol,
each client $i$ has a scalar factor $\alpha_i \in \mathbb{R}^+$
and would like to obtain the sum of all factors $\alpha = \sum_{i=1}^C \alpha_i$.
In SMC, since we may only work with integers, it is necessary to convert
these factors into
a fixed-point representation, which in turn can be easily represented with
integer coding.
When choosing parameters $a$ and $\lambda$ of the fixed-point representation
(see \eqref{eq:fixed-point-represention}), we must account for potential
overflows when summing together the $C$ scalar factors.
In practice, $\lambda$ is fixed to 32 bits in order to have a reasonable
precision without unnecessarily increasing the size of the working field.
Subsequently, $a$ is chosen so as to avoid this potential overflow.

After this representation conversion, the clients will securely evaluate the
sum of these converted factors in $\mathbb{Z}_{2^{\lambda}}$, again using the
secure sum protocol of Alg.~\ref{algo:secure-sum}.
Finally, each client will convert the resulting factor back into the initial space $\mathbb{R}^+$.

\begin{algorithm}[t!]
\caption{Secure Sum of Factors}\label{algo:secure-sum-factors}
\DontPrintSemicolon
\KwInput{Each client $i$ has a factor $\alpha_i \in \mathbb{R}^+$}
\textbf{Locally on each Client $i$}\;
\Indp
    \tcc{Convert $\alpha_i$ into the fixed point representation}
    $\tilde{\alpha}_i = Q(\alpha_i)$\;
\Indm
\textbf{Via Secure Sum between clients and servers (Alg.~\ref{algo:secure-sum})}\;
\Indp
    $\tilde{\alpha} = \sum_{i=1}^C \tilde{\alpha}_i \mod 2^{\lambda}$\;
\Indm
\textbf{Locally on each Client $i$}\;
\Indp
    \tcc{Convert $\tilde{\alpha}$ into $\mathbb{R}^+$}
    $\alpha = Q^{-1} (\tilde{\alpha})$\;
\Indm
\KwOutput{$\begin{cases}
                \text{Clients: } \alpha \approx \sum_{i=1}^C \alpha_i \\
                \text{Servers: } \varnothing \end{cases}$}
\end{algorithm}

\begin{table*}[!t]
\centering
\begin{tabular}{lcc}
\toprule
Protocol & Sec. Agg. & Communication Cost per Federated Round (bits) \\
\midrule
\texttt{FedAvg} & \xmark & $2 \cdot C \cdot 32 \cdot N$ \\
Our method w/ \texttt{NoUnion} & \cmark &
$\Big(2 \cdot S \cdot C \cdot N \cdot \lceil \log_2 (2C+1) \rceil \Big)
+ \Big(2 \cdot S \cdot C \cdot 32 \Big)$\\
Our method w/ \texttt{SecureUnion} & \cmark &
$\Big(2 \cdot S \cdot C \cdot N \cdot q \Big)
+\Big(2 \cdot S \cdot C \cdot |V| \cdot \lceil \log_2 (2C+1) \rceil \Big)
+ \Big(2 \cdot S \cdot C \cdot 32 \Big)$\\
Our method w/ \texttt{PartialSecureUnion} & \cmark &
$\Big(2 \cdot S \cdot C \cdot N \cdot \lceil \log_2 (C+1) \rceil \Big)
+\Big(2 \cdot S \cdot C \cdot |V| \cdot \lceil \log_2 (2C+1) \rceil \Big)
+ \Big(2 \cdot S \cdot C \cdot 32 \Big)$\\
Our method w/ \texttt{PlaintextUnion} & \cmark &
$\Big(2 \cdot C \cdot N \Big)
+\Big(2 \cdot S \cdot C \cdot |V| \cdot \lceil \log_2 (2C+1) \rceil \Big)
+ \Big(2 \cdot S \cdot C \cdot 32 \Big)$\\
\bottomrule
\end{tabular}
\caption{Communication costs per federated round for the different protocols\label{tab:comm-cost-estimations}}
\end{table*}

\subsection{Communication Costs}
\label{subsec:total_comm_cost}
In this section, we estimate the total communication cost per federated round of
\texttt{FedAvg} without secure aggregation
and our proposed method with secure aggregation.
The Table~\ref{tab:comm-cost-estimations} summarizes these communication costs.

For our calculations and experimental implementation, we chose a 32-bit floating-point representation for all ``unquantized'' real values.

\subsubsection{Federated Averaging without secure aggregation}
Each client sends his updates to one server ($32 \cdot N$ bits)
and then the server sends the aggregated updates to each client ($32 \cdot N$ bits).
Thus, the total communication cost for one aggregation with \texttt{FedAVg} is equal to
$2 \cdot C \cdot 32 \cdot N \text{ bits}$.

\subsubsection{Our method with secure aggregation}

We can easily evaluate the total communication cost in bits of each sub-protocol of our secure aggregation
 (Algorithms ~\ref{algo:partial-secure-union}, \ref{algo:secure-union}, \ref{algo:secure-sum-signs}, \ref{algo:secure-sum-factors})
 from \eqref{eq:secure_sum_comm_cost}:
\begin{align}
    2 \cdot S \cdot C \cdot N \cdot \lceil \log_2 (C+1) \rceil \tag{\texttt{PartialSecureUnion}} \\
    2 \cdot S \cdot C \cdot N \cdot q \tag{\texttt{SecureUnion}} \\
    2 \cdot C \cdot N \tag{\texttt{PlaintextUnion}} \\
    2 \cdot S \cdot C \cdot |V| \cdot \lceil \log_2 (2C+1) \rceil \tag{\texttt{Sum of Signs}} \\
    2 \cdot S \cdot C \cdot \lambda \tag{\texttt{Sum of Factors}}
\end{align}
where $|V|$ is the size of the union of indices $V$ and $\lambda$ is a parameter of the fixed point representation.

\section{Related Work}

\begin{table*}[t!]
\centering
\begin{tabular}{ccc}
\toprule
Protocol &  Total Comm. / Round & Required Operations \\
\midrule
    \cite{PracticalSA_GIKM17} & $C \cdot \left( 2 C \cdot a_K + (5 C-4)a_S + 2N \lceil \log_2 T \rceil\right)$ & Asymmetric encryption, PRG \\
    \cite{EaSTLy_DCSW20} with TSS & $2 S C N \lceil \log_2 (2C + 1) \rceil$ & Polynomial interpolation \\
    \cite{EaSTLy_DCSW20} with HE & $4 C N (prec + pad)$ & Paillier HE \\
\bottomrule
\end{tabular}
\caption{Communication and computation costs of the secure aggregations from \cite{PracticalSA_GIKM17,EaSTLy_DCSW20} \label{tab:related_works}}
\end{table*}

\subsection{General methods for Secure Aggregation in FL}
To date, proposed secure aggregation schemes in FL have utilized both SMC and HE approaches.
Secure aggregation methods based on HE~\cite{Hybrid_TBAS19,BatchCrypt_ZLXW20}
require a single round of communication, but also require expensive cryptographic operations.
On the contrary, secure aggregation method based on MPC~\cite{PracticalSA_GIKM17,HybridAlpha_XBZA19}
have a lower computational cost, but a higher communication cost.

\subsection{Practical Secure Aggregation}
\cite{PracticalSA_GIKM17} introduces a secure aggregation protocol based on Threshold Secret Sharing (TSS).
This protocol requires the use of a single aggregation server, a requirement which we relax in our
proposed method in Section~\ref{sec:proposed-method}.
In~\cite{PracticalSA_GIKM17}, at each round, the aggregator server learns the aggregated result
without learning any information on the local model updates, even if some parties drop out over the
course of the secure aggregation phase. To be resilient against dropouts is necessary for the use-case of
federated learning over mobile devices, where robust connectivity of the edge devices participating
in a federated round is not guaranteed.
Through the use of Shamir secret sharing, the aggregator will still be able to evaluate the
aggregation as long as sufficient number of parties remain over the course of the secure
aggregation round.

With respect to computational requirements, this protocol relies on key agreements,
asymmetric cryptography, and the use of
cryptographically-secure pseudo-random number generators (PRG).
These cryptographic operations are computationally expensive and increase the computational burden
for each participating party.

To be resilient against dropouts, the protocol of~\cite{PracticalSA_GIKM17} also requires
additional communication and coordination between the parties. Specifically,
public keys and encrypted shares are routed from one client to another through the central
coordination server, incurring extra communication costs.
More precisely, for one round, the total communication cost is
\begin{equation}
    C \cdot \left( 2 C \cdot a_K + (5 C-4)a_S + 2N \lceil \log_2 T \rceil \right)~~\text{bits},
\end{equation}
where $a_K=256$ is the number of bits in a public key,
$a_S=256$ is the number of bits in an encrypted share
and $\mathbb{Z}_T$ is the field in which all operations are evaluated (e.g. $T=2^{32}$). We refer to Appendix~\ref{appendix:PSA-CommCost} for more details about this communication cost.
The main drawbacks of this approach are its high computation cost and the fact that
aggregated updates are revealed to the aggregator server. In the collaborative FL
setting we investigate, the trade-offs made to tailor this protocol to the mobile device
use-case are not necessary.

\subsection{Secure Submodel Aggregation}
In~\cite{Submodel_NWTH19}, the authors introduce a new FL method to securely train a
deep interest network (DIN) in the context of mobile clients
(low computation, low bandwidth, low space).
In their protocol, each client updates only a small part of the global
model, a \emph{submodel}, the size of which depends on the number of the
client's previously bought products.
The main steps of the secure submodel aggregation are given as follows.
\begin{enumerate}
    \item Each client securely retrieves their submodel
    (without revealing his interest classes) from the aggregator server
    thanks to a \emph{private information retrieval} (PIR) protocol.

    \item The clients perform a \emph{private set union} (PSU) to
    obtain the union of their interest sets without revealing their own interest set.

    \item The clients and the server perform a secure aggregation on the submodel
    defined by the union of the interest sets.
\end{enumerate}

To accomplish this aggregation practically, the authors focus on two main concepts.
First, to reduce communication cost, clients only download submodels and never need
to download the full network, which can be massive in large-scale e-commerce applications.
Second, the secure aggregation is split into two components to scale costs according
to the client interest sets: the PSU step preceding the secure aggregation, which
permits the secure aggregation to be performed for only a fragment of the original,
massive DIN.

With respect to computational costs associated with their secure protocol,
their proposed PSU protocol is implemented with Bloom filters \cite{Bloom70},
thus requiring many hash function evaluations in order to build the different
filters. This extra hashing requirement can also incur significant computation
cost that scales with the size of the clients' interest sets.

In our demonstrations, we will not compare with this approach, as its proposed
secure aggregation is specific to the DIN use-case and cannot be applied on
generic neural networks.
Unlike the model-tailored approach of~\cite{Submodel_NWTH19}, our proposed technique
is based on simple concepts which can be generalized across a wide range of
neural network architectures.
While we do propose a two-step approach to efficient aggregation of compressed
model updates, as well, our PSU step does not utilize costly Bloom filter calculations.

\subsection{TernGrad Compression with Secure Aggregation}
To the best of our knowledge, only one proposal combines neural network update
compression with secure aggregation~\cite{EaSTLy_DCSW20}.
In this work, the authors make use of \texttt{TernGrad}~\cite{TernGrad_WXYW17}
for model update compression
and subsequently suggest two methods to perform the secure aggregation:
one based on HE and the second based on TSS.
With \texttt{TernGrad}, a vector $X \in \mathbb{R}^N$ is compressed as following
\begin{equation}
    \texttt{TernGrad}(X) = \lVert X \rVert_{\infty}\left( \text{sgn}(X) \odot B\right)
\end{equation}
where given $X$, each element of $B$ is sampled independently from a Bernoulli
distribution such that $\text{Pr}[B[k]=1 | X] = \lVert X \rVert_{\infty}^{-1} \left|X[k]\right|$.
Hence, the compressed vector consists of a scalar factor equal to
$\lVert X \rVert_{\infty}$  and a ternary vector $\text{sgn}(X) \odot B$
with values in $\{-1, 0, 1\}$.
Due to the construction of the unbiased stochastic quantizer used in
\texttt{TernGrad}, the compression ratio of the model update is not
a controllable parameter, however, the authors of~\cite{TernGrad_WXYW17}
demonstrate that around 50\% of model updates values are ignored during training.

In the secure aggregation of~\cite{EaSTLy_DCSW20}, the authors propose to
securely evaluate the sum of the ternary vectors and subsequently each
client updates their local model from this aggregated ternary vector and according to
their own local factor $||U_i||_{\infty}$ where $U_i$ is the model updates of client $i$.
With this aggregation, contrary to traditional FL methods, each client obtains a
different intermediate model at the beginning of each federated round.
The authors did not investigate the possibility for training divergence over the
course of federated training using such an approach. Additionally, since each
client obtains a different model, it is necessary to explain how these different
models should be used; e.g. do they generalize to other tasks individually? Should
they be aggregated through some other technique? While interesting in the context
of decentralized learning, the prospect of multi-model training is not well
explored in the FL literature. Contrary to this approach, we focus on the federated
training of a \emph{single} model across decentralized clients.

With respect to computation cost, the authors propose two different approaches
to perform the secure aggregation, each of which requires its own flavor of
costly cryptographic procedures.
For the version based on TSS, the implementation requires the evaluation of some polynomial interpolations, while their version based on Paillier HE requires
some expensive homomorphic encryption and decryption operations.
For communication costs, the authors do not take into account the sparsity
of the ternary vector and thus, their communication cost is not optimal with
respect to the significant information contained in the model update.
Moreover, with HE, the ciphertext is usually much larger than the plaintext data,
incurring an extra communication cost for its use.
More precisely, the total communication cost per round for their TSS-based secure
aggregation is equal to
\begin{equation}
    2 S C N \lceil \log_2 (2C + 1) \rceil \text{ bits},
\end{equation}
and the total communication cost per round for their HE secure aggregation is equal to
\begin{equation}
    C N (prec + pad) \text{ bits},
\end{equation}
where $prec = 24$ and $pad = 8$ are HE parameters used to avoid overflows.

In our proposed method, we adapt a compressed FL learning strategy to be more amenable to secure computation
in order to obtain a secure aggregation which has a lower communication and computation costs than reported in~\cite{PracticalSA_GIKM17,EaSTLy_DCSW20}.
Table~\ref{tab:related_works} summarizes the communication and computation costs of the secure aggregations from
\cite{PracticalSA_GIKM17,EaSTLy_DCSW20}.

redpajama_set_name: RedPajamaArXiv