# Efficient Secure Aggregation for Privacy-Preserving Federated Machine
Learning

Rouzbeh Behnia  University of South Florida  ,  Mohammadreza Ebrahimi
University of South Florida  ,  Arman Riasi  Virginia Tech  ,  Sherman Chow
The Chinese University of Hong Kong  ,  Balaji Padmanabhan  University of
South Florida  and  Thang Hoang  Virginia Tech

###### Abstract.

Secure aggregation protocols ensure the privacy of users’ data in the
federated learning settings by preventing the disclosure of users’ local
gradients. Despite their merits, existing aggregation protocols often incur
high communication and computation overheads on the participants and might not
be optimized to handle the large update vectors for machine learning models
efficiently. This paper presents e-SeaFL, an efficient, verifiable secure
aggregation protocol taking one communication round in aggregation. e-SeaFL
allows the aggregation server to generate proof of honest aggregation for the
participants. Our core idea is to employ a set of assisting nodes to help the
aggregation server, under similar trust assumptions existing works placed upon
the participating users. For verifiability, e-SeaFL uses authenticated
homomorphic vector commitments. Our experiments show that the user enjoys five
orders of magnitude higher efficiency than the state of the art (PPML 2022)
for a gradient vector of a high dimension up to $100,000$.

Federated learning, privacy-preserving machine learning, secure aggregation,
data privacy

††copyright: none

##  1\. Introduction

Federated learning (FL) is promising in training centralized machine-learning
(ML) models from the contribution of distributed parties while maintaining the
privacy of their local data (Konečnỳ et al., 2016b, a). The participating
parties train a “local model” on their local data instead of directly sharing
them with others. At the end of each iteration, the local gradient updates
representing the changes needed to improve the global model are then
transmitted back to a central server, which is tasked to make use of them to
derive and return an updated version of a global ML model to the participants.

Unfortunately, local gradients could leak information about users’ data (Hitaj
et al., 2017). For instance, in developing next-word prediction models
(Goodman et al., 2002), the gradients could leak individual words typed by
users. Observing that the FL server does not need to have access to the
individual gradients but only needs an element-wise weighted average of the
gradient vectors in deriving the updated/final model; we can use a secure
aggregation protocol (Naor et al., 1999; Chase and Chow, 2009; Bonawitz et
al., 2017) to compute the sum of weights (followed by a division of a publicly
known number of participants), which keeps individual gradients private. The
secure aggregation protocol of Bonawitz et al. (Bonawitz et al., 2017) let
each user mask their gradients with two random masking terms that are selected
symmetrical (among each user pair) and then secret-shared among other users
(Naor et al., 1999; Chase and Chow, 2009). Their protocol requires multiple
rounds of communication. Since then, a large body of privacy-preserving
aggregation protocols have been proposed, mainly based on multi-party
computation (MPC) (e.g., (Bell et al., 2020; Jahani-Nezhad et al., 2022;
Fereidooni et al., 2021; Guo et al., 2020, 2022)).

The core practical challenges (Bonawitz et al., 2017) include achieving the
following:

  1. (1)

Efficient processing of high-dimensional gradient vectors.

  2. (2)

Efficient setup for users with weak devices and connections.

  3. (3)

Robustness against users dropping out.

  4. (4)

Strong security against malicious attacks such as model poisoning in a server-
mediated environment.

###  1.1. Related Works

Most existing works (listed in Table 1) require multiple rounds of
communication, each of which often incurs a high user computation overhead.
Some use homomorphic encryption, e.g., (Zhang et al., 2020; Dasu et al.,
2022), which, instead, often incurs very high computational overhead for high-
dimensional vectors. These works (e.g., (Guo et al., 2022)) might not scale
for large models (e.g., foundation models (Bommasani et al., 2021)) with
billions of parameters (Floridi and Chiriatti, 2020), failing the first and
second requirements, or scale with the number of users (e.g., (Beguier and
Tramel, 2020)).

Meanwhile, most existing protocols can only tolerate a small fraction of user
dropouts since enough shares are needed to reconstruct the secrets of the
dropout users. Lastly, most prior works assume the aggregation server always
yields honest aggregations of the individual gradients, which may not be the
case in practice. This assumption can have adverse consequences in certain
applications (e.g., (Milajerdi et al., 2019)) where the trained model can be
later comprised by exploiting the maliciously aggregated final model (Fang et
al., 2020; Cao and Gong, 2022; Bhagoji et al., 2018).

###  1.2. Our Contribution

We propose e-SeaFL, an Efficient SEcure Aggregation for Federated Learning
that tackles all of the above challenges (Bonawitz et al., 2017). As Table 1
shows, e-SeaFL only requires one communication round during aggregation.
e-SeaFL also significantly minimizes the computational overhead as compared to
the state-of-the-art (Guo et al., 2022). For instance, for gradients vectors
with $100,000$ weights from with $1,000$ users (Figure 4), e-SeaFL is around
five orders of magnitudes faster in the aggregation phase for both users and
the server. Given its efficiency, e-SeaFL can efficiently handle high-
dimension gradient vectors required for training capable large/foundation
models (Bommasani et al., 2021). e-SeaFL also scales out to a large number of
users and is highly tolerant to dropout users. Last but not least, e-SeaFL
allows the aggregation server to generate a proof of honest aggregation in
each iteration to ensure the integrity of the model. e-SeaFL is secure in both
the semi-honest and malicious settings. We also prove the security of its
aggregation integrity module.

###  1.3. Technical Highlights

To hide a secret update $w_{i}$. MPC-based approaches (e.g., (Bonawitz et al.,
2017; Bell et al., 2020; Guo et al., 2022)) require each user $\mathtt{P}_{i}$
to derive a mask term $h_{i}$, which can be canceled out when the masked
updates are aggregated as in $\sum_{i\in[n]}{h_{i}=0}$. Each pair of users
$\mathtt{P}_{i}$ and $\mathtt{P}_{j}$ use (non-interactive) key agreement to
derive a key $\mathtt{mk}_{i,j}$, which can be used to derive the mask for
each iteration, to be canceled when both $\mathtt{P}_{i}$ and $\mathtt{P}_{j}$
participated. For robustness against dropout users, $\mathtt{mk}_{i,j}$ is
secret-shared, say, by $t$-out-of-$n$ Shamir secret sharing (Shamir, 1979).
For security against a malicious server, the protocol often involves more than
one masking term.

1\. Assisting nodes based on similar trust assumptions. Most existing works
(e.g., (Bonawitz et al., 2017; Bell et al., 2020; Guo et al., 2022)) assume a
subset of users _must_ remain honest. On one hand, we want more data
contribution from more users. On the other hand, the number of
dishonest/compromised users might eventually outnumber honest users. We relax
and extend this assumption to a set of _assisting nodes_ , which shares a
secret seed with the users and assist the server in unmasking the final
gradient by providing partial aggregated masking terms of the participating
users derived from the seeds. Our security guarantee here is that even if all
but one of the assisting nodes corrupt, the user gradients will not be leaked.
This allows a simpler design for efficiency improvement during both setup and
aggregation We note that the use of similar _assisting_ entities has been in
many other domains (e.g., (David et al., 2022; Wang et al., 2018; Huang et
al., 2017; Behnia and Yavuz, 2021)). Moreover, a rotating set of users can
serve as assisting nodes in each training phase, especially when the overhead
imposed on the assisting nodes is even lower than that of users in efficient
protocols such as MicroFedML (Guo et al., 2022).

2\. Poising detection via proof of honest aggregation. The malicious security
model of existing work (Bonawitz et al., 2017; Bell et al., 2020; Guo et al.,
2022)) only considers privacy attacks and does not capture the integrity of
the final model computed by the aggregation server. An attempt to achieve the
proof of integrity (Guo et al., 2020)) was shown to be insecure, and the
potential fix (if secure) could affect the computation overhead of the
protocol. e-SeaFL utilizes authenticated homomorphic vector commitments to
provide proof of honest aggregation to the participating parties. Namely, each
user first commits to their gradient. The homomorphism and unforgeability
enable individual users to check the integrity of the final aggregated model.

Table 1. Communication cost of a user for a training iteration

Round | BIK (Bonawitz et al., 2017) | BBG (Bell et al., 2020) | MicroFedML1 (Guo et al., 2022) | MicroFedML2 (Guo et al., 2022) | e-SeaFL
---|---|---|---|---|---
1: | $O(n)$ | $O(1)$ | 1 | 1 | $O(k)+1$
2: | $O(n)$ | $O(\log n)$ | 1+$n$ bits | 1+$\log n$ bits |
3: | 1 | $O(\log n)$ | $O(n)$ | $O(\log n)$ |
4: | $O(n)$ | $1$ |  |  |
5: | $O(n)$ | $O(\log n)$ |  |  |
6: |  | $O(\log n)$ |  |  |

  * •

Here we only consider security in the malicious setting: $n$ is the total
number of users; $k$ is the number of assisting nodes in e-SeaFL, which can be
as small as $2$.

Figure 1. e-SeaFL system model

##  2\. Preliminaries

Notations. We denote vectors by bold lowercase letters (e.g., →a).
$a\stackrel{{\scriptstyle\$}}{{\leftarrow}}{}\mathbb{Z}$ denotes $a$ is
randomly sampled from $\mathbb{Z}$. We use a hash function $\mathtt{H}(\cdot)$
to map the input to our masking term vector space. Let
$\mathbf{g}=(g_{1},\dots,g_{d})$ and $\mathbf{x}=(x_{1},\dots,x_{n})$, we
denote $\mathbf{g}^{\mathbf{x}}=\prod_{i=1}^{d}g_{i}^{x_{i}}$.

###  2.1. Cryptographic Building Blocks

A key exchange protocol allows two parties to agree on a symmetric key
securely over a public channel.

###### Definition 0 (Key Exchange).

A key exchange protocol is a tuple of algorithms
$\Sigma:({\mathtt{KeyGen}},{\mathtt{Agree}})$ defined as follows.

  * •

$(\mathsf{pk}_{\Sigma},\mathsf{sk}_{\Sigma})\leftarrow{\mathtt{KeyGen}}(1^{\kappa})$:
Takes as input a security parameter $\kappa$ and outputs a key pair
$(\mathsf{pk}_{\Sigma},\mathsf{sk}_{\Sigma})$.

  * •

${\mathtt{x}}^{\mathtt{U}_{2}}_{\mathtt{U}_{1}}\leftarrow{\mathtt{Agree}}(\mathsf{pk}_{\Sigma}^{\mathtt{U}_{1}},\mathsf{sk}_{\Sigma}^{\mathtt{U}_{2}})$:
Takes as input the public key of any user
$\mathsf{pk}_{\Sigma}^{\mathtt{U}_{1}}$ and the private key of user
$\mathtt{U}_{2}$, $\mathsf{sk}_{\Sigma}^{\mathtt{U}_{2}}$, and outputs a
shared secret key ${\mathtt{x}}^{\mathtt{U}_{2}}_{\mathtt{U}_{1}}$.

For semi-honest security any probabilistic polynomial time (PPT) adversary who
is given two honestly generated public keys
$\mathsf{pk}_{\Sigma}^{\mathtt{P}_{1}}$ and
$\mathsf{pk}_{\Sigma}^{\mathtt{P}_{2}}$, but without either of the
corresponding secret keys ($\mathsf{sk}_{\Sigma}^{\mathtt{P}_{1}}$ or
$\mathsf{sk}_{\Sigma}^{\mathtt{P}_{2}}$), is unable to distinguish the shared
secret ${\mathtt{x}}^{\mathtt{P}_{1}}_{\mathtt{P}_{2}}$ from a uniformly
random value. A malicious adversary has additional access to an oracle
$\mathcal{O}^{{\mathtt{Agree}}(\cdot)}$ and is able to learn the output for
any pair of keys except for $\mathtt{P}_{1}$ and $\mathtt{P}_{2}$. We can use
the protocols used in existing works (Bonawitz et al., 2017; Bell et al.,
2020) based on the corresponding Diffie-Hellman assumptions.

###### Definition 0 (Digital Signatures).

A digital signature scheme $\Pi$ for a messages space $\mathcal{M}_{\Pi}$ is
defined by ${\mathtt{KeyGen}}$, ${\mathtt{Sign}}$, and ${\mathtt{Verify}})$:

  * •

$(\mathsf{pk},\mathsf{sk})\leftarrow{\mathtt{KeyGen}}(1^{\kappa})$: Takes as
input a security parameter $\kappa$ and outputs a key pair
$(\mathsf{pk}_{\Pi},\mathsf{sk}_{\Pi})$.

  * •

$\sigma\leftarrow{\mathtt{Sign}}(\mathsf{sk}_{\Pi},m)$: Takes as input
$\mathsf{sk}_{\Pi}$ and a message $m\in\mathcal{M}_{\Pi}$ and outputs a
signature $\sigma$.

  * •

$\\{0,1\\}\leftarrow{\mathtt{Verify}}(\mathsf{pk}_{\Pi},m,\sigma)$: Takes as
input $\mathsf{pk}_{\Pi}$, a message $m\in\mathcal{M}_{\Pi}$, a signature
$\sigma$ and outputs $1$ if $\sigma$ is a valid signature under
$\mathsf{pk}_{\Pi}$ for message $m$. Otherwise, it outputs $0$.

Correctness requires that for any $m\in\mathcal{M}_{\Pi}$,
${\mathtt{Verify}}(\mathsf{pk}_{\Pi},m,\sigma)=1$, where
$(\mathsf{pk}_{\Pi},\mathsf{sk}_{\Pi})\leftarrow{\mathtt{KeyGen}}(1^{\kappa})$
and $\sigma\leftarrow{\mathtt{Sign}}(\mathsf{sk}_{\Pi},m)$.

Existential unforgeability against adaptive chosen message attacks is the de
facto standard. It requires that any PPT adversary which has provided a public
key and access to a signing oracle cannot create a forgery on a message not
queried to the oracle.

###### Definition 0 (Authenticated encryption (Bellare and Namprempre, 2000)).

Given a shared secret key ${\mathtt{x}}\in\mathcal{K}_{\mathtt{AE}}$ in a key
space $\mathcal{K}_{\mathtt{AE}}$, an authenticated encryption
$\mathtt{AE}:(\mathtt{enc},\mathtt{dec})$ is defined as follows.

  * •

$c\leftarrow\mathtt{enc}({\mathtt{x}},m)$: Takes as input a shared secret key
${\mathtt{x}}$ and a message $m\in\mathcal{M}_{\mathtt{AE}}$ (for a message
space $\mathcal{M}_{\mathtt{AE}}$) and outputs a ciphertext $c$.

  * •

$\\{m,\bot\\}\leftarrow\mathtt{dec}({\mathtt{x}},c)$: Takes as input a shared
secret key ${\mathtt{x}}$ and a ciphertext $c$ and outputs either the original
message $m$ or an error $\bot$.

Indistinguishability against chosen-plaintext attack (IND-CPA property)
requires that any PPT adversary has only negligible advantage in
distinguishing between ciphertexts of two different adversarially-chosen
messages.

Ciphertext integrity (INT-CTXT) requires that no PPT adversary can forge valid
ciphertexts of messages not queried to the encryption oracle.

###### Definition 0 (Vector Commitment).

A vector commitment $\mathtt{VC}:(\mathtt{Setup},\mathtt{Comm})$ for a vector
space $\mathcal{M}^{d}_{\mathtt{VC}}$, randomness space
$\mathcal{R}_{\mathtt{VC}}$, and commitment space $\mathcal{C}_{\mathtt{VC}}$
consists of the following PPT algorithms

  * •

$\mathtt{pp}\leftarrow\mathtt{Setup}(1^{\kappa},d)$: Takes as input security
parameter $\kappa$ and vector length $d$, and outputs public parameter
$\mathtt{pp}$.

  * •

$\mathtt{cm}\leftarrow\mathtt{Comm}(\mathbf{x},r)$: Takes as input a vector
$\mathbf{x}$ and a randomness $r$, and outputs a committed value
$\mathtt{cm}$.

VC offers homomorphic property under $(\mathcal{M}^{d},*)$, $(\mathcal{R},*)$,
$(\mathcal{C},\bullet)$ that
$\forall\mathbf{x}_{1},\mathbf{x}_{2}\in\mathcal{M}^{d}$,
$r_{1},r_{2}\in\mathcal{R}$,
$\mathtt{VC}.\mathtt{Comm}(\mathbf{x}_{1},r_{1})\bullet\mathtt{VC}.\mathtt{Comm}(\mathbf{x}_{2},r_{2})=\mathtt{VC}.\mathtt{Comm}(\mathbf{x}_{1}*\mathbf{x_{2}},r_{1}*r_{2})$.

For security:

  * •

Binding: For all PPT adversaries $\mathtt{Adv}$,
$\mathtt{pp}\leftarrow\mathtt{VC}.\mathtt{Setup}(1^{\kappa},d)$,
$(\mathbf{x}_{0},\mathbf{x}_{1})\leftarrow\mathtt{Adv}(\mathtt{pp}),b\stackrel{{\scriptstyle\$}}{{\leftarrow}}\\{0,1\\}$,
$r\stackrel{{\scriptstyle\$}}{{\leftarrow}}\mathcal{R}$,
$\mathtt{cm}=\mathtt{VC}.\mathtt{Comm}(\mathbf{x}_{b},r)$, and
$b^{\prime}\leftarrow\mathtt{Adv}(\mathtt{pp},\mathtt{cm})$, there exists a
negligible function $\mathtt{negl}$ such that

$\left|\Pr[b=b^{\prime}]-\frac{1}{2}\right|\leq\mathtt{negl}(\kappa)$

  * •

Hiding: For all PPT $\mathtt{Adv}$,
$\mathtt{pp}\leftarrow\mathtt{VC}.\mathtt{Setup}(1^{\kappa},d)$, and
$(\mathbf{x}_{0},\mathbf{x}_{1},r_{0},r_{1})\leftarrow\mathtt{Adv}(\mathtt{pp})$
such that $\mathbf{x}_{0},\mathbf{x}_{1}\in\mathcal{M}^{n}$, there exists a
negligible function $\mathtt{negl}$ such that
$\Pr[\mathtt{VC}.\mathtt{Comm}(\mathbf{x}_{0},r_{0})=\mathtt{VC}.\mathtt{Comm}(\mathbf{x}_{1},r_{1})]\leq\mathtt{negl}(\kappa)$

To provide proof of the model integrity (see Fig. 1 and Fig. 2), we utilize an
authenticated Pederson vector commitment $\mathtt{APVC}$ (Le et al., 2023).
$\mathtt{APVC}$ permits the commitor to commit to a vector in a way that
allows the commitor to verify the authenticity of committed value.
$\mathtt{APVC}$ has an extra algorithm
$\rho\leftarrow\mathtt{KeyGen}(1^{\kappa})$ that takes as input a security
parameter $\kappa$, and outputs a secret $\rho$ as follows.

###### Definition 0 (Authenticated Pedersen Vector Commitment).

Given $\mathcal{M},\mathcal{R}=\mathbb{Z}_{p}$, $\mathcal{C}=\mathbb{G}$ of
order $p$, an authenticated Pedersen vector commitment
$\mathtt{APVC}:(\mathtt{Setup},\mathtt{KeyGen},\mathtt{Comm})$ is defined as
follows.

  * •

$(\vec{g},h)\leftarrow\mathtt{Setup}(1^{\kappa},d)$: Takes as input a security
parameter $\kappa$ and an integer $d$ it outputs a vector
$\mathbf{g}=(g_{1},\dots,g_{d})$ and
$h\stackrel{{\scriptstyle\$}}{{\leftarrow}}\mathbb{G}$.

  * •

$\rho\leftarrow\mathtt{KeyGen}(1^{\kappa})$: Takes as input a security
parameter $\kappa$ and outputs
$\rho\stackrel{{\scriptstyle\$}}{{\leftarrow}}\mathbb{Z}_{p}$.

  * •

$\mathtt{cm}\leftarrow\mathtt{Comm}(\rho,\mathbf{x},r):$ Takes as input an
input vector $\mathbf{x}=(x_{1},\dots,x_{d})$, $\rho$ and $r$ and outputs the
commitment $\mathtt{cm}\leftarrow
h^{r}\mathbf{g}^{\rho\mathbf{x}}=h^{r}\prod_{i=1}^{n}g_{i}^{\rho
x_{i}}\in\mathbb{G}$.

$\mathtt{APVC}$ is homomorphic under $(\mathbb{Z}_{p}^{n},+)$,
$(\mathbb{Z}_{p},+)$, and $(\mathbb{G},\cdot)$. Specifically,
$\mathtt{Comm}(\rho,\mathbf{x}_{1},r_{1})\cdot\mathtt{Comm}(\rho,\mathbf{x}_{2},r_{2})=\allowbreak\mathtt{Comm}(\rho,\mathbf{x}_{1}+\mathbf{x}_{2},r_{1}+r_{2})$.

###### Definition 0 (Unforgeability modulo homomorphism).

Unforgeability of $\mathtt{APVC}$ is defined via a game
$\mathsf{EUGame}_{\mathtt{Adv}}(\kappa)$ between challenger $\mathcal{C}$ and
adversary $\mathtt{Adv}$: Setup. The challenger $\mathcal{C}$ samples a random
secret $\rho\stackrel{{\scriptstyle\$}}{{\leftarrow}}\mathcal{K}$, and
initializes an empty list $\mathcal{L}$ which records the responds to
$\mathtt{Adv}$’s queries in form of tuples $(\mathbf{x},r)$ and can be queried
s.t. $\mathbf{x}\leftarrow\mathcal{L}(r)$.

Query. $\mathtt{Adv}$ adaptively submits a query to $\mathcal{C}$ as
$\big{(}\mathbf{x},r\big{)}$, where $\mathbf{x}$ is a vector to be committed,
and $r$ is randomly sampled. $\mathcal{C}$ rejects if $r\in\mathcal{L}$.
Otherwise, $\mathcal{C}$ computes
$\mathtt{cm}\leftarrow\mathtt{APVC}.\mathtt{Comm}(\rho,\mathbf{x},r)$ and
sends $\mathtt{cm}$ to $\mathtt{Adv}$. $\mathcal{C}$ adds $(r;\mathbf{x})$ to
$\mathcal{L}$.

Output. $\mathtt{Adv}$ outputs a vector $\mathbf{x}^{*}$, a commitment
$\mathtt{cm}^{*}$, $m$ randoms $(r^{*}_{1},\dots,r^{*}_{m})$, and $m$
constants $(c^{*}_{1},\dots,c^{*}_{m})$ such that
$\sum_{i=1}^{m}c^{*}_{i}r^{*}_{i}\notin\mathcal{L}$, $\mathtt{Adv}$  _wins_
and the game outputs $1$ if (i)
$\mathtt{cm}^{*}=\mathtt{APVC}.\mathtt{Comm}(\rho,\mathbf{x}^{*},\sum_{i=1}^{m}c^{*}_{i}r^{*}_{i})$,
(ii) $(c^{*}_{1},\dots,c^{*}_{m})$ are not all zeros (trivial forgery), and
(iii) Unforgeability is w.r.t. homomorphism: Either 1) $\exists
r^{*}_{i}\notin\mathcal{L}$ for some $i\in[m]$, or 2
)$r^{*}_{i}\in\mathcal{L},\forall i\in[m]$ and
$\mathbf{x}^{*}\neq\prod_{i=1}^{m}(c_{i}\cdot\mathbf{x}_{i})$, where
$\mathbf{x}_{i}\leftarrow\mathcal{L}(r^{*}_{i})$. $\mathtt{APVC}$ achieves
_unforgeability_ if
$\Pr[\mathsf{EUGame}_{\mathtt{Adv}}(\kappa)]\leq\mathtt{negl}(\kappa).$

###  2.2. System Model

###### Definition 0 (Aggregation Protocol (Bonawitz et al., 2017; Bell et al.,
2020)).

An aggregation protocol $\Gamma:(\mathcal{P},\mathcal{A},\mathtt{S},T)$ with a
set of users $\mathcal{P}$, an aggregation server $\mathtt{S}$, set of
assisting nodes $\mathcal{A}$, and integer set $T$, takes places in two
phases:

  * •

_Setup Phase_ : This phase runs only once to set up the entities with their
keys and complete key distribution.

  * •

_Aggregation Phase_ : This phase runs for $T$ iterations. Each iteration $t\in
T$ of starts by each party $\mathtt{P}_{i}$ computing a local update
$w_{t}^{\mathtt{P}_{i}}$ and ends by the server outputting the update
$w_{t}=\sum_{\mathtt{P}_{i}\in\mathcal{P}}w_{t}^{\mathtt{P}_{i}}$ based on the
input provided by each participating party.

Correctness with dropout rate $\delta$ is said to hold if in each iteration
$t\in T$, for all the sets of offline users
$\mathcal{P}_{o}\subset\mathcal{P}$ where
$|\mathcal{P}_{o}|<\delta|\mathcal{P}|$, the server outputs
$w_{t}=\sum_{\mathtt{P}_{i}\in\mathcal{P}\setminus\mathcal{P}_{o}}w_{t}^{\mathtt{P}_{i}}$
with an overwhelming probability.

As Figure 1 illustrates, our system consists of:
1) $n$ parties (or interchangeably “users”)
$\\{\mathtt{P}_{1},\dots,\mathtt{P}_{n}\\}$ who aim to contribute to
collaborative training a shared model by computing local gradient vectors
$\vec{w}^{\mathtt{P}_{i}}_{t}$ on their (private) data at each iteration $t$.
2) A set of $k$ assisting nodes $\\{\mathtt{A}_{1},\dots,\mathtt{A}_{k}\\}$
which securely assist the aggregation server in aggregating the local updates.
We note that given the low computation and communication overhead of the
assisting node, we can consider a set of rotating users to assume the role of
assisting nodes in each iteration.
3) A central aggregation server $\mathtt{S}$, which is in charge of
aggregating the local user’s updates $\vec{w}_{t}^{\mathtt{P}_{i}}$ and
sending the updated model $\vec{w}_{t}$ back to the users after each completed
iteration.

Our departure from the existing system models (e.g., (Bonawitz et al., 2017;
Bell et al., 2020; Guo et al., 2022)) is the introduction of the $k$ assisting
nodes. The assisting nodes only communicate with the user in the
initialization phase, and the users only send a (authenticated) participation
message to the assisting nodes in each iteration.

Next, we elaborate on the workflow and discuss the additional steps needed in
each phase to provide proof of model aggregation integrity.

  1. (1)

_Setup phase_ : The Setup phase is a one-time process that could potentially
be carried out (at least in-part) offline. This phase takes place in one round
only, namely, _KeyGen and Advertise_. At the end of this phase, all the
parties $\\{\mathtt{P}_{1},\dots,\mathtt{P}_{n}\\}$ and assisting nodes
$\\{\mathtt{A}_{1},\dots,\mathtt{A}_{k}\\}$ are initialized with the key
exchange scheme (plus a digital signature scheme in the malicious setting)
public keys. The assisting nodes and the aggregation server receive a copy of
the user public keys. Additionally, all parties
$\\{\mathtt{P}_{1},\dots,\mathtt{P}_{n}\\}$ and assisting nodes
$\\{\mathtt{A}_{1},\dots,\mathtt{A}_{k}\\}$ have a computed a shared secret
${\mathtt{x}}$.

  2. (2)

_Aggregation phase_ : This phase consists of two rounds: _Masking Updates_ and
_Aggregate Updates_. As in Figure 1:
Step [1]1: Each party $\mathtt{P}_{i}$, after computing the local update
$\mathbf{w}^{\mathtt{P}_{i}}_{t}$, compute the masked update
$\mathbf{y}_{t}^{\mathtt{P}_{i}}$.
Step [1]2: $\mathtt{P}_{i}$ sends the masked update
$\mathbf{y}_{t}^{\mathtt{P}_{i}}$ and a participation message to the
aggregation server $\mathtt{S}$ and the $k$ assisting nodes, respectively.
Step [1]3: After receiving the participation message from the participants,
each assisting node computes an aggregated masking vector
$\mathbf{a}^{\mathtt{A}_{j}}_{t}$.
Step [1]4: All the assisting nodes $\\{\mathtt{A}_{1},\dots,\mathtt{A}_{k}\\}$
send their aggregated masks $\mathbf{a}^{\mathtt{A}_{j}}_{t}$ for
$j\in\\{1,\dots,j\\}$ to $\mathtt{S}$. For malicious security, the outgoing
messages are signed by the assisting nodes.
Step [1]5: $\mathtt{S}$ aggregates the final model using the user’s local
masked updates $\mathbf{y}_{t}^{\mathtt{P}_{i}}$ and the aggregated masks
$\mathbf{a}^{\mathtt{A}_{j}}_{t}$ provided by the assisting nodes.
Step [1]6: The aggregation server sends the updated model $\mathbf{w}_{t}$ to
the parties.

We also present an extension to the e-SeaFL protocol to protect the model’s
integrity against model poisoning attacks. This is done by enabling the
aggregation server $\mathtt{S}$ to provide proof of honest aggregation. To
achieve this, additional steps are to be taken in both the Setup and the
Aggregation phases. In the KeyGen and Advertise round (in the Setup phase),
one assisting node needs to compute a system-wide authenticated secret and
disseminates it to all the parties in the system. Additionally, in the
Aggregation phase, after computing the local update, each user needs to send
an authenticated commitment to the aggregation server. Lastly, in the last
step of the Aggregate updates round, $\mathtt{S}$ disseminates to all the
users the proof of honest aggregation to check if the final model was indeed
formed by honestly aggregating the local updates. To avoid a single point of
failure, one can initiate the protocol by having all the assisting nodes
generate different system-wide authenticated secrets with a small
communication and computation overhead.

###  2.3. Threat Model

The adversary’s goal is to learn any information about the individual updates
$\vec{w}^{\mathtt{P}_{i}}_{t}$. The adversary is assumed to be able to control
the aggregation server and a bounded fraction of the users and assisting
nodes. To capture the unstable network bandwidth in FL settings, we also allow
the adversary to drop or disconnect a fraction of users $\delta$. To preserve
the privacy of the user updates, we only require one of the assisting nodes to
be honest.

In the semi-honest setting, following the literature on multi-party
computation (Evans et al., 2018), the adversary corrupts parties but follows
the protocol. The corrupt parties run the protocol honestly but attempt to
infer secret information by observing the communication/message they receive
from other parties. This scenario can be perceived as a group of passive but
colluding parties pooling their views to learn about the secret information.

In the malicious setting, the corrupted parties actively deviate from the
protocol in order to undermine security (Evans et al., 2018). A malicious
adversary has all the capabilities of a semi-honest adversary in analyzing the
protocol communication, but it can also take any action such as dropping out,
ignoring certain communication, or sending incorrect messages during the
protocol execution (Evans et al., 2018).

In this work, we realistically assume that a malicious aggregation server can
poison the model by not honestly aggregating the local updates (Fang et al.,
2020; Cao and Gong, 2022; Bhagoji et al., 2018). We therefore propose an
extension that ensures the integrity of the final model and allows
participants to verify (in each iteration) that the aggregation server did
honestly aggregate the local user updates.

Following the work in (Bell et al., 2020), we define a summation protocol as
being $\alpha$-secure if the honest parties can be guaranteed that their
secret input is aggregated at most once with the minimum of
$\alpha|\mathcal{P}_{H}|$ other secrets, where $\mathcal{P}_{H}$ is the set of
honest parties. Similar to (Bell et al., 2020), we will use this summation
protocol in our simulation-based proof.

###### Definition 0.

[$\alpha$-summation ideal functionality] For integers $p,n,d$ and
$\alpha\in[0,1]$, let $L\subseteq[n]$ and
$\mathcal{X}_{L}:=\\{\vec{x}_{i}\\}_{i\in{L}}$ where
$\vec{x}_{i}\in\mathbb{Z}_{p}^{d}$. For $Q_{L}$ as the set of partitions of
$L$ and a collection of pairwise disjoint subsets $\\{L_{1},\dots,L_{l}\\}\in
Q_{L}$, the $\alpha$-summation ideal functionality for all subsets in $Q_{L}$
is denoted as $\mathcal{F}_{\mathbf{x},\alpha}(\cdot)$ and computes
$\mathcal{F}_{\mathbf{x},\alpha}(\\{L_{i}\\}_{i\in[1,\dots,l]})\rightarrow\\{\vec{s}_{i}\\}_{i\in[1,\dots,l]}$
where

$\forall j\in[1,\dots,l],\vec{s}_{j}=\begin{cases}\sum_{j\in
Q_{L}}\mathbf{x}_{j}&\text{if}~{}Q_{L}|\geq\alpha|L|\\\
\bot&\text{otherwise.}\end{cases}$

We use the above definition to define the privacy of our protocol later by
characterizing what an adversary, with control over the aggregation server,
cloud learn from the protocol.

Following (Bonawitz et al., 2017; Guo et al., 2022), we define the notion of
privacy against semi-honest/malicious adversaries in the following.

###### Definition 0.

[Privacy of secure aggregation protocols] Given a secure signature scheme
$\Pi$ and a key exchange protocol $\Sigma$ instantiated with security
parameter $\kappa$, an aggregation protocol
$\Gamma:({\mathcal{P},\mathtt{S},\mathcal{A},}T)$, as defined in Definition 7,
provides privacy against a semi-honest (malicious) adversary $\mathtt{Adv}$,
if there is exist a PPT simulator $\mathtt{Sim}$ that for any iteration
$t\in\\{1,\dots,T\\}$, and all input vectors
$\mathcal{X}^{t}=\\{\vec{x}_{1},\dots,\vec{x}_{n}\\}$, generates an output
that is computationally indistinguishable from the view of $\mathtt{Adv}$. We
assume the adversary $\mathtt{Adv}$ that controls $\mathtt{S}$,
$\lambda_{\mathtt{P}}$ fraction of users and $\lambda_{\mathtt{A}}$ fraction
of assisting nodes and its view consists of the joint view of the corrupted
server $\mathtt{S}^{*}$, the set of corrupted users $\mathcal{P}_{C}$ and
corrupted assisting nodes $\mathcal{A}_{C}$:
$\mathsf{REAL}^{\Gamma(\mathcal{P},\mathtt{S},\mathcal{A},T)}_{\mathcal{S}^{*},\mathcal{P}_{C},\mathcal{A}_{C},t}(\mathtt{Adv},\\{\vec{x}_{i}\\}_{i\in\mathcal{P}\backslash\mathcal{C}_{\mathtt{P}}})\approx_{\kappa}\\\
\mathsf{Simul}^{\Gamma(\mathcal{P},\mathtt{S},\mathcal{A},T),\mathcal{F}_{\mathcal{X}^{t},\alpha}(\cdot)_{\\{\vec{x}_{i}\\}_{i\in\mathcal{P}\backslash\mathcal{P}_{C}}}}(\mathtt{Adv})$

We also consider an adversary that targets the integrity of the final model by
compromising the aggregation server to replace or insert arbitrary gradients
to poison the final model (Fang et al., 2020; Cao and Gong, 2022; Bhagoji et
al., 2018). Malicious users could also attempt model poisoning by submitting
malicious gradient updates. However, there exist a number of mitigations
(e.g., (Rathee et al., 2022)).

##  3\. Our secure aggregation protocol

We present the concrete construction of e-SeaFL in Algorithm 1 and Algorithm
2. We consider the local updates $\vec{w}_{t}^{\mathtt{P}_{i}}$ as high-
dimensional vectors instead of individual coordinates as in many of the
existing works.

Algorithm 1 e-SeaFL Setup phase

Input: All parties are provided with the security parameter $\kappa$, the
number of assisting nodes $k$, a key exchange protocol $\Sigma$:
$({\mathtt{KeyGen}},{\mathtt{Agree}})$, a digital signature scheme $\Pi$:
$({\mathtt{KeyGen}},{\mathtt{Sign}},{\mathtt{Verify}})$, an authenticated
commitment scheme $\mathtt{APVC}$ with public parameters
$\mathtt{pp}=(\mathbf{g}=(g_{1},\dots,g_{d}),h)$, and an authenticated
symmetric encryption scheme $\mathtt{AE}$, instantiated using the security
parameter $\kappa$.

Output: All the entities generate their key exchange and signature key pairs.
All the users receive the public keys of all the assisting nodes
$\langle{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\uline{(\mathsf{pk}^{\mathtt{A}_{1}}_{\Pi},\dots,\mathsf{pk}^{\mathtt{A}_{k}}_{\Pi}),}}(\mathsf{pk}^{\mathtt{A}_{1}}_{\Sigma},\dots,\mathsf{pk}^{\mathtt{A}_{k}}_{\Sigma})\rangle$,
and shared secret seed ${\mathtt{x}}^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}$ for
each assisting node $\mathtt{A}_{j}$. All the assisting nodes receive the
public keys of all the participating users
$\langle({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\uline{\mathsf{pk}^{\mathtt{P}_{1}}_{\Pi},\dots,\mathsf{pk}^{\mathtt{P}_{n}}_{\Pi}),}}(\mathsf{pk}^{\mathtt{P}_{1}}_{\Sigma},\dots,\mathsf{pk}^{\mathtt{P}_{n}}_{\Sigma})\rangle$,
and a shared secret seed ${\mathtt{x}}^{\mathtt{A}_{j}}_{\mathtt{P}_{i}}$ with
each user $\mathtt{P}_{i}$. All the users receive the public keys of all the
assisting nodes
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\langle(\mathsf{pk}^{\mathtt{A}_{1}}_{\Pi},\dots,\mathsf{pk}^{\mathtt{A}_{k}}_{\Pi}),}(\mathsf{pk}^{\mathtt{A}_{1}}_{\Sigma},\dots,\mathsf{pk}^{\mathtt{A}_{k}}_{\Sigma})\rangle$,
and shared secret seed ${\mathtt{x}}^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}$ for
each assisting node $\mathtt{A}_{j}$.  Lastly, the aggregation server
$\mathtt{S}$ receives the public keys of all the users and assisting nodes
$\langle(\mathsf{pk}^{\mathtt{P}_{1}}_{\Pi},\dots,\mathsf{pk}^{\mathtt{P}_{k}}_{\Pi}),(\mathsf{pk}^{\mathtt{A}_{1}}_{\Pi},\dots,\mathsf{pk}^{\mathtt{A}_{k}}_{\Pi})\rangle$.

Round 1 (KeyGen and Advertise)

All the communications below are conducted via an authenticated channel
(similar to (Bonawitz et al., 2017; Guo et al., 2022))

1:Each user $\mathtt{P}_{i}$ generates its key pair(s)
$(\mathsf{sk}^{\mathtt{P}_{i}}_{\Pi},\mathsf{pk}^{\mathtt{P}_{i}}_{\Pi})\leftarrow\Pi.{\mathtt{KeyGen}}(\kappa)$
and
$(\mathsf{sk}^{\mathtt{P}_{i}}_{\Sigma},\mathsf{pk}^{\mathtt{P}_{i}}_{\Sigma})\leftarrow\Sigma.{\mathtt{KeyGen}}(\kappa)$
and sends the keys
$({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathsf{pk}^{\mathtt{P}_{i}}_{\Pi},}\mathsf{pk}^{\mathtt{P}_{i}}_{\Sigma})$
to the $k$ assisting nodes and $\mathsf{pk}^{\mathtt{P}_{i}}_{\Pi}$ to the
aggregation server.

2:Each assisting node $\mathtt{A}_{j}$ generates its key pair(s)
$(\mathsf{sk}^{\mathtt{A}_{j}}_{\Pi},\mathsf{pk}^{\mathtt{A}_{j}}_{\Pi})\leftarrow\Pi.{\mathtt{KeyGen}}(\kappa)$
and
$(\mathsf{sk}^{\mathtt{A}_{j}}_{\Sigma},\mathsf{pk}^{\mathtt{A}_{j}}_{\Sigma})\leftarrow\Sigma.{\mathtt{KeyGen}}(\kappa)$
and sends
$({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\mathsf{pk}^{\mathtt{A}_{j}}_{\Pi},}\mathsf{pk}^{\mathtt{A}_{j}}_{\Sigma})$
to the $n$ users  and sends $\mathsf{pk}^{\mathtt{A}_{j}}_{\Pi}$ the
aggregation server.

3:Upon receiving $\mathsf{pk}^{\mathtt{P}_{i}}_{\Sigma}$ from
$\mathtt{P}_{i}$, each assisting node $\mathtt{A}_{j}$ computes the shared
secret seed as
${\mathtt{x}}^{\mathtt{A}_{j}}_{\mathtt{P}_{i}}\leftarrow\Sigma.{\mathtt{Agree}}(\mathsf{sk}^{\mathtt{A}_{j}}_{\Sigma},\mathsf{pk}^{\mathtt{P}_{i}}_{\Sigma})$.

4:Upon receiving $\mathsf{pk}^{\mathtt{A}_{j}}_{\Sigma}$ from the assisting
node $\mathtt{A}_{j}$, the user $\mathtt{P}_{i}$ computes the shared secret
seed as
${\mathtt{x}}^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}\leftarrow\Sigma.{\mathtt{Agree}}(\mathsf{sk}^{\mathtt{P}_{i}}_{\Sigma},\mathsf{pk}^{\mathtt{A}_{j}}_{\Sigma})$.

5:One assisting node executes
$\rho\leftarrow\mathtt{APVC}.\mathtt{KeyGen}(1^{\kappa})$, computes
$c_{\mathtt{A}_{j}}^{\mathtt{P}_{i}}\leftarrow\mathtt{AE.enc}({\mathtt{x}}_{\mathtt{A}_{j}}^{\mathtt{P}_{i}},\rho)$
for all $i\in\\{1,\dots,n\\}$, and distribute
$c_{\mathtt{A}_{j}}^{\mathtt{P}_{i}}$ to the $n$ users.

6:Upon receiving $c_{\mathtt{A}_{j}}^{\mathtt{P}_{i}}$, each user
$\mathtt{P}_{i}$ computes
$\rho\leftarrow\mathtt{AE.dec}({\mathtt{x}}_{\mathtt{P}_{i}}^{\mathtt{A}_{j}},c_{\mathtt{A}_{j}}^{\mathtt{P}_{i}})$.

7:The aggregation server $\mathtt{S}$ generates a key pair
$(\mathsf{sk}^{\mathtt{S}}_{\Pi},\mathsf{pk}^{\mathtt{S}}_{\Pi})\leftarrow\Pi.{\mathtt{KeyGen}}(1^{\kappa})$
and sends $\mathsf{pk}^{\mathtt{S}}_{\Pi}$ to the users.

Algorithm 2 e-SeaFL Aggregation phase

Input: The iteration $t$, a user calculated model update
$\mathbf{w}^{\mathtt{P}_{i}}_{t}$, a keyed hash function $\mathtt{H}(\cdot)$,
a digital signature scheme $\Pi$, an authenticated commitment scheme
$\mathtt{APVC}$, an authenticated symmetric encryption scheme $\mathtt{AE}$,
the secret seeds ${\mathtt{x}}$ (shared between the users and the nodes) and
the signature key pair of the users and the assisting nodes.

Output: The final model update $\mathbf{w}_{t}\in\mathcal{M}^{d}$.

Round 1 (Masking Updates)

1:Upon computing the final updates $\vec{w}^{\mathtt{P}_{i}}_{t}$ for
iteration $t$, the user $\mathtt{P}_{i}$ computes
$\vec{a}^{\mathtt{P}_{i}}_{t}=\sum_{j=1}^{k}\mathtt{H}({\mathtt{x}}^{\mathtt{P}_{i}}_{\mathtt{A}_{j}},t)$
and the masked update
$\mathbf{y}^{\mathtt{P}_{i}}_{t}=\mathbf{w}^{\mathtt{P}_{i}}_{t}+\vec{a}^{\mathtt{P}_{i}}_{t}$.

2:The user $\mathtt{P}_{i}$ computes
$\mathtt{cm}^{\mathtt{P}_{i}}_{t}\leftarrow\mathtt{APVC}.\mathtt{Comm}(\rho,\mathbf{w}^{\mathtt{P}_{i}}_{t},\mathbf{\vec{a}}^{\mathtt{P}_{i}}_{t}[0])$
.

3:The user sets
$m=(t,\mathbf{y}^{\mathtt{P}_{i}}_{t},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\dashuline{\mathtt{cm}^{\mathtt{P}_{i}}_{t}}})$
and $m^{\prime}=(t)$, computes signatures
$\sigma^{\mathtt{P}_{i}}_{\mathtt{S}}\leftarrow\Pi.{\mathtt{Sign}}(\mathsf{sk}^{\mathtt{P}_{i}}_{\Pi},m)$
and
$\sigma^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}\leftarrow\Pi.{\mathtt{Sign}}(\mathsf{sk}^{\mathtt{P}_{i}}_{\Pi},m^{\prime})$
and sends
$(m{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\uline{,\sigma^{\mathtt{P}_{i}}_{\mathtt{S}}}})$
and
$(m^{\prime}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0},\sigma^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}})$
to the aggregation server and the assisting node $\mathtt{A}_{j}$ (for
$j\in[1,\dots,k]$), respectively.

Round 2 (Aggregate Updates)

1:Upon receiving
$(m^{\prime}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\uline{,\sigma^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}}})$
from all the users in the system, $\mathtt{A}_{j}$ checks if
$\Pi.{\mathtt{Verify}}(\mathsf{pk}_{\Pi}^{\mathtt{P}_{i}},m^{\prime},\sigma^{\mathtt{P}_{i}}_{\mathtt{A}_{j}})\stackrel{{\scriptstyle?}}{{=}}1$
holds, it adds the user to its user list $\mathcal{L}_{j,t}$.

2:Each assisting node checks if
$|\mathcal{L}_{j,t}|\geq\alpha\mathcal{P}_{H}$, it computes
$\vec{a}^{\mathtt{A}_{j}}_{t}=\sum_{i=1}^{|\mathcal{L}_{j,t}|}\mathtt{H}({\mathtt{x}}^{\mathtt{A}_{j}}_{\mathtt{P}_{i}},t)$,
sets $m^{\prime\prime}=(t,|\mathcal{L}_{j,t}|,\vec{a}^{\mathtt{A}_{j}}_{t})$
and
$\sigma^{\mathtt{A}_{i}}_{\mathtt{S}}\leftarrow\Pi.{\mathtt{Sign}}(\mathsf{sk}^{\mathtt{A}_{j}}_{\Pi},m^{\prime\prime})$
and sends
$(m^{\prime\prime}{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\uline{,\sigma^{\mathtt{A}_{j}}_{\mathtt{S}}}})$
to the aggregation server $\mathtt{S}$.

3:Upon receiving
$(m{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}\uline{,\sigma^{\mathtt{P}_{i}}_{\mathtt{S}}}})$,
$\mathtt{S}$ first checks if
$\Pi.{\mathtt{Verify}}(\mathsf{pk}_{\Gamma}^{\mathtt{P}_{i}},m,\sigma^{\mathtt{P}_{i}}_{\mathtt{S}})\stackrel{{\scriptstyle?}}{{=}}1$
holds, it adds $\mathtt{P}_{i}$ to its user list $\mathcal{L}_{\mathtt{S},t}$.

4:Next, $\mathtt{S}$ checks if
$\Pi.{\mathtt{Verify}}(\mathsf{pk}_{\Pi}^{\mathtt{A}_{j}},m^{\prime\prime},\sigma^{\mathtt{A}_{j}}_{\mathtt{S}})\stackrel{{\scriptstyle?}}{{=}}1$
holds for $j\in[1,\dots,k]$. It then checks if
$|\mathcal{L}_{\mathtt{S},t}|=|\mathcal{L}_{1,t}|=\dots=|\mathcal{L}_{k,t}|$,
does not hold it aborts. Otherwise, it computes and broadcasts the final
update as
$\mathbf{w}_{t}=\sum_{i=1}^{|\mathcal{L}_{\mathtt{S},t}|}\mathbf{y}^{\mathtt{P}_{i}}_{t}-\sum_{j=1}^{k}\vec{a}^{\mathtt{A}_{j}}_{t}$.

5:For all the users in $|\mathcal{L}_{\mathtt{S},t}|$, $\mathtt{S}$ computes
$x_{t}=\prod_{i=1}^{n}\mathtt{cm}^{\mathtt{P}_{i}}_{t}\prod_{j=1}^{k}h^{-\mathbf{\vec{a}}_{t}^{A_{j}}[0]}$
and sends $(x_{t},\mathbf{w}_{t})$ to the online users. Otherwise, it aborts.

6:The user $\mathtt{P}_{i}$ checks if
$\mathbf{g}^{\mathbf{w}_{t}\cdot\rho}\stackrel{{\scriptstyle?}}{{=}}x_{t}$
holds. If yes, the user accepts $\mathbf{w}_{t}$ as the valid aggregated
model. Otherwise, the user aborts.

The red and underlined parts are required to provide security in the malicious
setting and are not needed in the semi-honest setting. The blue and dashed-
underlined parts are required to provide proof of model integrity and are not
required for the semi-honest or malicious settings. e-SeaFL relies on
authenticated commitment (Definition 5) and authenticated symmetric encryption
(Definition 3) for integrity.

###  3.1. Detailed Construction

We introduce a set of assisting nodes to assist the aggregation server in
securely aggregating the local gradients and computing the final model. Our
approach is to extend the assumption made in most of the existing protocols,
which rely on a subset of honest users, to a set of assisting nodes.
Therefore, for the privacy guarantee of our protocol to hold, we only require
one of the assisting nodes to be honest. As we will discuss shortly (in
Section 4), the computation and communication overhead of the assisting nodes
is on par, if not lower, than the users in some of our most efficient
counterparts. Thus, we can assume a rotating set of users (similar to (David
et al., 2022)) to assume the role of the assisting nodes in each iteration.

In the KeyGen and Advertise round in Algorithm 1, for the semi-honest setting,
each user generates a key pair
$(\mathsf{sk}^{\mathtt{P}_{i}}_{\Sigma},\mathsf{pk}^{\mathtt{P}_{i}}_{\Sigma})$
for the key exchange protocol to computes a shared secret
${\mathtt{x}}_{\mathtt{P}_{i}}^{\mathtt{A}_{j}}$ with assisting nodes
$\mathtt{A}_{j}$. For the malicious setting, users and assisting nodes are
also initialized with signature key pairs. This will be used to sign outgoing
communications in the Aggregation phase (Algorithm 2). For the proof of the
model’s integrity, the underlying $\mathtt{APVC}$ algorithm is initialized,
and the system secret $\rho$ is computed, encrypted (with each users’ shared
secret) and sent to all the users.

The first round of the Aggregation phase (Algorithm 2) starts by the user
computing a masking vector $\vec{a}_{t}^{\mathtt{P}_{i}}$ (using the shared
secrets ${\mathtt{x}}_{\mathtt{P}_{i}}^{\mathtt{A}_{j}}$ for
$j=\\{1,\dots,k\\}$) to mask its local gradient vector
${\vec{w}_{t}^{\mathtt{P}_{i}}}$. To achieve the model’s integrity, each user
computes a commitment $\mathtt{cm}^{\mathtt{P}_{i}}$ on their local gradient
using $\mathtt{APVC}.\mathtt{Comm}(\cdot)$ and sends it to the aggregation
server. Next, the masked gradient $\vec{y}_{t}^{\mathtt{P}_{i}}$ and a
participation message (e.g., the iteration number) are sent to the aggregation
server and the $k$ assisting nodes, respectively. In the malicious setting,
the outgoing messages are signed using $\Pi.{\mathtt{Sign}}(\cdot)$.

In the second round of the Aggregation phase (Algorithm 2), for the semi-
honest (malicious) setting, upon receiving (and verifying) the participating
message (and signature), each $\mathtt{A}_{j}$ adds the user to the list
$\mathcal{L}_{j,t}$. Then for all users in $\mathcal{L}_{j,t}$, it computes
the aggregation of all their masking terms $\vec{a}^{\mathtt{A}_{j}}_{t}$
(using the shared keys ${\mathtt{x}}^{\mathtt{A}_{j}}_{\mathtt{P}_{i}}$) and
sends $\vec{a}^{\mathtt{A}_{j}}_{t}$ to the aggregation server. In the
malicious setting, the assisting nodes sign all their outgoing messages using
$\Pi.{\mathtt{Sign}}(\cdot)$. Next, for the semi-honest (malicious) setting,
upon receiving (and verifying) the participating message (and signature),
$\mathtt{S}$ adds the user to the list $\mathcal{L}_{\mathtt{S},t}$. Then it
checks if all the user lists (assisting node’s and the aggregation server’s)
are equal. Then, for all the users in $\mathcal{L}_{\mathtt{S},t}$, the server
uses the masked updates (i.e., $\vec{y}_{t}^{\mathtt{P}_{i}}$ and the
aggregated masking terms $\vec{a}^{\mathtt{A}_{j}}_{t}$, supplied by the
assisting nodes, to efficiently compute the final model. To provide the proof
of the model’s integrity, $\mathtt{S}$ computes $x$ using the users’
commitments $\mathtt{cm}^{\mathtt{P}_{i}}_{t}$. Lastly, $\mathtt{S}$ sends the
final model (and $x$ for the proof of integrity) back to the participating
users.

###  3.2. Security Analysis

In this section, we discuss how e-SeaFL achieves privacy against semi-honest
and malicious adversary and provides proof of model integrity to ensure final
model’s security. However, before we discuss the security and privacy of
e-SeaFL, we first discuss the correctness of the protocol is resistant to user
dropouts.

###### Theorem 1.

Given a secure and correct key exchange protocol 1, e-SeaFL protocol presented
in Algorithms 1 and 2, with parameters $(1-\delta)\geq\alpha$ guarantees
correctness with $\delta$ offline rate.

###### Proof.

Correctness directly follows from that of the underlying key exchange
protocol. Each user’s update (e.g., $\mathbf{w_{t}^{\mathtt{P}_{i}}}$) is
masked by the sum of $k$ masking terms computes as
$\vec{a}^{\mathtt{P}_{i}}_{t}=\sum_{j=1}^{k}\mathtt{PRF}({\mathtt{x}}^{\mathtt{P}_{i}}_{\mathtt{A}_{j}},t)$,
where the secure pseudorandom function $\mathtt{PRF}(\cdot)$ is invoked on the
input of the iteration number $t\in{T}$ and a shared secret key
${\mathtt{x}}^{\mathtt{A}_{j}}_{\mathtt{P}_{i}}$ between $\mathtt{P}_{i}$ and
the $k$ assisting nodes $\mathtt{A}_{j}$ for $j\in\\{1,\dots,k\\}$. The shared
secret key ${\mathtt{x}}$ is derived in the Setup phase (Algorithm 1), by
invoking the $\Sigma.{\mathtt{Agree}}(\cdot)$ algorithm of the underlying key
exchange protocol. Following Algorithm 1, $\mathtt{P}_{i}$ computes
${\mathtt{x}}^{\mathtt{A}_{j}}_{\mathtt{P}_{i}}\leftarrow\Sigma.{\mathtt{Agree}}(\mathsf{sk}^{\mathtt{A}_{j}}_{\Sigma},\mathsf{pk}^{\mathtt{P}_{i}}_{\Sigma})$
and $\mathtt{A}_{j}$ computes
${\mathtt{x}}^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}\leftarrow\Sigma.{\mathtt{Agree}}(\mathsf{sk}^{\mathtt{P}_{i}}_{\Sigma},\mathsf{pk}^{\mathtt{A}_{j}}_{\Sigma})$,
and the correctness of the underlying key exchange protocol ensures that
${\mathtt{x}}^{\mathtt{A}_{j}}_{\mathtt{P}_{i}}={\mathtt{x}}^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}$.
For the online user list $\mathcal{L}_{\mathtt{A}_{j},t}$, each assisting node
computes
$\vec{a}^{\mathtt{A}_{j}}_{t}=\sum_{i=1}^{|\mathcal{L}_{j,t}|}\mathtt{PRF}({\mathtt{x}}^{\mathtt{A}_{j}}_{\mathtt{P}_{i}},t)$.
Now, given
${\mathtt{x}}^{\mathtt{A}_{j}}_{\mathtt{P}_{i}}={\mathtt{x}}^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}$
for all $\mathtt{P}_{i}$ and $\mathtt{A}_{j}$, it is easy to see
$\sum_{j=1}^{k}\vec{a}^{\mathtt{A}_{j}}_{t}=\sum_{i=1}^{\mathcal{L}_{\mathtt{S},t}}\vec{a}^{\mathtt{P}_{i}}_{t}$
and
$\sum_{i=1}^{|\mathcal{L}_{\mathtt{S},t}|}\vec{y}^{\mathtt{P}_{i}}_{t}-\sum_{j=1}^{k}\vec{a}^{\mathtt{A}_{j}}_{t}=\sum_{i=1}^{|\mathcal{L}_{\mathtt{S},t}|}\vec{w}_{t}^{\mathtt{P}_{i}}+\sum_{i=1}^{|\mathcal{L}_{\mathtt{S},t}|}\vec{a}_{t}^{\mathtt{P}_{i}}-\sum_{j=1}^{k}\vec{a}^{\mathtt{A}_{j}}_{t}=\sum_{i=1}^{|\mathcal{L}_{\mathtt{S},t}|}\vec{w}_{t}^{\mathtt{P}_{i}}.$

This is satisfied when the number of participating honest parties
$(1-\delta)|\mathcal{P}_{h}|\geq\alpha|\mathcal{P}_{h}|$, where $\alpha$ is
defined in Definition 8. ∎

For user dropouts, unlike its predecessors (e.g., (Bonawitz et al., 2017; Bell
et al., 2020; Guo et al., 2022)), e-SeaFL’s aggregation phase is one-round.
Users only send a single message flow and can go offline during an iteration.
As long as the number of participating parties in each iteration satisfies
$|\mathcal{P}_{t}|\geq\alpha|\mathcal{P}_{h}|$, the final model can be
computed.

To ensure consistency, one could assume a dispute phase between the assisting
nodes where if a user is missing from a certain assisting node’s list, the
missing user participation message (signature) can be delivered to the
assisting node to update their list. We can also assume the same star network
topology where the user sends everything through the aggregation server and
the server distributes them to the assisting nodes.

Privacy Against Semi-Honest Adversary. Following (Bonawitz et al., 2017; Bell
et al., 2020; Guo et al., 2022), we consider two scenarios. In the first one,
the adversary only controls a subset of the users and assisting nodes, but not
the server. The proof of such a setting is rather trivial since the joint view
of any subset of the users and assisting nodes is fully independent of other
entities in the system. The second scenario considers the adversary that
controls the aggregation server in addition to a subset of users and assisting
nodes. We prove the security of our protocol against such a semi-honest
adversary in the following.

###### Theorem 2.

The e-SeaFL protocol presented in Algorithms 1 and 2, running with $n$ parties
$\\{\mathtt{P}_{1},\dots,\mathtt{P}_{n}\\}$, $k$ assisting nodes
$\\{\mathtt{A}_{1},\dots,\mathtt{A}_{k}\\}$, and an aggregation server
$\mathtt{S}$ provides privacy against a semi-honest adversary $\mathtt{Adv}$
which controls $\mathtt{S}$ and $1-\alpha$ fraction of users and $k-1$
assisting nodes with the offline rate $(1-\delta)\geq\alpha$.

###### Proof.

Please refer to Appendix. ∎

Privacy Against Malicious Adversaries. As in Section 1, two possible scenarios
are considered for the malicious setting. The first scenario that the
malicious adversary $\mathtt{Adv}$does not have control over the server
$\mathtt{S}$can be easily proven using the same rationale as in 1. In the
following, we consider an $\mathtt{Adv}$that controls $\mathtt{S}$ along with
a subset of the users and assisting nodes.

###### Theorem 3.

The e-SeaFL protocol presented in Algorithms 1 and 2, running with $n$ parties
$\\{\mathtt{P}_{1},\dots,\mathtt{P}_{n}\\}$, $k$ assisting nodes
$\\{\mathtt{A}_{1},\dots,\mathtt{A}_{k}\\}$, and an aggregation server
$\mathtt{S}$ provides privacy against a malicious adversary $\mathtt{Adv}$
which controls $\mathtt{S}$ and $1-\alpha$ fraction of users and $k-1$
assisting nodes with the offline rate $(1-\delta)\geq\alpha$.

###### Proof.

Please refer to Appendix. ∎

###### Lemma 0.

The protocol provided in Algorithms 1 and 2 with $\mathtt{APVC}$ offers local
model’s privacy and aggregation integrity against semi-honest/malicious
adversary $\mathtt{Adv}$.

###### Proof.

To prove this lemma we first prove the local model’s privacy in the presence
of $\mathtt{APVC}$, following the proof of Theorems 2 and 3 and how it affects
the certain hybrids in the proofs. We then prove the aggregation integrity. As
highlighted in the protocol description, in its plain form, we require the
initiating assisting node $\mathtt{A}_{j}$ to be honest. This proof applies to
the other extensions discussed in the paper.

In the Setup phase and $\mathtt{Hyb2}$ of the proofs $\mathtt{A}_{j}$ samples
random $\rho$ and $c_{\mathtt{A}_{j}}^{\mathtt{P}_{i}}$. Note that the
indistinguishability of this hybrid would also rely on the security of the
underlying vector commitment scheme $\mathtt{APVC}$ and the authenticated
symmetric encryption scheme $\mathtt{AE}$. In $\mathtt{Hyb3}$, the user will
also outputs $\mathtt{cm}^{\mathtt{P}_{i}}_{t}$. Note that the
indistinguishability of this hybrid relies on the _hiding_ property of the
underlying vector commitment scheme $\mathtt{APVC}$.

In $\mathtt{Hyb5}$, $\mathtt{Sim}$ sets
$x\leftarrow\vec{g}^{\vec{w}_{t}\cdot\rho}$ and sends $x$ along with the final
model $\vec{w}_{t}$. Therefore, the view of all the corrupted parties
controlled by $\mathtt{Adv}$ is computationally indistinguishable.

Next, we prove the integrity. The unfogearbility property of $\mathtt{APVC}$
permits the user to verify whether the linear combination of local weight
models (which is the aggregation) has been computed correctly. Let
$\mathbf{w}^{\prime}_{t}=\mathbf{w}_{t}+\epsilon$ be the tampered aggregated
model, where $\mathbf{\epsilon}$ is the error vector introduced by the
malicious server and
$\mathbf{w}_{t}=\sum_{i=1}^{n}\mathbf{w}^{\mathtt{P}_{i}}$ is the aggregated
model that is supposed to be computed honestly in the iteration $t$. For the
user to accept $\mathbf{w}^{\prime}_{t}$, the server needs to somehow generate
a valid
$\mathbf{g}^{\mathbf{w}^{\prime}_{t}\cdot\rho}=\mathbf{g}^{(\sum_{i=1}^{n}{\mathbf{w}_{t}^{\mathtt{P}_{i}}}+\mathbf{\epsilon})\cdot\rho}$
from
$\\{\mathbf{g}^{\mathbf{w}^{\mathtt{P}_{i}}\cdot\rho}h^{r^{\mathtt{P}_{i}}}\\}_{i\in[n]}$.
Given that $\rho$ and all $\\{r^{\mathtt{P}_{i}}\\}_{i\in[n]}$ are secret to
the server, this happens with only a negligible probability due to the
unforgeability property (by Definition 6) of $\mathtt{APVC}$, which only
permits the server to perform the predefined linear combination of
$\mathbf{g}^{\mathbf{w}^{\mathtt{P}_{i}}\cdot\rho}$, but nothing else. ∎

##  4\. Experimental Evaluation

###  4.1. Implementation and configurations

Implementation. We implemented our protocol in Python with $1500$ lines of
code. We used coincurve library (Lev, [n. d.]) to implement public key
primitives based on the elliptic curve (EC), including ECDSA signature and EC
Diffie-Hellman (ECDH) key exchange protocols. We used the Python cryptographic
libraries (i.e., hmac and hashlib) to implement hash functions for the masking
terms. We also used the standard Python socket to implement communication
between all the parties.

Parameter choice and counterpart comparison. As alluded to, there is a large
body of research on privacy-preserving aggregation protocol for federated
learning. However, a recent protocol, MicroFedML (Guo et al., 2022), allows
for the reuse of the masking terms in each iteration and hence, has achieved
significant communication and computation efficiency. Therefore, we consider
MicroFedML as our counterpart to evaluate the performance of e-SeaFL.

We have selected the parameters for our protocol and its counterpart to
achieve 128-bit security as follows.

e-SeaFL: We used secp256k1 curve with 256-bit group order for ECDSA and ECDH
protocols. We used SHA-256 for mask generation and set the number of assisting
nodes $k=3$. We evaluate our scheme in both Semi-Honest (SH) and Malicious
(MS) settings.

MicroFedML (Guo et al., 2022): We compare e-SeaFL with the two MicroFedML
instantiations (Guo et al., 2022), namely, MicroFedML1 and MicroFedML2, in the
semi-honest setting. In MicroFedML1, all users communicate with each other via
the aggregation server (star topology). To improve efficiency, following the
idea in (Bell et al., 2020), the users are grouped in smaller sets In
MicroFedML2. We selected the group size of 50 in MicroFedML2. We used the
originally suggested parameters and cryptographic instantiations (Guo et al.,
2022), including $2048$-bit prime, XSalsa20 for authenticated encryption,
Diffie-Hellman key exchange, and SHA-256 hash function. Due to its underlying
building blocks, MicroFedML can only handle weights to up to 20 bits.

Evaluation setting and metrics. We evaluated our protocol and its counterpart
on a local Macbook Pro 2021 with a $3.2$ GHz M1 Pro CPU and $16$ GB RAM. We
considered a range of $200$ to $1000$ users, three assisting nodes, and one
aggregation server. We measure the computation time and the outbound bandwidth
cost of the server, the users, and the assisting nodes (in our protocol) in
both the Setup and Aggregation phases.

To demonstrate the performance of e-SeaFL with high-dimensional gradient
vectors, we report the performance when the weight vector $\mathbf{w}$
consists of 100,000 gradients. In fact, compared to the existing works (e.g.,
(Guo et al., 2022)), our protocol offers a much higher efficiency for weight
vectors with high dimensions since it does not require any expensive
operations (e.g., solving for the discrete logarithm) to compute the final
model from local updates. In MicroFedML, the authors only reported performance
for single gradients. We projected their results for $100,000$ gradient
vectors. For a fair comparison, we also report the results for a single value
gradient. We ran all the experiments $10$ times and reported the average.

###  4.2. Results

$200$$400$$600$$800$$1000$$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$Number
of usersDelay (ms) (log)e-SeaFL (MS)MicroFedML1MicroFedML2 (50) (a) Server

$200$$400$$600$$800$$1000$$10^{-1}$$10^{0}$$10^{1}$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$Number
of usersDelay (ms) (log)e-SeaFL (SH)e-SeaFL (MS)MicroFedML1MicroFedML2 (50)
(b) User

$200$$400$$600$$800$$1000$$0$$20$$40$$60$Number of usersDelay (ms)e-SeaFL
(SH)e-SeaFL (MS) (c) Assisting node

Figure 2. Computation in the Setup phase (The dimension of the weight list is
set to 100K.)

$200$$400$$600$$800$$1000$$10^{4}$$10^{6}$$10^{8}$$10^{10}$$10^{12}$Number of
usersBandwidth (B) (log)e-SeaFL (MS)MicroFedML1MicroFedML2 \- 50 (a) Server

$200$$400$$600$$800$$1000$$10^{2}$$10^{3}$$10^{4}$$10^{5}$$10^{6}$$10^{7}$$10^{8}$$10^{9}$Number
of usersBandwidth (B) (log)e-SeaFL (SH)e-SeaFL (MS)MicroFedML1MicroFedML2 (50)
(b) User

$200$$400$$600$$800$$1000$$2$$4$$6$$8$$\cdot 10^{4}$Number of usersBandwidth
(B)e-SeaFL (SH)e-SeaFL (MS) (c) Assisting node

Figure 3. Outbound bandwidth in the Setup phase (The dimension of the weight
list is set to 100K.)

####  4.2.1. Setup phase

Computation. Figure 2 depicts the computation cost of our protocol in the
Setup phase compared with the one in MicroFedML. As depicted in Figure 2,
e-SeaFL outperforms MicroFedML for both server and user computation in the
semi-honest setting. Specifically, in the semi-honest setting, our server does
not incur any computation, while in the malicious setting, the server takes
0.19 ms to setup (generate an ECDSA key pair), compared to 375.75 and 177.77
ms for MicroFedML1 and MicroFedML2 (Figure 2(a)), respectively. In MicroFedML
protocols, given their design, the server is responsible to communicate all
the keys among the users. Thus, our malicious scheme is
53$\times$–1977$\times$ (for the defined number of users range) faster than
MicroFedML1 and 117$\times$–936$\times$ faster than MicroFedML2.

As shown in Figure 2(b), the user computation in the semi-honest (resp.
malicious) e-SeaFL is 470$\times$–13284$\times$ (resp.
352$\times$–9962$\times$) faster than MicroFedML1 and 173$\times$ (resp.
129$\times$) faster than MicroFedML2, where each user only takes 0.18 ms
(resp. 0.25 ms) to setup, while MicroFedML1 and MicroFedML2 take 2509.34 ms
and 32.71 ms, respectively, for 1000 users. Similar to the server cost,
e-SeaFL incurs a constant user time regardless of the number of users. Each
user only needs to compute a single ECDH key pair (plus a single ECDSA key
pair in the malicious setting), and compute the shared secret with each
assisting node. In MicroFedML, however, after creating the DH keys and
computing the shared secret key with all other users, the user needs to sample
masking term, secret share it to $n$ shares, and encrypt each of the $n$
shares with the shared secret key of all the users in the system.

Unlike MicroFedML, e-SeaFL requires assisting nodes to aid secure aggregation.
However, the computation costs associated with assisting node in e-SeaFL is
highly efficient, where it only takes 11.01 ms and 50.88 ms in semi-honest
setting (and 11.08 ms-51.78 ms in the malicious setting) to setup key
materials for 200 to 1000 users (Figure 2(c)). Each node computes an ECDH key
pair (plus an ECDSA key pair in the malicious setting), and a shared secret
seed for each user, and thus the overhead grows linearly w.r.t the number of
users.

Outbound bandwidth. We present the outbound bandwidth cost of all entities in
e-SeaFL in Figure 3. In the malicious setting, for 1000 users (Figure 3(a)),
the server transmits ~4–5 orders of magnitude less than MicroFedML1 and ~3–4
orders of magnitude less than MicroFedML2 (i.e., 33000 B vs. 1008 MB in
MicroFedML1 and 240 MB in MicroFedML2). The server bandwidth in our malicious
e-SeaFL protocol grows linearly as the number of users increases because the
server transmits its ECDSA public key to 200 to 1000 users. Meanwhile, our
semi-honest protocol does not require the server to transmit anything in the
Setup phase. In MicroFedML however, due to the design, all the communications
such as the distribution of the DH keys and encrypted shares need to be
communicated via the aggregation server, which incurs a significant
communication overhead.

As shown in Figure 3(b), user bandwidth in the semi-honest (resp. malicious)
e-SeaFL is 1877$\times$–9369$\times$ (resp. 804$\times$–4015$\times$) less
than MicroFedML, where each user only transmits a fixed message of size 99 B
(resp. 231 B), while for MicroFedML1 and MicroFedML2 protocols it is
approximately 905 KB and 183 KB, respectively. It is because each user only
needs to transmit an ECDH public key (plus an ECDSA public key in the
malicious setting) to a fixed number of assisting nodes. In MicroFedML, the
users send (via the aggregation server) their DH public keys along with the
encrypted masking shares to all other users in the system.

The bandwidth cost of assisting nodes in e-SeaFL is negligible, where each
node only transmits to 200–1000 users a total of 6–32 KB for the semi honest
protocol and 13–64 KB message for the malicious protocol (Figure 3(c)). The
overhead is due to the broadcast of an ECDH public key (and an ECDSA public
key in the malicious setting) to all the users (and the aggregating server),
and thus, its bandwidth cost grows linearly w.r.t the number of users.

$200$$400$$600$$800$$1000$$10^{2}$$10^{4}$$10^{6}$$10^{8}$$10^{10}$$10^{12}$Number
of usersDelay (ms) (log)e-SeaFL (SH)e-SeaFL (MS)MicroFedML1MicroFedML2 (50)
(a) Server

$200$$400$$600$$800$$1000$$10^{1}$$10^{3}$$10^{5}$$10^{7}$$10^{9}$Number of
usersDelay (ms) (log)e-SeaFL (SH)e-SeaFL (MS)MicroFedML1MicroFedML2 (50) (b)
User

$200$$400$$600$$800$$1000$$0$$10$$20$Number of usersDelay (ms)e-SeaFL
(SH)e-SeaFL (MS) (c) Assisting node

Figure 4. Computation in the Aggregation phase (The dimension of the weight
list is set to 100K.)

$200$$400$$600$$800$$1000$$10^{8}$$10^{10}$$10^{12}$$10^{14}$$10^{16}$Number
of usersBandwidth (B) (log)e-SeaFL (SH)e-SeaFL (MS)MicroFedML1MicroFedML2 (50)
(a) Server

$200$$400$$600$$800$$1000$$10^{6}$$10^{7}$$10^{8}$$10^{9}$$10^{10}$Number of
usersBandwidth (B) (log)e-SeaFL (SH)e-SeaFL (MS)MicroFedML1MicroFedML2 (50)
(b) User

$200$$400$$600$$800$$1000$$0$$50$$100$Number of usersBandwidth (B)e-SeaFL
(SH)e-SeaFL (MS) (c) Assisting node

Figure 5. Outbound bandwidth in the Aggregation phase (The dimension of the
weight list is set to 100K.)

####  4.2.2. Aggregation phase

Computation. Figure 4 shows the computation cost in the aggregation phase for
both e-SeaFL and MicroFedML. In our protocol, all entities incur a small
computation overhead in the Aggregation phase. In particular, for a single
gradient, the server computation time in our semi-honest (resp. malicious)
protocol is 815$\times$–1224$\times$ (resp. 139$\times$–187$\times$) faster
than MicroFedML1 and 891$\times$–1065$\times$ (resp. 117$\times$–222$\times$)
faster than MicroFedML2. When we consider the 100,000 gradients vector, the
server computation time in both of our semi-honest and malicious protocol is
~6 orders of magnitude faster than those in MicroFedML1 and MicroFedML2. When
there are 200 users, the server computation time in semi-honest and malicious
e-SeaFL is only 150.41 ms and 207.34 ms, respectively. Our server computation
time in both settings grows linearly as the number of users increases. In our
semi-honest protocol, the majority of the aggregation server’s cost is due to
the linear summation of the weights and the aggregated masking terms provided
by the assisting nodes. The added 82%–85% of extra overhead in the malicious
setting is due to the signature verification on the local weights sent by the
parties and the signatures on the aggregated masks sent by the assisting
nodes.

For a single gradient, user computation in semi-honest (resp. malicious)
e-SeaFL is 300$\times$–318$\times$ (resp. 120$\times$–127$\times$) faster than
the one in MicroFedML1. As shown in Figure 4(b), for 100,000 gradients vector,
the gap increases and the user computation in semi-honest and malicious
e-SeaFL becomes ~5 orders of magnitude faster than the ones in MicroFedML1 and
MicroFedML2. More precisely, for 1000 users, the user computation time in our
semi-honest (resp. malicious) protocol is only 18.48 ms (resp. 20.21 ms). The
user computation time of our protocol in both settings remains constant as the
number of users grows. Each user computes the masked update by invoking the
hash function (SHA-256) $k$ times (plus two ECDSA signatures in the malicious
setting). Therefore, the cost is linear to the (small) number of assisting
nodes rather than the number of users. In MicroFedML, after computing the mask
update via additive masking the user needs to compute the aggregation of the
masking shares in the exponent.

The computation time of the assisting nodes increases with the number of users
as shown in Figure 4(c); however, the overhead is small. Specifically, for
200–1000 users the assisting node’s time is 0.73–3.90 ms in the semi honest
setting and 3.03–15.22 ms in the malicious setting, due to computing the
aggregated masks for all the users (28%–%40 of total delay), and the signature
verification (in the malicious setting that contributes an extra $60\%$-$72\%$
overhead).

Outbound bandwidth. In Figure 5, we compare the outbound bandwidth costs of
the Aggregation phase for all the entities in our protocol with the ones in
MicroFedML. We have observed that the outbound bandwidth cost for the server
and the user in our protocol is considerably lower than those in the
MicroFedML protocols. As presented in Figure 5(a), the server in our semi-
honest (resp. malicious) protocol incurs $2564\times$–$10000\times$ (resp.
$2564\times$–$10000\times$) less outbound bandwidth overhead compared to
MicroFedML protocols. Specifically, for 1000 users, our protocol incurs is
390625 KB (model size) in the semi-honest and 390625 KB plus an additional 64
B (for signature) in the malicious setting, compared with 3814697 MB in
MicroFedML. In MicroFedML, the server needs to send the list of online users
to all the users in the system. Note that the overhead of distributing the
final model to all users is not captured in MicroFedML.

As shown in Figure 5(b), the user outbound bandwidth cost in our semi-honest
(resp. malicious) protocol is 279$\times$ (resp. 278$\times$)lower than the
one in MicroFedML. Specifically, the user outbound bandwidth is 400016 B for
the semi-honest and 400272 B for the malicious protocol, while it is 108996 KB
in MicroFedML. In addition, the user outbound bandwidth in e-SeaFL depends on
the number of assisting nodes (which is a small constant), and thus, it does
not increase as the number of users increases during the aggregation phase.
Specifically, the user transmits the masked model and the iteration number
(along with signature in the malicious setting) to the aggregation server, and
the iteration number (along with signature in the malicious setting ) to the
three assisting nodes. In MicrofedML, aside from sending the masked update,
the user sends the aggregation of the shares for all online users to the
server.

The outbound bandwidth cost of the assisting nodes in our protocol is small,
and does _not_ depend on the number of users. Specifically, in the semi-honest
setting, the node only sends a message of size 12 B consisting of the masking
term (4 B), the iteration number (4 B) (for $t\leq 128$), and the length of
the user list ( 4 B). For the malicious setting, a signature of size 64 B will
also be transmitted.

####  4.2.3. Performance of Proof of Aggregation Integrity

We measure the performance of our technique based on $\mathtt{APVC}$ to
achieve aggregation integrity against malicious server. In the setup phase,
the assisting node samples a random secret of size 32 B, and sends its
authenticated ciphertext (56 B) to all the users, resulting in a total
outbound bandwidth of 11200–56000 B for 200–1000 users. The encryption (or
decryption at the user side) takes roughly 40–200 ms for 200–1000 users.

In the aggregation phase, _each_ user computes the authenticated commitment
with EC operations, which takes 52208 ms (mostly due to EC scalar
multiplication), and incurs 64 B outbound bandwidth to send it to the server.
The server performs aggregation over the authenticated commitments received
from all the users, which takes a total of 4.02 ms–20.72 ms (mostly due to EC
point additions) and incurs a total of outbound bandwidth of 12800–64000 B for
200–1000 users.

## References

  * (1)
  * Beguier and Tramel (2020) Constance Beguier and Eric W Tramel. 2020.  Safer: Sparse secure aggregation for federated learning.  _arXiv preprint arXiv:2007.14861_ (2020).
  * Behnia and Yavuz (2021) Rouzbeh Behnia and Attilla Altay Yavuz. 2021.  Towards Practical Post-Quantum Signatures for Resource-Limited Internet of Things. In _Annual Computer Security Applications Conference_ (Virtual Event, USA) _(ACSAC ’21)_. Association for Computing Machinery, New York, NY, USA, 119–130.
  * Bell et al. (2020) James Henry Bell, Kallista A. Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. 2020.  Secure Single-Server Aggregation with (Poly)Logarithmic Overhead. In _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_ (Virtual Event, USA) _(CCS ’20)_. Association for Computing Machinery, New York, NY, USA, 1253–1269.  https://doi.org/10.1145/3372297.3417885
  * Bellare and Namprempre (2000) Mihir Bellare and Chanathip Namprempre. 2000.  Authenticated encryption: Relations among notions and analysis of the generic composition paradigm. In _Advances in Cryptology—ASIACRYPT 2000: 6th International Conference on the Theory and Application of Cryptology and Information Security Kyoto, Japan, December 3–7, 2000 Proceedings 6_. Springer, 531–545.
  * Bhagoji et al. (2018) Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo. 2018.  Model poisoning attacks in federated learning. In _Proc. Workshop Secur. Mach. Learn.(SecML) 32nd Conf. Neural Inf. Process. Syst.(NeurIPS)_. 1–23.
  * Bommasani et al. (2021) Rishi Bommasani, Drew A Hudson, Ehsan Adeli, Russ Altman, Simran Arora, Sydney von Arx, Michael S Bernstein, Jeannette Bohg, Antoine Bosselut, Emma Brunskill, et al. 2021\.  On the opportunities and risks of foundation models.  _arXiv preprint arXiv:2108.07258_ (2021).
  * Bonawitz et al. (2017) Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. 2017.  Practical secure aggregation for privacy-preserving machine learning. In _proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_. 1175–1191.
  * Cao and Gong (2022) Xiaoyu Cao and Neil Zhenqiang Gong. 2022.  MPAF: Model Poisoning Attacks to Federated Learning based on Fake Clients. In _Proceedings of the IEEE/CVF Conference on Computer Vision and Pattern Recognition_. 3396–3404.
  * Chase and Chow (2009) Melissa Chase and Sherman S. M. Chow. 2009.  Improving privacy and security in multi-authority attribute-based encryption. In _Proceedings of the 2009 ACM Conference on Computer and Communications Security, CCS 2009, Chicago, Illinois, USA, November 9-13, 2009_. ACM, 121–130.
  * Dasu et al. (2022) Vishnu Asutosh Dasu, Sumanta Sarkar, and Kalikinkar Mandal. 2022\.  PROV-FL: Privacy-preserving Round Optimal Verifiable Federated Learning. In _Proceedings of the 15th ACM Workshop on Artificial Intelligence and Security_. 33–44.
  * David et al. (2022) Bernardo David, Bernardo Magri, Christian Matt, Jesper Buus Nielsen, and Daniel Tschudi. 2022\.  GearBox: Optimal-size Shard Committees by Leveraging the Safety-Liveness Dichotomy. In _Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security_. 683–696.
  * Evans et al. (2018) David Evans, Vladimir Kolesnikov, Mike Rosulek, et al. 2018\.  A pragmatic introduction to secure multi-party computation.  _Foundations and Trends® in Privacy and Security_ 2, 2-3 (2018), 70–246.
  * Fang et al. (2020) Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong. 2020\.  Local model poisoning attacks to $\\{$Byzantine-Robust$\\}$ federated learning. In _29th USENIX Security Symposium (USENIX Security 20)_. 1605–1622.
  * Fereidooni et al. (2021) Hossein Fereidooni, Samuel Marchal, Markus Miettinen, Azalia Mirhoseini, Helen Möllering, Thien Duc Nguyen, Phillip Rieger, Ahmad-Reza Sadeghi, Thomas Schneider, Hossein Yalame, et al. 2021\.  SAFELearn: secure aggregation for private federated learning. In _2021 IEEE Security and Privacy Workshops (SPW)_. IEEE, 56–62.
  * Floridi and Chiriatti (2020) Luciano Floridi and Massimo Chiriatti. 2020.  GPT-3: Its nature, scope, limits, and consequences.  _Minds and Machines_ 30, 4 (2020), 681–694.
  * Goodman et al. (2002) Joshua Goodman, Gina Venolia, Keith Steury, and Chauncey Parker. 2002.  Language modeling for soft keyboards. In _Proceedings of the 7th international conference on Intelligent user interfaces_. 194–195.
  * Guo et al. (2020) Xiaojie Guo, Zheli Liu, Jin Li, Jiqiang Gao, Boyu Hou, Changyu Dong, and Thar Baker. 2020.  VeriFL: Communication-efficient and fast verifiable aggregation for federated learning.  _IEEE Transactions on Information Forensics and Security_ 16 (2020), 1736–1751.
  * Guo et al. (2022) Yue Guo, Antigoni Polychroniadou, Elaine Shi, David Byrd, and Tucker Balch. 2022.  MicroFedML: Privacy Preserving Federated Learning for Small Weights.  _Cryptology ePrint Archive_ (2022).
  * Hitaj et al. (2017) Briland Hitaj, Giuseppe Ateniese, and Fernando Perez-Cruz. 2017\.  Deep models under the GAN: information leakage from collaborative deep learning. In _Proceedings of the 2017 ACM SIGSAC conference on computer and communications security_. 603–618.
  * Huang et al. (2017) Yutao Huang, Xiaoqiang Ma, Xiaoyi Fan, Jiangchuan Liu, and Wei Gong. 2017.  When deep learning meets edge computing. In _2017 IEEE 25th international conference on network protocols (ICNP)_. IEEE, 1–2.
  * Jahani-Nezhad et al. (2022) Tayyebeh Jahani-Nezhad, Mohammad Ali Maddah-Ali, Songze Li, and Giuseppe Caire. 2022.  Swiftagg: Communication-efficient and dropout-resistant secure aggregation for federated learning with worst-case security guarantees.  _arXiv preprint arXiv:2202.04169_ (2022).
  * Konečnỳ et al. (2016a) Jakub Konečnỳ, H Brendan McMahan, Daniel Ramage, and Peter Richtárik. 2016a.  Federated optimization: Distributed machine learning for on-device intelligence.  _arXiv preprint arXiv:1610.02527_ (2016).
  * Konečnỳ et al. (2016b) Jakub Konečnỳ, H Brendan McMahan, Felix X Yu, Peter Richtárik, Ananda Theertha Suresh, and Dave Bacon. 2016b.  Federated learning: Strategies for improving communication efficiency.  _arXiv preprint arXiv:1610.05492_ (2016).
  * Le et al. (2023) Tung Le, Pengzhi Huang, Attila A Yavuz, Elaine Shi, and Thang Hoang. 2023.  Efficient Dynamic Proof of Retrievability for Cold Storage. In _The Network and Distributed System Security Symposium (NDSS) 2023_.
  * Lev ([n. d.]) Ofek Lev. [n. d.].  Cross-platform Python bindings for libsecp256k1.  https://github.com/ofek/coincurve.
  * Milajerdi et al. (2019) Sadegh M Milajerdi, Birhanu Eshete, Rigel Gjomemo, and VN Venkatakrishnan. 2019.  Poirot: Aligning attack behavior with kernel audit records for cyber threat hunting. In _Proceedings of the 2019 ACM SIGSAC conference on computer and communications security_. 1795–1812.
  * Naor et al. (1999) Moni Naor, Benny Pinkas, and Omer Reingold. 1999.  Distributed Pseudo-random Functions and KDCs. In _Advances in Cryptology - EUROCRYPT ’99, International Conference on the Theory and Application of Cryptographic Techniques, Prague, Czech Republic, May 2-6, 1999, Proceeding_. Springer, 327–346.
  * Rathee et al. (2022) Mayank Rathee, Conghao Shen, Sameer Wagh, and Raluca Ada Popa. 2022.  ELSA: Secure Aggregation for Federated Learning with Malicious Actors.  _Cryptology ePrint Archive_ (2022).
  * Shamir (1979) Adi Shamir. 1979\.  How to Share a Secret.  _Commun. ACM_ 22, 11 (nov 1979), 612–613.  https://doi.org/10.1145/359168.359176
  * Wang et al. (2018) Shiqiang Wang, Tiffany Tuor, Theodoros Salonidis, Kin K Leung, Christian Makaya, Ting He, and Kevin Chan. 2018.  When edge meets learning: Adaptive control for resource-constrained distributed machine learning. In _IEEE INFOCOM 2018-IEEE conference on computer communications_. IEEE, 63–71.
  * Zhang et al. (2020) Chengliang Zhang, Suyi Li, Junzhe Xia, Wei Wang, Feng Yan, and Yang Liu. 2020\.  $\\{$BatchCrypt$\\}$: Efficient homomorphic encryption for $\\{$Cross-Silo$\\}$ federated learning. In _2020 USENIX annual technical conference (USENIX ATC 20)_. 493–506.

## Appendix I

### Proof of Theorem 2

###### Proof.

Following Definition 9, we prove the above theorem by the standard hybrid
argument using the simulator $\mathtt{Sim}$. The proof relies on showing the
indistinguishability between different hybrids. We first define the behavior
of our simulator $\mathtt{Sim}$ in each round of the Setup and Aggregation
phase. In the following we define the set of all parties as $\mathcal{P}$,
honest parties as $\mathcal{P}_{h}$ and corrupt parties as $\mathcal{P}_{C}$,
i.e., $\mathcal{P}_{C}=\mathcal{P}\backslash\mathcal{P}_{h}$. We apply the
same notation to the set of assisting nodes $\mathcal{A}$.

_Setup phase:_

  1. (1)

Each honest user $\mathtt{P}_{i}$ and assisting node $\mathtt{A}_{j}$ follows
the protocol in Algorithm 1.

  2. (2)

For each corrupt user $\mathtt{P}_{i^{\prime}}\in\mathcal{P}_{C}$ and honest
assisting node $\mathtt{A}_{j}\in\mathcal{A}_{H}$, $\mathtt{A}_{j}$ computes
and stores
${\mathtt{x}}_{\mathtt{P}_{i^{\prime}}}^{\mathtt{A}_{j}}\leftarrow\Sigma.{\mathtt{Agree}}(\mathsf{sk}_{\Sigma}^{\mathtt{A}_{j}},\mathsf{pk}_{\Sigma}^{\mathtt{P}_{i^{\prime}}})$.

  3. (3)

For each honest user $\mathtt{P}_{i}\in\mathcal{P}_{H}$ and corrupt assisting
node $\mathtt{A}_{j^{\prime}}\in\mathcal{A}_{C}$, $\mathtt{P}_{i}$ computes
and stores
${\mathtt{x}}^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}\leftarrow\Sigma.{\mathtt{Agree}}(\mathsf{sk}_{\Sigma}^{\mathtt{P}_{i}},\mathsf{pk}_{\Sigma}^{\mathtt{A}_{j^{\prime}}})$.

  4. (4)

For each honest pair of user $\mathtt{P}_{i}$ and honest assisting node
$\mathtt{A}_{j}$, $\mathtt{Sim}$ picks
${\mathtt{x}}_{r}\stackrel{{\scriptstyle\$}}{{\leftarrow}}{}\mathcal{K}_{\Sigma}$
and sets
${\mathtt{x}}_{\mathtt{P}_{i}}^{\mathtt{A}_{j}}={\mathtt{x}}^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}={\mathtt{x}}_{r}$.

_Aggregation phase:_

  1. (1)

In each iteration $t$ of the protocol, each honest user picks a random
$\vec{y^{\prime}}_{t}^{\mathtt{P}_{i}}$ and sends $t$ to the assisting nodes
and $(\vec{y^{\prime}}_{t}^{\mathtt{P}_{i}},t)$ to the server.

  2. (2)

The aggregation server $\mathtt{S}$ first adds the user $\mathtt{P}_{i}$ to
the list $\mathcal{L}_{\mathtt{S},t}$ and then calls the $\alpha$-summation
ideal functionality
$\mathcal{F}_{\vec{x},\alpha}(\mathcal{L}_{\mathtt{S},t}\backslash\mathcal{P}_{C})$
(where $\mathcal{P}_{C}$ is the set of corrupt users) to get $\vec{w}_{t}$.

  3. (3)

Next, the simulator samples
$\vec{w^{\prime}}_{t}^{\mathtt{P}_{i}}\stackrel{{\scriptstyle\$}}{{\leftarrow}}{}\mathcal{M}^{d}$
for all $\mathtt{P}_{i}\in\mathcal{L}_{\mathtt{S},t}\backslash\mathcal{P}_{C}$
such that
$\vec{w}_{t}=\sum_{i\in\mathcal{P}_{C}}\vec{w^{\prime}}_{t}^{\mathtt{P}_{i}}$
and computes
$\vec{a^{\prime}}_{t}^{\mathtt{P}_{i}}=\vec{y^{\prime}}_{t}^{\mathtt{P}_{i}}-\vec{w^{\prime}}_{t}^{\mathtt{P}_{i}}$,
by utilizing random oracle, $\mathtt{Sim}$ sets
$\\{\vec{a^{\prime}}_{\mathtt{A}_{j},t}^{\mathtt{P}_{i}}\\}_{\mathtt{A}_{j}\in\mathcal{A}_{H}}=\\{\mathtt{RO}({\mathtt{x}}_{\mathtt{A}_{j}}^{\mathtt{P}_{i}},t)\\}_{\mathtt{A}_{j}\in\mathcal{A}_{H}}$
such that
$\vec{a^{\prime}}_{t}^{\mathtt{P}_{i}}=\sum_{\mathtt{A}_{j}\in\mathcal{A}_{H}}\\{\vec{a^{\prime}}_{\mathtt{A}_{j},t}^{\mathtt{P}_{i}}\\}$,
and for each $\mathtt{A}_{j}\in\mathcal{A}_{H}$, it computes
$\vec{a^{\prime}}_{\mathtt{P}_{i},t}^{\mathtt{A}_{j}}=\sum_{\mathtt{P}_{i}\in\mathcal{P}_{H}}\vec{a^{\prime}}_{j,t}^{\mathtt{P}_{i}}$.

We present our hybrids below. The hybrids represent different views of the
system as seen by corrupted entities e.g., aggregation server, assisting
nodes, and/or users), and the proof is based on the assumption that these
views are computationally indistinguishable from each other. The simulator
$\mathtt{Sim}$ is used to construct these hybrids, and the adversary
$\mathtt{Adv}$ controls the corrupted entities.

$\mathtt{Hyb0}$:

This random variable is distributed identical to , i.e., the real execution of
the protocol where $\mathtt{Adv}$ interacts with the honest entities.

$\mathtt{Hyb1}$:

In this hybrid, a simulator which has knowledge on all the secrets of the
honest parties (in each iteration) is introduced.

The distribution of this hybrid is identical to the previous one.

$\mathtt{Hyb2}$:

In this hybrid, we change the behaviour of the simulated honest parties
$\mathtt{P}_{i}\in\mathcal{P}_{H}$ and assisting nodes
$\mathtt{A}_{j}\in\mathcal{A}_{H}$ by selecting a random shared secret key
from the key space $\mathcal{K}_{\mathtt{\Sigma}}$ instead of instantiating
the $\Sigma.{\mathtt{Agree}}(\cdot)$ algorithm.

The indistinguishabilityof this hybrid with the one before is guaranteed by
the security of the instantiated key exchange protocol. For instance with the
Diffie-Hellman key exchange protocol, this is guaranteed by the 2ODH
assumption (Bonawitz et al., 2017).

$\mathtt{Hyb3}$:

In this hybrid, each honest user $\mathtt{P}_{i}\in\mathcal{P}_{H}$ replaces
$\vec{y}^{\mathtt{P}_{i}}_{t}$ it sends to the server with a random vector
$\vec{y^{\prime}}^{\mathtt{P}_{i}}_{t}$. As aforementioned, we require at
least one of the assisting nodes in our protocol to be honest. Therefore, the
indistinguishabilityof this hybrid is guaranteed since $\mathtt{Adv}$ does not
have knowledge on the honest entity’s secret and hence in the masked update
will have the same distribution as $\vec{y^{\prime}}^{\mathtt{P}_{i}}_{t}$ in
$\mathtt{Simul}$.

$\mathtt{Hyb4}$:

In this hybrid we replace the aggregated masking term outputted by the honest
assisting nodes $\mathtt{A}_{i}\in\mathcal{A}_{H}$ with
$\vec{a^{\prime}}_{\mathtt{P}_{i},t}^{\mathtt{A}_{j}}$ (computed in Step 3 of
the simulated Aggregation phase presented above) by calling the idea
functionality
$\mathcal{F}_{\vec{x},\alpha}(\mathcal{L}_{\mathtt{S},t}\backslash\mathcal{P}_{C})$
and utilizing a random oracle. Note that the view of this hybrid is
indistinguishabilitywith the previous hybrid since $\mathtt{Adv}$ does not
have any knowledge on the honest entities shared secret and the distribution
of the aggregate masking term in $\mathtt{Simul}$ is identical to the one in .

$\mathtt{Hyb5}$:

In this hybrid, $\mathtt{Sim}$ sends the output of the ideal functionality (as
in Step 2 in the simulated Aggregation phase above) as the universal model
update $\mathbf{w}_{t}$ for iteration $t$. Note that the ideal functionality
will not return $\bot$ based on the condition on the fraction of the honest
users. Hence, this hybrid is indistinguishabilityfrom the previous one given
the local updates are not known by $\mathtt{Adv}$ in .

In the above, we have shown that the view of all the corrupted parties
controlled by $\mathtt{Adv}$ is computationally indistinguishable ∎

### Proof of Theorem 3

###### Proof.

Following Definition 9 and similar to the proof of Theorem 2, we prove the
above theorem by the standard hybrid argument using the simulator
$\mathtt{Sim}$. In the following, we define the set of all parties as
$\mathcal{P}$, honest parties as $\mathcal{P}_{h}$ and corrupt parties as
$\mathcal{P}_{C}$, i.e.,
$\mathcal{P}_{C}=\mathcal{P}\backslash\mathcal{P}_{h}$. We apply the same
notation to the set of assisting nodes $\mathcal{A}$. $\mathtt{Sim}$ behaves
as follows in each round of the Setup and Aggregation phase

_Setup phase:_

  1. (1)

$\mathtt{Sim}$ works similar to the Setup phase in the proof of Theorem 2.

_Aggregation phase:_

  1. (1)

In each iteration $t$ of the protocol, each honest user picks a random
$\vec{y^{\prime}}_{t}^{\mathtt{P}_{i}}$. It then computes two signatures
$\sigma^{\mathtt{P}_{i}}_{\mathtt{S}}\leftarrow\Pi.{\mathtt{Sign}}(\mathsf{sk}^{\mathtt{P}_{i}}_{\Pi},m)$
and
$\sigma^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}\leftarrow\Pi.{\mathtt{Sign}}(\mathsf{sk}^{\mathtt{P}_{i}}_{\Pi},m^{\prime})$
and sends $(m{,\sigma^{\mathtt{P}_{i}}_{\mathtt{S}}})$ and
$(m^{\prime}{,\sigma^{\mathtt{P}_{i}}_{\mathtt{A}_{j}}})$ to the aggregation
server and the assisting node $\mathtt{A}_{j}$ (for $j\in[1,\dots,k]$),
respectively.

  2. (2)

$\mathtt{Sim}$ works similar to the Steps 2 and 3 of the Aggregation phase in
the proof of Theorem 2.

We present our hybrids below and follow the same approach for transitioning
between hybrids as we did in the proof of Theorem 2.

$\mathtt{Hyb0}$:

This random variable is distributed identical to , i.e., the real execution of
the protocol where $\mathtt{Adv}$ interacts with the honest entities.

$\mathtt{Hyb1}$:

In this hybrid, a simulator which has knowledge on all the secrets of the
honest parties (in each iteration) is introduced.

The distribution of this hybrid is identical to the previous one.

$\mathtt{Hyb2}$:

In this hybrid, we change the behaviour of the simulated honest parties
$\mathtt{P}_{i}\in\mathcal{P}_{H}$ and assisting nodes
$\mathtt{A}_{j}\in\mathcal{A}_{H}$ by selecting a random shared secret key
from the key space $\mathcal{K}_{\mathtt{\Sigma}}$ instead of instantiating
the $\Sigma.{\mathtt{Agree}}(\cdot)$ algorithm.

The indistinguishabilityof this hybrid with the one before is guaranteed by
the security of the instantiated key exchange protocol. For instance with the
Diffie-Hellman key exchange protocol, this is guaranteed by the 2ODH
assumption (Bonawitz et al., 2017).

$\mathtt{Hyb3}$:

In this hybrid, each honest user $\mathtt{P}_{i}\in\mathcal{P}_{H}$ samples a
random vector $\vec{y^{\prime}}^{\mathtt{P}_{i}}_{t}$ for the update domain.
It also computes a signature
$\sigma^{\mathtt{P}_{i}}_{\mathtt{S}}\leftarrow\Pi.{\mathtt{Sign}}(\mathsf{sk}^{\mathtt{P}_{i}}_{\Pi},<\vec{y^{\prime}}^{\mathtt{P}_{i}}_{t},t>)$
and sends
$(\vec{y^{\prime}}^{\mathtt{P}_{i}}_{t},\sigma^{\mathtt{P}_{i}}_{\mathtt{S}})$
to the server. Firstly, the indistinguishabilityof
$\sigma^{\mathtt{P}_{i}}_{\mathtt{S}}$ is guaranteed by the underlying
signature scheme. Secondly, as aforementioned, we require at least one of the
assisting nodes in our protocol to be honest. Therefore, the
indistinguishabilityof this hybrid is guaranteed since $\mathtt{Adv}$ does not
have knowledge on the honest entity’s secret and hence in the masked update
will have the same distribution as $\vec{y^{\prime}}^{\mathtt{P}_{i}}_{t}$ in
$\mathtt{Simul}$.

$\mathtt{Hyb4}$:

In this hybrid we call the idea functionality
$\mathcal{F}_{\vec{x},\alpha}(\mathcal{L}_{\mathtt{S},t}\backslash\mathcal{P}_{C})$
and utilize random oracles to replace the aggregated masking term outputted by
the honest assisting nodes $\mathtt{A}_{i}\in\mathcal{A}_{H}$ with
$\vec{a^{\prime}}_{\mathtt{P}_{i},t}^{\mathtt{A}_{j}}$ (computed in Step 3 of
the simulated Aggregation phase presented above). The output of this hybrid is
$(\vec{a^{\prime}}_{\mathtt{P}_{i},t}^{\mathtt{A}_{j}},\sigma^{\mathtt{A}_{i}}_{\mathtt{S}})$
where
$\sigma^{\mathtt{A}_{i}}_{\mathtt{S}}\leftarrow{\mathtt{Sign}}(\mathsf{sk}^{\mathtt{A}_{j}}_{\Pi},m^{\prime\prime})$.
The indistinguishabilityof $\sigma^{\mathtt{A}_{i}}_{\mathtt{S}}$ is provided
via the security of the underlying signature scheme. Hence, the view of this
hybrid is indistinguishabilitywith the previous hybrid since $\mathtt{Adv}$
does not have any knowledge on the honest entities shared secret and the
distribution of the aggregate masking term in $\mathtt{Simul}$ is identical to
the one in .

$\mathtt{Hyb5}$:

In this hybrid, $\mathtt{Sim}$ sends the output of the ideal functionality (as
in Step 2 in the simulated Aggregation phase above) as the universal model
update $\mathbf{w}_{t}$ for iteration $t$. Note that the ideal functionality
will not return $\bot$ based on the condition on the fraction of the honest
users. Hence, this hybrid is indistinguishabilityfrom the previous one given
the local updates are not known by $\mathtt{Adv}$ in .

In the above, we have shown that the view of all the corrupted parties
controlled by $\mathtt{Adv}$ is computationally indistinguishable ∎