# Secure and Verifiable Data Collaboration with Low-Cost Zero-Knowledge Proofs

Yizheng Zhu  National University of SingaporeSingapore<EMAIL_ADDRESS>,
Yuncheng Wu  National University of SingaporeSingapore<EMAIL_ADDRESS>,
Zhaojing Luo  National University of SingaporeSingapore
<EMAIL_ADDRESS>,  Beng Chin Ooi  National University of
SingaporeSingapore<EMAIL_ADDRESS>and  Xiaokui Xiao  National
University of SingaporeSingapore<EMAIL_ADDRESS>
###### Abstract.

Organizations are increasingly recognizing the value of data collaboration for
data analytics purposes. Yet, stringent data protection laws prohibit the
direct exchange of raw data. To facilitate data collaboration, federated
Learning (FL) emerges as a viable solution, which enables multiple clients to
collaboratively train a machine learning (ML) model under the supervision of a
central server while ensuring the confidentiality of their raw data. However,
existing studies have unveiled two main risks: (i) the potential for the
server to infer sensitive information from the client’s uploaded updates
(i.e., model gradients), compromising client input privacy, and (ii) the risk
of malicious clients uploading malformed updates to poison the FL model,
compromising input integrity. Recent works utilize secure aggregation with
zero-knowledge proofs (ZKP) to guarantee input privacy and integrity in FL.
Nevertheless, they suffer from extremely low efficiency and, thus, are
impractical for real deployment. In this paper, we propose a novel and highly
efficient solution RiseFL for secure and verifiable data collaboration,
ensuring input privacy and integrity simultaneously. Firstly, we devise a
probabilistic integrity check method that significantly reduces the cost of
ZKP generation and verification. Secondly, we design a hybrid commitment
scheme to satisfy Byzantine robustness with improved performance. Thirdly, we
theoretically prove the security guarantee of the proposed solution. Extensive
experiments on synthetic and real-world datasets suggest that our solution is
effective and is highly efficient in both client computation and
communication. For instance, RiseFL is up to 28x, 53x and 164x faster than
three state-of-the-art baselines ACORN, RoFL and EIFFeL for the client
computation.

data collaboration, federated learning, zero-knowledge proof

##  1\. Introduction

Organizations and companies are progressively embracing digitization and
digitalization as pathways to transformation, targeting enhancements in
profitability, efficiency, or sustainability. Data plays a crucial role in
such transformations. For example, financial analysts may use users’
historical data to adjudicate on credit card applications, and clinicians may
use patients’ electronic health records for disease diagnosis. While many
organizations may lack expansive or pertinent datasets, there is a growing
inclination towards data collaboration (Wang et al., 2023b; Wu et al., 2023;
Baunsgaard et al., 2021) for analytics purposes. Nevertheless, the ascent of
rigorous data protection legislation, such as GDPR (GDP, 2016), deters direct
raw data exchange. For example, in a healthcare data collaboration scenario
shown in Figure 1, three hospitals aim to share their respective brain image
databases to build a more accurate machine learning (ML) model. However, due
to the highly sensitive nature of patients’ data, directly sharing those brain
images among hospitals is not permissible.

In this landscape, federated learning (McMahan et al., 2017; Yang et al.,
2019; Li et al., 2020; Liu et al., 2021a; Nguyen et al., 2022; Wu et al.,
2020; Liu et al., 2021b; Bao et al., 2022; Fu et al., 2022, 2021; Li et al.,
2022; Fan et al., 2022; Fu et al., 2023; Xie et al., 2023; Wang et al., 2023a;
Zeng et al., 2023) emerges as a viable solution to facilitate data
collaboration. It enables multiple data owners (i.e., clients) to
collaboratively train an ML model without necessitating the direct sharing of
raw data, thereby complying with data protection acts. Typically, there is a
centralized server that coordinates the FL training process as follows. For
example, in Figure 1, the server (i.e., the healthcare center) first
initializes the model parameter and broadcasts it to all the hospitals. Then,
in each iteration, each hospital computes a local model update (i.e., model
gradients) on its own patients’ data and uploads it to the server. The server
aggregates all hospitals’ updates to generate a global update and sends it
back to the hospitals for iterative training (McMahan et al., 2017). Finally,
the hospitals obtain a federated model that is trained on the three hospitals’
brain datasets. After that, the doctor in each hospital can use it to assist
in diagnosing new patients.

Despite the fact that FL could facilitate data collaboration among multiple
clients, two main risks remain. The first is the client’s input privacy. Even
without disclosing the client’s raw data to the server, recent studies (Melis
et al., 2019; Nasr et al., 2019) have shown that the server can recover the
client’s sensitive data through the uploaded update with a high probability.
The second is the client’s input integrity. In FL, there may exist a set of
malicious clients that aim to poison the collaboratively trained model via
Byzantine attacks, such as imposing backdoors so that the model is susceptible
to specific input data (Bagdasaryan et al., 2020; Xie et al., 2020),
contaminating the training process with malformed updates to degrade model
accuracy (Hayes and Ohrimenko, 2018; Fung et al., 2018; Bhagoji et al., 2019),
and so on.

A number of solutions (Bell et al., 2020; Zheng et al., 2023; Kairouz et al.,
2021; Yin et al., 2018, 2019; Pan et al., 2020; Cao et al., 2021; Ma et al.,
2022; Xu et al., 2022) have been proposed to protect input privacy and ensure
input integrity in FL. On the one hand, instead of uploading the plaintext
local updates to the server, the clients can utilize secure aggregation
techniques (Bonawitz et al., 2017; Bell et al., 2020; Kairouz et al., 2021),
such as secret sharing (Shamir, 1979; Keller, 2020) and homomorphic encryption
(Damgård and Jurik, 2001; Gamal, 1985), to mask or encrypt the local updates
so that the server can aggregate the clients’ updates correctly without
knowing each update. In this way, the client’s input privacy is preserved.
However, these solutions do not ensure input integrity because it is difficult
to distinguish a malicious encrypted update from benign ones. On the other
hand, (Yin et al., 2018, 2019; Pan et al., 2020; Cao et al., 2021; Ma et al.,
2022; Xu et al., 2022) present various Byzantine-robust aggregation
algorithms, allowing the server to identify malformed updates and eliminate
them from being aggregated into the global update. Nevertheless, these
algorithms require the clients to send plaintext updates to the server for the
integrity verification, compromising the client’s input privacy.

In order to ensure input integrity while satisfying input privacy, (Roy
Chowdhury et al., 2022; Lycklama et al., 2023; Bell et al., 2023) use secure
aggregation to protect each client’s update and allow the server to check the
encrypted update’s integrity using zero-knowledge proof (ZKP) (Li et al.,
2023) protocols. The general idea is to let each client compute a commitment
of its local update and generate a proof that the update satisfies a publicly-
known predicate, for example, the $L_{2}$-norm is within a specific range;
then, the server can verify the correctness of the proofs based on the
commitments without the need of knowing the plaintext values and securely
aggregate the valid updates. Unfortunately, these solutions suffer from
extremely low efficiency in proof generation and verification, making them
impractical for real deployments. For example, under the experiment settings
in Section 6, EIFFeL (Roy Chowdhury et al., 2022) takes 161 seconds to
generate and verify proofs on 10K model parameters, compared to 7.6 seconds
for client local training.

Figure 1. An example for healthcare data collaboration.

To introduce a practical FL system which ensures both input privacy and input
integrity, we propose a secure and verifiable federated learning approach,
called RiseFL, with high efficiency. In this paper, we focus on the
$L_{2}$-norm integrity check, i.e., the $L_{2}$-norm of a client’s local
update is less than a threshold, which is widely adopted in existing works
(Sun et al., 2019; Lycklama et al., 2023; Corrigan-Gibbs and Boneh, 2017; Roy
Chowdhury et al., 2022). Our key observation of the low-efficiency in
(Lycklama et al., 2023; Roy Chowdhury et al., 2022) is that their proof
generation and verification costs for each client are linearly dependent on
the number of parameters $d$ in the FL model. Therefore, we aim to reduce the
proof cost, which particularly makes sense in the FL scenario because the
clients often have limited computation and communication resources.
Specifically, our approach has the following novelties. First, we propose a
probabilistic $L_{2}$-norm check method that decreases the cryptographic
operation cost of proof generation and verification from $O(d)$ to
$O(d/\log{d})$. The intuitive idea is to sample a set of public vectors and
let each client generate proofs with respect to the inner product between its
update and each public vector, instead of checking the $L_{2}$-norm of the
update directly. This allows us to reduce the proof generation and
verification time significantly. Second, we devise a hybrid commitment scheme
based on Pedersen commitment (Pedersen, 2001) and verifiable Shamir secret
sharing commitment (Shamir, 1979; Feldman, 1987), ensuring Byzantine-
robustness while achieving further performance improvement on the client
computation. Third, although we consider the $L_{2}$-norm check, the proposed
approach can be easily extended to various Byzantine-robust integrity checks
(Cao et al., 2021; Yin et al., 2018; Steinhardt et al., 2017) based on
different $L_{2}$-norm variants, such as cosine similarity (Bagdasaryan et
al., 2020; Cao et al., 2021), sphere defense (Steinhardt et al., 2017), Zeno++
(Xie et al., 2019), and so on.

In summary, we make the following contributions.

  * •

We propose a novel and highly efficient solution RiseFL for FL-based data
collaboration, which simultaneously ensures each client’s input privacy and
input integrity.

  * •

We present a probabilistic $L_{2}$-norm integrity check method and a hybrid
commitment scheme, which significantly reduces the ZKP generation and
verification costs.

  * •

We provide a formal security analysis of RiseFL and theoretically compare its
computational and communication costs with three state-of-the-art solutions.

  * •

We implement RiseFL and evaluate its performance with a set of micro-benchmark
experiments as well as FL tasks on two real-world datasets. The results
demonstrate that RiseFL is effective in detecting various attacks and is up to
28x, 53x and 164x faster than ACORN (Bell et al., 2023), RoFL (Lycklama et
al., 2023) and EIFFeL (Roy Chowdhury et al., 2022) for the client computation,
respectively.

The rest of the paper is organized as follows. Section 2 introduces
preliminaries and Section 3 presents an overview of our solution. We detail
the system design in Section 4 and analyze the security and cost in Section 5.
The evaluation is provided in Section 6. We review the related works in
Section 7 and conclude the paper in Section 8.

##  2\. Preliminaries

We first introduce the notations used in this paper. Let $\mathbb{G}$ denote a
cyclic group with prime order $p$, where the discrete logarithm problem
(Pomerance and Goldwasser, 1990) is hard. Let $\mathbb{Z}_{p}$ denote the set
of integers modulo the prime $p$. We use $x$, x, and X to denote a scalar, a
vector, and a matrix, respectively. We use $\mathsf{Enc}_{\mathsf{K}}(x)$ to
denote an encrypted value of $x$ under an encryption key $\mathsf{K}$, and
$\mathsf{Dec}_{\mathsf{K}}(y)$ to denote a decrypted value of $y$ under the
same key $\mathsf{K}$. Since the data used in ML are often in the floating-
point representation, we use fixed-point integer representation to encode
floating-point values. In the following, we introduce the cryptographic
building blocks used in this paper.

Pedersen Commitment. A commitment scheme is a cryptographic primitive that
allows one to commit a chosen value without revealing the value to others
while still allowing the ability to disclose it later (Goldreich, 2001).
Commitment schemes are widely used in various zero-knowledge proofs. In this
paper, we use the Pedersen commitment (Pedersen, 2001) for a party to commit
its secret values. Given the independent group elements $(g,h)$, the Pedersen
commitment encrypts a value $x\in\mathbb{Z}_{p}$ to $C(x,r)=g^{x}h^{r}$, where
$r\in\mathbb{Z}_{p}$ is a random number. An important property of the Pedersen
commitment is that it is additively homomorphic. Given two values
$x_{1},x_{2}$ and two random numbers $r_{1},r_{2}$, the commitment follows
$C(x_{1},r_{1})\cdot C(x_{2},r_{2})=C(x_{1}+x_{2},r_{1}+r_{2})$.

Verifiable Shamir’s Secret Sharing Scheme. Shamir’s $t$-out-of-$n$ secret
sharing (SSS) scheme (Shamir, 1979) allows a party to distribute a secret
among a group of $n$ parties via shares so that the secret can be
reconstructed given any $t$ shares but cannot be revealed given less than $t$
shares. The SSS scheme is verifiable (aka. VSSS) if auxiliary information is
provided to verify the validity of the secret shares. We use the VSSS scheme
(Shamir, 1979; Feldman, 1987) to share a number $r\in\mathbb{Z}_{p}$.
Specifically, the VSSS scheme consists of three algorithms, namely,
$\mathsf{SS.Share}$, $\mathsf{SS.Verify}$, and $\mathsf{SS.Recover}$.

  * •

$((1,r_{1}),\dots,(n,r_{n}),\Psi)\leftarrow\mathsf{SS.Share}(r,n,t,g)$. Given
a secret $r\in\mathbb{Z}_{p}$, $g\in\mathbb{G}$, and $0<t\leq n$, this
algorithm outputs a set of $n$ shares $(i,r_{i})$ for $i\in[n]$ and a check
string $\Psi$ as the auxiliary information to verify the shares. Specifically,
it generates a random polynomial $f$ in $\mathbb{Z}_{p}$ of degree at most
$(t-1)$ whose constant term is $r$. We set $r_{i}=f(i)$ and
$\Psi=(g^{r},g^{f_{1}},\dots,g^{f_{t-1}})$ where $f_{i}$ is the $i$-th
coefficient.

  * •

$r\leftarrow\mathsf{SS.Recover}(\\{(i,r_{i})\\}:{i\in A})$. For any subset
$A\subset[n]$ with size at least $t$, this algorithm recovers the secret $r$.

  * •

$\mathsf{True}/\mathsf{False}\leftarrow\mathsf{SS.Verify}(\Psi,i,r_{i},n,t,g)$.
Given a share $(i,r_{i})$ and the check string $\Psi$, it verifies the
validity of this share so that it outputs $\mathsf{True}$ if $(i,r_{i})$ was
indeed generated by $\mathsf{SS.Share}(r,n,t,g)$ and $\mathsf{False}$
otherwise.

This scheme is additively homomorphic in both the shares and the check string.
If $((1,r_{1}),\dots,(n,r_{n}),\Psi_{r})\leftarrow\mathsf{SS.Share}(r,n,t,g)$
and
$((1,s_{1}),\dots,(n,s_{n}),\Psi_{s})\leftarrow\mathsf{SS.Share}(s,n,t,g)$,
then:

  * •

$r+s\leftarrow\mathsf{SS.Recover}(\\{(i,r_{i}+s_{i})\\}:{i\in A})$ for any
subset $A\subset[n]$ with size at least $t$,

  * •

$\mathsf{True}\leftarrow\mathsf{SS.Verify}(\Psi_{r}\cdot\Psi_{s},i,r_{i}+s_{i},n,t,g)$.

Zero-Knowledge Proofs. A zero-knowledge proof (ZKP) allows a prover to prove
to a verifier that a given statement is true, such as a value is within a
range, without disclosing any additional information to the verifier (Blum et
al., 1988). We utilize two additively homomorphic ZKP protocols based on the
Pedersen commitment as building blocks. Note that the zkSNARK protocols (Ben-
Sasson et al., 2013; Gennaro et al., 2013; Parno et al., 2016) are not
additively homomorphic, thus they cannot support the secure aggregation
required in federated learning.

The first is the $\Sigma$-protocol (Camenisch and Stadler, 1997) for proof of
square and proof of relation. For proof of square
$((x,r_{1},r_{2}),(y_{1},y_{2}))$, denote $(g,h)$ as the independent group
elements, and let $y_{1}=C(x,r_{1})$ and $y_{2}=C(x^{2},r_{2})$ be the
Pedersen commitments, where $x,r_{1},r_{2}\in\mathbb{Z}_{p}$ are the secrets.
The function $\mathsf{GenPrfSq}((x,r_{1},r_{2}),(y_{1},y_{2}))$ generates a
proof $\pi$ that the secret value in $y_{2}$ is the square of the secret value
in $y_{1}$. Accordingly, the function $\mathsf{VerPrfSq}(\pi,y_{1},y_{2})$
verifies the correctness of this proof. Similarly, for proof of a relation
$((r,v,s),(z,e,o))$, denote $(g,q,h)$ as the independent group elements, and
let $z=g^{r},e=g^{v}h^{r},o=g^{v}q^{s}$ be the Pedersen commitments, where
$r,v,s\in\mathbb{Z}_{p}$ are the secrets. The function
$\mathsf{GenPrfWf}((r,v,s),(z,e,o))$ generates a proof $\pi$ that the secrets
in $e$ and $o$ are equal, and that the secret in $z$ is equal to the blind in
$e$. The function $\mathsf{VerPrfWf}(\pi,z,e,o)$ verifies the proof. The
second ZKP protocol used is the Bulletproofs protocol (Bünz et al., 2018) for
checking the bound of a value $x$ with its Pedersen commitment $y=C(x,r)$. We
denote $\mathsf{GenPrfBd}(x,y,r,b)$ as the function that generates a proof
$\pi$ that $x\in[0,2^{b})$, where $2^{b}$ is the bound to be ensured. The
corresponding function $\mathsf{VerPrfBd}(\pi,y,b)$ verifies the proof. We
refer the interested readers to (Bünz et al., 2018) for more details.

These building blocks can be easily extended to the vector form such that the
proof generation and verification execute on a batch of values. Unless noted
otherwise, we use the vector form in the rest of this paper.

##  3\. System Overview

In this section, we present the system model and the threat model, and then we
give an overview of the proposed RiseFL system which ensures input privacy and
input integrity.

###  3.1. System Model

There are $n$ clients $\\{\mathcal{C}_{1},\cdots,\mathcal{C}_{n}\\}$ and a
centralized server in the system. Each client $\mathcal{C}_{i}(i\in[1,n])$
holds a private dataset $\mathcal{D}_{i}$ to participate in data collaboration
for training a federated learning (FL) model $\mathcal{M}$. Let $d$ be the
number of parameters in $\mathcal{M}$. In each iteration, the training process
consists of three steps. Firstly, the server broadcasts the current model
parameters to all the clients. Secondly, each client $\mathcal{C}_{i}$ locally
computes a model update (i.e., gradients) $\textbf{u}_{i}$ given the model
parameters and its dataset $\mathcal{D}_{i}$, and submits $\textbf{u}_{i}$ to
the server. Thirdly, the server aggregates the clients’ gradients to a global
update $\mathcal{U}=\sum\nolimits_{i\in[1,n]}\textbf{u}_{i}$ and updates the
model parameters of $\mathcal{M}$ for the next round of training until
convergence.

(a) System initialization

(b) Commitment generation

(c) Proof generation and verification

(d) Secure aggregation

Figure 2. An overview of the proposed RiseFL system.

###  3.2. Threat Model

We consider a malicious threat model in two aspects. First, regarding input
privacy, we consider a malicious server (i.e., the adversary) that can deviate
arbitrarily from the specified protocol to infer each client’s uploaded model
update. Also, the server may collude with some of the malicious clients to
compromise the honest clients’ privacy. Similar to (Roy Chowdhury et al.,
2022), we do not consider the scenario that the server is malicious against
the input integrity because its primary goal is to ensure the well-formedness
of each client’s uploaded update. Second, regarding input integrity, we assume
that there are at most $m$ malicious clients in the system, where $m<n/2$. The
malicious clients can also deviate from the specified protocol arbitrarily,
such as sending malformed updates to the server to poison the aggregation of
the global update, or intentionally marking an honest client as malicious to
interfere with the server’s decision on the list of malicious clients.

###  3.3. Problem Formulation

We aim to ensure both input privacy (for the clients) and input integrity (for
the server) under the threat model described in Section 3.2. We formulate our
problem as a relaxed variant of the secure aggregation with verified inputs
(SAVI) problem in (Roy Chowdhury et al., 2022), namely $(D,F)$-relaxed SAVI,
as defined in Definition 1. It achieves the same level of input privacy while
relaxing the input integrity for significant efficiency improvement.

###### Definition 0.

Given a security parameter $\kappa$, a function
$D:\mathbb{R}^{d}\to\mathbb{R}$ satisfying that u is malicious if and only if
$D(\textbf{u})>1$, a function $F:(1,+\infty)\to[0,1]$, a set of inputs
$\\{\textbf{u}_{1},\cdots,\textbf{u}_{n}\\}$ from clients
$\mathcal{C}=\\{\mathcal{C}_{1},\dots,\mathcal{C}_{n}\\}$ respectively, and a
list of honest clients $\mathcal{C}_{H}$, a protocol $\Pi$ is a
$(D,F)$-relaxed SAVI protocol for $\mathcal{C}_{H}$ if:

  * •

Input Privacy. The protocol $\Pi$ realizes the ideal functionality
$\mathcal{F}$ such that for an adversary $\mathcal{A}$ that consists of the
malicious server and the malicious clients
$\mathcal{C}_{M}=\mathcal{C}\setminus\mathcal{C}_{H}$ attacking the real
interaction, there exist a simulator $\mathcal{S}$ attacking the ideal
interaction, and

$\displaystyle|\mathrm{Pr}[\mathrm{Real}_{\Pi,\mathcal{A}}(\\{\textbf{u}_{\mathcal{C}_{H}}\\})=1]-\mathrm{Pr}[\mathrm{Ideal}_{\mathcal{F},\mathcal{S}}(\mathcal{U}_{H})=1]|\leq\mathrm{negl}(\kappa),$

where
$\mathcal{U}_{H}=\sum\nolimits_{\mathcal{C}_{i}\in\mathcal{C}_{H}}\textbf{u}_{i}$.

  * •

Input Integrity. The protocol $\Pi$ outputs
$\sum_{\mathcal{C}_{i}\in\mathcal{C}_{\mathrm{Valid}}}\textbf{u}_{i}$ with
probability of at least $1-\mathrm{negl}(\kappa)$, where
$\mathcal{C}_{H}\subseteq\mathcal{C}_{\mathrm{Valid}}$. For any malformed
input $\textbf{u}_{j}$ from a malicious client $\mathcal{C}_{j}$, the
probability that it passes the integrity check satisfies:

$\displaystyle\mathrm{Pr}[\mathcal{C}_{j}\in\mathcal{C}_{\mathrm{Valid}}]\leq
F(D(\textbf{u}_{j})).$

For input privacy in Definition 1, it ensures that the server can only learn
the aggregation of honest clients’ updates. For input integrity, Definition 1
relaxes the integrity verification by introducing a malicious pass rate
function $F$. $F$ is a function that maps the degree of maliciousness of an
input to the pass rate of the input, and the degree of maliciousness is
measured by the function $D$. For instance, with an $L_{2}$-norm bound $B$, a
natural choice is $D(\textbf{u})=||\textbf{u}||_{2}/B$. Intuitively, the
higher the degree of maliciousness, the lower the pass rate. So $F$ is usually
decreasing. Our system also satisfies
$\limsup_{x\to+\infty}F(x)\leq\mathrm{negl}(\kappa)$. It means that any
malicious client’s malformed update whose degree of maliciousness passes a
threshold can be detected with an overwhelming probability. When
$F\equiv\mathrm{negl}(\kappa)$, a protocol that satisfies $(D,F)$-relaxed SAVI
will also satisfy SAVI.

###  3.4. Solution Overview

To solve the problem in Definition 1, we propose a secure and verifiable
federated learning system RiseFL with high efficiency. It tolerates $m<n/2$
malicious clients for input integrity, which means that the server can
securely aggregate the clients’ inputs as long as a majority of the clients
are honest. Figure 2 gives an overview of RiseFL, which is composed of a
system initialization stage and three iterative rounds: commitment generation,
proof generation and verification, and secure aggregation. In the
initialization stage (Figure 2a), all the parties agree on some hyper-
parameters, such as the number of clients $n$, the maximum number of malicious
clients $m$, the security parameters, e.g., key size, and so on.

In each iteration of the FL training process, each client
$\mathcal{C}_{i}(i\in[n])$ commits its model update $\textbf{u}_{i}$ using the
hybrid commitment scheme based on Pedersen commitment and verifiable Shamir’s
secret sharing (VSSS) in Section 4.3, and then sends the commitment to the
server and the secret shares to the corresponding clients (see Figure 2b). In
the proof generation and verification round (Figure 2c), there are two steps.
In the first step, each client verifies the authenticity of other clients’
secret shares. For the secret shares that are verified to be invalid, the
client marks the respective clients as malicious. With the marks from all
clients, the server can then identify a subset of malicious clients. In the
second step, the server uses a probabilistic integrity check method presented
in Section 4.4 to check each client’s update $\textbf{u}_{i}$. Next, the
server filters out the malicious client list $\mathcal{C}^{*}$ and broadcasts
it to all the clients. In the secure aggregation round (Figure 2d), each
client aggregates the secret shares from clients
$\mathcal{C}_{j}(j\notin\mathcal{C}^{*})$ and sends the result to the server.
The server reconstructs the sum of secret shares and securely aggregates the
updates $\textbf{u}_{j}(j\notin\mathcal{C}^{*})$ based on the Pedersen
commitments. We summarize the process of each iteration in Algorithm 1, and we
shall detail the steps in the following section.

1

Input: the number of clients $n$, the maximum number of malicious clients $m$,
the number of random vectors $k$

Output: the aggregated model update u of honest clients

2 Procedure  _CommitmentGeneration_

3 Client $i$:

4 generate a random secret $r_{i}$

5 compute commitment $\textbf{y}_{i}=C(\textbf{u}_{i},r_{i})$ in Eqn 4.3

6 share $r_{i}$ via VSSS and encrypt shares $r_{i}j,\forall j\in[1,n]$

7 send $\textbf{y}_{i}$ and $\mathsf{Enc}(r_{ij}),\forall j\in[1,n]$ with
check string to server

8 Server:

9 send encrypted shares and check strings to clients

10

11 Procedure  _ProofGenerationAndVerification_

12 Step 1: Verify the authenticity of secret shares (Section 4.4.1)

13 Client $i$:

14 initialize local malicious client set $\mathcal{C}_{i}^{*}=\emptyset$

15 decrypt to get $r_{ji},\forall j\in[1,n]$ and check their authenticity

16 put clients do not pass the check to $\mathcal{C}_{i}^{*}$ and send it to
server

17 Step 2: Verify the integrity of each client’s update (Section 4.4.2)

18 Server:

19 initialize malicious client set $\mathcal{C}^{*}=\emptyset$

20 generate a random $s$ and broadcast it to clients

21 sample $k+1$ random vectors
$\textbf{A}=(\textbf{a}_{0},\cdots,\textbf{a}_{k})$

22 compute $h_{t},\forall t\in[0,k]$ and broadcast it to clients

23 Client $i$:

24 compute A according to $s$

25 compute proof $\pi$ based on and send it to server

26 Server:

27 verify $\mathcal{C}_{i}^{*},\forall i\in[1,n]$ and the proofs

28 update $\mathcal{C}^{*}$ and broadcast

29

30 Procedure  _SecureAggregation_

31 Client $i$:

32 sends aggregated shares $r_{i}^{\prime}$ from honest clients to server

33 Server:

34 aggregate shares $r_{i}^{\prime},\forall i\in[1,n]$

35 compute aggregated model update u in Eqn 7

36

37

Algorithm 1 RiseFL (One Iteration)

##  4\. RiseFL Design

In this section, we introduce our system design. We first present the
rationale of the protocol in Section 4.1. Then, we introduce the
initialization stage in Section 4.2 and the three steps in each iteration of
the training stage in Sections 4.3-4.5, respectively. Finally, we discuss the
extension of our system in Section 4.6.

###  4.1. Rationale

The most relevant work to our problem is EIFFeL (Roy Chowdhury et al., 2022),
which also ensures input privacy and integrity in FL training. However, its
efficiency is low, and thus is impractical to be deployed in real-world
systems. For example, under the experiment settings in Section 6, given 100
clients and 1K model parameters, EIFFeL takes around 15.3 seconds for proof
generation and verification on each client. More severely, the cost is
increased to 152 seconds when the number of model parameters $d$ is 10K. The
underlying reason is that the complexity of its proof generation and
verification is linearly dependent on $d$, making EIFFeL inefficient and less
scalable. We shall detail the cost analysis of EIFFeL in Section 5.2.

The rationale behind our idea is to reduce the complexity of expensive group
exponentiations in ZKP generation and verification. To do so, we design a
probabilistic $L_{2}$-norm integrity check method, as shown in Algorithm 2.
The intuition is that, instead of generating and verifying proofs for the
$L_{2}$-norm of an update ${||\textbf{u}||}_{2}$, where
$\textbf{u}\in\mathbb{R}^{d}$, we randomly sample $k$ points
$\textbf{a}_{1},\dots,\textbf{a}_{k}$ from the normal distribution
$\mathcal{N}(\mathbf{0},\mathbf{I}_{d})$. Then random variable is:

(1)
$\displaystyle\frac{1}{||\textbf{u}||_{2}^{2}}\sum\nolimits_{i=1}^{k}\langle\textbf{a}_{i},\textbf{u}\rangle^{2},$

which follows a chi-square distribution $\chi_{k}^{2}$ with $k$ degrees of
freedom. In Algorithm 2, if $||\textbf{u}||_{2}\leq B$, then the probability
that u passes the check is at least $1-\epsilon$. where $\epsilon$ is chosen
to be cryptographically small, e.g., $2^{-128}$. In this way, the probability
that the client fails the check is of the same order as the probability that
the client’s encryption is broken. Figure 3 gives an illustration of this
method. Assume that $||u||_{2}=1$. We sample two random normal samples
$\textbf{a}_{1},\textbf{a}_{2}$; then, the inner products
$\langle\textbf{a}_{1},\textbf{u}\rangle,\langle\textbf{a}_{2},\textbf{u}\rangle$
are the projections of $\textbf{a}_{1},\textbf{a}_{2}$ onto u. Figure 3b shows
the probability density function of $\chi_{k}^{2}$. With a specific bound
$\gamma_{k,\epsilon}$ (we shall introduce this bound in Section 5.1), there is
an overwhelming probability such that
$\sum_{t=1}^{k}\langle\textbf{a}_{t},\textbf{u}\rangle^{2}\leq\gamma_{k,\epsilon}$.

Based on this method, we further devise an optimization technique, as will be
introduced in Section 4.4, which can significantly reduce the cryptographic
operation costs from $O(d)$ to $O(d/\log d)$. We shall present the details in
the following subsections.

1

Input: $\textbf{u}\in\mathbb{R}^{d}$, $B$, $k$, $\epsilon$

Output: “Pass” or “Fail”

2 Sample $\textbf{a}_{1},\dots,\textbf{a}_{k}\in\mathbb{R}^{d}$ i.i.d. from
$\mathcal{N}(\mathbf{0},\mathbf{I}_{d})$

3 Compute $\gamma_{k,\epsilon}$ which satisfies that
$\mathrm{Pr}_{t\sim\chi_{k}^{2}}[t<\gamma_{k,\epsilon}]=1-\epsilon$

4 if  _$\sum_{i=1}^{k}\langle\textbf{a}_{i},\textbf{u}\rangle^{2}\leq
B^{2}\gamma_{k,\epsilon}$_ then

5 return _“Pass”_

6else

7 return _“Fail”_

8 end if

Algorithm 2 Probabilistic $L_{2}$-norm bound check

###  4.2. System Initialization

In this stage, all parties (the server and the clients) are given the system
parameters, including the number of clients $n$, the maximum number of
malicious clients $m$, the bound on the number of bits $b_{\text{ip}}$ of each
inner product, the maximum number of bits $b_{\text{max}}>b_{\text{ip}}$ of
the sum of squares of inner product, the bound of the sum of inner products
$B_{0}<2^{b_{\text{max}}}$, the number of samples $k$ for the probabilistic
check, a set of independent group elements
$g,q\in\mathbb{G},\textbf{w}=(w_{1},\cdots,w_{d})\in\mathbb{G}^{d}$, the
factor $M>0$ used in discretizing the normal distribution samples, and a
cryptographic hash function $H(\cdot)$. Note that $b_{\text{ip}}$ and
$b_{\text{max}}$ define the maximum values of
$\langle\textbf{a}_{i},\textbf{u}\rangle$ and
$\sum\nolimits_{i=1}^{k}\langle\textbf{a}_{i},\textbf{u}\rangle^{2}$ in
Equation 1, respectively.

Since there is no direct channel between any two clients in the FL setting
considered in this paper, we let the server forward some of the messages. To
prevent the server from accessing the secret information, each client
$\mathcal{C}_{i}(i\in[n])$ generates a public/private key pair
$(pk_{i},sk_{i})$ and sends the public key $pk_{i}$ to a public bulletin.
Subsequently, each client fetches the other clients’ public keys such that
each pair of clients can establish a secure channel via the Diffie-Hellman
protocol (Merkle, 1978) for exchanging messages securely.

###  4.3. Commitment Generation

Recall that in each iteration of the FL training process, each client
$\mathcal{C}_{i}(i\in[n])$ obtains a model update $\textbf{u}_{i}$ via local
training on its dataset $\mathcal{D}_{i}$. In order to prove to the server
that the $L_{2}$-norm of $\textbf{u}_{i}$ is within a bound $B_{0}$, the
client $\mathcal{C}_{i}$ needs to commit its update $\textbf{u}_{i}$ before
generating the proofs. In RiseFL, the server is expected to not only identify
malicious clients, but also aggregate well-formed model updates. Therefore, we
propose a novel hybrid commitment scheme based on Pedersen commitment and
VSSS, where VSSS is used to protect the random secret in the Pedersen
commitment for secure aggregation.

Hybrid commitment scheme. Note that the clients and server agree on
independent group elements $g,w_{1},\dots,w_{d}\in\mathbb{G}$, where
$w_{j}(j\in[d])$ is used for committing the $j$-th coordinate in
$\textbf{u}_{i}$. Then, $\mathcal{C}_{i}$ generates a random secret
$r_{i}\in\mathbb{Z}_{p}$ and encrypts $\textbf{u}_{i}$ with Pedersen
commitment as follows:

$\displaystyle\textbf{y}_{i}=C(\textbf{u}_{i},r_{i})$
$\displaystyle=(C({u_{i1}},r_{i}),\dots,C({u_{id}},r_{i}))$ (2)
$\displaystyle=(g^{u_{i1}}w_{1}^{r_{i}},\dots,g^{u_{id}}w_{d}^{r_{i}}),$

where $u_{ij}$ is the $j$-th coordinate in $\textbf{u}_{i}$. Each client
$\mathcal{C}_{i}$ sends $\textbf{y}_{i}=C(\textbf{u}_{i},r_{i})$ and
$z_{i}=g^{r_{i}}$ to the server as commitments. Given that $r_{i}$ is held by
each client $\mathcal{C}_{i}$, the server knows nothing regarding each update
$\textbf{u}_{i}$.

To facilitate the server to aggregate well-formed updates, we also require
each client $\mathcal{C}_{i}$ to share its secret $r_{i}$ with other clients
using VSSS. Specifically, $\mathcal{C}_{i}$ computes
$((1,r_{i1}),\dots,(n,r_{in}),\Psi_{r_{i}})\leftarrow\mathsf{SS.Share}(r_{i},n,m+1,g)$
and sends $((j,r_{ij}),\Psi_{r_{i}})$ to $\mathcal{C}_{j}$, where
$g^{r_{i}}=\Psi_{r_{i}}(0)$. Since the clients do not have communication
channels, $\mathcal{C}_{i}$ encrypts each share $r_{ij}$ with the
corresponding symmetric key established by $(pk_{j},sk_{i})$ for each client
$\mathcal{C}_{j}(j\in[1,n])$, obtaining $\mathsf{Enc}(r_{ij})$. The encrypted
$\mathsf{Enc}(r_{ij})$ ensures that only $\mathcal{C}_{j}$ can decrypt it.
Finally, $\mathcal{C}_{i}$ sends the commitment $\textbf{y}_{i}$, the
encrypted share $\mathsf{Enc}(r_{ij})(j\in[1,n])$, and the check string
$\Psi_{r_{i}}$ to the server. For example, suppose in Figure 2b, Client 2 has
a model update $\textbf{u}_{2}=(5,1)$ and its generates a random secret
$r_{2}=10$. Let $w_{1}=g^{3},w_{2}=g^{4}$ (ignoring the independence
requirement of $g,w_{1},w_{2}$). Client 2 can commit
$\textbf{y}_{2}=(g^{5}\cdot w_{1}^{10},g^{1}\cdot
w_{2}^{10})=(g^{35},g^{41})$. Then, it can generate secret shares of
$r_{2}=(r_{21},r_{22},r_{23})=(3,-4,-11)$ using the polynomial $-7x+10$, where
$r_{21}=3$ and $r_{23}=-11$ will be encrypted using keys shared with Client 1
and Client 3 respectively, before they are sent to the server together with
the check string.

After receiving the messages from all clients, the server forwards the
encrypted shares $\mathsf{Enc}(r_{ij})(i\in[1,n])$ to client
$\mathcal{C}_{j}$, and broadcasts the check strings $\Psi_{r_{i}}(i\in[1,n])$
to all clients. We will introduce how the server aggregates well-formed
updates from honest clients based on these commitments in Section 4.5.

(a) Sample random vectors and
compute inner products

(b) Check the bound of the sum of
inner products

Figure 3. The probabilistic check when $||\textbf{u}||_{2}=1$.

###  4.4. Proof Generation and Verification

In this round, the clients and the server jointly flag the malicious clients.
Specifically, the server initializes a list $\mathcal{C}^{*}=\emptyset$ to
record the malicious clients that will be identified in the current iteration.
This round consists of two steps: verifying the authenticity of secret shares
and verifying the integrity of each client’s update.

####  4.4.1. Verify the authenticity of secret shares.

After receiving the encrypted shares $\mathsf{Enc}(r_{ji})$ and check strings
$\Psi_{r_{j}}$ for $j\in[1,n]$, each client $\mathcal{C}_{i}$ decrypts
$r_{ji}$ and checks against $\Psi_{r_{j}}$. If a check fails,
$\mathcal{C}_{i}$ marks the corresponding client $\mathcal{C}_{j}$ as
malicious because the share is not authenticated. Subsequently,
$\mathcal{C}_{i}$ sends a list of candidate malicious clients that do not pass
the check to the server.

The server follows two rules to flag the malicious clients (Roy Chowdhury et
al., 2022). First, if a client $\mathcal{C}_{i}$ flags more than $m$ clients
as malicious or is flagged as malicious by more than $m$ clients, the server
puts $\mathcal{C}_{i}$ to $\mathcal{C}^{*}$. This is because there are at most
$m$ malicious clients in the system. An honest client cannot mark more than
$m$ clients as malicious clients and will not be marked as malicious by more
than $m$ clients. For example, in Figure 2c, Client 3 marks the other two
clients as malicious, then the server can ensure that this client is
malicious.

Second, if a client $\mathcal{C}_{i}$ is flagged as malicious by $[1,m]$
clients, the server requests the shares $r_{ij}$ in the clear for all
$\mathcal{C}_{j}$ that flags $\mathcal{C}_{i}$ and checks against
$\Psi_{r_{i}}$, if the clear $r_{ij}$ fails the check, the server puts
$\mathcal{C}_{i}$ to $\mathcal{C}^{*}$. Note that if client $\mathcal{C}_{i}$
receives more than $m$ requests of the clear-text shares $r_{ij}$ from the
server, it marks the server as malicious and quits the protocol because this
should not happen. If $\mathcal{C}_{i}$ receives $m^{\prime}\in[1,m]$ requests
of clear-text $r_{ij}$, it sends them to the server. Under the assumption of
at most $m$ malicious clients, there are at most $m-m^{\prime}$ malicious
clients left. Even if all of the malicious clients collude with the server, at
most $m$ values of $r_{ij}$ would be revealed, so $r_{i}$ remains secure.

####  4.4.2. Verify the integrity of each client’s update.

Next, we present how the server and clients jointly execute the probabilistic
integrity check described in Section 4.1. Without loss of generality, we
describe the check for one client $\mathcal{C}_{i}$.

Sampling $k$ random vectors. At the beginning, the server and clients need to
agree on $k$ random samples $\textbf{a}_{1},\cdots,\textbf{a}_{k}$ with
dimensionality $d$. Intuitively, we can let the server sample the $k$ vectors
and broadcast them to all clients. However, there are two main issues. First,
the communication cost can be very high. As will be discussed in Section 5.1,
the choice of $k$ typically requires to be several thousand. Therefore, it is
communication inefficient for the server to broadcast $k$ vectors (each vector
contains $d$ elements). Second, the server may select special vectors that are
not random, i.e., the vectors may allow the server to infer the client’s
update easily. For example, if the server selects
$\textbf{a}_{t}=(1,0,\dots,0)$ for all $t\in[1,k]$, it may infer the range of
the first element in a client’s update. To solve these issues, we let the
server select a random value $s$ and broadcast it to all clients. Based on
$s$, the server and each client $\mathcal{C}_{i}(i\in[n])$ can compute a seed
$H(s,\\{pk_{i}\\}_{1\leq i\leq n})$ using $s$ and all clients’ public keys.
Hence, the clients and the server can generate the same set of random samples
because the seed is the same. Note it is computationally infeasible to find a
seed that produces specific vectors since $H(\cdot)$ is a cryptographic hash
function.

Optimization of cryptographic operations. Given the random vectors
$\textbf{a}_{1},\cdots,\textbf{a}_{k}$, a naive way of realizing the
probabilistic bound check in Algorithm 2 is to let client $\mathcal{C}_{i}$
commit to $\langle\textbf{a}_{t},\textbf{u}_{i}\rangle$ with
$z_{t}=g^{\langle\textbf{a}_{t},\textbf{u}_{i}\rangle}w_{d+t}^{r_{i}}$ for
$t\in[1,k]$ based on additional independent group elements
$w_{d+1},\dots,w_{d+k}$. It can then generate a $\Sigma$-protocol (Camenisch
and Stadler, 1997) proof that the secret in $z_{t}$ is indeed the inner
product of the secrets in $\textbf{y}_{i}$ and $\textbf{a}_{t}$ for
$t\in[1,k]$ and a proof that the sum of the squares of the secrets in $z_{t}$
is bounded. However, its computational cost will be $O(d)$ in terms of group
exponentiations. We thus propose an optimization to reduce the cost of proof
generation to $O(d/\log d)$ group exponentiations.

We observe that the following term $e_{t}(t\in[1,k])$ is used in the inner
product proof generation and verification:

(3) $\displaystyle e_{t}:=y_{i1}^{a_{t1}}\dots y_{id}^{a_{td}}$
$\displaystyle=(g^{u_{i1}}w_{1}^{r_{i}})^{a_{t1}}\dots(g^{u_{id}}w_{d}^{r_{i}})^{a_{td}}$
(4)
$\displaystyle=g^{\langle\textbf{a}_{t},\textbf{u}_{i}\rangle}(w_{1}^{a_{t1}}\dots
w_{d}^{a_{td}})^{r_{i}}.$

Let $h_{t}=w_{1}^{a_{t1}}\dots w_{d}^{a_{td}}$, which is the same for all the
clients as the random vector $\textbf{a}_{t}$ and the group elements
$w_{1},\cdots,w_{d}$ are shared by the server and clients. Thus, we let the
server precompute $h_{t}$ for $t\in[1,k]$ and broadcast them to all clients
before they generate proofs. Given $h_{t}$, the cost of computing the values
$e_{t}$ in Equation 3 for $t\in[1,k]$ is $O(k)$ group exponentiations and
$O(kd)$ finite field operations. Still, the client cannot blindly compute the
value in Equation 3 by
$e_{t}=g^{\langle\textbf{a}_{t},\textbf{u}_{i}\rangle}h_{t}^{r_{i}}$ as
$h_{t}$ is received from the server, which could be malicious. Therefore, we
let the client use batch verification111To check whether
$x_{1}=\dots=x_{n}=1$, it is enough to randomly sample
$\alpha_{1},\dots,\alpha_{n}$ from the uniform distribution on
$\mathbb{Z}_{p}$ and check whether $x_{1}^{\alpha_{1}}\dots
x_{n}^{\alpha_{n}}=1$. to check whether $h_{t}=w_{1}^{a_{t1}}\dots
w_{d}^{a_{td}}$ for $t\in[1,k]$. The cost of batch verification is $O(d/\log
d)$ group exponentiations and $O(kd)$ finite field operations. Note that the
group exponentiations are the major cost as they are much more complex than
finite field operations. The reduction of the number of group exponentiations
from $O(d)$ to $O(d/\log d)$ significantly reduces client cost, while the
additional cost of $O(kd)$ finite field operations is not large.222The
corresponding micro-benchmark results will be presented in Section 6.2.

To make sure that $e_{t}$ is indeed the commitment of the inner product of
$\textbf{a}_{t}$ and the secret in $\textbf{y}_{i}$, the server uses batch
verification to check that the values $e_{t}$, $t\in[1,k]$, submitted by
client $\mathcal{C}_{i}$ satisfy Equation 3:
$e_{t}\stackrel{{\scriptstyle?}}{{=}}y_{i1}^{a_{t1}}\dots y_{id}^{a_{td}}$.
The only issue at this step is that even if all of the equations
$e_{t}=y_{i1}^{a_{t1}}\dots y_{id}^{a_{td}}$ are satisfied, the server is
still not sure that client $\mathcal{C}_{i}$ possesses a value
$\textbf{u}_{i}$ that is used to produce $\textbf{y}_{i}$. To address this
issue, the server additionally samples $\textbf{a}_{0}\in\mathbb{Z}_{p}^{d}$
from the uniform distribution on $\mathbb{Z}_{p}$ with cryptographically
secure pseudo-random number generator (PRNG), computes the corresponding
$h_{0}=\prod_{l}w_{l}^{a_{il}}$ and broadcasts it together with
$h_{1},\dots,h_{k}$. The client needs to additionally verify the correctness
of $h_{0}$ together with $h_{1},\dots,h_{k}$ by batch verification, which is
detailed in Algorithm 3. The server then uses batch verification in Algorithm
3 to check the correctness of
$e_{t}\stackrel{{\scriptstyle?}}{{=}}y_{i1}^{a_{t1}}\dots y_{id}^{a_{td}}$ for
$t\in[0,k]$. With the additional commitment $e_{0}$, the server can acquire an
additional $\Sigma$-protocol proof that client $\mathcal{C}_{i}$ possesses a
value $\gamma$ that satisfies $e_{0}=g^{\gamma}h_{0}^{r_{i}}$. Once this
additional proof is satisfied, the server is sure that client
$\mathcal{C}_{i}$ possesses $\textbf{u}_{i}$ that satisfies
$y_{il}=g^{u_{il}}w_{l}^{r_{i}}$, and that
$\gamma=\langle\textbf{a}_{0},\textbf{u}_{i}\rangle$. Therefore, the secrets
in $e_{t}$ are indeed the inner product between $\textbf{a}_{t}$ and
$\textbf{u}_{i}$, $t\in[0,k]$.

Finally, the commitment $e_{t}$ uses group element $h_{t}$, which is different
for different $t$. In order to verify the bound of the sum of the squares of
the secrets in $e_{t}$, we need to fix another independent group element $q$
and convert $e_{t}$ to another commitment
$o_{t}=g^{\langle\textbf{a}_{t},\textbf{u}_{i}\rangle}q^{s_{t}}$, where
$s_{t}$ is another blind chosen by client $\mathcal{C}_{i}$. $o_{t}$,
$t\in[1,k]$ are all based on $q$. We then proceed to check the bound of the
squares of the secrets in $o_{t}$.

1

Input: $\textbf{w}=(w_{1},\dots,w_{d})\in\mathbb{G}^{d}$,
$\textbf{h}=(h_{0},\dots,h_{k})\in\mathbb{Z}_{p}^{(k+1)}$,
$\textbf{A}\in\mathbb{M}_{(k+1)\times d}(\mathbb{Z}_{p})$.

2 Randomly Sample $\textbf{b}=(b_{0},\dots,b_{k})\in\mathbb{Z}_{p}^{k+1}$.

3 Compute
$\textbf{c}=(c_{1},\dots,c_{d})=\textbf{b}\cdot\textbf{A}\in\mathbb{Z}_{p}^{d}$.

return _$h_{0}^{b_{0}}\dots h_{k}^{b_{k}}==w_{1}^{c_{1}}\dots w_{d}^{c_{d}}$._

Algorithm 3 $\mathsf{VerCrt}(\textbf{w},\textbf{h},\textbf{A})$

Probabilistic input integrity verification. Now we detail the probabilistic
input integrity verification in Algorithm 2. Assume the server and clients
generate $k+1$ random samples
$\textbf{A}=(\textbf{a}_{0},\textbf{a}_{1},\cdots,\textbf{a}_{k})\in\mathbb{Z}_{p}^{d}$
using the aforementioned techniques. After that, the server computes
$h_{t}=\prod_{l}w_{l}^{a_{tl}}$ for $t\in[0,k]$. Let
$\textbf{h}=(h_{0},h_{1},\cdots,h_{k})$. The server sends h to the client.
Upon receiving the information, the client first verifies the correctness of h
using $\mathsf{VerCrt}(\textbf{w},\textbf{h},\textbf{A})$ in Algorithm 3. If
it is correct, the client computes the following items for generating the
proof that Eqn 1 is less than the bound $B_{0}$. An illustration of the
client’s proof generation is given in Figure 4.

  * •

The client computes the inner products between $\textbf{u}_{i}$ and each row
of A, obtaining $\textbf{v}^{*}=(v_{0},v_{1},\cdots,v_{k})$, where
$v_{t}=\langle\textbf{a}_{t},\textbf{u}_{i}\rangle$ for $t\in[0,k]$. The
client commits $e_{t}=g^{v_{t}}h_{t}^{r_{i}}$ using its secret $r_{i}$ for
$t\in[0,k]$. Let $\textbf{e}^{*}=(e_{0},e_{1},\cdots,e_{k})$ and
$\textbf{e}=(e_{1},\cdots,e_{k})$. The commitment $e_{0}$ is used for
integrity check of $\textbf{y}_{i}$. The commitments e are used for bound
check of $\textbf{v}=(v_{1},\cdots,v_{k})$.

  * •

The client commits $v_{t}$ using $o_{t}=g^{v_{t}}q^{s_{t}}$ for $t\in[1,k]$,
where $s_{t}$ is a random number. Let $\textbf{o}=(o_{1},\cdots,o_{k})$ be the
resulted commitment. Note that $e_{t}$ and $o_{t}$ commit to the same secret
$v_{t}$ using different group elements $h_{t}$ and $q$.

  * •

The client generates a proof $\rho$ to prove that
$(z,\textbf{e}^{*},\textbf{o})$ is well-formed, which means that the secret in
$z$ is used as the blind in $e_{t}$, $t\in[0,k]$, and that the secrets in
$e_{t}$ and $o_{t}$ are equal, $t\in[1,k]$. Note that
$z=g^{r_{i}}=\Psi_{r_{i}}(0)$ is the $0$-th coordinate of the check string of
Shamir’s share of $r_{i}$.

  * •

The client generates a proof $\sigma$ that the secret in $o_{t}$ is in the
interval $[-2^{b_{\mathsf{ip}}},2^{b_{\mathsf{ip}}})$ for $t\in[1,k]$. This
ensures the inner product of $\textbf{a}_{t}$ and $\textbf{u}_{i}$ does not
cause overflow when squared.

  * •

The client commits $o_{t}^{\prime}=g^{v_{t}^{2}}q^{s_{t}^{\prime}}$ for
$t\in[1,k]$, where $s_{t}^{\prime}$ is a random number. Let
$\textbf{o}^{\prime}=(o_{1}^{\prime},\cdots,o_{k}^{\prime})$ be the resulted
commitment. This commitment will be used in the proof generation and
verification for proof of square.

  * •

The client generates a proof $\tau$ to prove that the secret in
$o_{t}^{\prime}$ is the square of the secret in $o_{t}$ for $t\in[1,k]$, using
the building block described in Section 2.

  * •

The client computes $B_{0}-\sum_{t}v_{t}^{2}$ and further commits it with
$p=g^{B_{0}}(\prod_{t}o_{t}^{\prime})^{-1}$.

  * •

The client generates a proof $\mu$ that $B_{0}-\sum_{t}v_{t}^{2}$ is in the
interval $[0,2^{b_{\mathsf{max}}})$. This proof is to guarantee that Eqn 1 is
less than the bound of the probabilistic check.

Figure 4. An illustration of the ZKP proof generation on the $i$-th client.

Finally, the client sends the proof
$\pi=(\textbf{e}^{*},\textbf{o},\textbf{o}^{\prime},p,\rho,\tau,\sigma,\mu)$
to the server for verifcation.

After receiving the proof, the server verifies it accordingly, including
checking the correctness of $\textbf{e}^{*}$ using Algorithm 3, checking the
well-formedness proof $\rho$, checking the square proofs of
$(\textbf{o}^{\prime},\textbf{o})$, and checking the two bound proofs. If all
the checks are passed, the server guarantees that the client’s update passes
the probabilistic check in Algorithm 2. Consequently, the server can verify
the proof of each client $\mathcal{C}_{i}$ and put it to the malicious client
list $\mathcal{C}^{*}$ if the verification fails. The list $\mathcal{C}^{*}$
is broadcast to all the clients.

###  4.5. Secure Aggregation

Let $\mathcal{H}=\mathcal{C}\setminus\mathcal{C}^{*}$ be the set of honest
clients. In this round, each client $\mathcal{C}_{i}\in\mathcal{H}$ selects
the corresponding secret shares from the honest clients
$\mathcal{C}_{j}\in\mathcal{H}$, aggregates the shares
$r_{i}^{\prime}=\sum_{\mathcal{C}_{j}\in\mathcal{H}}r_{ji}$, and sends
$r_{i}^{\prime}$ to the server. The server uses $\mathsf{SS.Verify}$ to verify
the integrity of each $r_{i}^{\prime}$ and uses $\mathsf{SS.Recover}$ to
recover $r^{\prime}=\sum_{\mathcal{C}_{i}\in\mathcal{H}}r_{i}^{\prime}$.
According to the homomorphic property of VSSS,
$r^{\prime}=r=\sum_{\mathcal{C}_{i}\in\mathcal{H}}r_{i}$ is the summation of
the honest clients’ secrets. The summation will be used for calculating the
aggregation of honest clients’ model updates
$\mathcal{U}=\sum\nolimits_{\mathcal{C}_{i}\in\mathcal{H}}\textbf{u}_{i}$.

Specifically, the server executes the following steps. For each dimension
$l\in[d]$ in the updates, the server multiplies the commitments from honest
clients $\mathcal{C}_{j}\in\mathcal{H}$ and obtains:

(5) $\displaystyle C(\mathcal{U},r)$
$\displaystyle=(\prod\nolimits_{\mathcal{C}_{i}\in\mathcal{H}}C({u_{i1}},r_{i}),\dots,\prod\nolimits_{\mathcal{C}_{i}\in\mathcal{H}}C({u_{id}},r_{i})).$

Without loss of generality, we consider the $l$-th dimension and derive the
calculation as follows.

(6)
$\displaystyle\prod\nolimits_{\mathcal{C}_{i}\in\mathcal{H}}C({u_{il}},r_{i})$
$\displaystyle=g^{\sum_{\mathcal{C}_{i}\in\mathcal{H}}u_{il}}w_{l}^{\sum_{\mathcal{C}_{i}\in\mathcal{H}}r_{i}}$
(7) $\displaystyle=g^{u_{l}}w_{l}^{r},$

where $u_{l}$ is the aggregation of the $l$-th elements in honest clients’
updates, $w_{l}$ is the common group element used for the commitment in Eqn
4.3, and $r$ is the summation of honest clients’ secrets. Note that the
derivation of Eqn 6 is due to clients using the same group elements $g$ and
$w_{l}$. Since the server has already calculated $r=r^{\prime}$, it can thus
compute $g^{u_{l}}$ for $l\in[d]$ and solve $u_{l}$ according to Eqn 7.

###  4.6. Extensions

Although we focus on the $L_{2}$-norm bound check in this paper, our solution
can be easily extended to support a wide range of defense methods. For
instance, we can support the sphere defense (Steinhardt et al., 2017), the
cosine similarity defense (Bagdasaryan et al., 2020; Cao et al., 2021) and the
Zeno++ defense (Xie et al., 2019).

For sphere defense, the server broadcasts a public vector v and a bound $B$,
and then checks whether the model update u satisfies
$||\textbf{u}-\textbf{v}||_{2}\leq B$. We can change our protocol in which the
$i$-th client commits to $\textbf{u}_{i}-\textbf{v}$ instead of
$\textbf{u}_{i}$. The server then recovers
$\sum_{i\in\mathcal{H}}(\textbf{u}_{i}-\textbf{v})$ and computes
$\sum_{i\in\mathcal{H}}\textbf{u}_{i}=\sum_{i\in\mathcal{H}}(\textbf{u}_{i}-\textbf{v})+\textbf{v}\cdot|\mathcal{H}|$,
where $\mathcal{H}$ is the set of honest clients. For cosine similarity
defense, the server broadcasts $\textbf{v},B$ and a public hyperparameter
$\alpha$, and then checks whether the model update u satisfies both
$||\textbf{u}||_{2}\leq B$ and
$\langle\textbf{u},\textbf{v}\rangle\geq\alpha||\textbf{u}||_{2}||\textbf{v}||_{2}$.
We can add a predicate to the protocol that checks
$||\textbf{u}||_{2}\leq\frac{\langle\textbf{u},\textbf{v}\rangle}{\alpha||\textbf{v}||_{2}}$
based on Algorithm 2. For the Zeno++ defense
$\gamma\langle\textbf{v},\textbf{u}\rangle-\rho||\textbf{u}||_{2}^{2}\geq\gamma\epsilon$,
where $\rho,\gamma,\epsilon$ are public hyperparameters, it can be converted
into sphere defense by
$||\textbf{u}-\frac{\gamma}{2\rho}\textbf{v}||_{2}\leq\sqrt{\frac{\gamma}{\rho}\epsilon+\frac{\gamma^{2}}{4\rho^{2}}||\textbf{v}||_{2}^{2}}$
for the check.

##  5\. Analysis

(a) $k$ vs. $F_{k,\epsilon,d,M}$

(b) $k$ vs. maximum damage

Figure 5. The effect of $k$ when $\epsilon=2^{-128}$, $d=10^{6}$, $M=2^{24}$:
(a) the trend of $F_{k,\epsilon,d,M}$ w.r.t. $k$; (b) the trend of the maximum
damage w.r.t. $k$.

###  5.1. Security Analysis

We state the formal security theorem and outline its proof.

###### Theorem 1.

By choosing $\epsilon=\mathrm{negl}(\kappa)$ and
$B_{0}=B^{2}M^{2}(\sqrt{\gamma_{k,\epsilon}}+\frac{\sqrt{kd}}{2M})^{2}$, for
any list of honest clients $\mathcal{C}_{H}$ of size at least $n-m$, RiseFL
satisfies $(D,F_{k,\epsilon,d,M})$-SAVI, where
$D(\textbf{u})=||\textbf{u}||_{2}/B$ and

(8) $\displaystyle
F_{k,\epsilon,d,M}(c)=\mathrm{Pr}_{x\sim\chi_{k}^{2}}\left[x<\frac{1}{c^{2}}\left(\sqrt{\gamma_{k,\epsilon}}+\frac{3\sqrt{kd}}{2M}\right)^{2}\right]+\mathrm{negl}(\kappa).$

The proof consists of three parts: showing that the server computes an
aggregate $\textbf{U}=\sum_{i\in H^{\prime}}\textbf{u}_{i}$ for some
$H^{\prime}\supseteq H$ with probability at least $1-\mathrm{negl}(\kappa)$;
showing that with probability at least $1-\mathrm{negl}(\kappa)$, nothing else
except $\sum_{\mathcal{C}_{i}\in\mathcal{C}_{H}}\textbf{u}_{i}$ is known about
$\textbf{u}_{i}$ for any $i\in H$; and showing that if $\mathcal{C}_{i}$ is
malicious with $||\textbf{u}||_{2}/B=c$, then the probability that $i\in
H^{\prime}$ is bounded by $F_{k,\epsilon,d,M}(c)$.

The server aggregates model updates from honest clients and possibly some
malicious clients. The aggregation step in Section 4.5 ensures that the server
computes an aggregate
$\textbf{U}=\sum_{\mathcal{C}_{i}\in\mathcal{C}_{H}^{\prime}}\textbf{u}_{i}$
for a list $\mathcal{C}_{H}^{\prime}$ that is marked as honest clients by the
server. We need to prove that this list $\mathcal{C}_{H}^{\prime}$ must
contain $\mathcal{C}_{H}$. In fact, if $\mathcal{C}_{i}$ is honest, then
$||\textbf{u}_{i}||\leq B$. If $\textbf{b}_{1},\dots,\textbf{b}_{k}$ are
sampled i.i.d. from the normal distribution
$\mathcal{N}(\textbf{0},M\cdot\textbf{I}_{d})$. Then,
$\frac{1}{||\textbf{u}||_{2}^{2}M^{2}}\sum_{t=1}^{k}\langle\textbf{b}_{t},\textbf{u}\rangle^{2}$
follows the chi-square distribution $\chi_{k}^{2}$. So the probability that

(9)
$\displaystyle\sum_{t=1}^{k}\langle\textbf{b}_{t},\textbf{u}_{i}\rangle^{2}\leq
B^{2}M^{2}\gamma_{k,\epsilon}$

is at least $1-\epsilon$. Define $\mathsf{round}:\mathbb{R}\to\mathbb{Z}$ by
$\mathsf{round}(n+\alpha)=n$ for $n\in\mathbb{Z}$, $-1/2\leq\alpha<1/2$.
Define $\textbf{a}_{t}$ by $a_{tj}=\mathsf{round}(b_{tj})$ for $t\in[1,k]$.
After rounding $\textbf{b}_{t}$ to $\textbf{a}_{t}$, (9) implies the relaxed
inequality

(10)
$\displaystyle\sum_{t=1}^{k}\langle\textbf{a}_{t},\textbf{u}_{i}\rangle^{2}\leq
B_{0}$

If (10) holds, $\mathcal{C}_{i}$ can produce a proof which passes the
integrity check. Since $\epsilon=\mathrm{negl}(\kappa)$, the probability that
all of the honest clients can produce a valid proof is at least
$1-\mathrm{negl}(\kappa)$.

Security of honest clients. Cryptographically, the values of $\Psi_{r_{i}}$,
$C(\textbf{u}_{i},r_{i})$, and $\pi_{i}$ do not reveal any information about
$\textbf{u}_{i}$ or $r_{i}$. VSSS ensures that nothing is revealed from the
$\leq m$ shares $\\{r_{ij}\\}_{j\notin\mathcal{C}_{H}}$ of the secret $r_{i}$.
At the secure aggregation step in Section 4.5, VSSS ensures that only
$\sum_{\mathcal{C}_{i}\in\mathcal{C}_{H}}r_{i}$ is revealed. From
$\sum_{\mathcal{C}_{i}\in\mathcal{C}_{H}}r_{i}$, the only value that can be
computed is $\sum_{\mathcal{C}_{i}\in\mathcal{C}_{H}}\textbf{u}_{i}$.
Therefore, nothing else except
$\sum_{\mathcal{C}_{i}\in\mathcal{C}_{H}}\textbf{u}_{i}$ is known about
$\textbf{u}_{i}$ for any $i\in H$.

Pass rate of malicious clients is bounded by $F$. Suppose that
$\mathcal{C}_{i}$ is malicious and
$D(\textbf{u}_{i})=||\textbf{u}_{i}||/B=c>1$. Suppose that
$\textbf{b}_{1},\dots,\textbf{b}_{k}$ are sampled i.i.d. from the normal
distribution $\mathcal{N}(\textbf{0},M\cdot\textbf{I}_{d})$ and
$\textbf{a}_{t}$ is rounded from $\textbf{b}_{t}$ as before. With probability
at least $1-\mathrm{negl}(\kappa)$, if $\mathcal{C}_{i}$ passes the integrity
check, it must happen that
$\sum_{t=1}^{k}\langle\textbf{a}_{t},\textbf{u}\rangle^{2}\leq B_{0}$. If
$\sum_{t=1}^{k}\langle\textbf{a}_{t},\textbf{u}\rangle^{2}\leq B_{0}$ holds,
then the following relaxed inequality on $\textbf{b}_{t}$ must hold:

(11)
$\displaystyle\sum_{t=1}^{k}\langle\textbf{b}_{t},\textbf{u}\rangle^{2}\leq\frac{1}{c^{2}}\left(\sqrt{\gamma_{k,\epsilon}}+\frac{3\sqrt{kd}}{2M}\right)^{2}.$

The probability that (11) happens is bounded by $F_{k,\epsilon,d,M}(c)$.

Table 1. Cost comparison (g.e. = group exponentiation, f.a. = field arithmetic) |  | EIFFeL | RoFL | ACORN | RiseFL
---|---|---|---|---|---
g.e. | f.a. | g.e. | f.a.
Client comp. | commit. | $O(md)$ | $O(nmd)$ | $O(d)$ | $O(d)$ | $O(d)$ | small
proof gen. | 0 | $O(bnmd)$ | $O(db)$ | $O(d)$ | $O(d/\log d)$ | $O(kd)$
proof ver. | $O(nmd/\log(md))$ | $O(bnmd)$ | 0 | 0 | 0 | 0
total | $O(nmd/\log(md))$ | $O(bnmd)$ | $O(db)$ | $O(d)$ | $O(d)$ | $O(kd)$
Server comp. | prep. | 0 | 0 | 0 | 0 | $O(kd\log M/\log d\log p)$ | small
proof ver. | 0 | small | $O(ndb/\log(db))$ | $O(nd/\log(d))$ | $O(nd/\log d)$ | small
agg. | 0 | $O(nmd)$ | $O(nd/\log p)$ | $O(nd/\log(p))$ | $O(nd/\log p)$ | small
total | 0 | $O(nmd)$ | $O(ndb/\log(db))$ | $O(nd/\log(d))$ | $O(d(n+k\log M/\log p)/\log d)$ | small
Comm. per client | $\approx 2dnb$ | $\approx 12d$ | $\approx(b+\log n)/\log(p)$ | $\approx d$

Discussion. Now we discuss the effect of $k$ on $F_{k,\epsilon,d,M}$ and the
maximum damage, which is illustrated in Figure 5. We set $\epsilon=2^{-128}$
by default in this paper. We set $M=2^{24}$ so that when $k\leq 10^{4}$ and
$d\leq 10^{6}$, the term $\frac{3\sqrt{kd}}{2M}$ is insignificant in Eqn 8.
Figure 5a shows the trend of $F_{k,\epsilon,d,M}$ with $d=10^{6}$ and
different choices of $k$. We can see that $F_{k,\epsilon,d,M}(c)$ is very
close to 1 when $c$ is slightly larger than 1, and it drops to negligible
rapidly as $c$ continues to increase. Specifically, it means that when
$k=1000$, a malicious $\textbf{u}_{i}$ with $||\textbf{u}_{i}||_{2}\leq 1.2B$
will very likely pass the integrity check, but when
$||\textbf{u}_{i}||_{2}\geq 1.4B$, the check will fail with close-to-1
probability.

This is the downside of the probabilistic $L_{2}$-norm checking, i.e.,
slightly out-of-bound vectors may pass the check. We can quantify the size of
damages caused by such malicious vectors. For example, with strict checking, a
malicious client can use a malicious u with $||\textbf{u}||_{2}=B$ which
passes the check, so that it can do damage of magnitude $B$ to the aggregate.
With the probabilistic check, the malicious client can use slightly larger
$||\textbf{u}||_{2}$ at a low failure rate. The expected damage it can do to
the aggregate is $||\textbf{u}||_{2}\cdot
F_{k,\epsilon,d,M}(||\textbf{u}||_{2}/B)$. By choosing a suitable
$||\textbf{u}||_{2}$, the maximum expected damage is

(12) $\displaystyle B\cdot\max\\{c\cdot
F_{k,\epsilon,d,M}(c):c\in(1,+\infty)\\}.$

The value $\max\\{c\cdot F_{k,\epsilon,d,M}(c):c\in(1,+\infty)\\}$ can be
calculated easily as $c^{*}\cdot F_{k,\epsilon,d,M}(c^{*})$ because $c\cdot
F_{k,\epsilon,d,M}(c)$ is increasing for $c\in(1,c^{*}]$ and decreasing for
$c\in[c^{*},+\infty)$ for some $c^{*}$. Figure 5b shows the maximum expected
damage with respect to $k$ when $B=1$. It turns out that with
$\epsilon=2^{-128}$ and $k\geq 10^{3}$, the maximum expected damage is close
to 1. In other words, the magnitude of damage that a malicious client can do
to the aggregate is only slightly more than the one under the strict
$L_{2}$-norm check protocol. We will experiment with
$k=1\text{K},3\text{K},9\text{K}$ in Section 6, corresponding to the ratio of
the magnitudes of damages $1.24$, $1.13$, $1.08$, respectively.

###  5.2. Cost Analysis

We theoretically analyze the cost of RiseFL under the assumption of $d>>k$ by
comparing it to EIFFeL, RoFL and ACORN as summarized in Table 1. Here we count
the number of cryptographic group exponentiations (g.e.) and finite field
arithmetic (f.a.) separately for EIFFeL and RiseFL. The communication cost per
client is measured in the number of group elements.

EIFFeL. The commitment includes the Shamir secret shares and the check string
for each coordinate. The Shamir shares incur a cost of $O(nmd)$ f.a.
operations. The check strings use information-theoretic secure VSSS333The
Feldman check string (Feldman, 1987) is not secure because weight updates are
small. $u_{il}$ can be easily computed from $g^{u_{il}}$ because $u_{il}$ has
short bit-length. (Pedersen, 2001), which involves $O(m)$ group
exponentiations per coordinate for Byzantine tolerance of $m$ malicious
clients. The proof generation444In order to prevent overflow in finite field
arithmetic, client $\mathcal{C}_{i}$ has to prove that each $u_{il}$ is
bounded, so it has to compute shares of every bit of $u_{il}$. and
verification555We use the multiplicative homogeneity of Shamir’s share to
compute shares of the sum of squares at the cost of requiring $m<(n-1)/4$.
This is discussed in (Roy Chowdhury et al., 2022, Section 11.1). The
corresponding cost is $O(d)$ per sum of squares. In comparison, the polynomial
interpolation approach in (Roy Chowdhury et al., 2022, Section 11.1) is
actually $O(d^{2})$ per sum of squares because one needs to compute $d$ values
of polynomials of degree $d$, even if the Lagrange coefficients are
precomputed. (excluding verification of check strings) costs $O(bnmd)$ f.a.
and about $2dnb$ elements of bandwidth on the client side, where $b$ is the
bit length of the update. The verification of the check strings of one client
takes a mult-exponentiation of length $(m+1)d$, or $O(md/\log md)$ g.e. using
a Pippenger-like algorithm (Pippenger, 1980). The server cost is small
compared to client cost.

Table 2. Breakdown cost comparison w.r.t. the number of model parameters $d$, where $k=1000$ $\\#$Param. | Approach | Client Computation (seconds) | Server Computation (seconds) |  Comm. Cost per Client (MB)
---|---|---|---|---
commit. |  proof gen. |  proof ver. |  total | prep. |  proof ver. |  agg. |  total
$d$ = 1K | EIFFeL | 0.865 | 3.63 | 11.7 | 16.2 | - | - | 0.182 | 0.182 | 125
RoFL | 0.051 | 4.43 | - |  4.5 | - | 91.2 | 0.040 | 91.3 | 0.37
ACORN | 0.076 | 2.49 | - |  2.6 | - | 58.9 | 0.040 | 58.9 | 0.004
RiseFL (ours) | 0.054 | 1.48 | 0.08 |  1.6 | 1.17 | 75.6 | 0.071 | 76.8 | 0.44
$d$ = 10K | EIFFeL | 8.38 | 36.8 | 115 | 161 | - | - | 1.81 | 1.81 | 1250
RoFL | 0.51 | 46.4 | - | 46.9 | - | 860 | 0.41 | 860 | 3.66
ACORN | 0.75 | 24.5 | - | 25.3 | - | 522 | 0.41 | 523 | 0.03
RiseFL (ours) | 0.49 |  1.8 | 0.08 | 2.3 | 8.61 | 82.5 | 0.71 | 91.8 | 0.71
$d$ = 100K | EIFFeL | 84.7 | 382 | 1070 | 1536 | - | - | 18.8 | 18.8 | 12500
RoFL |  5.1 | 496 | - | 502 | - | 8559 |  4.1 | 8563 | 36.6
ACORN |  7.6 | 253 | - | 261 | - | 5087 |  4.1 | 5091 |  0.3
RiseFL (ours) |  4.8 | 4.5 | 0.08 | 9.3 | 73.3 | 139 |  7.2 | 219 |  3.5
$d$ = 1M | EIFFeL | OOM | OOM | OOM | OOM | OOM | OOM | OOM | OOM | OOM
RoFL | OOM | OOM | OOM | OOM | OOM | OOM | OOM | OOM | OOM
ACORN | OOM | OOM | OOM | OOM | OOM | OOM | OOM | OOM | OOM
RiseFL (ours) | 48.0 | 31.2 | 0.08 | 79.3 | 653 | 612 | 72.1 | 1338 | 30.9

RoFL. It uses the ElGammal (Gamal, 1985) commitment
$(g^{u_{il}}h^{r_{il}},g^{r_{il}})$ for each coordinate $u_{il}$ with a
separate blind $r_{il}$, which costs $O(d)$ g.e. in total. The dominating cost
of proof generation includes the generation of a well-formedness proof, which
involves $O(d)$ g.e., $4d$ elements, a commitment, a proof of squares ($O(d)$
g.e., $6d$ elements), and a proof of bound of each coordinate ($4\log(bd)$
multi-exponentiations of length $bd$, or $O(bd)$ g.e.). The proof verification
is executed by the server, where the verification of the bound proof per
client takes 1 multi-exponentiation of length about $2bd$. The aggregation
cost is small.

ACORN. The ZKP part uses a variant of Bulletproofs by Leveraging Lagrange’s
four-square theorem. Compared to RoFL, its computational cost does not depend
on $b$. It uses PRG-SecAgg (Bell et al., 2020) whose communication cost is
only $(1+\log(n)/b)$ times more than plaintext.

RiseFL (Ours). We use Pederson commitment $g^{u_{il}}w_{i}^{r_{i}}$ for each
coordinate, which costs $O(d)$ g.e. in total. On the client side, the main
cost of proof generation is to verify the correctness of h received from the
server, using $\mathsf{VerCrt}$. It costs one multi-exponentiation of length
$d$, or $O(d/\log d)$ g.e., plus $O(kd)$ f.a. to compute
$\textbf{b}\cdot\textbf{A}$. On the server side, the main cost can be divided
into two parts: (1) the computation of multi-exponentiations h at the
preparation stage; (2) the verification of the correctness of e for each
client using $\mathsf{VerCrt}$ at the proof verification stage. Each $h_{t}$,
$t\in[1,k]$ is a multi-exponentiation of length $d$ where the powers are
discrete normal samples from $\mathcal{N}(0,M^{2})$, whose bit-lengths are
$\log(M)$. The cost of computing such an $h_{t}$ is $O(d\log M/\log d\log p)$,
a factor of $\log M/\log p$ faster than a multi-exponentiation whose powers
have bit-lengths $\log p$. The verification of e costs $O(d/\log d)$ g.e. The
aggregation cost is small.

##  6\. Experiments

We implement the proposed RiseFL system in C/C++. The cryptographic primitives
are based on libsodium666https://doc.libsodium.org/ which implements the
Ristretto group777https://ristretto.group/ on Curve25519 that supports 126-bit
security. The implementation consists of 9K lines of code in C/C++.

###  6.1. Methodology

Experimental Setup. We conduct the micro-benchmark experiments on a single
server equipped with Intel(R) Core(TM) i7-8550U CPU and 16GB of RAM. The
experiments of the federated learning tasks are simulated on a server with
Intel(R) Xeon(R) W-2133 CPU, 64GB of RAM, and GeForce RTX 2080 Ti. The default
security parameter is 126 bits. We set $\epsilon=2^{-128}$ to ensure that the
level of security of RiseFL matches the baselines. For the fixed-point integer
representation, we use 16 bits to encode the floating-point values by default.
As discussed in Section 5, we set $M=2^{24}$ to make sure that the rounding
error of discrete normal samples is small.

Datasets. We use three real-world datasets, namely, OrganAMNIST (Yang et al.,
2021, 2023), OrganSMNIST (Yang et al., 2021, 2023) and Forest Cover Type
(Blackard, 1998), to run the FL tasks and measure the classification accuracy.
The OrganAMNIST and OrganSMNIST datasets are medical image datasets based on
abdominal clinical computed tomography. These datasets comprise 58850 and
25221 images of 784 numerical features (28 $\times$ 28) in 11 classes,
respectively. The Forest Cover Type dataset is a tabular dataset consisting of
581012 rows of 10 numerical features, 44 categorical features and a
classification label from 7 label classes. We also generate a synthetic
dataset for micro-benchmarking the computational and communication costs.

Models. We employ a CNN model for the OrganAMNIST dataset, ResNet-18 (He et
al., 2016) for the OrganSMNIST dataset, and TabNet (Arik and Pfister, 2021)
for the Forect Cover Type dataset. The CNN model consists of four layers and
31K parameters. The ResNet-18 model consists of 18 layers and 11M parameters.
The TabNet model consists of 471K parameters. For the micro-benchmark
experiments on synthetic datasets, we use synthetic models with 1K, 10K, 100K,
and 1M parameters for the evaluation.

Figure 6. Cost comparison w.r.t. the number of clients.

Baselines. We compare RiseFL with three secure baselines, namely RoFL
(Lycklama et al., 2023), EIFFeL (Roy Chowdhury et al., 2022), and ACORN (Bell
et al., 2023), using the same secure parameter, to evaluate the performance.
Furthermore, we compare RiseFL with two non-private baselines for input
integrity checking to evaluate model accuracy. The following describes the
baselines:

  * •

RoFL (Lycklama et al., 2023) adopts the ElGammal commitment scheme and uses
the strict checking zero-knowledge proof for integrity check. It does not
guarantee Byzantine robustness.

  * •

EIFFeL (Roy Chowdhury et al., 2022) employs the verifiable Shamir secret
sharing (VSSS) scheme and secret-shared non-interactive proofs (SNIP) for
SAVI, ensuring Byzantine robustness. We implement EIFFeL as it is not open-
sourced.

  * •

ACORN (Bell et al., 2023) adopts the PRG-SecAgg protocol (Bell et al., 2020)
and uses the strict checking zero-knowledge proof for integrity check. It does
not guarantee Byzantine robustness.

  * •

NP-SC is a non-private baseline with strict integrity checking, i.e., the
server checks each client’s update and eliminates the update that is out of
the $L_{2}$-norm bound.

  * •

NP-NC is a non-private baseline without any checking on clients’ updates. In
this baseline, malicious clients can poison the aggregated models through
malformed updates.

Metrics. We utilize three metrics to evaluate the performance of our RiseFL
system.

  * •

Computational Cost refers to the computation time on each client and on the
server. It measures the computational efficiency of the protocol.

  * •

Communication Cost per Client refers to the size of messages transmitted
between the server and each client. It measures the communication efficiency.

  * •

Model Accuracy refers to the ratio of correct predictions for the trained FL
model. It measures the effectiveness of the integrity check method in RiseFL.

###  6.2. Micro-Benchmark Efficiency Evaluation

We first compare the cost of our RiseFL with EIFFeL, RoFL, and ACORN, using
micro-benchmark experiments. Unless otherwise specified, we set the number of
clients to 100 and the maximum number of malicious clients to 10 in this set
of experiments. We use 16 bits888The effect of bit-length on the computational
cost of RiseFL is small. for encoding floating-point values and run the
experiments on one CPU thread on both the client side and the server side.

Effects of $d$. Tables 2 shows the breakdown cost comparison of RiseFL,
EIFFeL, RoFL, and ACORN w.r.t. the number of parameters $d$ in the FL model,
on the client computational cost, the server computational cost, and the
communication cost per client. We set the number of samples $k=1000$. We
failed to run the experiments with $d=1$M on EIFFeL, RoFL, and ACORN due to
insufficient RAM, i.e., out of memory (OOM).

From the table, we observe that RiseFL is superior to the baselines when
$d>>k$. For example, when $d=100$K, the client cost of RiseFL is 28x smaller
than ACORN, $53$x smaller than RoFL and $164$x smaller than EIFFeL. Compared
to RoFL and ACORN, the savings occur at the proof generation stage, which is
attributed to our probabilistic check technique. The cost of EIFFeL is large
as every client is responsible for computing a proof digest of every other
client’s proof in the proof verification stage, which dominates the cost. In
comparison, the client-side proof verification cost of RiseFL is negligible
since every client $\mathcal{C}_{i}$ only verifies the check string of the
Shamir share of one value $r_{j}$ from every other client $\mathcal{C}_{j}$.
This is consistent with the theoretical cost analysis in Table 1.

With regard to server cost, RiseFL is $23$x faster than ACORN999We did not
experiment with server-side batch optimization in ACORN. In ACORN, batch
optimization at the server-side can significantly reduce server-side costs
only when few clients are malicious. With the $10\%$ malicious rate in our
experiment, the improvement with batch optimization is small. and $39$x faster
than RoFL when $d=100$K, due to our probabilistic check method. RiseFL incurs
a higher server cost than EIFFeL because in EIFFeL, the load of proof
verification is on the client side, and the dominating cost of the server is
at the aggregation stage. In fact, the total server cost of RiseFL is $7$
times smaller than the cost of EIFFeL of every client.

For communication cost, when $d=100$K, RiseFL results in 16x more than
transmitting the weight updates in clear text: the committed value of a 16-bit
weight update is 256-bit long. The proof size is negligible because $k<<d$.
ACORN transmits only about $2$x more than clear text, due to its use of PRG-
SecAgg. RoFL transmits about $10$x more elements than RiseFL in the form of
proofs of well-formedness and proofs of squares. The communication cost of
EIFFeL is three orders of magnitude larger than RiseFL as it transmits the
share of every bit of every coordinate of the weight update to every other
client.

Effects of $n$. Figure 6 shows the comparison of the computational cost and
communication cost per client in terms of the number of clients. We vary the
number of clients $n\in\\{50,100,150,200,250\\}$, and set the number of
parameters $d=100$K, and the maximum number of malicious clients $m=0.1n$. We
set the number of samples $k=1$K for RiseFL in this experiment. From Figures
6(a) and (c), we can observe that both the client computational cost and
communication cost per client of RiseFL are at least one order of magnitude
lower than RoFL, EIFFeL, and ACORN, while the server cost of RiseFL is linear
in $n$. In addition, the cost of EIFFeL both on the client side and the server
side, increases quadratically in $n$. When $n$ gets larger, the advantage of
RiseFL is even larger compared to EIFFeL.

(a) Client cost (b) Server cost

Figure 7. Cost v.s. the number of samples ($d=1$M).

Effects of $k$. Figure 7 shows the per-stage breakdown of RiseFL with $d=1$M
by varying $k\in\\{1\text{K},3\text{K},9\text{K}\\}$. On the client side,
proof generation is the only stage that scales with $k$. On the server side,
as $k$ gets larger, the preparation cost of computing h becomes dominant. The
effects of $k$ on the cost breakdown can be explained by Table 1.
Specifically, the terms that scale linearly with $k$ are the $O(kd)$ f.a. term
of the client’s proof generation and the server’s preparation costs. The
linear-in-$k$ terms become dominant as $k$ becomes larger.

(a) OrganAMNIST sign flip attack with
$L_{2}$-norm bound check

(b) OrganAMNIST scaling attack with
$L_{2}$-norm bound check

(c) OrganAMNIST label flip attack with
cosine similarity check

(d) OrganAMNIST noise attack with
sphere defense check

(e) OrganSMNIST sign flip attack with
$L_{2}$-norm bound check

(f) OrganSMNIST scaling attack with
$L_{2}$-norm bound check

(g) OrganSMNIST label flip attack with
cosine similarity check

(h) OrganSMNIST noise attack with
sphere defense check

(i) Forest Cover Type sign flip attack with $L_{2}$-norm bound check

(j) Forest Cover Type scaling attack with $L_{2}$-norm bound check

(k) Forest Cover Type label flip attack with cosine similarity check (l)
Forest Cover Type noise attack with sphere defense check

Figure 8. Comparison of training curves, where NP-SC and NP-NC denote the non-
private methods with strict check and with no check, respectively.

###  6.3. Robustness Evaluation

To evaluate the effectiveness of our probabilistic input integrity check
method, we show the FL model accuracy of RiseFL against four commonly used
attacks on OrganAMNIST, OrganSMNIST and Forest Cover Type datasets,
respectively. The first is the sign flip attack (Damaskinos et al., 2018),
where each malicious client submits $-c\cdot\textbf{u}$ as its model update
with $c>1$. The second is the scaling attack (Bhagoji et al., 2019), where
each malicious client submits $c\cdot\textbf{u}$ as its model update with
$c>1$. The third is the label flip attack (Sun et al., 2019), which labels one
category of instances as another. The fourth is the additive noise attack (Li
et al., 2019), which adds Gaussian noises to the model update.

We experiment with three different defenses: the $L_{2}$ norm defense, the
sphere defense (Steinhardt et al., 2017), and the cosine similarity defense
(Bagdasaryan et al., 2020; Cao et al., 2021). In this set of experiments, We
use FLSim101010https://github.com/facebookresearch/FLSim to simulate federated
learning with 100 clients and 10 malicious clients. Figure 8 shows the
training curves of RiseFL with two non-private baselines, NP-SC and NP-NC (see
Section 6.1). There are two main observations. First, RiseFL achieves better
accuracy than the no-checking baseline NP-NC. This is expected as the
malicious clients can poison the aggregated models by invaliding model updates
if the server does not check the input integrity, leading to lower accuracy or
non-converging curves. Second, the training curves of RiseFL and the strict
$L_{2}$ norm check baseline NP-SC are very close. This confirms the
effectiveness of RiseFL in identifying malformed updates and robust
aggregation under a variety of attacks.

##  7\. Related Works

Secure Aggregation. To protect the client’s input privacy in federated
learning (FL), a number of studies have explored the secure aggregation
(Bonawitz et al., 2017; Zheng et al., 2023; Kairouz et al., 2021), which
enables the server to compute the aggregation of clients’ model updates
without knowing individual updates. A widely adopted approach (Bonawitz et
al., 2017) is to let each client use pairwise random values to mask the local
update before uploading it to the server. The server can then securely cancel
out the masks for correct aggregation. Nonetheless, these solutions do not
guarantee input integrity, as malicious clients can submit arbitrary masked
updates.

Robust Learning. Several works have been proposed for robust machine learning,
including (Liu et al., 2018; Shen and Sanghavi, 2019; Steinhardt et al., 2017;
Yin et al., 2018, 2019; Pan et al., 2020; Cao et al., 2021; Ma et al., 2022;
Xu et al., 2022; Xiang et al., 2023). However, some of these approaches, such
as (Liu et al., 2018; Shen and Sanghavi, 2019; Steinhardt et al., 2017), are
designed for centralized training and require access to the training data,
which makes them unsuitable for FL. On the other hand, solutions like (Yin et
al., 2018, 2019; Pan et al., 2020; Cao et al., 2021; Ma et al., 2022; Xu et
al., 2022) specifically address the FL setting and focus on ensuring Byzantine
resilient gradient aggregation. These solutions operate by identifying and
eliminating client updates that deviate significantly from the majority of
clients’ updates, as they are likely to be malformed updates. However, it is
worth noting that these approaches require the server to access the plaintext
model updates, which compromises the client’s input privacy.

Input Integrity Check with Secure Aggregation. In this research direction,
Prio (Corrigan-Gibbs and Boneh, 2017) and Elsa (Rathee et al., 2023) ensure
both input privacy and input integrity with multiple non-colluding servers.
Under the stronger assumption of at least two non-colluding servers, secure
aggregation can be achieved with a lower computation cost. In contrast, we
focus on a single-server setting. Under this setting, (Lycklama et al., 2023;
Roy Chowdhury et al., 2022; Bell et al., 2023) ensure both input privacy and
integrity. RoFL (Lycklama et al., 2023) utilizes homomorphic commitments
(Gamal, 1985) that are compatible with existing mask-based secure aggregation
methods and adopt the zero-knowledge proof (Bünz et al., 2018) to validate the
clients’ inputs. ACORN (Bell et al., 2023) utilizes PRG-SecAgg (Bell et al.,
2020) which is bandwidth-efficient. However, neither RoFL nor ACORN supports
Byzantine-robust aggregation. EIFFeL (Roy Chowdhury et al., 2022) designs an
approach based on verifiable secret sharing (Shamir, 1979) and secret-shared
non-interactive proofs (SNIP) (Corrigan-Gibbs and Boneh, 2017) techniques,
which can tolerate Byzantine attacks. Nevertheless, the efficiency of these
three solutions is quite low, especially when the number of model parameters
is large. In contrast, in RiseFL, we propose a hybrid commitment scheme and
design a probabilistic input integrity check method, providing support for
Byzantine-robust aggregation and achieving significant efficiency
improvements.

##  8\. Conclusions

In this paper, we propose RiseFL, a robust and secure federated learning
system that guarantees both input privacy and input integrity of the
participating clients. We design a hybrid commitment scheme based on Pedersen
commitment and verifiable Shamir secret sharing, and present a probabilistic
$L_{2}$-norm integrity check method, which achieves a comparable security
guarantee to state-of-the-art solutions while significantly reducing the
computation and communication costs. The experimental results confirm the
efficiency and effectiveness of our solution.

## References

  * (1)
  * GDP (2016) 2016\.  Regulation (eu) 2016/679 of the european parliament and of the council of 27 april 2016 on the protection of natural persons with regard to the processing of personal data and on the free movement of such data, and repealing directive 95/46/ec (general data protection regulation).  (2016).
  * Arik and Pfister (2021) Sercan Ö Arik and Tomas Pfister. 2021.  Tabnet: Attentive interpretable tabular learning. In _Proceedings of the AAAI conference on artificial intelligence_ , Vol. 35. 6679–6687.
  * Bagdasaryan et al. (2020) Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov. 2020\.  How To Backdoor Federated Learning. In _AISTATS_. 2938–2948.
  * Bao et al. (2022) Ergute Bao, Yizheng Zhu, Xiaokui Xiao, Yin Yang, Beng Chin Ooi, Benjamin Hong Meng Tan, and Khin Mi Mi Aung. 2022.  Skellam Mixture Mechanism: a Novel Approach to Federated Learning with Differential Privacy.  _Proc. VLDB Endow._ 15, 11 (2022), 2348–2360.
  * Baunsgaard et al. (2021) Sebastian Baunsgaard, Matthias Boehm, Ankit Chaudhary, Behrouz Derakhshan, Stefan Geißelsöder, Philipp M. Grulich, Michael Hildebrand, Kevin Innerebner, Volker Markl, Claus Neubauer, Sarah Osterburg, Olga Ovcharenko, Sergey Redyuk, Tobias Rieger, Alireza Rezaei Mahdiraji, Sebastian Benjamin Wrede, and Steffen Zeuch. 2021.  ExDRa: Exploratory Data Science on Federated Raw Data. In _SIGMOD_. ACM, 2450–2463.
  * Bell et al. (2023) James Bell, Adrià Gascón, Tancrède Lepoint, Baiyu Li, Sarah Meiklejohn, Mariana Raykova, and Cathie Yun. 2023.  $\\{$ACORN$\\}$: Input Validation for Secure Aggregation. In _USENIX Security 23_. 4805–4822.
  * 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 _CCS_. 1253–1269.
  * Ben-Sasson et al. (2013) Eli Ben-Sasson, Alessandro Chiesa, Daniel Genkin, Eran Tromer, and Madars Virza. 2013.  SNARKs for C: Verifying program executions succinctly and in zero knowledge. In _Advances in Cryptology–CRYPTO 2013: 33rd Annual Cryptology Conference, Santa Barbara, CA, USA, August 18-22, 2013. Proceedings, Part II_. Springer, 90–108.
  * Bhagoji et al. (2019) Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin B. Calo. 2019.  Analyzing Federated Learning through an Adversarial Lens. In _ICML_. 634–643.
  * Blackard (1998) Jock Blackard. 1998\.  Covertype.  UCI Machine Learning Repository.  DOI: https://doi.org/10.24432/C50K5N.
  * Blum et al. (1988) Manuel Blum, Paul Feldman, and Silvio Micali. 1988\.  Non-Interactive Zero-Knowledge and Its Applications (Extended Abstract). In _STOC_. 103–112.
  * 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 _CCS_. 1175–1191.
  * Bünz et al. (2018) Benedikt Bünz, Jonathan Bootle, Dan Boneh, Andrew Poelstra, Pieter Wuille, and Greg Maxwell. 2018.  Bulletproofs: Short proofs for confidential transactions and more. In _S &P_. IEEE, 315–334.
  * Camenisch and Stadler (1997) Jan Camenisch and Markus Stadler. 1997.  Proof systems for general statements about discrete logarithms.  _Technical Report/ETH Zurich, Department of Computer Science_ 260 (1997).
  * Cao et al. (2021) Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong. 2021.  FLTrust: Byzantine-robust Federated Learning via Trust Bootstrapping. In _NDSS_.
  * Corrigan-Gibbs and Boneh (2017) Henry Corrigan-Gibbs and Dan Boneh. 2017.  Prio: Private, Robust, and Scalable Computation of Aggregate Statistics.. In _NSDI_. 259–282.
  * Damaskinos et al. (2018) Georgios Damaskinos, Rachid Guerraoui, Rhicheek Patra, Mahsa Taziki, et al. 2018\.  Asynchronous Byzantine machine learning (the case of SGD). In _ICML_. PMLR, 1145–1154.
  * Damgård and Jurik (2001) Ivan Damgård and Mads Jurik. 2001.  A Generalisation, a Simplification and Some Applications of Paillier’s Probabilistic Public-Key System. In _Public Key Cryptography_. 119–136.
  * Fan et al. (2022) Zhenan Fan, Huang Fang, Zirui Zhou, Jian Pei, Michael P. Friedlander, Changxin Liu, and Yong Zhang. 2022.  Improving Fairness for Data Valuation in Horizontal Federated Learning. In _ICDE_. 2440–2453.
  * Feldman (1987) Paul Feldman. 1987\.  A practical scheme for non-interactive verifiable secret sharing. In _FOCS_. IEEE, 427–438.
  * Fu et al. (2021) Fangcheng Fu, Yingxia Shao, Lele Yu, Jiawei Jiang, Huanran Xue, Yangyu Tao, and Bin Cui. 2021.  VF${}^{\mbox{2}}$Boost: Very Fast Vertical Federated Gradient Boosting for Cross-Enterprise Learning. In _SIGMOD_ , Guoliang Li, Zhanhuai Li, Stratos Idreos, and Divesh Srivastava (Eds.). ACM, 563–576.
  * Fu et al. (2022) Fangcheng Fu, Huanran Xue, Yong Cheng, Yangyu Tao, and Bin Cui. 2022.  BlindFL: Vertical Federated Machine Learning without Peeking into Your Data. In _SIGMOD_. 1316–1330.
  * Fu et al. (2023) Rui Fu, Yuncheng Wu, Quanqing Xu, and Meihui Zhang. 2023\.  FEAST: A Communication-efficient Federated Feature Selection Framework for Relational Data.  _Proc. ACM Manag. Data_ 1, 1 (2023), 107:1–107:28.
  * Fung et al. (2018) Clement Fung, Chris J. M. Yoon, and Ivan Beschastnikh. 2018\.  Mitigating Sybils in Federated Learning Poisoning.  _CoRR_ abs/1808.04866 (2018).
  * Gamal (1985) Taher El Gamal. 1985\.  A public key cryptosystem and a signature scheme based on discrete logarithms.  _IEEE Trans. Inf. Theory_ 31, 4 (1985), 469–472.
  * Gennaro et al. (2013) Rosario Gennaro, Craig Gentry, Bryan Parno, and Mariana Raykova. 2013.  Quadratic span programs and succinct NIZKs without PCPs. In _Advances in Cryptology–EUROCRYPT 2013: 32nd Annual International Conference on the Theory and Applications of Cryptographic Techniques, Athens, Greece, May 26-30, 2013. Proceedings 32_. Springer, 626–645.
  * Goldreich (2001) Oded Goldreich. 2001\.  _The Foundations of Cryptography - Volume 1: Basic Techniques._ Cambridge University Press.
  * Hayes and Ohrimenko (2018) Jamie Hayes and Olga Ohrimenko. 2018.  Contamination Attacks and Mitigation in Multi-Party Machine Learning. In _NeurIPS_. 6604–6616.
  * He et al. (2016) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016\.  Deep Residual Learning for Image Recognition. In _CVPR_. 770–778.
  * Kairouz et al. (2021) Peter Kairouz, Ziyu Liu, and Thomas Steinke. 2021.  The Distributed Discrete Gaussian Mechanism for Federated Learning with Secure Aggregation. In _ICML_. 5201–5212.
  * Keller (2020) Marcel Keller. 2020\.  MP-SPDZ: A Versatile Framework for Multi-Party Computation. In _CCS_. 1575–1590.
  * Li et al. (2019) Liping Li, Wei Xu, Tianyi Chen, Georgios B Giannakis, and Qing Ling. 2019.  RSA: Byzantine-robust stochastic aggregation methods for distributed learning from heterogeneous datasets. In _AAAI_ , Vol. 33. 1544–1551.
  * Li et al. (2022) Qinbin Li, Yiqun Diao, Quan Chen, and Bingsheng He. 2022\.  Federated Learning on Non-IID Data Silos: An Experimental Study. In _ICDE_. 965–978.
  * Li et al. (2020) Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. 2020\.  Federated learning: Challenges, methods, and future directions.  _IEEE Signal Processing Magazine_ 37, 3 (2020), 50–60.
  * Li et al. (2023) Xiling Li, Chenkai Weng, Yongxin Xu, Xiao Wang, and Jennie Rogers. 2023.  ZKSQL: Verifiable and Efficient Query Evaluation with Zero-Knowledge Proofs.  _Proc. VLDB Endow._ 16, 8 (2023), 1804–1816.
  * Liu et al. (2021a) Junxu Liu, Jian Lou, Li Xiong, Jinfei Liu, and Xiaofeng Meng. 2021a.  Projected Federated Averaging with Heterogeneous Differential Privacy.  _PVLDB_ 15, 4 (2021), 828–840.
  * Liu et al. (2018) Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg. 2018\.  Fine-Pruning: Defending Against Backdooring Attacks on Deep Neural Networks. In _RAID_. 273–294.
  * Liu et al. (2021b) Yejia Liu, Weiyuan Wu, Lampros Flokas, Jiannan Wang, and Eugene Wu. 2021b.  Enabling SQL-based Training Data Debugging for Federated Learning.  _Proc. VLDB Endow._ 15, 3 (2021), 388–400.
  * Lycklama et al. (2023) Hidde Lycklama, Lukas Burkhalter, Alexander Viand, Nicolas Küchler, and Anwar Hithnawi. 2023\.  Rofl: Robustness of secure federated learning. In _S &P_. IEEE, 453–476.
  * Ma et al. (2022) Xu Ma, Xiaoqian Sun, Yuduo Wu, Zheli Liu, Xiaofeng Chen, and Changyu Dong. 2022\.  Differentially Private Byzantine-Robust Federated Learning.  _IEEE Trans. Parallel Distributed Syst._ 33, 12 (2022), 3690–3701.
  * McMahan et al. (2017) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017\.  Communication-efficient learning of deep networks from decentralized data. In _AISTATS_. 1273–1282.
  * Melis et al. (2019) Luca Melis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov. 2019.  Exploiting Unintended Feature Leakage in Collaborative Learning. In _S &P_. 691–706.
  * Merkle (1978) Ralph C. Merkle. 1978\.  Secure Communications Over Insecure Channels.  _Commun. ACM_ 21, 4 (1978), 294–299.
  * Nasr et al. (2019) Milad Nasr, Reza Shokri, and Amir Houmansadr. 2019.  Comprehensive Privacy Analysis of Deep Learning: Passive and Active White-box Inference Attacks against Centralized and Federated Learning. In _S &P_. 739–753.
  * Nguyen et al. (2022) Thien Duc Nguyen, Phillip Rieger, Huili Chen, Hossein Yalame, Helen Möllering, Hossein Fereidooni, Samuel Marchal, Markus Miettinen, Azalia Mirhoseini, Shaza Zeitouni, Farinaz Koushanfar, Ahmad-Reza Sadeghi, and Thomas Schneider. 2022.  FLAME: Taming Backdoors in Federated Learning. In _USENIX Security Symposium_. 1415–1432.
  * Pan et al. (2020) Xudong Pan, Mi Zhang, Duocai Wu, Qifan Xiao, Shouling Ji, and Min Yang. 2020\.  Justinian’s GAAvernor: Robust Distributed Learning with Gradient Aggregation Agent. In _USENIX Security_. 1641–1658.
  * Parno et al. (2016) Bryan Parno, Jon Howell, Craig Gentry, and Mariana Raykova. 2016\.  Pinocchio: Nearly practical verifiable computation.  _Commun. ACM_ 59, 2 (2016), 103–112.
  * Pedersen (2001) Torben Pryds Pedersen. 2001\.  Non-interactive and information-theoretic secure verifiable secret sharing. In _CRYPTO_. Springer, 129–140.
  * Pippenger (1980) Nicholas Pippenger. 1980\.  On the evaluation of powers and monomials.  _SIAM J. Comput._ 9, 2 (1980), 230–250.
  * Pomerance and Goldwasser (1990) C. Pomerance and S. Goldwasser. 1990.  _Cryptology and Computational Number Theory_.  American Mathematical Society.  https://books.google.com.sg/books?id=yyfS7MKQhJUC
  * Rathee et al. (2023) Mayank Rathee, Conghao Shen, Sameer Wagh, and Raluca Ada Popa. 2023.  Elsa: Secure aggregation for federated learning with malicious actors. In _S &P_. IEEE, 1961–1979.
  * Roy Chowdhury et al. (2022) Amrita Roy Chowdhury, Chuan Guo, Somesh Jha, and Laurens van der Maaten. 2022.  EIFFeL: Ensuring Integrity for Federated Learning. In _CCS_. 2535–2549.
  * Shamir (1979) Adi Shamir. 1979\.  How to share a secret.  _Commun. ACM_ 22, 11 (1979), 612–613.
  * Shen and Sanghavi (2019) Yanyao Shen and Sujay Sanghavi. 2019.  Learning with Bad Training Data via Iterative Trimmed Loss Minimization. In _ICML_. 5739–5748.
  * Steinhardt et al. (2017) Jacob Steinhardt, Pang Wei Koh, and Percy Liang. 2017.  Certified Defenses for Data Poisoning Attacks. In _NeurIPS_. 3517–3529.
  * Sun et al. (2019) Ziteng Sun, Peter Kairouz, Ananda Theertha Suresh, and H Brendan McMahan. 2019.  Can you really backdoor federated learning?  _arXiv preprint arXiv:1911.07963_ (2019).
  * Wang et al. (2023a) Yansheng Wang, Yongxin Tong, Zimu Zhou, Ruisheng Zhang, Sinno Jialin Pan, Lixin Fan, and Qiang Yang. 2023a.  Distribution-Regularized Federated Learning on Non-IID Data. In _ICDE_. IEEE, 2113–2125.
  * Wang et al. (2023b) Yatong Wang, Yuncheng Wu, Xincheng Chen, Gang Feng, and Beng Chin Ooi. 2023b.  Incentive-Aware Decentralized Data Collaboration.  _Proc. ACM Manag. Data_ 1, 2 (2023), 158:1–158:27.
  * Wu et al. (2020) Yuncheng Wu, Shaofeng Cai, Xiaokui Xiao, Gang Chen, and Beng Chin Ooi. 2020.  Privacy Preserving Vertical Federated Learning for Tree-based Models.  _Proc. VLDB Endow._ 13, 11 (2020), 2090–2103.
  * Wu et al. (2023) Yuncheng Wu, Naili Xing, Gang Chen, Tien Tuan Anh Dinh, Zhaojing Luo, Beng Chin Ooi, Xiaokui Xiao, and Meihui Zhang. 2023\.  Falcon: A Privacy-Preserving and Interpretable Vertical Federated Learning System.  _Proc. VLDB Endow._ 16, 10 (2023), 2471–2484.
  * Xiang et al. (2023) Zihang Xiang, Tianhao Wang, Wanyu Lin, and Di Wang. 2023\.  Practical Differentially Private and Byzantine-resilient Federated Learning.  _Proc. ACM Manag. Data_ 1, 2 (2023), 119:1–119:26.
  * Xie et al. (2020) Chulin Xie, Keli Huang, Pin-Yu Chen, and Bo Li. 2020\.  DBA: Distributed Backdoor Attacks against Federated Learning. In _ICLR_.
  * Xie et al. (2019) Cong Xie, O Koyejo, and I Gupta. 2019.  Zeno++: robust asynchronous SGD with arbitrary number of Byzantine workers.  _arXiv preprint arXiv:1903.07020_ (2019).
  * Xie et al. (2023) Yuexiang Xie, Zhen Wang, Dawei Gao, Daoyuan Chen, Liuyi Yao, Weirui Kuang, Yaliang Li, Bolin Ding, and Jingren Zhou. 2023.  FederatedScope: A Flexible Federated Learning Platform for Heterogeneity.  _Proc. VLDB Endow._ 16, 5 (2023), 1059–1072.
  * Xu et al. (2022) Chang Xu, Yu Jia, Liehuang Zhu, Chuan Zhang, Guoxie Jin, and Kashif Sharif. 2022\.  TDFL: Truth Discovery Based Byzantine Robust Federated Learning.  _IEEE Trans. Parallel Distributed Syst._ 33, 12 (2022), 4835–4848.
  * Yang et al. (2021) Jiancheng Yang, Rui Shi, and Bingbing Ni. 2021.  MedMNIST Classification Decathlon: A Lightweight AutoML Benchmark for Medical Image Analysis. In _IEEE 18th International Symposium on Biomedical Imaging (ISBI)_. 191–195.
  * Yang et al. (2023) Jiancheng Yang, Rui Shi, Donglai Wei, Zequan Liu, Lin Zhao, Bilian Ke, Hanspeter Pfister, and Bingbing Ni. 2023\.  MedMNIST v2-A large-scale lightweight benchmark for 2D and 3D biomedical image classification.  _Scientific Data_ 10, 1 (2023), 41.
  * Yang et al. (2019) Qiang Yang, Yang Liu, Tianjian Chen, and Yongxin Tong. 2019\.  Federated Machine Learning: Concept and Applications.  _ACM TIST_ 10, 2 (2019), 12:1–12:19.
  * Yin et al. (2018) Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter L. Bartlett. 2018.  Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates. In _ICML_. 5636–5645.
  * Yin et al. (2019) Dong Yin, Yudong Chen, Kannan Ramchandran, and Peter L. Bartlett. 2019.  Defending Against Saddle Point Attack in Byzantine-Robust Distributed Learning. In _ICML_. 7074–7084.
  * Zeng et al. (2023) Zhihao Zeng, Yuntao Du, Ziquan Fang, Lu Chen, Shiliang Pu, Guodong Chen, Hui Wang, and Yunjun Gao. 2023\.  FLBooster: A Unified and Efficient Platform for Federated Learning Acceleration. In _ICDE_. IEEE, 3140–3153.
  * Zheng et al. (2023) Yifeng Zheng, Shangqi Lai, Yi Liu, Xingliang Yuan, Xun Yi, and Cong Wang. 2023\.  Aggregation Service for Federated Learning: An Efficient, Secure, and More Resilient Realization.  _IEEE Trans. Dependable Secur. Comput._ 20, 2 (2023), 988–1001.
  * Zhu et al. (2023) Yizheng Zhu, Yuncheng Wu, Zhaojing Luo, Beng Chin Ooi, and Xiaokui Xiao. 2023.  Robust and Secure Federated Learning with Low-Cost Zero-Knowledge Proof.  https://www.comp.nus.edu.sg/~ooibc/risefl-20230901.pdf