0.85eiffel-tower.png: Ensuring Integrity For Federated Learning

Amrita Roy ChowdhuryWork done during internship at Meta AI
UW Madison
Chuan Guo
Meta AI
Somesh Jha
Employed part-time at Meta during this work
UW Madison
Laurens van der Maaten
Meta AI

Federated learning (FL) enables clients to collaborate with a server to train a machine learning model. To ensure privacy, the server performs secure aggregation of updates from the clients.
Unfortunately, this prevents verification of the well-formedness (integrity) of the updates  as the updates are masked. Consequently, malformed updates  designed to poison the model can be injected without detection. In this paper, we formalize the problem of ensuring both update privacy and integrity in FL and present a new system, , that enables secure aggregation of verified updates.  is a general framework that can  enforce arbitrary integrity checks and remove  malformed updates from the aggregate, without violating privacy. Our empirical evaluation demonstrates the practicality of . For instance, with $100$ clients and $10\%$ poisoning,  can train an  classification model to the same accuracy as that of a non-poisoned federated learner in just $2.4$s per iteration.

<concept_desc>Security and privacy Cryptography</concept_desc>
<concept_desc>Security and privacy Privacy-preserving protocols</concept_desc>

[500]Security and privacy Cryptography
[500]Security and privacy Privacy-preserving protocols

§ PROBLEM OVERVIEW

consists of multiple clients $\Cl$ and a server $\Ser$ with a public validation predicate $\Vl(\cdot)$ that defines the integrity check. A client $\Cl_i$ needs to provide a proof $\pi_i$ for $\Vl(u_i)=1$ (Round 1).

For checking the proof $\pi_i$, all other clients $\Cl_{\setminus i}$ act as the verifiers under the supervision of $\Ser$. $C_i$ splits its update $u_i$ and proof $\pi_i$ using Shamir's  scheme with threshold $m+1$   and shares it with $\Cl_{\setminus i}$ (Round 2).

Conceptually, any set of $m+1$ clients in $\Cl_{\setminus i}$ can emulate the SNIP verification protocol. The server uses this redundancy to robustly verify the proof (Round 3).

The clients only aggregate the shares of well-formed updates and the resulting aggregate is revealed to the server (Round 4).

High-level overview of . See Sec. <ref> for key ideas, and Sec. <ref> for a detailed description of the system.

In this section, we introduce the problem setting, followed by its threat analysis and an overview of our solution.

§.§ Problem Setting

In FL, multiple parties with distributed data jointly train a global model, $\mathcal{M}$,  without explicitly disclosing their data to each other. FL has two types of actors:

* Clients. There are $n$ clients where each client, $\Cl_i, i \in [n]$, owns a private dataset, $D_i$. The raw data is never shared, instead, every client computes a local update for $\mathcal{M}$, such as the average gradient, over the private dataset $D_i$.

* Server. There is a single untrusted server, $\Ser$, who coordinates the updates from different clients to train $\mathcal{M}$.

A single training iteration in FL consists of the following steps:

* Broadcast. The server broadcasts the current parameters of the model $\mathcal{M}$ to all the clients.

* Local computation. Each client $\Cl_i$ locally computes an update, $u_i$, on its dataset $D_i$.

* Aggregation. The server $\Ser$ collects the client updates and aggregates them, $\Ul = \sum_{i\in [n]} u_i$.

* Global model update. The server $\Ser$ updates the global model $\mathcal{M}$ based on the aggregated update $\Ul$.

In settings where there is a large number of clients, it is typical to subsample a small subset of clients to participate in a given iteration. We assume $n$ to denote the number of clients that participate in each iteration and $\Cl$ denotes the subset of these $n$ clients, which the server announces at the beginning of the iteration.

§.§ Security Goals

* Input Privacy (Client's Goal). The first goal is to ensure privacy for all honest clients. That is, no party should be able learn anything about the raw input (update) $u_i$ of an honest client 0.9$C_i$, other than what can be learned from the final aggregate 0.9$\Ul$.

* Input Integrity (Server's Goal). The server $\Ser$ is motivated to ensure that the individual updates from each client are well-formed. Specifically, the server has a public validation predicate, 0.9$\textsf{Valid}(\cdot)$, that defines a syntax for the inputs (updates). An input (update) $u$ is considered valid and, hence, passes the integrity check iff 0.9$\textsf{Valid}(u)=1$. For instance, any per-client update check, such as  Zeno++ [93], can be a good candidate for 0.9$\Vl(\cdot)$ (we evaluate four state-of-the-art validation predicates in Sec. <ref>).

We assume that the honest clients, denoted by 0.9$\Cl_H$: $(1)$ follow the protocol correctly, and $(2)$ have well-formed inputs. We require the second condition because, in case the input of an honest client does not pass the integrity check (which can be verified locally since 0.9$\Vl(\cdot)$ is public), the client has no incentive to participate in the training iteration.

§.§ Threat Model

We consider a malicious adversary threat model:

* Malicious Server. We consider a malicious server that can deviate from the protocol arbitrarily with the aim of recovering the raw updates $u_i$ for $i \in [n]$ (see Remark 1 later for more details).

* Malicious Clients.   We also consider a set of $m$ malicious clients, $\Cl_M$. Malicious clients can arbitrarily deviate from the protocol with the goals of: (1) sending malformed inputs to the server and thus, compromising the final aggregate; (2) failing the integrity check of an honest client that submits well-formed updates;  (3) violating the privacy of an honest client, potentially in collusion with the server.

§.§ Solution Overview

Prior work has mostly focused on ensuring input privacy via secure aggregation, i.e., securely computing the aggregate 0.9$\Ul=\sum_{\Cl_i\in\Cl}u_i$.
Motivated by the above problem setting and threat analysis, we introduce a new type of FL protocol, called secure aggregation with verified inputs (), that ensures both input privacy and integrity. The goal of a  protocol is to securely aggregate only well-informed inputs.
In order to demonstrate the feasibility of , we propose : a system that instantiates a  protocol for any 0.9$\Vl(\cdot)$ that can be expressed as an arithmetic circuit with public parameters (Fig. <ref>).  ensures input privacy by using Shamir's threshold secret sharing scheme [75] (Sec. <ref>).
Input integrity is guaranteed via SNIP and verifiable secret shares (VSS) which validates the correctness of the secret shares (Sec. <ref>).
The key ideas are:

* SNIP requires multiple honest verifiers.  enables this in a single-server setting by having the clients act as the verifiers for each other under the supervision of the server (in Fig. <ref>, verifiers are marked by medal.png).

*  extends SNIP to the malicious threat model to account for the malicious clients (verifiers). Our key observation is that using a threshold secret sharing scheme creates multiple subsets of clients that can emulate the SNIP verification protocol. The server uses this redundancy to robustly verify the proofs and aggregate updates with verified proofs only (Fig. <ref> and <ref>).

§ SECURE AGGREGATION WITH VERIFIED INPUTS

Below, we provide the formal definition of a secure aggregation with verified inputs () protocol.
That is, given a
party identifier c ∈ C, a round index i, a transcript T of all
messages sent and received so far by all parties in C, joint
randomness rC for the corrupt parties’ execution, and access
to random oracle O, MC(c, i, T, rC) outputs the message for
party c in round i (possibly making several queries to O along
the way). Additionally, given a round index i, a transcript T
of all messages sent and received so far by all parties in C,
and joint randomness rC for the corrupt parties’ execution,
MC(i, T, rC) outputs the set of parties Ui that abort due to
failure in that round (again, possibly making several queries
to O along the way). 9 We note that MC is thus effectively
choosing the inputs for all corrupt users.

Given a public validation predicate 0.9$\Vl(\cdot)$ and security parameter 0.9$\kappa$, a protocol 0.9$\Pi(u_1,\cdots,u_n)$ is a secure aggregation with verified inputs () protocol if:

* Integrity. The output of the protocol, $\textsf{out}$, returns the aggregate of a subset of clients, 0.9$\Cl_\Vl$, such that all clients in 0.9$\Cl_\Vl$ have  well-formed inputs.

\begin{gather*} \mathrm{Pr}\big[\textsf{out}=\Ul_{\Vl}\big] \geq 1 -\mathrm{negl}(\kappa) \mbox{ where }\Ul_\Vl=\sum_{\Cl_i\in \Cl_\Vl}u_i \\ \mbox{for all } \Cl_i \in \Cl_\Vl \mbox{ we have } \Vl(u_i)=1 \\ \Cl_H\subseteq\Cl_\Vl\subseteq\Cl.   \numberthis\label{eq:SAVI:integrity}\vspace{-0.5cm}\end{gather*}

* Privacy. For a set of malicious clients 0.9$\Cl_M$ and a malicious server 0.9$\Ser$, there exists a probabilistic polynomial-time (P.P.T.) simulator 0.9$\mathrm{Sim}(\cdot)$ such that:
\begin{gather*}\vspace{-0.3cm}\mathrm{Real}_{\Pi}\big(
\{u_{\Cl_H}\}, \Omega_{\Cl_M\cup\Ser}\big)\equiv_C\mathrm{Sim}\big(\Ul_H,\Cl_H,\Omega_{\Cl_M\cup \Ser}\big)\\\mbox{where }\Ul_H=\sum_{\Cl_i\in \Cl_H}u_i.\numberthis\label{eq:SAVI:privacy}\vspace{-0.5cm}\end{gather*}
0.9$\{u_{\Cl_H}\}$ denotes the input of all the honest clients, 0.9$\mathrm{Real}_\Pi$ denotes a random variable representing the joint view of all the parties in $\Pi$'s execution,  0.9$\Omega_{\Cl_M\cup\Ser}$ indicates a polynomial-time algorithm implementing
the “next-message” function of the parties in 0.9$\Cl_M\cup\Ser$ (see App. <ref>),
and 0.9$\equiv_C$ denotes computational indistinguishability.
From Def. <ref>, the output of a  protocol is of the form:

\begin{gather}\Ul_{valid}=\underbrace{\Ul_H}_{\substack{\text{well-formed updates of}\\\textit{all }\text{honest clients }\Cl_H}}+\underbrace{\sum_{\Cl_i\in \Cl_\Vl\setminus\Cl_H}u_i.}_{\substack{\text{well-formed updates of}\\\text{some malicious clients}}}\label{eq:SAVI:U}\end{gather}

The clients in 0.9$\Cl_\Vl\setminus \Cl_H$ are clients who have submitted well-formed inputs but can behave maliciously otherwise (e.g., by violating input privacy/integrity of honest clients).

The privacy constraint of the  protocol means that a simulator  can generate the views of all parties with just access to the list of the honest clients 0.9$\Cl_H$ and their aggregate 0.9$\Ul_H$. Note that  takes 0.9$\Ul_H$ as an  input instead of the protocol output 0.9$\Ul_\Vl$. This is because the clients in 0.9$\Cl_\Vl\setminus\Cl_H$, by virtue of being malicious, can behave arbitrarily and announce their updates to reveal 0.9$\Ul_H=\Ul_\Vl-\sum_{\Cl_i\in \Cl_\Vl\setminus\Cl_H} u_i$.
Thus,  ensures that nothing can be learned about the input $u_i$ of an honest client 0.9$\Cl_i \in \Cl_H$ except:

* that $u_i$ is well-formed, i.e., 0.9$\Vl(u_i)=1$,

* anything that can be learned from the aggregate $\Ul_H$.
[sharp corners, breakable]
Remark 1. Note that we consider a malicious server only for input privacy and the reason is as follows. For input integrity, a malicious server can do the following:

* Case 1.  Mark the input of an honest client as invalid and not include it in the final aggregate.

* Case 2. Mark the (invalid) input of a malicious client as valid.
prevents Case 1 from happening since, from Def. <ref>,  is guaranteed to output the aggregate of all honest clients (Lemma <ref>). If we consider a malicious server even for data integrity, the only thing that can happen is Case 2. However, the server’s primary goal is to ensure that each input is well-formed. Hence, Case 2, i.e., marking the (invalid) input of a malicious client as valid, is at odds with the server’s goal.  Therefore, it is unnecessary to protect against this behavior in our setting and we consider the server to be honest for the purposes of input integrity.

[sharp corners]
Remark 2. The integrity constraint of  requires the protocol to detect and remove all malformed inputs before computing the final aggregate. Note that there is a fundamental difference between the design choice of just detection of a malformed input versus detection and removal.
In the former, the server can only abort the current round even when just a single malformed input is detected.
This allows an adversary to stage a denial-of-service attack that renders the server incapable of training the model.
When the protocol can both detect and remove malformed inputs, such denial-of-service attacks are prevented as the server can train the model using just the valid updates.

§ E SYSTEM DESCRIPTION

This section introduces : the system we propose to perform secure aggregation of verified inputs.

§.§ Cryptographic Building Blocks

Arithmetic Circuit. An arithmetic circuit, 0.9$\mathcal{C}: \Fl^k\mapsto \Fl$, represents a computation over a finite field 0.9$\Fl$.
Conceptually, it is similar to a Boolean circuit but it uses finite field addition, multiplication and multiplication-by-constant instead of , , and  gates.

Shamir's $t$-out-of-$n$ Secret Sharing Scheme [75] allows distributing a secret $s$ among $n$ parties such that: (1) the complete secret can be reconstructed from any combination of $t$ shares; (2) any set of
$t - 1$ or fewer shares reveals no information about $s$ where $t$ is the threshold of the secret sharing scheme. The scheme is parameterized over a finite field $\Fl$ and consists of  two algorithms:

* 0.9$\{(i,s_i)\}_{i\in P}\randarrow \textsf{SS.share}(s,P,t)$. Given a secret $s  \in \Fl$, a set of $n$ unique field elements 0.9$P \in\Fl^n$ and a threshold $t$ with $t \leq n$, this algorithm constructs $n$ shares. The algorithm chooses a random polynomial 0.9$p\in \Fl[X]$ such that 0.9$p(0)=s$ and generates the shares as 0.9$(i,p(i)), i \in P$.

* 0.9$s\leftarrow \textsf{SS.recon}(\{(i,s_i)_{i\in Q}\})$. Given the  shares corresponding to a subset 0.9$Q\subseteq P, |Q|\geq t$, the reconstruction algorithm recovers the secret $s$.

Shamir's secret sharing scheme is linear, which means a party can locally perform: $(1)$ addition of two shares, $(2)$ addition of a constant, and $(3)$ multiplication by a constant.

Shamir's secret sharing scheme is closely related to Reed-Solomon error correcting codes [55], which is a group of polynomial-based error correcting codes. The share generation is similar to (non-systemic) message encoding in these codes which can successfully recover a message even in the presence of errors and erasures (message dropouts). Consequently, we can leverage Reed-Solomon decoding for robust reconstruction of Shamir's secret shares:

* 0.9$s\leftarrow\textsf{SS.robustRecon}(\{(i,s_i)\}_{i\in Q})$. Shamir's secret sharing scheme results in a 0.9$[n,t,n-t+1]$ Reed-Solomon code that can tolerate up to 0.9$q$ errors and 0.9$e$ erasures (message dropouts) such that 0.9$2q+e< n-t+1$. Given any subset of $n\!-\!e$ shares 0.9$Q \subseteq P, |Q|\geq n-e$ with up to 0.9$q$ errors, any standard Reed Solomon decoding algorithm [13] can robustly reconstruct 0.9$s$.  uses Gao's decoding algorithm [37].
Verifiable secret sharing scheme is a related concept where the scheme has an additional property of verifiability. Given a share of the secret, a party must be able to check whether it is indeed a valid share. If a share is valid, then there exists a unique secret which will be the output of the reconstruction algorithm when run on any $t$ distinct valid shares. Formally:

* 0.9$1/0\leftarrow\textsf{SS.verify}((i,v),\Psi))$.  The verification algorithm inputs a share and a check string $\Psi_s$ such that
\begin{gather*}\vspace{-0.2cm}
\small\forall \thinspace V \subset \Fl\times\Fl \mbox{ where } |V|=t, \exists s  \in \Fl \mbox{ s.t. }\\ \hspace{-0.4cm}\small (\forall (i,v) \in V,\textsf{SS.verify}((i,v),\Psi_s)=1)  \implies \textsf{SS.recon}(V)=s \vspace{-0.3cm}\end{gather*}
The share construction algorithm is augmented to output the check string as 0.9$(\{(i,s_i)_{i \in P}\},\Psi_s)\larrow \textsf{SS.share}(s,P,t)$.

For , we use the non-interactive verification scheme by Feldman [35] (details in App. <ref>).

Key Agreement Protocol.
A key agreement protocol  consists of a tuple of the following three algorithms:

* 0.9$(pp)\randarrow \textsf{KA.param}(1^\kappa)$. The parameter generation algorithm samples a set of public parameters $pp$ with security parameter $\kappa$.

* 0.9$(pk,sk)\randarrow\textsf{KA.gen}(pp)$. The key generation algorithm samples a public/secret key pair from the public parameters.

* 0.9$sk_{ij}\leftarrow \textsf{KA.agree}(pk_i,sk_j)$. The key agreement protocol receives a public key $pk_i$ and a secret key $sk_j$ as input and generates  the shared key $sk_{ij}$.

Authenticated Encryption provides confidentiality and integrity guarantees for messages exchanged between
two parties. It consists of a tuple of three algorithms as follows:

* 0.9$k\randarrow \textsf{AE.gen}(1^\kappa)$.  The key generation algorithm that
outputs a private key   $k$ where $\kappa$ is the security parameter.

* 0.9$\overline{x}\randarrow \textsf{AE.enc}(k,x)$. The encryption algorithm takes as input a key $k$ and a message $x$, and outputs a ciphertext $\overline{x}$.

* 0.9$x\leftarrow\textsf{AE.dec}(k,\overline{x})$. The decryption algorithm takes as
input a ciphertext and a key and outputs either the original plaintext, or a special error symbol $\bot$ on failure.

Secret-shared Non-interactive Proofs.

Prover sends secret shares of its input  and the SNIP proof to multiple verifiers.

The verifiers gossip among themselves and check the proof.

The check passes successfully if all verifiers are honest.

High-level overview of a secret-shared non-interactive proof (SNIP; [28]).

The secret-shared non-interactive proof (SNIP) [28] is an information-theoretic zero-knowl- edge proof for distributed data (Fig. <ref>). SNIP is designed for a multi-verifier setting where the private data is distributed or secret-shared among the verifiers. Specifically, SNIP relies on an additive secret sharing scheme over a field $\Fl$ as described below.  A secret $s \in \Fl$ is split into $k$ random shares $([s]_1,\cdots,[s]_k)$ such that $\sum_{i=1}^k[s]_i=s$. A subset of up to $k-1$ shares reveals no information about the secret $s$. The additive secret-sharing scheme is linear as well.

SNIP Setting. SNIP considers 0.9$k\geq 2$ verifiers 0.9$\{\Ver_i\}, i \in [k]$ and a prover 0.9$\Pro$ with a private vector 0.9$x\in\Fl^d$. All parties also hold a public arithmetic circuit representing a
validation predicate 0.9$\Vl: \Fl^d\mapsto \Fl$
. Let 0.9$\Ml$ be the number of multiplication gates in 0.9$\Vl(\cdot)$.  0.9$\Fl$ is chosen such that 0.9$2\Ml \ll |\Fl|$. The prover 0.9$\Pro$ splits 0.9$x$ into 0.9$k$ shares 0.9$\{[x_1],\cdots, [x_k]\}$. Next, they generate $k$ proof strings 0.9$[\pi]_i, i \in [k]$ based on 0.9$\Vl(\cdot)$ and shares 0.9$( [x_i], [\pi]_i)$ with every verifier 0.9$\Ver_i$ (Fig. <ref>).

The prover's goal is to convince the verifiers that, indeed, 0.9$\Vl(x) =
1$. The prover does so via proof strings 0.9$[\pi]_i, i\in [k]$, that do not reveal anything else about $x$. After
receiving the proof, the verifiers gossip with each other to conclude either that 0.9$\Vl(x) = 1$
(the verifiers “0.9$\textsf{Accept } x$") or not (“0.9$\textsf{Reject } x$”, Figs. <ref> and <ref>). Formally, SNIP satisfies the following security properties:
* Completeness. If all parties are honest and 0.9$\Vl(x)=1$, then the verifiers will
accept $x$.
\begin{gather*}\vspace{-0.4cm}\small\forall x \in \Fl \mbox{ s.t. } \Vl(x)=1: \mathrm{ Pr}_{\pi}[\textsf{Accept } x]=1. \label{eq:SNIP:complete}\vspace{-0.5cm}\end{gather*}

* Soundness. If all verifiers are honest, and if 0.9$\Vl(x)=0$,
then for all malicious provers, the verifiers will reject $x$ with
overwhelming probability.

\begin{gather*}\vspace{-0.4cm}\small\forall x \in \Fl \mbox{ s.t. } \Vl(x)=0:  \thinspace\thinspace
\mathrm{ Pr}_{\pi
}\big[\textsf{Reject } x\big] \geq 1- \nicefrac{(2M-2)}{|\Fl|}.\label{eq:SNIP:sound}\vspace{-0.4cm}\end{gather*}

* Zero knowledge. If the prover and at least one verifier are
honest, then the verifiers learn nothing about $x$, except
that 0.9$\Vl(x) = 1$. Formally, when 0.9$\Vl(x)=1$, there exists a simulator 0.9$\mathrm{Sim}(\cdot)$ that can simulate the view of
the protocol execution for every proper subset of verifiers:

\begin{gather*}\vspace{-0.3cm}\small\forall x \mbox{ s.t. } \Vl(x)=1\mbox{ and } \forall \bar{\Ver}\subset \bigcup_{i=1}^k\Ver_i \mbox{ we have}\\ \vspace{-0.5cm}\small  \mathrm{ Sim}_\pi(\Vl(\cdot),\{([x]_i,[\pi]_i)\}_{i\in \bar{\Ver}})\equiv \mathrm{View}_{\pi,\bar{\Ver}}(\Vl(\cdot),x).%\numberthis\label{eq:SNIP:zeroknowledge}
\vspace{-0.2cm}
\end{gather*}

Thus, SNIP allows the verifiers  to collaboratively check – without ever accessing the prover’s private data in the clear – that the prover's
submission is, indeed, well-formed.
SNIP works in two stages as follows:

$(1)$ Generation of Proof. For generating the proof, the prover $\Pro$ first evaluates the
circuit 0.9$\Vl(\cdot)$ on its input $x$ to obtain the value of every wire in the arithmetic circuit corresponding to the computation of 0.9$\Vl(x)$.
Using these wire values, $\Pro$  constructs
three polynomials 0.9$f$, 0.9$g$, and 0.9$h$ of the lowest possible degrees such that 0.9$h=f\cdot g$ and 0.9$f(j),g(j)$ and 0.9$h(j), j \in \big[\Ml\big]$ encode the values of the two input wires and one output wire of the $j$-th multiplication gate, respectively.
$\Pro$ also samples a single set of Beaver's multiplication triples [7]: 0.9$(a,b,c)\in \Fl^3$ such that 0.9$a\cdot b = c \in \Fl$. Finally, it generates the shares of the proof, 0.9$[\pi]_i =\big( [h]_i, ([a]_i,[b]_i,[c]_i)\big)$, which consists of:

* shares of the coefficients of the polynomial $h$, denoted by $[h]_i$,
* shares of the  Beaver's triples, 0.9$([a]_i,[b]_i,[c]_i)\in \Fl^3$. The prover then sends the respective shares of the input and the proof 0.9 $( [x]_i, [\pi]_{i})$ to each of the verifiers $\Ver_i$.

$(2)$ Verification of Proof. To verify that 0.9$\Vl(x)=1$ and hence, accept the input $x$, the verifiers need to check two things:

* check that the value of final output wire of the computation, 0.9$\Vl(x)$, denoted by $w^{out}$ is indeed $1$, and
* check the consistency of $\Pro$'s computation of 0.9$\Vl(x)$.
To this end, each verifier 0.9$\Ver_i$ locally constructs the shares of every wire in 0.9$\Vl(x)$
via affine operations
on the shares of the private input 0.9$[x]_i$ and 0.9$[h]_i$. Next, 0.9$\Ver_i$ broadcasts a summary 0.9$[\sigma]_i=([w^{out}]_i,[\lambda]_i)$, where 0.9$[w^{out}]_i$ is 0.9$\Ver_i$'s share of the output wire of the circuit and 0.9$[\lambda]_i$ is a share of a random digest that the verifier computes from the shares of the other wire values and the proof  string $[\pi]_i$. Using these  summaries, the verifiers check the proof as follows:

* For checking the output wire, the verifiers can reconstruct its exact value from all the broadcasted shares 0.9$w^{out}=\sum_{i=1}^k [w^{out}]_i$ and check whether 0.9$w^{out}=1$. This would imply that  0.9$\Vl(x)=1$.
* The circuit consistency check is more involved and is performed using the random digest 0.9$\lambda$.
First, 0.9$\Ver_i$ locally computes the shares of the polynomials $f$ and $g$ (denoted as 0.9$[f]_i$ and 0.9$[g]_i$).
To verify the  consistency of the circuit evaluation, the verifiers need to check that the shares  0.9$[h]_i$ sent by the prover $\Pro$ are of the correct polynomial, i.e., confirm that 0.9$f\cdot g =h$. For this, SNIP uses the  Schwartz-Zippel polynomial identity test [74, 98]. Specifically, verifiers reconstruct 0.9$\lambda = \sum_{1=1}^k[\lambda]_i$ from the broadcasted shares and test whether 0.9$\lambda=r(f(r) \cdot g(r)-h(r))=0$ on a randomly selected $r\in \Fl$.  The computation of the share of the random digest 0.9$[\lambda]_i$
uses the shares of Beaver's triples 0.9$([a]_i,[b]_i,[c]_i)$.

A more detailed description of the SNIP protocol is in App. <ref>.

§.§ System Building Blocks

Public Validation Predicate.  requires a public validation predicate 0.9$\Vl(\cdot)$, expressed by an arithmetic circuit, that captures the notion of update well-formedness. In principle, any per-client update robustness test [84, 83, 93, 54, 31, 5, 76] from the ML literature can be a suitable candidate. The parameters of the test (for instance, threshold 0.9$\rho$ for a norm bound check 0.9$\Vl(u) = \mathbb{I}[ \lVert u\rVert_2 < \rho$) can be computed from a clean, public dataset $\DP$ that is available to the server $\Ser$. This assumption of a clean, public dataset is common in both ML [93, 24, 45] as well as privacy literature [57, 6, 8]. The dataset can be small and obtained by manual labeling [60].

Public Bulletin Board.  assumes the availability of a public bulletin board $\Bl$ that is accessible to all the parties, similar to prior work [72, 17, 45]. In practice, the bulletin $\Bl$ can be implemented as an append-only log hosted at a public web address where every message and its sender is visible.  Every party in  has read/write access to it. We use the bulletin $\Bl$ as a tool for broadcasting [21, 30].

§.§  Design Goals

In terms of the design,  should:

* provide  flexibility in the choice of integrity checks.

* be compatible with the existing FL infrastructure in deployment.

* be efficient in performance.

§.§  Design Goals.

The design goals of  are:

*  should ensure input privacy for all honest clients.

*  should support integrity checks using an arbitrary validation predicate 0.9$\Vl(\cdot)$.

*  should ensure input integrity by detecting and removing malformed inputs from the final aggregate.

§.§  Workflow

The  goal of  is to instantiate a secure aggregation with verified inputs () protocol in FL. For a given public validation predicate $\Vl(\cdot)$,  checks the integrity of every client update using SNIP and outputs the aggregate of only well-formed updates, i.e., 0.9$\Vl(u)=1$.

To implement SNIP for our setting,  introduces two main ideas:
[sharp corners, breakable,left=8pt,right=8pt,bottom=0.8pt]

Main Ideas.

* In , the clients act as the verifiers for each other. Specifically, for every client 0.9$\Cl_i, i \in \Cl$, all of the other $n\!-\!1$ clients, 0.9$\Cl_{\setminus i}$, and the server 0.9$\Ser$ jointly acts as the verifiers. This is different from Prio [28] (the original SNIP deployment setting) that rely on multiple honest servers to perform verification.

* In , verification can be performed even with malicious verifiers. This is essential in our setting since we have $m$ malicious clients (i.e., verifiers).[
The server works honestly towards verifying the integrity (its primary goal) but could behave maliciously  (possibly colluding with other malicious clients) to violate the privacy of the honest clients (see Sec. <ref>).] For this,  uses Shamir's $t$-out-of-$n$ threshold scheme for the entire protocol. This allows any cohort of $t$ verifiers to reconstruct a secret and, hence, instantiate a SNIP protocol. If $t\!<\!n$, we have multiple such instantiations and can use the redundancy to perform the integrity check even with some of the verifiers being malicious.

The full protocol is presented in Fig. <ref>. The protocol involves a setup phase followed by four rounds.

Setup Phase. In the setup phase, all parties are initialized with the system-wide parameters, namely the security parameter $\kappa$, the number of clients $n$ out of which only 0.9$m < \lfloor\frac{n-1}{3} \rfloor$ can be malicious, public parameters for the key agreement protocol 0.9$pp\randarrow \textsf{KA.param}(\kappa)$, and a field 0.9$\Fl$ where 0.9$|\Fl|\geq 2^{\kappa}$.
works in a synchronous protocol between the server $\Ser$ and the $n$ clients in four rounds. To prevent the server from simulating an arbitrary number
of clients, the clients register themselves with a specific user ID on the public bulletin board $\Bl$ and are authenticated with the help of standard public key infrastructure (PKI).
The bulletin board $\Bl$ allows parties to register IDs only for themselves, preventing impersonation. More concretely, the PKI enables the clients to register identities (public keys), and sign messages using their identity (associated secret keys),
such that others can verify this signature, but cannot
impersonate them [46]. We omit this detail for the ease of exposition. For notational simplicity, we assume that each client $\Cl_i$ is assigned a unique logical ID in the form of an integer $i$ in $[n]$. Each client holds as input a $d$-dimensional vector $u_i\in \Fl^d$ representing its local update. All clients have a private, authenticated communication channel with the server $\Ser$.
Additionally, every party (clients and server) has read and write access to the public bulletin $\Bl$ via authenticated channels.
For every client $\Cl_i$, the server $\Ser$ maintains a list, 0.9$\textsf{Flag}[i]$, of all clients that have flagged $\Cl_i$ as malicious. All 0.9$\textsf{Flag}[i]$ lists are initialized to be empty lists.

Round 1 (Announcing Public Information). In the first round, all the parties announce their public information relevant to the protocol on the public bulletin $\Bl$. Specifically, each client $\Cl_i$ generates its key pair  0.9$({pk}_i,{sk}_i)\randarrow\textsf{KA.gen}(pp)$ and advertises the public key $pk_i$ on the public bulletin $\Bl$. The server $\Ser$ publishes the validation predicate 0.9$\Vl(\cdot)$ on $\Bl$.

Round 2 (Generate and Distribute Proofs). Every client generates shares of its private update $u_i$ and the proof $\pi_i$, and distributes these shares to the other clients 0.9$\Cl_{\setminus i}$.
First, client 0.9$\Cl_i$ generates a common pairwise encryption key 0.9$sk_{ij}$ for every other client 0.9$\Cl_j\in \Cl_{\setminus i}$ using the key agreement protocol, 0.9$sk_{ij}\larrow \textsf{KA.agree}(sk_i,pk_j)$. Next, the client generates the secret shares of its private update 0.9$\{ (1,u_{i1}), \cdots, (n,u_{in}),\Psi_{u_i}\}\randarrow \textsf{SS.share}(u,[n],m+1)$. The sharing of $u_i$ is performed dimension-wise; we abuse notations and denote the $j$-th such share by 0.9$(j,u_{ij}), j \in [n]$. Note that the client $\Cl_i$ generates a share $(i,u_{ii})$ for itself as well which will be used later in the protocol.
Next, the client $\Cl_i$ generates the proof  for the computation 0.9$\Vl(u_i)\!=\!1$. Specifically, it computes the polynomials $f_i, g_i$, and $h_i=f_i\cdot g_i$ and samples a set of Beaver's multiplication triples 0.9$(a_i,b_i,c_i)\in \Fl^3, a_i\cdot b_i=c_i \in \Fl$. Since the other clients will verify the proof,  client $\Cl_i$ then splits the proof to generate shares 0.9$\pi_{ij}=\big( (j,h_{ij}),$ 0.9 $(j,a_{ij}),(j,b_{ij}),(j,c_{ij}) \big )$ for every other client 0.9$\Cl_j \in \Cl_{\setminus i}$. The shares themselves are generated via 0.9$\{(1,h_{i1}),\cdots,(i-1,h_{i(i-1)}),(i+1,h_{i(i+1)}),$  0.9$\cdots, (n,h_{in}),\Psi_{h_i}\}$0.8$\randarrow$0.9$\textsf{SS.share}(h_i, [n] \setminus i, m+1)$, and so on. Finally, the client encrypts the proof strings (shares of the update $u_i$ and the proof $\pi_i$) using the corresponding pairwise secret key, 0.9$\overline{(j,u_{ij})||(j,\pi_{ij})}$
0.8$\randarrow$0.9$\textsf{AE.enc}\big(sk_{ij},(j,u_{ij})||(j,\pi_{ij})\big)$, and publishes the encrypted proof strings on the public bulletin $\Bl$. The client also publishes the check strings 0.9$\Psi_{u_i}$ and 0.9$\Psi_{\pi_i}=(\Psi_{h_i},\Psi_{a_i},\Psi_{b_i},\Psi_{c_i})$ for verifying the validity of the shares of $u_i$ and $\pi_i$, respectively.

Round 3 (Verify Proof). In this round, every client $\Cl_i$ partakes in the verification of the proofs $\pi_j$ of all other clients $\Cl_j\in \Cl_{\setminus i}$, under the supervision of the server $\Ser$. The goal of the server is to identify the malicious clients, $\Cl_M$. To this end, the server maintains a (partial) list, $\CA$ (initialized as an empty list), of clients it has so far identified as malicious.
The proof-verification round consists of three phases as follows:

$(i)$ Verifying the validity of the secret shares.
First, every client $\Cl_i$ downloads and decrypts their shares from the bulletin 0.9$\Bl$, 0.85$(i,u_{ji})||(i,\pi_{ji})$ 0.9$\larrow\textsf{AE.dec}\big(sk_{ij},\overline{(i,u_{ji})||(i,\pi_{ji})}\big), \forall \Cl_j \in \Cl_{\setminus i}$. Additionally, $\Cl_i$ downloads the check strings 0.9$(\Psi_{{u}_i},\Psi_{{\pi}_i})$ and verifies the validity of the shares. If the shares from any client $\Cl_j$:

* fail to be decrypted, i.e., 0.9$\textsf{AE.dec}(\cdot)$ outputs $\bot$, OR

* fail to pass the verification, i.e., 0.9$\textsf{SS.verify}(\cdot)$ returns $0$,

0.9$\Cl_i$ flags 0.9$\Cl_j$ on the bulletin 0.9$\Bl$.
Every time a client 0.9$\Cl_i$ flags another client 0.9$\Cl_j$, the server updates the corresponding list 0.8$\textsf{Flag}[j]\hspace{-0.1cm}\leftarrow\textsf{Flag}[j]\cup \Cl_i$. If 0.9$|\textsf{Flag}[j]|\geq m+1$, the server $\Ser$ marks $\Cl_j$ as malicious: 0.9$\CA\leftarrow\CA\cup \Cl_j$. The server can do so because the pigeon hole principle implies that $\Cl_j$ must have sent an invalid share to at least one honest client; hence, the correctness of the value recovered from that client's shares cannot be guaranteed. In case 0.9$1\leq |\textsf{Flag}[j]|\leq m$, the server supervises the following actions.  Suppose client $\Cl_i$ has flagged client $\Cl_j$. Client $\Cl_j$ then reveals the shares for $\Cl_i$, 0.9$\big((i,u_{ji}),(i,\pi_{ji})\big)$ in the clear (on bulletin $\Bl$) for the server $\Ser$ (or anyone else) to verify using 0.9$\textsf{SS.Verify}(\cdot)$. If that verification passes, $\Cl_i$ is instructed by the server to use the released shares for its computations. Otherwise, $\Cl_j$ is marked as malicious by the server $\Ser$. Note that this does not lead to privacy violation for an honest client since at most $m$ shares corresponding to the $m$ malicious clients would be revealed (see Sec. <ref>). If a client $\Cl_i$ flags $\geq m+1$ other clients, $\Ser$ marks  $\Cl_i$ as malicious.  Thus, at this point every client on the list $\CA$ has either

* provided invalid shares to at least one honest client, OR

* flagged an honest client.
In other words, every client who is not in 0.9$\CA$, 0.9$\Cl_i\in \Cl\setminus \CA$, is guaranteed to have submitted at least 0.9$n\!-\!m\!-\!1$ valid shares for the honest clients in 0.9$\Cl_H\setminus\Cl_i$ (see Sec. <ref> for details). Additionally, the server cannot be tricked into marking an honest client as malicious, i.e.,  ensures 0.9$\CA\cap\Cl_H=\varnothing$ (see Sec. <ref>). The server $\Ser$ publishes $\CA$ on the bulletin $\Bl$.

$(ii)$ Computation of proof summaries by clients.  For this phase, the server 0.9$\Ser$ advertises a random value 0.9$r \in \Fl$ on the  bulletin $\Bl$.
Next, a client 0.9$\Cl_i$ proceeds to distill the proof strings of all clients not in 0.9$\CA$ to generate summaries for the server 0.9$\Ser$. Specifically, client 0.9$\Cl_i$ prepares a proof summary 0.9$\sigma_{ji}=\big((i,w^{out}_{ji}),(i,\lambda_{ji})\big)$ for 0.9$\forall\Cl_j \in \Cl\setminus(\CA\cup \Cl_i)$ as per the description in the previous section, and publishes it on  0.9$\Bl$.

$(iii)$ Verification of proof summaries by the server. Next, the server moves to the last step of verifying the proof summaries 0.9$\sigma_i=(w^{out}_i,\lambda_i )$ for all clients not in $\CA$. Recall from the discussion in Sec. <ref> that this involves recovering the values 0.9$w^{out}_i$ and 0.9$\lambda_i$ from the shares of $\sigma_i$ and checking whether  0.9$w^{out}_{i}=1$ and 0.9$\lambda_i=0$. However, we cannot simply use the naive share reconstruction algorithm from Sec. <ref> since some of the shares might be incorrect (submitted by the malicious clients). To address this issue,  performs a
robust reconstruction of the shares as follows.
A naive strategy would be sampling multiple subsets of $m+1$ shares (each subset can emulate a SNIP setting), reconstructing the secret for each subset, and taking the  majority vote.
However, we can do much better by exploiting the connections between Shamir's secret shares and Reed-Solomon error correcting codes (Sec. <ref>). Specifically, the Shamir's secret sharing scheme used by  is a 0.9$[n\!-\!1,m+1,n\!-\!m]$ Reed-Solomon code that can correct up to $q$ errors and $e$ erasures (message dropouts) where 0.9$2q+e<n\!-\!m\!-\!1$. The server $\Ser$ can, therefore, use 0.9$\textsf{SS.robustRecon}(\cdot)$ to reconstruct the secret when 0.9$m<\lfloor\frac{n-1}{3}\rfloor$.

After the robust reconstruction of the proof summaries, the server $\Ser$ verifies them and updates the list $\CA$ with all malicious clients with malformed updates.  Specifically:

\begin{gather*}\small \forall \Cl_i \in \Cl\setminus \CA\\\vspace{-0.5cm}
\hspace{-1.8cm} \small
\Big(\textsf{SS.robustRecon}(\{(j,w^{out}_{ij})\}_{\Cl_j\in \Cl\setminus\{\CA\cup\Cl_i\}})\neq 1 \thinspace\thinspace \vee\\  \vspace{-0.5cm}\small \textsf{SS.robustRecon}(\{(j,\lambda_{ij})\}_{\Cl_j\in \Cl\setminus\{\CA\cup\Cl_i\}}) \neq 0\Big) \\\hspace{5cm}\small\implies \CA\leftarrow\CA \cup \Cl_i. \vspace{-0.5cm}\end{gather*}

Additionally, if  a client $\Cl_i$ withholds some of the shares of the proof summaries for other clients, $\Cl_i$ is marked as malicious as well by the server. Thus, in addition to the malicious clients listed above, the list $\CA$ now has all clients that have either:

* failed the proof verification, i.e., provided malformed updates, OR
* withheld shares of proof summaries of other clients (malicious message dropout).

To conclude the round, the server publishes the updated list $\CA$ on the public bulletin $\Bl$.

Round 4 (Compute Aggregate). This is the final round of  where the  aggregate of the well-formed updates is computed. If a client $\Cl_i$ is on $\CA$ wrongfully, it can dispute its malicious status by showing the other clients the transcript of the robust reconstruction from all the shares of $\sigma_i$ (publicly available on bulletin $\Bl$).
If any client $\Cl_i \in \Cl$ successfully raises a dispute, all clients abort the protocol because they conclude that the server $\Ser$ has acted maliciously by trying to withhold a verified well-formed update from the aggregation. If no client raises a successful dispute, every client 0.9$\Cl_i \in \Cl\setminus\CA$ generates its share of the aggregate, 0.9$(i,\Ul_{i})$ with 0.9$\Ul_{i}=\sum_{\Cl_j\in \Cl\setminus \CA}u_{ji}$, and sends that share to the server $\Ser$. Note that, herein, $\Cl_i$ uses its own share of the update, 0.9$(i,u_{ii})$, as well.

The server recovers the aggregate 0.9$\Ul=\sum_{\Cl_i\in \Cl\setminus \CA} \Ul_j$ using robust reconstruction: 0.9$\Ul\leftarrow \textsf{SS.robustRecon}(\{(i,\Ul_{i})\}_{\Cl_i\in \Cl\setminus \CA})$.

Discussion.   meets the design goals of Sec. <ref> as follows.

Flexibility of Integrity Checks. SNIP supports arbitrary arithmetic circuits for 0.9$\Vl(\cdot)$. The server 0.9$\Ser$ can choose a different  0.9$\Vl(\cdot)$ for every iteration (the protocol described above corresponds to a single iteration of model training in FL). Additionally, 0.9$\Ser$ can hold
multiple 0.9$\Vl_1(\cdot),\cdots,\Vl_k(\cdot)$ and want
to check whether the client’s update passes them all. For this, we have 0.9$\Vl_i(\cdot)$ return zero
(instead of one) on success. If 0.9$w^{out}_i$ is the value on the output wire of the circuit 0.9$\Vl_i(\cdot)$, the server chooses random values 0.9$(l_1, \cdots ,l_k) \in \Fl^k$ and recovers the sum 0.9$\sum_{i=1}^kl_i\cdot w^{out}_i$ in Round 3. If any 0.9$w^{out}_i=0$, then the sum will be non-zero with high probability and $\Ser$ will reject.

Compatibility with FL's Infrastructure. Current deployments of FL involves a single server who wants to train the global model. Hence, as explained above, we design SNIP to be compatible with a single server in . Solutions involving two or more non-colluding servers are unrealistic for FL. For instance, currently the server can be owned by Meta who wants to train privately on the data of its user base. For a two-server model here, the second server has to be owned by an independent party. Moreover, both the servers have to do an equal amount of computation for model training (verification, aggregation etc) since SNIP uses secret shares. This would make sense only if both the servers are interested in training the model. For instance, if Meta and Google collaborate to train a model on their joint user base which is an unrealistic scenario.

Efficiency. 's usage of SNIP as the underlying ZKP is made from the efficiency point of view. SNIP is a light-weight ZKP system that is specialized for the server-client settings resulting in good performance. For instance, its performance is about three-orders of magnitude better than that of zkSNARKs [28]. Instead of using ZKPs, one alternative is to use standard secure multi-party computation (MPC) for the entire aggregation to directly compute 0.9$\Ul_{valid}=\sum_{\Cl_i}\Vl(u_i)\cdot u_i$. However, doing the entire aggregation under MPC would result in a massive circuit with 0.9$O(nd)$ multiplication gates where 0.9$d$ is the data dimension. Multiplications are costly for MPC and each gate requires a round of communication in general making the above computation prohibitively costly. Extending the  computation to the malicious threat model would be even costlier. This is where SNIP proves to be advantageous: SNIP enables the verifiers to check all the multiplication gates very efficiently (in a non-interactive fashion) with just one polynomial identity test (Sec. <ref>).

[sharp corners, breakable]
Remark 3. In a nutshell, 's technical novelty is in providing an efficient extension of SNIP to a $(1)$ fully malicious threat model in a $(2)$ single server setting.

's problem setting is different from that of the original SNIP proposal in the following ways:

* The original SNIP deployment setting (Prio) uses $\geq 2$  non-colluding servers as the verifiers;
requires a single server.

* Originally, SNIP considers honest verifiers;  supports a fully malicious threat model (provers and verifiers).
The above changes cannot be supported in SNIP as is and are necessary to capture the constraints of a realistic FL setting.

The core essence of the technical differences between the original deployment of SNIP and  is that the roles of the parties are changed: the former has a clear distinction between the prover (clients) and verifiers ($k\geq 2$ honest servers), whereas the clients and the single server jointly act as the (malicious) verifiers in .

Consequently, SNIP's interaction pattern is different in  which required the following technical changes.

* Originally, SNIP uses additive secret shares whereas  uses Shamir’s threshold secret sharing.

* In the original construction of SNIP, the reconstruction (a fundamental operation in the protocol) of shares is very simple: just add (+) the individual shares. In , we propose a robust reconstruction technique, $\textsf{SS.robustRecon}(\cdot)$, based on Reed-Solomon codes. This is key in ensuring robust verification even with malicious verifiers.

* , in addition, requires verifiable secret shares: shares are augmented with a check string $\Psi$ which is integrated into the protocol.

* Messages (shares, proofs) are distributed in the clear in the original SNIP deployment; messages are encrypted in .

* We propose novel optimizations for  (Sec. <ref> targets the new operations for verifying secret shares and robust reconstruction while Sec. <ref> provides general improvements for SNIP).

Current, deployment
The key cryptographic tool we use for extending SNIP to the malicious threat model to account for the malicious verifiers (clients) is threshold secret sharing (as explained in Sec. IVC) to introduce data redundancy for robust proof verification. However, this transformation is not straightforward since:
- The original SNIP deployment setting has a clear distinction between the prover and the verifiers; it considers $k>=2$ servers (verifiers) which would make the usage of threshold secret shares for the malicious setting easy. However for FL, we are constrained to work in the single-server setting which makes the problem significantly challenging. EIFFeL
tackles this challenge by using the clients to act as the verifiers for each other under the supervision of the server - this completely changes the interaction pattern of the SNIP proof system from its original proposal. Hence, our 4-round EIFFeL protocol that is designed to be compatible with the FL infrastructure is a novel technical contribution.

* Setup Phase.
* All parties are given the security parameter $\kappa$, the number of clients $n$ out of which at most 0.9$m<\lfloor \frac{n-1}{3}\rfloor$ are malicious,  honestly generated
0.9$pp \randarrow \textsf{KA.gen}(\kappa)$ and a field $\Fl$ to be used
for secret sharing. Server initializes lists 0.9$\textsf{Flag}[i]=\varnothing, i \in [n]$ and 0.9$\CA=\varnothing$.

* Round 1 (Announcing Public Information).

Client: Each client $\Cl_i$

* Generates its key pair and announces the public key. $(pk_i,sk_i)\randarrow \textsf{KA.gen}(pp)$, $\Cl_i \xrightarrow{pk_i} \Bl$.

* Publishes the validation predicate $\Vl(\cdot)$. $\Ser \xrightarrow{\Vl(\cdot)}\Bl$
* Round 2 (Generate and Distribute Proof).
Client: Each client $C_i$
* Computes $n-1$ pairwise keys. $\forall \Cl_j \in \Cl_{\setminus i}, sk_{ij}\larrow \textsf{KA.agree}(pk_j,sk_i)$
* Generates proof $\pi_{i}=\big( h_i,(a_i,b_i,c_i) \big), h_i \in \Fl[X],$ $(a_i,b_i,c_i)\in \Fl^3,$ $a_i\cdot b_i=c_i$ for the statement $\Vl(u_i)=1$.
* Generates shares of the input $u_i\in \Fl^d$. $\{(1,u_{i1}),\cdots ,(n,u_{in}),\Psi_{u_{i}}\}\randarrow\textsf{SS.share}(u_i,[n],m+1)$
* Generates shares of the proof $\pi_i$.

\begin{gather*}\small\{(1,h_{i1}),\cdots,(n,h_{in}),\Psi_{h_{i}}\}\randarrow \textsf{SS.share}(h_i,[n]\setminus i,m+1), \{(1,a_{i1}),\cdots,(n,a_{in}),\Psi_{a_{i}}\}\randarrow \textsf{SS.share}(a_i,[n]\setminus i,m+1 )\small\\\{(1,b_{i1}),\cdots,(n,b_{in}),\Psi_{b_{i}}\}\randarrow \textsf{SS.share}(b_i,[n]\setminus i,m+1 ), \{(1,c_{i1}),\cdots,(n,c_{in}),\Psi_{c_{i}}\}\randarrow \textsf{SS.share}(c_i,[n]\setminus i,m+1 )\end{gather*}

* Encrypts proof strings for all other clients. $ \forall \Cl_j\in\Cl_{\setminus i}, \overline{(j,u_{ij})||(j,\pi_{ij})}\randarrow \textsf{AE.enc}\big(sk_{ij},(j,u_{ij})||(j,\pi_{ij})\big), \pi_{ij}=h_{ij}||a_{ij}||b_{ij}||c_{ij}$.
* Publishes check strings and the encrypted proof strings on the bulletin.
$ \forall \Cl_j\in\Cl_{\setminus i}, \Cl_i\xrightarrow{\overline{(j,u_{ij})||(j,\pi_{ij})}}\Bl; \Cl_i\xrightarrow{\Psi_{{u}_i},\Psi_{\pi_i}}\Bl$

* Round 3 (Verify Proof).

(i)  Verifying validity of secret shares:

Each client $\Cl_i$

* Downloads and decrypts proof strings for all other clients from the public bulletin.  Flags a client in case their decryption fails.

\begin{gather*}\vspace{-0.2cm}\small\forall \Cl_j \in \Cl_{\setminus i}, \Cl_i\xleftarrow{\overline{(i,u_{ji})||(i,\pi_{ji})},\Psi_{{u}_j},\Psi_{{\pi}_j}}\Bl, (i,u_{ji})||(i,\pi_{ji}) \leftarrow \textsf{AE.dec}\big(sk_{ij},\overline{(i,u_{ji})||(i,\pi_{ji})}\big)\\\vspace{-0.1cm} \small\bot\leftarrow \textsf{AE.dec}\big(sk_{ij},\overline{(i,u_{ji})||(i,\pi_{ji})}\big) \implies Cl_i\xrightarrow {\text{Flag } \Cl_j} \Bl \end{gather*}

* Verifies the shares $u_{ji}(\pi_{ji})$ using checkstrings $\Psi_{{u}_j} (\Psi_{{\pi}_j})$ and flags all clients with invalid shares.

\begin{gather*}\forall \Cl_j \in \Cl_{\setminus i}, 0 \leftarrow \big(\textsf{SS.verify}((i,u_{ji}),\Psi_{{u}_{j}})\wedge \textsf{SS.verify}((i,\pi_{ji}),\Psi_{{\pi}_{j}})\big)\implies  \Cl_i \xrightarrow{\text{Flag }\Cl_j}\Bl  \end{gather*}

* If client $\Cl_i$ flags client $\Cl_j$, the server updates $\textsf{Flag}[j]=\textsf{Flag}[j]\cup \Cl_i$
* Updates the list of malicious client  $\CA$ as follows:
* Adds all clients who have flagged $\geq m+1$ other clients. $\forall \Cl_i \mbox{ s. t. } Z=\{j|\Cl_i \in \textsf{Flag}[j]\}, |Z|\geq m+1\implies \CA\leftarrow\CA\cup \Cl_i$
* Adds all clients with more than $m+1$ flag reports. $|\textsf{Flag}[i]|\geq m+1 \implies \CA\leftarrow\CA\cup \Cl_i$
* For clients with less flag reports, the server obtains the corresponding shares in the clear, verifies them and updates $\CA$ accordingly. $\forall \Cl_j \text{ s.t } 1 \leq |\textsf{Flag}[j]|\leq m, \forall \Cl_i \text{ s.t. } \Cl_i \text{ has flagged } \Cl_j $
* $\Cl_j \xrightarrow{(i,u_{ji}),(i,\pi_{ji})} \Bl$
* $
\text{if } \big(\textsf{SS.verify}((i,u_{ji}),\Psi_{{u}_{j}}) \wedge \textsf{SS.verify}((i,\pi_{ji}),\Psi_{\pi_{j}})\big)=0 \implies \CA\leftarrow\CA\cup \Cl_j, \text{ otherwise, } \Cl_i$  uses the verified shares to compute its proof summary  $\sigma_{ji}\vspace{-0.1cm} $

* Publishes $\CA$ on the bulletin. $\Ser\xrightarrow{\CA}\Bl$

(ii)   Generation of proof summaries by the clients.

* Server announces a random number $r\in \Fl$. $\Ser \xrightarrow{r}\Bl$
Client: Each client $\Cl_i \in \Cl\setminus\CA$

* Generates a summary $\sigma_{ji}$ of the proof string $\pi_{ji}$ based on $r$, $\forall \Cl_j \in \Cl\setminus (\CA\cup\Cl_i), \Cl_i\xleftarrow{r}\Bl,\sigma_{ji}=\big( (i,w^{out}_{ji}),(i,\lambda_{ji})\big),\Cl_i\xrightarrow{\sigma_{ji}}\Bl$

(iii) Verification of proof summaries by the server.

* Downloads and verifies the proof for all clients not on $\CA$ via robust reconstruction of the digests and updates $\CA$ accordingly. 0.87$\forall \Cl_i \in \Cl\setminus\CA, \Ser\xleftarrow{\sigma_{ij}}\Bl, \big( \textsf{SS.robustRecon}(\{(j,w^{out}_{ij})\}_{\Cl_j \in \Cl\setminus(\CA\cup\Cl_i)}) \neq 1 \vee \textsf{SS.robustRecon}(\{(j,\lambda_{ij})\}_{\Cl_j \in \Cl\setminus(\CA\cup\Cl_i)})\neq 0 \big)\implies \CA\leftarrow\CA\cup \Cl_i$
* Publishes the updated list $\CA$ on the  bulletin. $\Ser \xrightarrow{\CA} \Bl$

* Round 4 (Compute Aggregate).
Client: Each client $\Cl_i$
* If $\Cl_i$ is on $\CA$, $\Cl_i$ raises a dispute by sending the transcript of the reconstruction of $\sigma_i$ that shows 0.9$\lambda_i=0\wedge w^{out}_j=1$ and aborts, OR
$\forall \Cl_j \in \Cl_{\setminus i}, \Cl_i \xleftarrow{\sigma_{ij}}\Bl,$ $ \Cl_i\xrightarrow{\mbox{Transcript of } \textsf{SS.robustRecon}(\{(j,\sigma_{ij})\}_{\Cl_j \in \Cl\setminus(\CA\cup\Cl_i)})}\Bl$

* Aborts protocol if it sees any other client on $\CA$ successfully raise a dispute,  OR

* If no client has raised a dispute and $\Cl_i$ is not on $\CA$, sends the aggregate of the shares of clients in 0.9$\Cl\setminus\CA$ to the server. 0.9$\Ul_{i}=\underset{\Cl_j\in \Cl\setminus \CA}{\sum u_{ji}}, \Cl_i\xrightarrow{\Ul_i}\Ser$

* Reconstructs the final aggregate. $\Ul\leftarrow \textsf{SS.robustRecon}(\{(i,\Ul_i)\}_{\Cl_i \in \Cl\setminus\CA })$

: Description of the secure aggregation with verified inputs protocol.

Table <ref> analyses the complexity of   in terms of the number of clients $n$, number of malicious clients $m$ and data dimension $d$. We assume that  0.9$|\Vl|$ is of the order of 0.9$O(d)$. The total number of one-way communication is $12$ and $9$ for the clients and the server, respectively. A per-round analysis is presented in App. <ref>.

!     Computation      Communication

Client       $O(mnd)$     $O(mnd)$

Server     $O\big((n+d)n\log^2n\log \log n+md\min(n,m^2)\big)$     $O\big(n^2+md\min(n,m^2)\big)$

Computational and communication complexity of  for the server and an individual client.

§ SECURITY ANALYSIS

In this section, we formally analyze the security of .

For any public validation predicate 0.9$\Vl(\cdot)$ that can be expressed by an arithmetic circuit,  is a  protocol (Def. <ref>) for 0.9$|\Cl_M|<\lfloor\frac{n-1}{3}\rfloor$ and $\Cl_\Vl=\Cl\setminus\CA$.

We present a proof sketch of the above theorem here; the formal proof is in App. <ref>.

Proof Sketch. The proof  relies on the following two facts.

Fact 1. Any set of $m$ or less shares in  reveals nothing about the secret.

Fact 2. A $(n,m\!+\!1,n\!-\!m)$ Reed-Solomon error correcting code can correctly construct the message with up to  $q$ errors and $e$ erasures (message dropout), where $2q+e<n-m
+1$. In , we have $q+e\!=\!m$ where $q$ is the number of malicious clients that provide erroneous shares and $e$ is the number of clients that withhold a message or are barred from participation (i.e., are in $\Cl^*$).

Integrity. We prove that  satisfies the integrity constraint of the  protocol using the following three lemmas.

accepts the update of every honest client.

\begin{equation}\vspace{-0.3cm}
\forall \Cl_i \in \Cl_{H}: \Pr_{\name}[\textsf{Accept } u_i]=1. \label{eq:complete}
\end{equation}

By definition, client $\Cl_i\in \Cl_H$ has well-formed inputs, that is, $\Vl(u_i)\!=\!1$. Additionally, $\Cl_i$, by virtue of being honest, submits valid shares. Hence, at least $n-m-1$ other honest clients $\Cl_H\setminus \Cl_i$ will produce correct shares of the proof summary $\sigma_i=(w^{out}_i,\lambda_i)$. Using Fact 2, the server $\Ser$ is able to correctly reconstruct the value of $\sigma_i$. Eq. <ref> is now implied by the completeness property of SNIP.

All updates accepted by  are well-formed with probability $1-\mathrm{negl}(\kappa)$.

\begin{gather*}\vspace{-0.3cm}\small\forall \Cl_i \in \Cl, \Pr_\name\big[\Vl(u_i)=1\big| \textsf{Accept } u_i\big]=1-\mathrm{negl}(\kappa).\numberthis\label{eq:soundness}
\end{gather*}

The proof relies on the fact that a client will be verified only if it has submitted $\geq n-m-1$ valid shares (see App. <ref>).

rejects all malformed updates with probability $1-\mathrm{negl}(\kappa)$.

Based on the above lemmas, at the end of Round 3, $\Cl\setminus \CA$ (set of clients whose updates have been accepted) must contain all honest clients $\Cl_H$. Additionally, it may contain some clients $\Cl_i$ who have submitted well-formed updates with at least $n-m-1$ valid shares for $\Cl_H$, but may act maliciously for other steps of the protocol (for instance, give incorrect shares of proof summary for other clients or give incorrect shares of the final aggregate). This is acceptable provided that  is able to reconstruct the final aggregate containing only well-formed updates which is guaranteed by the following lemma.

The aggregate $\Ul$ must contain the updates of all honest clients or the protocol is aborted.
\begin{gather*}\vspace{-0.5cm} \small\Ul=\Ul_H +\sum_{\Cl_i\in \bar{\Cl}} u_i \mbox{ where }\Ul_H=\sum_{\Cl_i\in \Cl_H}u_i\\\small\bar{\Cl}\subseteq \Cl\setminus\{\CA\cup \Cl_H\}\numberthis \label{eq:aggregate} \vspace{-0.5cm}\end{gather*}

If the server 0.9$\Ser$ acts maliciously and publishes a list 0.9$\CA$ such that  0.9$\CA\cap \Cl_H\neq \varnothing$, an honest client 0.9$\Cl_i \in \CA\cap \Cl_H$ publicly raises a dispute. This is possible since all the shares of $\sigma_i$ are publicly logged on 0.9$\Bl$. If the dispute is successful, all honest clients will abort the protocol. Note that a malicious client with malformed updates cannot force the protocol to abort in this way since it will not be able to produce a successful transcript with high probability (Lemma <ref>). If no clients raise a successful dispute, Eq. <ref> follows directly from Fact 2.  0.9$\bar{\Cl}$ represents a set of  malicious clients with well-formed updates which corresponds to 0.9$\Cl_\Vl\setminus\Cl_H$ in Eq. <ref>.

Privacy. The privacy constraint of  states that nothing should be revealed about a private update $u_i$ for an honest client $\Cl_i$, except:

* $u_i$ passes the integrity check, i.e., $\Vl(u_i)=1$

* anything that can be learned from the aggregate of honest clients, $\Ul_H$.

We prove that  satisfies this privacy constraint with the help of the following two helper lemmas.

In Rounds 1-3, for an honest client $\Cl_i\in \Cl_H$,  reveals nothing about $u_i$ except $\Vl(u_i)=1$.
The proof uses the fact that only $m$ shares of $\Cl_i$, which correspond to the $m$ malicious clients, can be revealed (see App. <ref>).

In Round $4$, for an honest client $\Cl_i\in \Cl_H$,  reveals nothing about $u_i$ except whatever can be learned from the aggregate.

In Round $4$, from Lemma <ref> and Fact 2,  the information revealed is either the aggregate or $\bot$.

§  OPTIMIZATIONS

§.§ Probabilistic Reconstruction

The Gao's decoding algorithm alongside the use of verifiable secret sharing guarantees that the correct secret will be recovered (with probability one). However,  we can improve performance at the cost of a small probability of failure.

Verifying Secret Shares. As discussed in Sec. <ref>, verifying the validity of the secret shares is the dominating cost for client-side computation. To reduce this cost, we propose an optimization where the validation of the shares corresponding to the proof 0.9$\pi_i=\big( h_i, (a_i,b_i,c_i)\big)$ can be eliminated. Specifically, we propose the following changes to  Round 3:

* Each client $\Cl_i$ skips verifying the validity of the shares $(i,\pi_{ji})$ for  $\Cl_j \in \Cl_{\setminus i}$.
* Let 0.9$e=|\CA|$. The server 0.9$\Ser$ samples two sets of clients 0.9$P_1, P_2$ from 0.9$\Cl \setminus \{\Cl_i\cup\CA\}$ of size at least 0.9$3m-2e+1$ (0.9$P_1, P_2$ can be overlapping) and performs Gao's decoding on both the sets to obtain polynomials $p_1$ and $p_2$. The server accepts the  0.9$w^{out}_{i}$ (0.9$\lambda_i$) only iff 0.9$p_1\!=\!p_2$ and  0.9$p_1(0)=p_1(0)=1 (p_1(0)=p_1(0)=0)$. The cost of this step is 0.9$O(n^2\log^2 n\log\log n)$ which is less than verifying the shares of 0.9$\pi_i$ when 0.9$m<n\ll d$ (improves runtime by 0.9$2.3\times$, see Table <ref>).
Note that a 0.9$[n,k, n\!-\!k+1]$ Reed-Solomon error correcting code can correct up to 0.9$\lfloor \frac{n-k -l}{2}\rfloor$ errors with $l$ erasures. Thus, with 0.9$m\!-\!e$ malicious clients, only 0.9$3m \!-\! 2e\!+\!1$ shares are sufficient to correctly reconstruct the secret for honest clients.  Since, the random sets $P_1$ and $P_2$ are not known, a malicious client with more than 0.9$m \!-\! e$ invalid shares can cheat only with probability at most $\nicefrac{1}{\binom{3m-2e+2}{n-e}}$. We cannot extend this technique for the secret shares of the update $u$, because, unlike the value of the digests 0.9($w^{out}\!=\!1,\lambda\!=\!0$), the final aggregate is unknown and needs to be reconstructed from the shares.

Improvement. Eliminates verification of check strings for the proof $\pi_i$ which reduces time by $2.3\times$ (Table <ref>).

Cost. Additional 0.9$\nicefrac{1}{\binom{3m-2e+2}{n-e}}$
probability of failure where 0.9$e=|C^*|$ .

Robust Reconstruction. In case 0.9$m\leq \sqrt{n}-2$, the robust reconstruction mechanism can be optimized as follows.
Let 0.9$q=m-|\CA|$ be the number of malicious clients that remain undetected.
The server $\Ser$ partitions the set of clients in $\Cl\setminus \CA$ into at least $q+2$ disjoint partitions, $P=\{P_1,\cdots, P_{q+2}\}$ each of size $m+1$. Let $p_j(x)=c_{j,0} + c_{j,1}x+c_{j,2}x^2+ \cdots +c_{j,m}x^{m}$ represent the polynomial corresponding to the $m+1$ shares of partition $P_j$. Recall that recovering just $p_j(0)=c_{j,0}$ suffices for a typical Shamir secret share reconstruction. However, now, the server $\Ser$ recovers the entire polynomial $p_j$, i.e., all of its coefficients  $\{c_{j,0}, c_{j,1},
\cdots, c_{j,q}\}$ for all $q+2$ partitions. Based on the pigeon hole principle, it can be argued that at least two of the partitions $(P_l,P_k \in P)$ will consist of honest clients only. Hence, we must have at least two polynomials $p_l$ and $p_k$ that match and the value of the secret is their constant coefficient $p_l(0)$.

Note that the above mentioned optimization of skipping verifying the shares of the proof can be applied here as well.
A malicious client can cheat (i.e., make the server $\Ser$ accept even when 0.9$w^{out}_i\neq 1 \vee \lambda_i\neq 0$ or reject the proof for an honest client) only if they can  manipulate the shares of at least two partitions which must contain at least 0.9$2(m+1)-q$ honest clients.  Since the random partition $P$ is not known to the clients, this can happen only with probability $\nicefrac{1}{\binom{2(m+1)-q}{n-m-1}}$.

Improvement. Reduces the number of polynomial interpolations.

Cost. Additional 0.9$\nicefrac{1}{\binom{2(m+1)-q}{n-m-1}}$ probability of failure where 0.9$q=m-|\CA|$ .

Case I $m\leq \sqrt{n}-2$. Let $p_j(x)=c_{j,0} + c_{j,1}x+c_{j,2}x^2+ \cdots +c_{j,m-1}x^{(m-1)}$ represent the polynomial corresponding to the $m+2$ shares of partition $P_j$. Recall, recovering just $p_j(0)=c_{j,0}$ would suffice for a typical Shamir secret share reconstruction. However, now, the server $\Ser$ recovers the entire polynomial $p_j$, i.e., all of its coefficients  $\{c_{j,0}, c_{j,1},
\cdots, c_{j,m-1}\}$ (this takes $O(m^2)$ additional steps).  The server accepts a digest $\sigma=(d,w)$ iff we have at least two polynomials that match and has the correct value of the recovered secret, i.e., for recovering ()$\exists p_i,p_j \text{s.t.} p
_i=p_j \wedge c_{i,0}=c_{j,0}=0 ()$ .
Faster Share Generation. Recall, that we assume that the shares for client $\Cl_i$ is of the form $(i,s_i)$ where $i\in[n]$ is its logical ID. This provides an advantage as the computation can be sped up by using the calculus of finite differences <cit.>.
Here, we outline opportunities for pre-computing certain and cahing them to speed up the performance of the online pahse . Note that the .

* Lagrange Base Polynomials. Polynomial interpolations at a given point $r$ can be sped up by pre-computing the Lagrange base polynomials  which only depend on . This is used $i$s can be since the . This trick is also used by the clients to compute the (see [28] for details).

* Share Generation.

§.§ Crypto-Engineering Optimizations

Equality Checks. The equality operator $=$ is relatively complicated to implement in an arithmetic circuit. To circumvent this issue, we replace any validation check of the form 0.9$\Phi(u)=c_1\vee \Phi(u)=c_2\vee \cdots $ 0.9$\vee\Phi(u)=c_k$ in the output nodes of 0.9$\Vl(\cdot)$, where 0.9$\Phi(\cdot)$ is some arithmetic function, by an output of the form 0.9$(\Phi(u)-c_1)\times\cdots\times(\Phi(u)-c_k)$. Recall that in , the honest clients have well-formed inputs that satisfy 0.9$\Vl(\cdot)$ by definition. Hence, this optimization does not violate the privacy of honest, which is our security goal.

Improvement. Reduces the circuit size $|\Vl|$.

Cost. No cost.

Proof Summary Computation. In addition to being a linear secret sharing scheme, Shamir's scheme is also multiplicative: given the shares of two secrets $(i,z_i)$ and  $(i,v_i)$, a party can locally compute $(i,s_{i})$ with $s\!=\!z\cdot v$. However, if the original shares correspond to a polynomial of degree $t$, the new shares represent a polynomial of degree $2t$. Hence, we do not rely on this property for the multiplication gates of 0.9$\Vl(\cdot)$ as it would support only limited number of  multiplications. However, if 0.9$m\!<\!\frac{n-1}{4}$, we can still leverage the multiplicative property to generate shares of the random digest 0.9$\lambda_i=f_i(r)\cdot g_i(r)=h_i(r)$ locally (instead of using Beaver's triples).

Improvement.  Saves a round of communication and reduces the number of robust reconstructions for $\lambda_i$ from three to just one (details in App. <ref>).
Cost. No cost.

Random Projection.
As shown in Table <ref>, both communication and computation grows linearly with the data dimension $d$.  Hence, we rely on the random projection [66] technique for reducing the dimension of the updates. Specifically, we use the fast random projection using Walsh-Hadamard transforms [4].

Improvement. Reduces the data dimension which helps both computation and communication cost.

Cost. Empirical evaluation (Sec. <ref>) shows that the efficacy of $\Vl(\cdot)$ is still preserved.

Computation cost analysis of . The left two plots show the runtime of a single client client in milliseconds as a function of: (left)
the number of clients $n$ and  (right) dimensionality of the updates $d$. The right two plots show the runtime of the server as a function of the same variables. The results demonstrate that performance decays quadratically in $n$, and linearly in $d$.

Communication cost analysis of . The left two plots show the amount of communication (in MB) for each client as a function of: (left)
the number of clients $n$ and  (right) dimensionality of the updates $d$. The right two plots show the the amount of communication (in MB) for the server as a function of the same variables. The results show communication increases quadratically in $n$, and linearly in $d$.

§ EXPERIMENTAL EVALUATION

§.§ Performance Evaluation.

In this section, we analyze the performance of .

We run experiments on two Amazon EC2  instances with Intel Xeon Platinum 8000 processors.
To emulate server-client communication, we use two instances in the US East (Ohio) and US West (Oregon) regions, with a round trip time of 21 ms.
We implemented  in Python and  C++ using NTL library [1].
We use AES-GCM for encryption, a $56$-bit prime field $\Fl$ and probabilistic quantization [47]. For key agreement, we use elliptic curve Diffie-Hellman [32] over the NIST P-256 curve. Unless otherwise specified, the default settings are $d\!=\!1K$, $n\!=\!100$, $m\!=\!10\%$ and $|\Vl(\cdot)|\approx4d$. We report the mean of 10 runs for each experiment. The rejection probability $(negl(\kappa))$ is dominated by  $\nicefrac{2\Ml-2}{|\Fl|}$
(soundness error of SNIP, Sec. <ref>).  $\Ml < 4d < 40K$ in our evaluation so the failure probability is of the order of $O(10^{-12})$.

Computation Costs.
Fig. <ref> presents 's runtime.  We vary the number of malicious clients between $5\%$-$20\%$ of the number of clients.

We observe that per-client runtime of  is low: it is $1.3s$ if $m=10\%$, $d=1K$, and $n=100$.
The runtime scales quadratically in $n$ because a client has $O(mnd)$ computation complexity (see Table <ref>) and $m$ is a linear function of $n$. As expected, the runtime increases linearly with $d$. A client takes around $11s$ when $d=10K$, $n=100$, and $m=10\%$.
The runtime for the server is also low: the server completes its computation in about $1s$ for $n=100$, $d=1K$, and $m=10\%$.
The server's runtime also scales quadratically in $n$  due to the $O(mnd)$ computation complexity (Table <ref>).
The runtime increases linearly with $d$.

In Fig. <ref>, we break down the runtime per round.
We observe that: Round 1 (announcing public information) incurs negligible cost for both clients and the server; and Round 3 (verify proof) is the costliest round for both clients and the server where the dominating cost is verifying the validity of the shares (Sec. <ref>). Note that the server has no runtime cost for Round 2 since the proof generation only involves clients.

Table <ref> presents our end-to-end performance which contains the runtimes of a client, the server and the communication latencies.  For instance, the end-to-end runtime for 0.9$n=100$, $d=1K$ and 0.9$m=10\%$ is $\sim2.4s$. We also present the impact of one of our key optimizations – eliminating the verification of the secrets shares of the proof – which cuts down the costliest step in  and improves the performance by $2.3\times$. Additionally, we compare 's performance with
BREA [80], which is a Byzantine-robust secure aggregator.  differs from BREA in two key ways: $(1)$  is a general framework for per-client update integrity checks whereas BREA implements the multi-Krum aggregation algorithm [15] that considers the entire dataset to determine the malicious updates (computes all the pairwise distances between the clients and then, detects the outliers), and $(2)$ BREA has an additional privacy leakage as it reveals the values of all the pairwise distances between clients. Nevertheless, we choose BREA as our baseline because, to the best of our knowledge, this is the only prior work that: $(1)$ detects and removes malformed updates, and $(2)$ works in the malicious threat model with $(3)$ a single server (see Table <ref>, Sec. <ref>). We observe that  outperforms BREA and that the improvement increases with $n$. For instance, for $n\!=\!250$,  is $18.5\times$ more performant than BREA. This is due to BREA's complexity of 0.9$O(n^3\log^2n\log\log n +mnd)$, where the 0.9$O(n^3)$ factor is due to each client partaking in the computation of the 0.9$O(n^2)$ pairwise distances.
2cImprovement over

(lr)3-4 # Clients ($n$)     Time (ms)     Unoptimized     BREA [80]

50     1,072    2.3$\times$    2.5$\times$

100      2,367     2.3$\times$    5.2$\times$

150     4,326     2.3$\times$    7.8$\times$

200      6,996     2.3$\times$    12.8$\times$

250      10,389     2.3$\times$    18.5$\times$

End-to-end time for a single iteration of  with $d\!=\!1000$ and $m\!=\!10\%$ malicious clients, as a function of the number of clients, $n$. We also compare it with a variant of  without optimizations, and with BREA [80].

Computation cost per round in .

MNIST: Sign flip attack with norm ball validation predicate (defense).

MNIST: Scaling attack and cosine similarity validation predicate.

FMNIST: Additive noise attack with Zeno++ validation predicate.

FMNIST: Sign flip attack with norm ball validation predicate.

MNIST: Min-Max attack with Zeno++ validation predicate.

CIFAR-10: Min-Sum attack with cosine similarity validation predicate.

EMNIST: Backdoor Attack-1 with norm bound validation predicate.

CIFAR-10: Backdoor Attack-2 with norm bound validation predicate.

Accuracy analysis of . Test accuracy is shown as a function of the FL iteration for different datasets and attacks.

Communication Cost.
Fig. <ref> depicts the total data transferred by a client and the server. The communication complexity is 0.9$O(mnd)$ for a single client and for the server. Hence, the total communication increases quadratically with $n$ and linearly with $d$, respectively. We observe that  has acceptable communication cost. For instance, the total data consumed by a client is $132$MB for the configuration 0.9$n=100, d=10K, m=10\%$.
This is equivalent to streaming a full-HD video for $26s$ [2]. Since most clients partake in FL training iterations infrequently, this communication is acceptable.

Note. Recall, we assume the size of the validation predicate to be 0.9$|\Vl| = O(d)$ since 0.9$\Vl(\cdot)$ defines a function on the input which is 0.9$d$-dimensional. This assumption is validated by the state-of-the-art predicates tested in Sec. <ref>. The above experiments use 0.9$|\Vl|\approx 4d$. Hence, the overall complexity (App. <ref>) is dominated by the 0.9$O(mnd)$ term and does not depend on the validation predicate.

§.§ Integrity Guarantee Evaluation

In this section, we evaluate 's efficacy in ensuring update integrity on real-world datasets.

Datasets. We evaluate  on three image datasets:

* MNIST [51] is a digit classification dataset of $60K$ training images and $10K$ test images with ten classes.

* EMNIST [27] is a writer-annotated handwritten digit classification dataset with $\sim 340K$ training and $\sim 40K$ testing images.

* FMNIST [96] is
identical to MNIST in terms number of classes, and number of training and test images.
* CIFAR-10 [49] contains RGB images with ten object classes. It has $50K$ training and $10K$ test images.

Models. We test  with three classification models:

* LeNet-5 [50] has five layers and $60K$ parameters, and  is used to experiment on MNIST and EMNIST.

* For FMNIST, we use a five-layer convolutional network with $70K$ parameters and a similar architecture as LeNet-5.

* We use ResNet-20 [40] with $20$ layers and $273K$ parameters for CIFAR-10.

Validation Predicates.
To demonstrate the flexibility of , we evaluate four validations predicates, which represent the current state-of-the-art defenses against data poisoning, as follows:

* Norm Bound [85]. This method checks whether the 0.9$\ell_2$-norm of a client update is bounded: 0.9$
\Vl(u) = \mathbb{I}[ \lVert u\rVert_2 < \rho ]
where 0.9$\mathbb{I}[\cdot]$ is the indicator function and the threshold 0.9$\rho$ is computed from the public dataset $\DP$.

* Norm Ball [83]. This method checks whether a client update is within a spherical radius from $v$ which is the gradient update computed from the clean public dataset $\DP$: 0.9$\Vl(u)=\mathbb{I}\big[\lVert u-v\Vert_2\leq \rho \big]$
where radius $\rho$ is also computed from $\DP$.

* Zeno++ [91] compares the client update with a loss gradient $v$ that is computed on the public dataset $\DP$: 0.9$
\Vl(u) =
\mathbb{I}[\gamma\langle v,u\rangle - \rho||u||_2$ 0.9$\geq -\gamma\epsilon]
where $\gamma$, $\rho$ and $\epsilon$ are threshold parameters also computed from  $\DP$ and $u$ is $\ell_2$-normalized to have the same norm as $v$.

* Cosine Similarity [24, 5]. This method compares the cosine similarity between the client update $u$ and the global model update of the last iteration $u'$: 0.9$\Vl(u)=\mathbb{I}\big[\frac{\langle u,u'\rangle}{\lVert u\rVert_2 \lVert u'\rVert_2}< \rho \big]$ where $\rho$ is computed from $\DP$ and $u$ is $\ell_2$-normalized to match norm of $u'$.

Poisoning Attacks.
To test the efficacy of 's implementations of the four validation predicates introduced above, we test it against seven poisoning attacks:

* Sign Flip Attack [31]. In this attack, the malicious clients flip the sign of their local update: 0.9$\hat{u}=-c\cdot u, c\in \mathbb{R}_+$.

* Scaling Attack [10] scales a local update to increase its influence on the global update: 0.9$\hat{u}=c\cdot u, c \in \mathbb{R}_+$.

* Additive Noise Attack [53] adds Gaussian noise to the local update: 0.9$\hat{u}=u+\eta, \eta \sim \mathcal{N}(\sigma,\mu)$.

* Min-Max Attack [77] sets all the malicious updates to be: 0.9$\mathrm{argmax}_{\gamma}$ 0.9$\max_{i \in [n]}||\hat{u}-u_i||_2\leq \max_{i,j\in [n]}||u_i-u_j||_2; \hat{u}=\frac{1}{n}\sum_{i=1}^n u_i + \gamma\cdot u^p$,
where $u^p$ is a dataset optimized perturbation vector. Here, the adversary is assumed to have access to the benign (well-formed) updates of all clients.  This attack finds the malicious gradient
whose maximum distance from a benign gradient is less than
the maximum distance between any two benign gradient.

* Min-Sum Attack [77] sets all the malicious updates to be: 0.9$\mathrm{argmax}_{\gamma}$ 0.9$\sum_{i \in [n]}||\hat{u}-u_i||_2\leq \max_{i\in [n]}\sum_{j\in[n]}||u_i-u_j||_2; \hat{u}=\frac{1}{n}\sum_{i=1}^n u_i + \gamma\cdot u^p$, where $u^p$ is a dataset optimized perturbation vector. Here, the adversary is assumed to have access to the benign updates of all clients.
This attack finds the malicious gradient such that the
sum of its distances from all the other gradients is less than the sum of distances of any benign gradient from other benign

* Backdoor Attack-1 [85] classifies the digit seven as the digit one for EMNIST.

* Backdoor Attack-2 [5] classifies images of green cars as birds for CIFAR-10.
Configuration. We use the same  configuration as before. We implement the image-classification models in PyTorch. We randomly select 10K samples from each training set as the public dataset $\DP$ and train on the remaining samples. EMNIST is collected from 3383 clients with $\sim100$ images per client.
For all other datasets, the training set is divided into 5K subsets to create the local dataset for each client. For each training iteration, we sample the required number of data subsets out of these 5K subsets.

Fig. <ref> shows the accuracy of different image-classification models in . We set $n=100$ and $m=10\%$, and use random projection to project the updates to a dimension $d$ of 1K (MNIST, EMNIST), 5K (FMNIST), or 10K (CIFAR-10). For the two backdoor attacks, we consider $m=5\%$. Our experiment assesses how the random projection affects the efficacy of the integrity checks.  We observe that for MNIST (Figs. <ref>, <ref> and <ref>), EMNIST (Fig. <ref>) and FMNIST (Fig. <ref> and <ref>),  achieves performance comparable to a baseline that applies the defense (validation predicate) on the plaintext.
In most cases, the defenses retain their efficacy even after random projection. This is because they rely on computing inner products and norms of the update; these operations preserve their relative values after the projection with high probability [66].
We observe a drop in accuracy ($\sim7\%$) on CIFAR-10 (Figs. <ref> and <ref>) as updates for ResNet-20 with 273K parameters are projected to 10K.

The end-to-end per-iteration time $(m=10\%)$ for MNIST, EMNIST, FMNIST, and CIFAR-10 is $2.4s$ (Table <ref>), $2.4s$, $10.7s$, and $20.5s$, respectively.
The associated communication costs for the client are $13.3$MB,  $13.3$MB, $65.8$MB, and $132$MB (Fig. <ref>). Additional evaluation results are presented in Fig. <ref> (App. <ref>).

§ DISCUSSION

In this section, we discuss possible avenues for future research (additional discussion in App. <ref>).

Handling Higher Fraction of Malicious Clients. For 0.9$\lfloor \frac{n-1}{3}\rfloor < m$ 0.9$< \lfloor \frac{n-1}{2} \rfloor$ (honest majority), the current implementation of  can detect but not remove malformed inputs (Gao's decoding algorithm returns 0.9$\bot$ if  0.9$m>\lfloor \frac{n-1}{3}\rfloor$). Robust reconstruction in this case could be done via Guruswami-Sudan list decoder [59]. We do not do so in  because the reconstruction might fail  sometimes.

Handling Client Dropouts.  In practice, clients might have only sporadic access to connectivity and so, the protocol must be robust to clients dropping out.  can already accommodate malicious client dropping out – it is straightforward to extend this for the case of honest clients as well.

Identifying All Malicious Clients. Currently,  identifies a partial list of malicious clients. To detect all malicious clients, one can use: $(1)$  to identify all clients who have submitted at least one invalid share, and $(2)$ decoding algorithms such as Berlekamp-Welch [13] that can detect the location of the errors from the reconstruction.  We do not use them in  as they have higher computation cost.

Reducing Client's Computation. Currently, verifying the validity of the secret shares is the dominant cost for clients. This task can be offloaded to the server $\Ser$ by using a publicly verifiable secret sharing scheme () [73, 82, 86] where the validity of a secret share can be verified by any party.
However, typically  employs public key cryptography (which is costlier than symmetric cryptography) which might increase the end-to-end running time.

Additional Defense Strategies.  supports any defense strategy that can be expressed as a per-update anomaly detection mechanism (captured via the public validation predicate $\Vl(\cdot)$). A recent line of work [43, 52, 69, 71, 87, 89] proposes a complimentary style of defense which involves inspecting the final aggregate and the resulting model. For instance, Sparsefed [69] is a state-of-the-art backdoor defense where the server selects the top $k$ dimensions of the final aggregate and updates the model only along those dimensions (others are set to zero). CRFL [89] provides certified robustness against backdoor attacks by clipping and perturbing the final aggregate and performing parameter smoothing on the global model during testing.  Jia et al. [43] propose an ensemble learning mechanism where the server learns multiple global models on randomly selected subset of clients and takes majority vote among the global models for test-time prediction. Such defenses can be immediately integrated with  since the server has access to the final aggregate and the updated global model in the clear.

Towards poly-logarithmic complexity.  Currently,  dominant term in the complexity is $O(mnd)$ which results in a $O(n^2)$ dependence on $n$ (since we consider $m$ is a fraction of $n$). This can be reduced to $O(n\log^2 nd)$ by using the techniques from [9]. A detailed discussion is presented in App. <ref>.

§ RELATED WORK

Comparison of  with Related Work

2*Work     Malicious     Single     Removes      Arbritrary

Threat Model     Server     Malformed Inputs     Integrity Checks

He et.al [41]     $\times$      $\times$     $\times$      $\times$

FLGuard [67]     $\times$     $\times$     $\times$     $\times$

RoFL [23]      $\times$           $\times$     $\times$

BREA* [80]                    $\times$

aliceblue (Our)

*Has additional privacy leakage

Secure Aggregation. Prior work has addressed the problem of (non-Byzantine) secure aggregation in FL [17, 9, 3, 81]. A popular approach is to use pairwise random masking to protect the local updates [17, 3]. Advancements have been made in the communication overhead [48, 18, 81].

Robust Machine Learning.
A large number of studies have explored methods to make machine learners robust to Byzantine failures [5, 10, 45].
Many of these robust machine-learning methods require the learned to have full access to the training data or to fully control the training process [29, 39, 56, 79, 83, 88] which is infeasible in FL.
Another line of work has focused on the development of estimators that are inherently robust to Byzantine errors [15, 25, 68, 70, 94].
In our work, we target a set of methods that provides robustness by checking per-client updates  [15, 36, 78].

Verifying Data Integrity in Secure Aggregation.

Table <ref> compares  with prior work. There are three key differences between RoFL [23] and : $(1)$ RoFL is designed only for range checks with $\ell_2$ or $\ell_{\infty}$ norms. Specifically, RoFL uses Bulletproofs which is especially performant for range proofs (range proofs can be aggregated where one can prove that $n$ commitments lie within a given range by providing only an additive $O(log(n))$ group elements over the length of a single proof). RoFL's performance is primarily based on this aspect of Bulletproof and all of its optimizations work only for range proofs. As such RoFL cannot support any other checks with the same performance as currently reported in the paper. By contrast,  is a general framework that supports arbitrary validation predicates with good performance.
$(2)$ RoFL is susceptible to DoS attacks because it only detects malformed updates and aborts if it finds one. Specifically, the recovery of the final aggregate in RoFL requires a step of nonce cancellation that involves all the inputs by design. Hence, even if one of the input is invalid, the final aggregate will be ill-formed. By contrast,  is a  protocol that  detects and removes malformed updates in every round.
$(3)$ RoFL assumes an honest-but-curious server, whereas  considers a  malicious threat model.
BREA [80] also removes  outlying updates but, unlike , it leaks pairwise distances between inputs.
Alternative solutions [67, 41] for distance-based Byzantine-robust
aggregation uses two non-colluding servers in the semi-honest threat model, which is incompatible with FL.

§ CONCLUSION

Practical FL settings need to ensure both the privacy and integrity of model updates provided by the clients.
In this paper, we have formalized these goals in a new protocol, , that securely aggregates only well-formed inputs (i.e., updates).
To demonstrate the feasibility of , we have proposed : a system that efficiently instantiates a  protocol.

[1]

[2]
Youtube system requirements.

[3]
Gergely Ács and Claude Castelluccia.
I have a dream! differentially private smart metering.
In Proceedings of the 13th International Conference on
Information Hiding, IH'11, page 118–132, Berlin, Heidelberg, 2011.

[4]
Nir Ailon and Bernard Chazelle.
Approximate nearest neighbors and the fast johnson-lindenstrauss
In Proceedings of the Thirty-Eighth Annual ACM Symposium on
Theory of Computing, STOC '06, page 557–563, New York, NY, USA, 2006.
Association for Computing Machinery.

[5]
Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly
How to backdoor federated learning.
In arXiv:1807.00459, 2018.

[6]
Raef Bassily, Albert Cheu, Shay Moran, Aleksandar Nikolov, Jonathan Ullman, and
Zhiwei Steven Wu.
Private query release assisted by public data.
In ICML, 2020.

[7]
Donald Beaver.
Efficient multiparty protocols using circuit randomization.
In Joan Feigenbaum, editor, Advances in Cryptology — CRYPTO
'91, pages 420–432, Berlin, Heidelberg, 1992. Springer Berlin Heidelberg.

[8]
Amos Beimel, Aleksandra Korolova, Kobbi Nissim, Or Sheffet, and Uri Stemmer.
The power of synergy in differential privacy: Combining a small
curator with local randomizers.
In ITC, 2020.

[9]
James Henry Bell, Kallista A. Bonawitz, Adrià Gascón, Tancrède
Lepoint, and Mariana Raykova.
Secure single-server aggregation with (poly)logarithmic overhead.
In Proceedings of the 2020 ACM SIGSAC Conference on Computer and
Communications Security, CCS '20, page 1253–1269, New York, NY, USA, 2020.
Association for Computing Machinery.

[10]
Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo.
Analyzing federated learning through an adversarial lens.
In Proceedings of the International Conference on Machine
Learning, pages 634–643, 2019.

[11]
Abhishek Bhowmick, John C. Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan M.
Protection against reconstruction and its applications in private
federated learning.
ArXiv, abs/1812.00984, 2018.

[12]
Battista Biggio, Blaine Nelson, and Pavel Laskov.
Poisoning attacks against support vector machines.
In Proceedings of the International Coference on International
Conference on Machine Learning, pages 1467–1474, 2012.

[13]
Richard E. Blahut.
Theory and practice of error control codes.

[14]
P. Blanchard, E. M. E. Mhamdi, R. Guerraoui, and J. Stainer.
Byzantine-tolerant machine learning.
In arXiv:1703.02757, 2017.

[15]
Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer.
Machine learning with adversaries: Byzantine tolerant gradient
In Advances in Neural Information Processing Systems, pages
118–128, 2017.

[16]
Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex
Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečný, Stefano Mazzocchi,
H. Brendan McMahan, Timon Van Overveldt, David Petrou, Daniel Ramage, and
Jason Roselander.
Towards federated learning at scale: System design, 2019.

[17]
Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H. Brendan
McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth.
Practical secure aggregation for privacy-preserving machine learning.
In Proceedings of the ACM SIGSAC Conference on Computer and
Communications Security, pages 1175–1191, 2017.

[18]
Keith Bonawitz, Fariborz Salehi, Jakub Konecný, H. Brendan McMahan, and
Marco Gruteser.
Federated learning with autotuned communication-efficient secure
2019 53rd Asilomar Conference on Signals, Systems, and
Computers, pages 1222–1226, 2019.

[19]
Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai.
Zero-knowledge proofs on secret-shared data via fully linear pcps.
In CRYPTO, 2019.

[20]
Dan Boneh, Rosario Gennaro, Steven Goldfeder, Aayush Jain, Sam Kim, Peter M. R.
Rasmussen, and Amit Sahai.
Threshold cryptosystems from threshold fully homomorphic encryption.
In Advances in Cryptology – CRYPTO 2018: 38th Annual
International Cryptology Conference, Santa Barbara, CA, USA, August 19–23,
2018, Proceedings, Part I, page 565–596, Berlin, Heidelberg, 2018.

[21]
Gabriel Bracha and Sam Toueg.
Asynchronous consensus and broadcast protocols.
J. ACM, 32(4):824–840, oct 1985.

[22]
Zvika Brakerski, Craig Gentry, and Vinod Vaikuntanathan.
(leveled) fully homomorphic encryption without bootstrapping.
In Proceedings of the 3rd Innovations in Theoretical Computer
Science Conference, ITCS '12, page 309–325, New York, NY, USA, 2012.
Association for Computing Machinery.

[23]
Lukas Burkhalter, Hidde Lycklama, Alexander Viand, Nicolas Küchler, and
Anwar Hithnawi.
Rofl: Attestable robustness for secure federated learning.
In arXiv:2107.03311, 2021.

[24]
Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong.
Fltrust: Byzantine-robust federated learning via trust bootstrapping.

[25]
Lingjiao Chen, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos.
Draco: Byzantine-resilient distributed training via redundant
In Proceedings of the International Conference on Machine
Learning, 2018.

[26]
Xinyun Chen, Chang Liu, Bo Li, Kimberly Lu, and Dawn Song.
Targeted backdoor attacks on deep learning systems using data
In arXiv:1712.05526, 2017.

[27]
Gregory Cohen, Saeed Afshar, Jonathan Tapson, and André van Schaik.
Emnist: Extending mnist to handwritten letters.
In 2017 International Joint Conference on Neural Networks
(IJCNN), pages 2921–2926, 2017.

[28]
Henry Corrigan-Gibbs and Dan Boneh.
Prio: Private, robust, and scalable computation of aggregate
In Proceedings of the USENIX Symposium on Networked Systems
Design and Implementation, 2017.

[29]
Gabriela F. Cretu, Angelos Stavrou, Michael E. Locasto, Salvatore J. Stolfo,
and Angelos D. Keromytis.
Casting out demons: Sanitizing training data for anomaly sensors.
In IEEE Symposium on Security and Privacy (SP), pages 81–95,

[30]
Scott A. Crosby and Dan S. Wallach.
Efficient data structures for tamper-evident logging.
In Proceedings of the 18th Conference on USENIX Security
Symposium, SSYM'09, page 317–334, USA, 2009. USENIX Association.

[31]
Georgios Damaskinos, El Mahdi El Mhamdi, Rachid Guerraoui, Rhicheek Patra, and
Mahsa Taziki.
Asynchronous byzantine machine learning (the case of sgd).
In ICML, 2018.

[32]
W. Diffie and M. Hellman.
New directions in cryptography.
IEEE Transactions on Information Theory, 22(6):644–654, 1976.

[33]
El Mahdi El Mhamdi, Rachid Guerraoui, and Sébastien Rouault.
The hidden vulnerability of distributed learning in Byzantium.
In Jennifer Dy and Andreas Krause, editors, Proceedings of the
35th International Conference on Machine Learning, volume 80 of Proceedings of Machine Learning Research, pages 3521–3530. PMLR, 10–15 Jul

[34]
Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Zhenqiang Gong.
Local model poisoning attacks to byzantine-robust federated learning.
In USENIX Security Symposium, 2020.

[35]
Paul Feldman.
A practical scheme for non-interactive verifiable secret sharing.
In 28th Annual Symposium on Foundations of Computer Science
(sfcs 1987), pages 427–438, 1987.

[36]
Clement Fung, Chris J.M. Yoon, and Ivan Beschastnikh.
Mitigating sybils in federated learning poisoning.
In arXiv:1808.04866, 2018.

[37]
Shuhong Gao.
A New Algorithm for Decoding Reed-Solomon Codes, pages 55–68.
Springer US, Boston, MA, 2003.

[38]
Joachim von zur Gathen and Jrgen Gerhard.
Modern Computer Algebra.
Cambridge University Press, USA, 3rd edition, 2013.

[39]
Tianyu Gu, Brendan Dolan-Gavitt, and Siddharth Garg.
Badnets: Identifying vulnerabilities in the machine learning model
supply chain.
In arXiv:1708.06733, 2017.

[40]
Kaiming He, X. Zhang, Shaoqing Ren, and Jian Sun.
Deep residual learning for image recognition.
2016 IEEE Conference on Computer Vision and Pattern Recognition
(CVPR), pages 770–778, 2016.

[41]
Lie He, Sai Praneeth Karimireddy, and Martin Jaggi.
Secure byzantine-robust machine learning, 2020.

[42]
Aayush Jain, Peter M. R. Rasmussen, and Amit Sahai.
Threshold fully homomorphic encryption.
Cryptology ePrint Archive, Report 2017/257, 2017.

[43]
Jinyuan Jia, Xiaoyu Cao, and Neil Zhenqiang Gong.
Intrinsic certified robustness of bagging against data poisoning
In AAAI, 2021.

[44]
Peter Kairouz, Ziyu Liu, and Thomas Steinke.
The distributed discrete gaussian mechanism for federated learning
with secure aggregation.
ArXiv, abs/2102.06387, 2021.

[45]
Peter Kairouz, H. Brendan McMahan, Brendan Avent, Aurelien Bellet, Mehdi
Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham
Cormode, Rachel Cummings, Rafael G.L. D’Oliveira, Hubert Eichner, Salim El
Rouayheb, David Evans, Josh Gardner, Zachary Garrett, Adria Gascon, Badih
Ghazi, Phillip B. Gibbons, Marco Gruteser, Zaid Harchaoui, Chaoyang He, Lie
He, Zhouyuan Huo, Ben Hutchinson, Justin Hsu, Martin Jaggi, Tara Javidi,
Gauri Joshi, Mikhail Khodak, Jakub Konecny, Aleksandra Korolova, Farinaz
Koushanfar, Sanmi Koyejo, Tancrede Lepoint, Yang Liu, Prateek Mittal, Mehryar
Mohri, Richard Nock, Ayfer Ozgur, Rasmus Pagh, Hang Qi, Daniel Ramage, Ramesh
Raskar, Mariana Raykova, Dawn Song, Weikang Song, Sebastian U. Stich, Ziteng
Sun, Ananda Theertha Suresh, Florian Tramer, Praneeth Vepakomma, Jianyu Wang,
Li Xiong, Zheng Xu, Qiang Yang, Felix X. Yu, Han Yu, and Sen Zhao.
Advances and open problems in federated learning.
In arXiv:1912.04977, 2019.

[46]
Jonathan Katz and Yehuda Lindell.
Introduction to Modern Cryptography, Second Edition.
Chapman & Hall/CRC, 2nd edition, 2014.

[47]
Jakub Konečný, H. Brendan McMahan, Felix X. Yu, Peter
Richtárik, Ananda Theertha Suresh, and Dave Bacon.
Federated learning: Strategies for improving communication
CoRR, abs/1610.05492, 2016.

[48]
Jakub Konecný, H. Brendan McMahan, Felix X. Yu, Peter Richtárik,
Ananda Theertha Suresh, and Dave Bacon.
Federated learning: Strategies for improving communication
ArXiv, abs/1610.05492, 2016.

[49]
Alex Krizhevsky.
The cifar-10 dataset.

[50]
Y. Lecun, L. Bottou, Y. Bengio, and P. Haffner.
Gradient-based learning applied to document recognition.
Proceedings of the IEEE, 86(11):2278–2324, 1998.

[51]
Yann LeCun, Corinna Cortes, and Christopher J.C. Burges.
The mnist database of handwritten digits.

[52]
Alexander Levine and Soheil Feizi.
Provable adversarial robustness for fractional lp threat models.
In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera,
editors, International Conference on Artificial Intelligence and
Statistics, AISTATS 2022, 28-30 March 2022, Virtual Event, volume 151 of
Proceedings of Machine Learning Research, pages 9908–9942. PMLR,

[53]
Liping Li, Wei Xu, Tianyi Chen, Georgios Giannakis, and Qing Ling.
Rsa: Byzantine-robust stochastic aggregation methods for distributed
learning from heterogeneous datasets.
Proceedings of the AAAI Conference on Artificial Intelligence,
33:1544–1551, 07 2019.

[54]
Suyi Li, Yong Cheng, Wei Wang, Yang Liu, and Tianjian Chen.
Learning to detect malicious clients for robust federated learning.
CoRR, abs/2002.00211, 2020.

[55]
Shu Lin and Daniel J. Costello.
Error control coding: fundamentals and applications.
Pearson/Prentice Hall, Upper Saddle River, NJ, 2004.

[56]
Kang Liu, Brendan Dolan-Gavitt, and Siddharth Garg.
Fine-pruning: Defending against backdooring attacks on deep neural
pages 273–294, 2018.

[57]
Terrance Liu, Giuseppe Vietri, Thomas Steinke, Jonathan Ullman, and
Zhiwei Steven Wu.
Leveraging public data for practical private query release, 2021.

[58]
Wolfram Mathworld.
Lagrange interpolating polynomial.

[59]
R. J. McEliece.
The guruswami–sudan decoding algorithm for reed–solomon codes,

[60]
Brendan McMahan and Daniel Ramage.
Federated learning: Collaborative machine learning without
centralized training data, 2017.

[61]
H. Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and
Blaise Agüera y Arcas.
Communication-efficient learning of deep networks from decentralized
In Proceedings of the International Conference on Artificial
Intelligence and Statistics, 2017.

[62]
Shike Mei and Xiaojin Zhu.
Using machine teaching to identify optimal training-set attacks on
machine learners.
In Proceedings of the AAAI Conference on Artificial
Intelligence, pages 2871–2877, 2015.

[63]
Luca Melis, Congzheng Song, Emiliano De Cristofaro, and Vitaly Shmatikov.
Exploiting unintended feature leakage in collaborative learning.
In 2019 IEEE Symposium on Security and Privacy (SP), pages
691–706, 2019.

[64]
Mohammad Naseri, Jamie Hayes, and Emiliano De Cristofaro.
Local and central differential privacy for robustness and privacy in
federated learning, 2021.

[65]
Milad Nasr, Reza Shokri, and Amir Houmansadr.
Comprehensive privacy analysis of deep learning: Passive and active
white-box inference attacks against centralized and federated learning.
2019 IEEE Symposium on Security and Privacy (SP), May 2019.

[66]
Jelani Nelson.
Sketching algorithms.

[67]
Thien Duc Nguyen, Phillip Rieger, Hossein Yalame, Helen Möllering, Hossein
Fereidooni, Samuel Marchal, Markus Miettinen, Azalia Mirhoseini, Ahmad-Reza
Sadeghi, Thomas Schneider, and Shaza Zeitouni.
Flguard: Secure and private federated learning, 2021.

[68]
Xudong Pan, Mi Zhang, Duocai Wu, Qifan Xiao, Shouling Ji, and Zhemin Yang.
Justinian’s GAAvernor: Robust distributed learning with gradient
aggregation agent.
In USENIX Security, pages 1641–1658, 2020.

[69]
Ashwinee Panda, Saeed Mahloujifar, Arjun Nitin Bhagoji, Supriyo Chakraborty,
and Prateek Mittal.
Sparsefed: Mitigating model poisoning attacks in federated learning
with sparsification.
In Gustau Camps-Valls, Francisco J. R. Ruiz, and Isabel Valera,
editors, Proceedings of The 25th International Conference on Artificial
Intelligence and Statistics, volume 151 of Proceedings of Machine
Learning Research, pages 7587–7624. PMLR, 28–30 Mar 2022.

[70]
Shashank Rajput, Hongyi Wang, Zachary Charles, and Dimitris Papailiopoulos.
Detox: A redundancy-based framework for faster and more robust
gradient aggregation.

[71]
Elan Rosenfeld, Ezra Winston, Pradeep Ravikumar, and J. Zico Kolter.
Certified robustness to label-flipping attacks via randomized
In ICML, 2020.

[72]
Edo Roth, Daniel Noble, Brett Hemenway Falk, and Andreas Haeberlen.
Honeycrisp: Large-scale differentially private aggregation without a
trusted core.
In Proceedings of the 27th ACM Symposium on Operating Systems
Principles, SOSP '19, page 196–210, New York, NY, USA, 2019. Association
for Computing Machinery.

[73]
Berry Schoenmakers.
A simple publicly verifiable secret sharing scheme and its
application to electronic voting.
In In CRYPTO, pages 148–164. Springer-Verlag, 1999.

[74]
J. T. Schwartz.
Fast probabilistic algorithms for verification of polynomial
J. ACM, 27(4):701–717, October 1980.

[75]
Adi Shamir.
How to share a secret.
Commun. ACM, 22(11):612–613, November 1979.

[76]
Virat Shejwalkar and Amir Houmansadr.
Manipulating the byzantine: Optimizing model poisoning attacks and
defenses for federated learning.
In NDSS, 2021.

[77]
Virat Shejwalkar and Amir Houmansadr.
Manipulating the byzantine: Optimizing model poisoning attacks and
defenses for federated learning.
In NDSS, 2021.

[78]
Shiqi Shen, Shruti Tople, and Prateek Saxena.
Auror: Defending against poisoning attacks in collaborative deep
learning systems.
In ACM ACSAC, pages 508–519, 2016.

[79]
Yanyao Shen and Sujay Sanghavi.
Learning with bad training data via iterative trimmed loss
In International Conference on Machine Learning (ICML), pages
5739–5748, 2019.

[80]
Jinhyun So, Basak Guler, and A. Salman Avestimehr.
Byzantine-resilient secure federated learning.
IEEE Journal in Selected Areas in Communications: Machine
Learning in Communications and Networks, 2020.

[81]
Jinhyun So, Basak Guler, and A. Salman Avestimehr.
Turbo-aggregate: Breaking the quadratic aggregation barrier in secure
federated learning, 2021.

[82]
Markus Stadler.
Publicly verifiable secret sharing.
pages 190–199. Springer-Verlag, 1996.

[83]
Jacob Steinhardt, Pang Wei W. Koh, and Percy S. Liang.
Certified defenses for data poisoning attacks.
In Advances in Neural Information Processing Systems (NeurIPS),
pages 3517–3529, 2017.

[84]
Ziteng Sun, Peter Kairouz, Ananda Theertha Suresh, and H. Brendan McMahan.
Can you really backdoor federated learning?
In arXiv:1911.07963, 2019.

[85]
Ziteng Sun, Peter Kairouz, Ananda Theertha Suresh, and H. Brendan McMahan.
Can you really backdoor federated learning?
ArXiv, abs/1911.07963, 2019.

[86]
Chunming Tang, Dingyi Pei, and Zhuojun Liu Yong He.
Non-interactive and information-theoretic secure publicly verifiable
secret sharing.

[87]
Binghui Wang, Xiaoyu Cao, Jinyuan jia, and Neil Zhenqiang Gong.
On certifying robustness against backdoor attacks via randomized
smoothing, 2020.

[88]
Bolun Wang, Yuanshun Yao, Shawn Shan, Huiying Li, Bimal Viswanath, Haitao
Zheng, and Ben Y. Zhao.
Neural cleanse: Identifying and mitigating backdoor attacks in neural
In IEEE Symposium on Security and Privacy (SP), pages 707–723,

[89]
Chulin Xie, Minghao Chen, Pin-Yu Chen, and Bo Li.
Crfl: Certifiably robust federated learning against backdoor attacks.
In Marina Meila and Tong Zhang, editors, Proceedings of the 38th
International Conference on Machine Learning, volume 139 of Proceedings
of Machine Learning Research, pages 11372–11382. PMLR, 18–24 Jul 2021.

[90]
Chulin Xie, Keli Huang, Pin-Yu Chen, and Bo Li.
Dba: Distributed backdoor attacks against federated learning.
In ICLR, 2020.

[91]
Cong Xie.
Zeno++: robust asynchronous SGD with arbitrary number of byzantine
CoRR, abs/1903.07020, 2019.

[92]
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta.
Zeno: Distributed stochastic gradient descent with suspicion-based
In Proceedings of the International Conference on Machine
Learning, 2019.

[93]
Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta.
Zeno++: Robust fully asynchronous SGD.
In Proceedings of the International Conference on Machine
Learning, 2020.

[94]
Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett.
Byzantine-robust distributed learning: Towards optimal statistical
In International Conference on Machine Learning (ICML), 2019.

[95]
Hongxu Yin, Arun Mallya, Arash Vahdat, José Manuel Álvarez, Jan Kautz,
and Pavlo Molchanov.
See through gradients: Image batch recovery via gradinversion.
2021 IEEE/CVF Conference on Computer Vision and Pattern
Recognition (CVPR), pages 16332–16341, 2021.

[96]
Fashion mnist.

[97]
Ligeng Zhu, Zhijian Liu, and Song Han.
Deep leakage from gradients.
In NeurIPS, 2019.

[98]
Richard Zippel.
Probabilistic algorithms for sparse polynomials.
In Proceedings of the International Symposiumon on Symbolic and
Algebraic Computation, EUROSAM '79, page 216–226, Berlin, Heidelberg,
1979. Springer-Verlag.

§ APPENDIX

Symbol     Description

$n$     Total number of clients

$m$     Number of malicious clients

$\mathcal{S}$     Server

$\Cl_i$     $i$-th client

$D_i$     Private dataset of $\Cl_i$

$\Cl$     Set of all $n$ clients

$\Cl_H$     Set of $n-m$ honest clients

$\Cl_M$     Set of $m$ malicious clients

$\Vl(\cdot)$     Validation predicate

$\mathcal{M}$     Global model to be trained

$u_i$     Local update (gradient) of client $\Cl_i$

$\mathcal{U}$     Aggregate update

$\Cl_{\Vl}$     Set of clients  such that for all $\Cl_i \in \Cl_{\Vl}$, $\Vl(u_i)=1$

$\mathcal{U}_\Vl$     Aggregate of valid updates only $\mathcal{U}_\Vl = \sum_{\Cl_i\in \Cl_\Vl}u_i  $

$\kappa$     Security parameter

$(i,s_i)$     $i$-th Shamir's secret share for a secret $s\in \Fl$

$\Psi$     Check string for the verifiable secret sharing

$pp$     Public parameters of the cryptographic protocols

$pk$     Public key

$sk$     Secret key

$sk_{ij}$     Shared secret key between clients $\Cl_i$ and $\Cl_j$

$\mathcal{P}$     Prover in the SNIP protocol

$\mathcal{V}_i$     $i$-th verifier in the SNIP protocol

$\pi$     SNIP proof

$h/f/g$     Polynomials generated by $\Pro$ for the construction of $\pi$

$(a,b,c)$     Beaver's triplet generated by $\Pro$ for the construction of $\pi$

$[s]_i$     $i$-th additive secret share for a secret $s \in \Fl$

$w^{out}$      Value of the output wire of the circuit $\Vl(\cdot)$

$\sigma$     Proof summary broadcasted by the verifiers

$\Fl$     A prime field

$\Ml$      Number of multiplication gates in $\Vl(\cdot)$

$\Bl$     Public bulletin board

$\Cl_{\setminus i}$    Set of all clients except $\Cl_i$, $\Cl_{\setminus i} = \Cl\setminus \Cl_i$

$\CA$     List of malicious clients maintained by $\Ser$ in

$(j,s_{ij})$     Client $\Cl_j$'s (Shamir secret) share of client $\Cl_i$'s secret $s_i\in \Fl$ in

$\pi_i$     Client $\Cl_i$'s proof in

$h_i/f_i/g_i$     Polynomials generated by client $\Cl_i$ for the construction of $\pi_i$ in

$(a_i,b_i,c_i)$     Beaver's triplet generated by client $\Cl_i$ for the construction of $\pi_i$ in

$w^{out}_i$      Value of the output wire of the circuit $\Vl(u_i)$ for client $\Cl_i$

$\Psi_{\pi_i}$     Check string generated by client $\Cl_i$ for the shares of their proof $\pi_i$

$\Psi_{u_i}$     Check string generated by client $\Cl_i$ for the shares of their update $u_i$

$\sigma_{ji}$     Client $\Cl_j$'s shar of the summary for client $\Cl_i$'s proof  in

$\lambda_{ji}$     Client $\Cl_j$'s share of the random digest for client $\Cl_i$'s proof  in

$\lambda_{i}$     Client $\Cl_i$'s random digest reconstructed from the shares $\{\lambda_{ji}\}, j \in \Cl_{\setminus i}$
$\sigma_{i}$     Client $\Cl_i$'s proof summary reconstructed from the shares $\{\sigma_{ji}\}, j \in \Cl_{\setminus i}$

§.§ Building Blocks Cntd.

Arithmetic Circuit. An arithmetic circuit, 0.9$\mathcal{C}: \Fl^k\mapsto \Fl$, represents a computation over a finite field $\Fl$. It can be represented by a directed acyclic graph (DAG) consisting of three types of nodes: $(1)$ inputs, $(2)$ gates and $(3)$ outputs.
Input nodes have in-degree zero and out-degree one: the $k$ input nodes return input variables $\{x_1,\cdots,x_k\}$ with $x_i \in \Fl$.
Gate nodes have in-degree two and out-degree one; they perform either the $+$ operation (addition gate) or the $\times$ operation (multiplication gate).
Every circuit has a single output node with out-degree zero.
A circuit is evaluated by traversing the DAG, starting from the inputs, and assigning a value in $\Fl$ to every wire until the output node is evaluated.

Beaver's multiplication protocol. Beaver showed that the servers can use pre-computed
multiplication triples to evaluate multiplication gates [9].
A multiplication triple is a one-time-use triple of values
$(a, b, c) \in \Fl^3$, chosen at random subject to the constraint
that $a · b = c ∈ F$.  When used in the context of multi-party
computation, each verifier $\Ver_i$ holds a share $([a]i
, [b]i
, [c]i) ∈
3 $of the triple.
Using their shares of one such triple (a, b, c), the servers
can jointly evaluate shares of the output of a multiplication
gate yz. To do so, each server $i$ uses her shares [y]i and [z]i
of the input wires, along with the first two components of
its multiplication triple to compute the following values:
[d]i = [y]i − [a]i
; [e]i = [z]i − [b]i
Each server i then broadcasts [d]i and [e]i
. Using the
broadcasted shares, every server can reconstruct d and e
and can compute:
σi = de/s + d[b]i + e[a]i + [c]i
Recall that s is the number of servers—a public constant—
and the division symbol here indicates division (i.e., inversion then multiplication) in the field F. A few lines of
278 14th USENIX Symposium on Networked Systems Design and Implementation USENIX Association
arithmetic confirm that σi
is a sharing of the product yz.
To prove this we compute:
σi =

de/s + d[b]i + e[a]i + [c]i
= de + db + ea + c
= (y − a)(z − b) + (y − a)b + (z − b)a + c
= (y − a)z + (z − b)a + c
= yz − az + az − ab + c
= yz − ab + c
= yz.
The last step used that c = ab (by construction of the
multiplication triple), so: P
i σi = yz, which implies that
σi = [yz]i
Since the servers can perform addition and multiplication of shared values, they can compute any function of
the client’s data value in this way, as long as they have
a way of securely generating multiplication triples. The
expensive part of traditional MPC protocols is the process by which mutually distrusting servers generate these
triples in a distributed way.

Shamir's Secret Sharing Scheme. The scheme is additive, i.e., it allows addition of two secret shared values locally. Formally, for all $s,w \in \Fl$ and $Q\subseteq P, |Q|\leq t$:
\begin{gather}s+w\leftarrow \textsf{SS.recon}(\{(i,s_i+w_i)_{i\in Q}\})\end{gather}
Additionally, the scheme is a linear secret sharing scheme which means that any linear operations performed on the individual shares translates to operations performed on the secret, upon reconstruction. Specifically, for $Q \subseteq P, |Q|\geq t$ and $\alpha,\beta \in \Fl$:

\begin{gather}\alpha s+\beta\larrow\textsf{SS.recon}(\{(i,\alpha s_i+\beta)_{i\in Q}\})\end{gather}
This means that a party can perform linear operations on the secret locally.

Verifiable Secret Shares. To make the Shamir's Secret shares verifiable, we use Feldman's [35] VSS technique.
Let $c(x)=c_0+c_1x+\cdots c_{t-1}x^{t-1}$ denote the  polynomial used in generating the shares where $c_0=s$ is the secret.
The check string are the commitments to the coeffcients given by

\begin{gather}
\psi_i=g^{c_i} , i \in \{0,\cdots,t-1\}
\end{gather}

where $g$ denotes a generator of $\Fl$.  All arithmetic is taken
modulo $q$ such that $(p|q-1)$ where $p$ is the prime of $\Fl$.

For verifiying a share $(j,s_j)$, a party needs to check  whether $g^{s_j}=\prod_{i=0}^{t-1}\psi_i^{j^i}$.
The privacy of the secret $s=c_0$ is implied by the
the intractability of computing discrete
logarithms [35].

Short Non-Interactive Proofs (SNIP). Here, we detail the SNIP protocols. SNIP works in two stages as follows:

(1) Generation of Proof. The prover $\mathcal{P}$ evaluates the circuit $\Vl(\cdot)$ on its input $x$ to obtain the value that
every wire in the circuit takes on during the computation
of $\Vl(x)$. Using these wire values,  $\mathcal{P}$ constructs
three randomized polynomials $f$ , $g$, and $h$, which encode
the values of the input and output wires of each of the $\Ml$
multiplication gates in the computation of $\Vl(x)$.

Let us label the $M$  multiplication gates in the $\Vl(\cdot)$ circuit in the  topological order from inputs to outputs as $\{
1, \cdots , \Ml\}$. Let $u_t$ and $v_t$ denote the values on  the left and right input wires
of the $t$-th multiplication gate for $t \in [M]$. The prover $\mathcal{P}$ samples two values $u_0$ and $v_0$ uniformly at random from $\Fl$. $f$ and $g$ are defined to be the lowest degree polynomials such that $f(t) = u_t$ and $g(t) = v_t, \forall t \in [\Ml]$. Next, $h$ is defined as the polynomial
$h = f \cdot g$. The polynomials $f$ and $g$ has degree at most $M$
and the polynomial $h$ has degree at most $2\Ml$. It is easy to see that  $h(t)$ is
the value of the output wire $(u_t\cdot v_t)$ of the $t$-th
multiplication gate in the $ \Vl(x)$ circuit since $h(t) = f(t) \cdot g(t) = u_t\cdot v_t, \forall t \in [\Ml]$. The prover $\mathcal{P}$ can construct the polynomials $f$ and $g$ using polynomial interpolation and can multiply them
produce $h = f \cdot g$. Additionally, $\mathcal{P}$ samples a single set of Beaver's multiplication triples [7]: $(a,b,c)\in \Fl^3$ such that $a\cdot b = c \in \Fl$. Prover $\mathcal{P}$ constructs the proof share $[\pi]_i = \langle [f(0)]_i,[g(0)]_i,[h]_i,([a]_i,[b]_i,[c]_i)\rangle$ [Note that we omitted the terms $[f(0)]_i$ and  $[g(0)]_i$ from $\pi_i$ in Sec. <ref>  for the ease of exposition.] for verifier $\mathcal{V}_i$ by splitting:

* the random values $f(0) = u_0$ and $g(0) = v_0$, using
additive secret sharing,
* the coefficients of $h$ (denoted by $[h]_i$,  and

* the sampled Beaver's triplets $(a,b,c)$.

The prover then sends the respective shares of the input and the proof $( [x]_i, [\pi]_{i})$ to each of the verifiers $\Ver_i$.

(2) Verification of Proof. Using  $[x]_i$, the share of the provers's  private value $x$, and $[f(0)]_i$, $[g(0)]_i$, and $[h]_i$, each verifier $\Ver_i$ can locally (i.e., without communicating with the other verifiers/prover) produce shares $[f]_i$ and
$[g]_i$ of the polynomials $f$ and $g$ as follows:

* $\Ver_i$ reconstructs a share of every wire for the $\Vl(x)$ circuit. This is possible since $\Ver_i$ has access to $(1)$ a share of each of the input wire values $([x]_i)$ and $(2)$ a  share of each wire value coming out of a multiplication gate $([h]_i(t), t \in [\Ml]$ is a share of the $t$-th such wire). Hence, $\Ver_i$  can derive all other wire value shares via affine operations on the wire value shares it already has.

* Using these wire value shares and shares of $f(0)$
and $g(0)$,  $\Ver_i$  uses polynomial
interpolation to construct $[f]_i$ and $[g]_i$

To verify that $\Vl(x)=1$ and hence, accept the input $x$, the verifiers need to check two things:

* check the consistency of $\Pro$'s computation of $\Vl(x)$, and
* check that the value of final output wire of the computation, $\Vl(x)$, denoted by $w^{out}$ is indeed $1$.
For carrying out the above mentioned checks, the verifier $\Ver_i$ broadcasts a summary $\sigma_i=([w^{out}]_i,[\lambda]_i)$, where $[w^{out}]_i$ is $\Ver_i$'s share of the output wire and $[\lambda]_i$ is a share of a random digest that the verifier computes from the shares of the other wire values and the proof  share $\pi_i$. The details are discussed  as follows:

(2a) Checking the Consistency of $\Pro$'s Computation of $\Vl(x)$.
For honest provers and verifiers, the verifiers will now hold shares of polynomials $f$ , $g$, and $h$ such that $f \cdot g = h$.
In contrast, a malicious prover could have sent the
verifiers shares of a different polynomial $\hat{h}$ such that, for some
$t \in [M], hˆ(t)$ is not the value on the output wire in
the $t$-th multiplication gate of the $\Ver(x)$ circuit.
In this case, the verifiers end up reconstructing shares of polynomials $\hat{f}$ and $\hat{g}$ that might not be equal to $f$ and $g$. Then, we have $\hat{h}\neq  \hat{f} \cdot \hat{g}$ as explained below. Consider the least $t'$ for which $\hat{h}(t') \neq h(t')$. For all $t \leq t'$,
$\hat{f}(t) = f(t)$ and $g(t) = g(t)$, by construction. Since,

\begin{gather}
\hat{h}(t') \neq h(t') = f(t') \cdot g(t') = \hat{f}(t)' \cdot \hat{g}(t'),
\end{gather}

it must be that $\hat{h}(t') \neq \hat{f}(t') \cdot \hat{g}(t')$, so $\hat{h} \neq \hat{f} \cdot \hat{g}.$ The verifiers can employ the above check using the Schwartz-Zippel randomized polynomial identity test [74, 98] as explained later in this section.

(2b) Output Verification. In case all the verifiers are honest,  each $\Ver_i$
now holds a set of shares of the values of all the wires of the $\Vl(x)$ circuit. So to confirm that
$\Vl(x) = 1$, the verifiers need only broadcast their shares of
the output wire $w^{out}_i$. The verifiers can thus reconstruct its exact value from all the broadcasted shares $w^{out}=\sum_{i=1}^k [w^{out}]_i$ and check whether $w^{out}=1$, in which case  it must be that $\Vl(x) = 1$ (except with some small failure probability due to the polynomial identity test).

Polynomial Identity Test. Recall that each verifier $\Ver_i$
holds shares $[\hat{f}]_i$, $[\hat{g}]_i$ and $[\hat{h}]_i$
of the  polynomials $\hat{f}$ , $\hat{g}$ and $\hat{h}$. Furthermore, it holds that $\hat{f} \cdot \hat{g} = \hat{h}$
if and only the set of the wire value shares, held by the verifiers, sum up to the internal
wire values of the $\Vl(x)$ circuit computation.
The verifiers now execute a variant of the Schwartz-Zippel randomized polynomial identity test
to check whether this relation holds. The main idea of the test is that  if $\hat{f}(t) \cdot \hat{g}(t) \neq \hat{h}(t)$, then the polynomial
$t \cdot (\hat{f}(t) \cdot \hat{g}(t) - \hat{h}(t))$ is a non-zero polynomial of degree at
most $2\Ml + 1$. (The utility of multiplying the polynomial $\hat{f} \cdot \hat{g} - \hat{h}$ by $t$ is explained in the next paragraph)
Such a polynomial can have at
most $2\Ml + 1$ zeros in $\Fl$, so for a $r \in \Fl$ chosen at random
and after evaluating $r \cdot (
\hat{f}(r) \cdot \hat{g}(r) - \hat{h}(r))$, the verifiers will detect
that $\hat{f } \cdot \hat{g} \neq \hat{h}$ with probability at least $1 \frac{2\Ml+1}{|\Fl|}$.

For the polynomial identity test, one of the
verifiers samples a random value $r \in \Fl$ and broadcasts it. Each verifier $\Ver_i$ can locally compute the shares $[\hat{f}(r)]_i$, $[\hat{g}(r)]_i$, and $[\hat{h}(r)]_i$ since polynomial evaluation
requires only affine operations. $\Ver_i$ then
applies a local linear operation to these last two shares to
obtain the shares $[r \cdot \hat{g}(r)]_i$ and $[r \cdot \hat{h}(r)]_i$.

Multiplication of Shares. Note that  the verifiers need to securely multiply their shares  $[\hat{f}(r)]_i$ and $[r \cdot \hat{g}(r)]_i$
to get a share $[r \cdot
\hat{f}(r) \cdot \hat{g}(r)]_i$ without leaking anything
to each other about the values $\hat{f}(r)$ and $\hat{g}(r)$. This can be performed via the Beaver's MPC multiplication protocol (described later). Using this protocol, verifiers with access to one-time-use shares $([a]_i, [b]_i, [c]_i) \in \Fl^3$ of
random values such that $a \cdot b = c \in \Fl$ (“multiplication
triples”), can execute a
multi-party multiplication of a pair of secret-shared values.
For SNIPs, the prover $\mathcal{P}$ generates the multiplication triple on behalf of the verifiers and sends shares of
these values to each verifier. If $\mathcal{P}$ produces the shares
of these values correctly, then the verifiers can perform
a multi-party multiplication of shares to complete the
correctness check as discussed above. More importantly,
we can ensure that even if $\mathcal{P}$ sends
shares of an invalid multiplication triple,
the verifiers will still catch the cheating prover with high
probability. Let's assume that the cheating prover sends the
shares $([a]_i, [b], [c]i) \in \Fl^3$
such that $a \cdot b \neq c \in \Fl$.
Let $a \cdot b = (c + \alpha) \in \Fl$, for some constant
$\alpha > 0$. Executing the polynomial identity
test using the above triples will shift the result of the test by $\alpha$. So the verifiers will be effectively testing
whether the polynomial

\begin{gather}
\hat{Q}(t) = t \cdot (\hat{f}(t) \cdot \hat{g}(t) - \hat{h}(t)) + \alpha \end{gather}

is identically zero. Whenever $\hat{f} \cdot \hat{g} \neq \hat{h}$, it holds that
$t \cdot (\hat{f}(t) \cdot \hat{g}(t) - \hat{h}(t))$ is a non-zero polynomial. So, if
$\hat{f} \cdot \hat{g}\neq \hat{h}$, then $\hat{Q}(t)$ must also be a non-zero polynomial.
Note that the multiplying the term $"\hat{f}\cdot\hat{g}-\hat{h}"$ by $t$ ensures that whenever this expression is non-zero, the
resulting polynomial $\hat{Q}$ is guaranteed to be non-zero, even if $\hat{f}$ , $\hat{g}$, and $\hat{h}$ are
constants, and the prover chooses $\alpha$ adversarially. Since SNIP assumes honest verifiers, we may assume that the prover did not know
the random value $r$ while generating
its multiplication triple. This implies that $r$ is distributed
independently of $\alpha$ which means that we will catch a cheating prover with probability $1-\frac{2M+1}{|\Fl|}$.

Beaver's MPC Multiplication Protocol. SNIP uses  Beaver's
multiplication triples as follows.
A multiplication triple is a one-time-use triple of values
$(a, b, c) \in \Fl^3$, chosen at random subject to the constraint
that $a \cdot b = c \in \Fl$.  In SNIP,
computation, each verifier $\Ver_i$ holds a share $([a]_i, [b]_i, [c]_i) \in \Fl^3$ of the triple.
Using their shares of one such triple $(a, b, c)$, the verifiers
can jointly evaluate shares of the output of a multiplication
gate $yz$. To do so, each verifier  uses its shares $[y]_i$ and $[z]_i$
of the input wires, along with the first two components of
its multiplication triple to compute the following values:

\begin{gather}[d]_i = [y]_i - [a]_i
\\ [e]_i = [z]_i - [b]_i
\end{gather}

Each verifier $\Ver_i$  then broadcasts $[d]_i$ and $[e]_i$. Using the
broadcasted shares, every verifier can reconstruct $d$ and $e$
and can compute:

\begin{gather}[\lambda]_i = de/k + d[b]_i + e[a]_i + [c]_i
\end{gather}

Clearly, $\sum_{i=1}^k[\lambda]_i=yz$. Thus, this step requires a round of communication for the broadcast and three reconstructions for $d$, $e$ and $\lambda$.

For SNIPs on Shamir's secret shares, the verifier $\Ver_i$ compute the shares  $(i,\lambda_i)$ where $\lambda_i=de+db_i+ea_i+c_i$ which gives $yz\leftarrow \textsf{SS.recon}((i,\lambda_i))$.

As mentioned in Sec. <ref>, we can leverage the multiplicativity of Shamir's secret shares to generate $\lambda_i$ for client $\Cl_i$ locally. Specifically, each client can locally multiply the shares $(j,f_{ij})$ and $(j,g_{ij})$ to generate $(i,(f_j\cdot g_j)_i)$. In order to make the shares consistent, $\Cl_i$  multiplies the share of $(i,h_{ji})$ with $(i,z_i)$ where $z=1$ (these can be generated and shared by the server $\Ser$ in the clear). In this way, $\Cl_j$ can locally generate a share of the digest $(j,d_{ij})$ that correspond to a polynomial of degree $2m$. Since $m<\frac{n-1}{4}$, this optimization is still compatible with robust reconstruction. In this way, we save one round of communication and require only one reconstruction for $\lambda_i$ instead of three.

(Decisional Diffie-Hellman assumption).
Let $\mathcal{G}(\kappa) \rightarrow (G, g, q, H)$ be an efficient algorithm which
samples a group $G$ of order $q$ with generator $g$, as well as a
function $H : \{0, 1\}^* \mapsto \{0, 1\}^\kappa$. Consider the following probabilistic experiment, parameterized by a PPT adversary $\A$, a
bit $b$, and a security parameter $\kappa$.

* $(G, g, q, H) \leftarrow \mathcal{G}(\kappa)$

* $a \leftarrow \mathbb{Z}_q$; $A\leftarrow g^a$

* $b \leftarrow \mathbb{Z}_q; B\leftarrow g^b$

* if $b = 1, s\leftarrow H(g^{ab})$, else $s\leftarrow \{0, 1\}^k$

* $\A(G, g, q, H, A, B, s) \mapsto b'$

* Output $1$ if $b = b'$, $0$ otherwise.

The advantage of the adversary is defined as:

\begin{gather*}\hspace{-1cm}Adv^{\textsf{DDH}}_{\mathcal{G},\A}(\kappa) := \big|\mathrm{Pr}[ \textsf{DDH-Game}^{1}_{\mathcal{G},\A}(\kappa)=1]-\\\hspace{3cm}
\mathrm{Pr}[DDH-Game^{0}_{\mathcal{G},\A}(\kappa)=1]\big|
\end{gather*}

We say that the decisional Diffie-Hellman assumption holds
for $\mathcal{G}$ if for all PPT adversaries $\A$, there exists a negligible
function $\textsf{negl}(\cdot)$ such that $Adv^{\textsf{DDH}}_{\mathcal{G},\A}(\kappa) \leq \textsf{negl}(\kappa)$

§.§ Complexity Analysis

We present the complexity analysis of  in terms of the number of clients $n$, number of malicious clients $m$ and data dimension $d$ (Table <ref>).

Computation Cost.
Each client $\Cl_i$'s computation cost can be broken into six components: $(1)$ performing 0.9$n\!-\!1$ key agreements – 0.9$O(n)$; $(2)$ generating proof $\pi_i$ for 0.9$\Vl(u_i)=1$ – 0.9$O(|\Vl|+\Ml\log\Ml)$[We use standard discrete FFT for all polynomial operations [38].]; $(3)$ creating secret shares of the update $u_i$ and the proof $\pi_i$ – 0.9$O(mn(d+\Ml))$[This uses the fact that the Lagrange coefficients can be pre-computed [58].]; $(4)$ verifying the validity of the received shares – 0.9$O(mn(d+\Ml)$;  $(5)$ generating proof digest for all other clients – 0.9$O(n|\Vl|)$; and $(6)$ generating shares of the final aggregate – 0.9$O(nd)$. Assuming 0.9$|\Vl|$ is of the order of 0.9$O(d)$, the overall computation complexity of each client $\Cl_i$ is 0.9$O(mnd)$.
The server $\Ser$'s computation costs can be divided into three parts: $(1)$ verifying the validity of the flagged shares – 0.9$O(md\min(n,m^2))$; $(2)$ verifying the proof digest for all clients – 0.9$O(n^2\log^2n\log\log n)$; and $(3)$ computing the final aggregate – 0.9$O(dn\log^2n\log\log n)$. Hence, the total computation complexity of the server is 0.9$O\big((n+d)n\log^2n\log \log n$ 0.9$+md\min(n,m^2)\big)$.

Communication Cost.  The communication
cost of each client $\Cl_i$ has seven components: $(1)$ exchanging keys with all other clients – 0.9$O(n)$; $(2)$ receiving 0.9$\Vl(\cdot)$ – 0.9$O(|\Vl|)$; $(3)$ sending encrypted secret shares and check strings for all other clients – 0.9$O(n(d+\Ml)+md)$; $(4)$ receiving encrypted secret shares and check strings from all other clients – 0.9$O(n(d+\Ml)+mnd)$; $(5)$ sending proof digests for every other client – 0.9$O(n)$; $(6)$ receiving the list of corrupt clients $\Cl$ – 0.9$O(m)$; and $(7)$ sending the final aggregate – 0.9$O(d)$. Thus, the communication complexity for every client is 0.9$O(mnd)$.

The servers communication costs include: $(1)$ sending the validation predicate – 0.9$O(|\Vl|)$; $(2)$
receiving check strings and secret shares from flagged clients – 0.9$O(md\min(n,m^2))$; $(3)$ receiving proof digests – 0.9$O(n^2)$; $(4)$ sending the list of malicious clients – 0.9$O(m)$; and $(5)$ receiving the shares of the final aggregate – 0.9$O(nd)$. Hence, the overall communication complexity of the server is 0.9$O(n^2+md\min(n,m^2))$.
The total number of one-way communication is $12$ and $9$ for the clients and server, respectively, independent of the complexity of the validation predicate.

§.§ Proof for Lemma <ref>

In Round 3, the proof corresponding to a  client $\Cl_i$ is verified iff it has submitted valid shares for the $n\!-\!m\!-\!1$ honest clients $\Cl_H\setminus \Cl_i$. This is clearly true if $\Cl_i$ is honest. If $\Cl_i$ is malicious, i.e., it submitted at least one invalid share:

* Case 1: 0.9$|\textsf{Flag}[i]|\geq m+1$. It is clear that $\Cl_i$ has submitted an invalid share to at least one honest client and, hence, is removed from the rest of the protocol.

* Case 2: 0.9$|\textsf{Flag}[i]|\leq m$. All honest clients in $\Cl_H$ will be flagging $\Cl_i$. Hence, $\Cl_i$ either has to submit the corresponding valid shares or be removed from the protocol.
Given $n\!-\!m\!-\!1$ valid shares, using Fact 2, we know that  reconstructs the proof summary for $\Cl_i$ correctly. Eq. <ref> then follows from the soundness property of SNIP.

§.§ Proof for Lemma <ref>

In Round 2, observe that the shares $(j,u_{ij}), (j,\pi_{ij})$ for each client $\Cl_j \in \Cl_{\setminus i}$ are encrypted with the pairwise secret key and distributed. Hence, a collusion of $m$ malicious clients (and the server $\Ser$)[The server does not have access to any share of its own in .] can access at most $m$ shares of any honest client $\Cl_i\in \Cl_H$. This is true even in Round 3 where:

* A malicious client might falsely flag $\Cl_i$.

* No honest client in $\Cl_H\setminus \Cl_i$ will flag $\Cl_i$ since they would be receiving valid shares (and their encryptions) from $\Cl_i$.

* $\Ser$ cannot lie about who flagged who, since everything is logged publicly on the bulletin $\Bl$.
Thus, only $m$ shares of $\Cl_i$ can be revealed which correspond to the $m$ malicious clients.

Since at least $m+1$ shares are required to recover the secret, any instantiation of the SNIP verification protocol (i.e., reconstruction of the values of $\sigma_i=(w^{out}_i,\lambda_i)$) requires at least one honest client to act as the verifier. Hence, at the end of Round 3, from Fact 1 and the zero-knowledge property of SNIP, the only information revealed is that $\Vl(u_i)=1$.

§.§ Security Proof

Given a public validation predicate 0.9$\Vl(\cdot)$, security parameter 0.9$\kappa$, set of $m$ malicious clients $\Cl_M, \lfloor m<\frac{n-1}{3}\rfloor$ and a malicious server $\Ser$, there exists a probabilistic polynomial-time (P.P.T.) simulator $\textsf{Sim}(\cdot)$ such that:
\begin{gather*}\textsf{Real}_{\name}\big(\{u_{\Cl_H}\}, \Omega_{\Cl_M\cup\Ser}\big)\equiv_C\textsf{Sim}\big(\Omega_{\Cl_M\cup \Ser},\Ul_H,\Cl_H\big)\\\mbox{where }\Ul_H=\sum_{\Cl_i\in \Cl_H}u_i.\end{gather*}
$\{u_{\Cl_H}\}$ denotes the input of all the honest clients, $\textsf{Real}_\name$ denotes a random variable representing the joint view of all the parties in 's execution,  $\Omega_{\Cl_M\cup\Ser}$ indicates a polynomial-time algorithm implementing
the “next-message” function of the parties in $\Cl_M\cup\Ser$,
and $\equiv_C$ denotes computational indistinguishability.
We prove the theorem by a standard hybrid argument. Let $\Omega_{\Cl_M\cup \Ser}$ indicate the polynomial-time algorithm that denotes
the “next-message” function of parties in $\Cl_M\cup \Ser$. That is, given a
party identifier $c \in \Cl_M\cup \Ser$, a round index $i$, a transcript $T$ of all
messages sent and received so far by all parties in
$\Cl_M\cup \Ser$, joint
randomness $r_{\Cl_M\cup \Ser}$ for the corrupt parties’ execution, and access