# ScionFL: Secure Quantized Aggregation for Federated Learning

Yaniv Ben-Itzhak  VMWare Research  0000-0002-3844-5940 Helen Möllering
Technical University of Darmstadt  0000-0001-9371-3592 Benny Pinkas  Bar-Ilan
University  0000-0002-9053-3024 Thomas Schneider  Technical University of
Darmstadt  0000-0001-8090-1316 Ajith Suresh  Technical University of Darmstadt
0000-0002-5164-7758 Oleksandr Tkachenko  DFINITY Foundation
0000-0001-9232-6902 Shay Vargaftik  VMWare Research  0000-0002-0982-7894
Christian Weinert  Royal Holloway, University of London  0000-0003-4906-6871
Hossein Yalame  Technical University of Darmstadt  0000-0001-6438-534X Avishay
Yanai  VMWare Research  0000-0003-4060-0150

###### Abstract

Privacy concerns in federated learning (FL) are commonly addressed with secure
aggregation schemes that prevent a central party from observing plaintext
client updates. However, most such schemes neglect orthogonal FL research that
aims at reducing communication between clients and the aggregator and is
instrumental in facilitating cross-device FL with thousands and even millions
of (mobile) participants. In particular, quantization techniques can typically
reduce client-server communication by a factor of 32$\times$.

In this paper, we unite both research directions by introducing an efficient
secure aggregation framework based on outsourced multi-party computation (MPC)
that supports any linear quantization scheme. Specifically, we design a novel
approximate version of an MPC-based secure aggregation protocol with support
for multiple stochastic quantization schemes, including ones that utilize the
randomized Hadamard transform and Kashin’s representation. In our empirical
performance evaluation, we show that with no additional overhead for clients
and moderate inter-server communication, we achieve similar training accuracy
as insecure schemes for standard FL benchmarks.

Beyond this, we present an efficient extension to our secure quantized
aggregation framework that effectively defends against state-of-the-art
untargeted poisoning attacks.

##  1 Introduction

Federated learning (FL) [89], where in each training round a subset of clients
locally updates a global model that is then centrally aggregated, quickly
became a leading paradigm for large-scale distributed machine learning
training with decentralized data due to its promises of data privacy, resource
efficiency, and ability to handle dynamic participants.

However, in terms of  _privacy_ , the central aggregator learns the individual
client updates in the clear and thus can infer sensitive details about the
clients’ private input data [90, 104, 53, 114, 125]. Hence, many secure
aggregation schemes, e.g., [23, 51, 94], have been developed, where the
central aggregator only learns the aggregation result, i.e., the global model
(we refer the reader to [65, 98] for a discussion of differential privacy as
another paradigm to protect privacy in FL). Most prominently, in the “SegAgg”
protocol [23], clients exchange masks with peers to blind their model updates
such that the masks cancel out during aggregation and reveal only the exact
result. However, this approach requires an interactive setup between clients
and thus is less reliable when dealing with real-world problems such as client
dropouts (except for special variants [128, 64, 81]).

In terms of  _resource efficiency_ of plain FL, clients have to send parameter
updates (also known as gradients), which typically consist of thousands or
millions of coordinates with one floating point number per coordinate. For
cross-device FL involving mobile clients with limited upload bandwidth, this
quickly becomes infeasible when dealing with increasingly large model
architectures, where gradients consist of millions of coordinates. Therefore,
quantization schemes that exploit the noise resiliency of gradient-based FL
methods (e.g., federated averaging [89]) have been proposed to significantly
compress client updates (typically replacing the representation of each
coordinate by a single bit, instead of a 32-bit floating point number), e.g.,
[120, 28, 123, 4, 11, 17, 111].

Unfortunately, so far the ML and security research communities have mostly
worked individually on optimizing FL in terms of secure aggregation for
privacy and quantization for resource efficiency. One of the very few
exceptions is a work [33] that combines the SegAgg approach with sketching
[108] for compression of gradients. Besides the mentioned disadvantage of
SegAgg, their work considers only a single compression method. However, due to
the trade-offs between accuracy and computational efficiency provided by
different forms of quantization, which become especially relevant for
gradients with millions of coordinates, it is important to have a modular
approach.

In our work, we instead enable secure aggregation on quantized client updates
considering a distributed aggregator to avoid a single point of trust. In this
model, clients apply information-theoretically secure and computationally
efficient secret-sharing techniques to distribute their sensitive updates
among multiple servers such that none of the servers learns any information
except for the final aggregation result. This model is well established in
other recent works on secure aggregation (that do not consider quantized
inputs) due to its manifold performance benefits [97, 94] and as it does not
require an interactive setup between clients. We additionally emphasize that
it corresponds well to trending multi-cloud and sky computing strategies
[117], where organizations simultaneously utilize multiple infrastructure
providers, which potentially also operate in different jurisdictions, thereby
reducing the risk of having to disclose sensitive user data even upon
receiving subpoena requests. Furthermore, this distributed computing model is
useful when multiple organizations want to cooperate to jointly train with
clients.

###  1.1 Our Contributions

In this paper, we make several contributions to enable efficient secure
aggregation for FL with a distributed aggregator on  _quantized_ client
updates.

  1. 1.

Minimal Client Communication. Most importantly, our secure aggregation
framework, which we call ScionFL, incurs _no_ additional overhead in terms of
client communication (modulo a small constant number of bytes) compared to
insecure quantized schemes. We support a range of state-of-the-art
quantization schemes, thereby allowing for use-case specific optimizations in
terms of accuracy and run-time.

For this, we rely on outsourced multi-party computation (MPC), where clients
secret-share their sensitive (quantized) model updates among servers that use
interactive cryptographic protocols to securely compute the aggregation and
then return the updated global model.

  2. 2.

Unbiased Approximated Aggregation for Minimizing Inter-server Communication.
Since network traffic is costly even among powerful servers [59], we further
optimize inter-server communication by studying _approximate_ MPC variants
that exploit the noise tolerance of FL and might be of independent interest.
Specifically, we extend a SPDZ-style dishonest majority MPC protocol [42] with
an approximate conversion of Boolean-shared bit values to arithmetically-
shared fixed point values. We formally prove that our resulting secure
aggregation scheme is an unbiased estimator of the arithmetic mean and explore
trade-offs between efficiency and accuracy that arise. Besides secure
aggregation for FL, we point out that our approximate conversion approach can
also result in significant performance improvements for systems such as PRIO
[36], which is deployed by the ISRG [1], and PRIO+ [2], that currently rely on
expensive exact conversions for privacy-preserving aggregation of user
statistics.

  3. 3.

Benchmarking Framework. We implement a combined end-to-end FL evaluation and
MPC simulation environment. It allows to assess the performance and accuracy
of our solution for various stochastic quantization schemes, including recent
state-of-the-art distributed mean estimation techniques utilizing the
randomized Hadamard transform [120] and Kashin’s representation [28].

Our results demonstrate that standard FL benchmarks’ accuracy is barely
impacted while our approximation and optimizations can significantly reduce
inter-server communication. For example, when training the LeNet architecture
for image classification on the MNIST data set [80] using $1$-bit stochastic
quantization with Kashin’s representation [28], training accuracy is only
slightly reduced from $99.04\%$ to $98.71\%$ after 1000 rounds, while inter-
server communication drops from $16.44$GB to $0.94$GB compared to naive MPC-
based secure aggregation when considering 500 clients per round, an
improvement by factor $17.51\times$.

  4. 4.

Untargeted Poisioning Defense. Since a minority of clients may act maliciously
and try to degrade accuracy with their updates, we additionally design an
efficient defense mechanism, which builds upon ScionFL to ensure the
robustness of our framework. Our novel bipartite defense ScionFL-Aura defends
against state-of-the-art untargeted poisoning attacks [112], combining
magnitude clipping and directional filtering based on the gradients’
approximate L2-norms and cosine distances. Our optimizations and
approximations enable a highly efficient realization in MPC.

In our empirical evaluation, we also implement and reproduce the results of
the state-of-the-art  _Min-Max_ untargeted poisoning attack [112]. We can show
that ScionFL-Aura effectively diminishes the impact of the attack with $20\%$
malicious clients: it consistently filters out most of the manipulated updates
and reduces the attack impact to less than $5\%$ for almost all training
iterations when quantization is in place.

###  1.2 Related Work

We present a summary of the most relevant related works here, with a more
comprehensive discussion in App. A.

Compression Techniques. To reduce communication costs, there are three main
directions for gradient compression in cross-device FL: (1) gradient
sparsification (e.g., [50, 116, 3, 73]), (2) client-side memory and error-
feedback (e.g., [111, 4, 106, 18]), and (3) entropy encodings (e.g., [120,
122, 4]). Reviews of current state-of-the-art gradient compression techniques
and some open challenges can be found in [65, 73, 124].

Secure Aggregation & Model Inference Attacks. Several works [22, 79, 96] have
shown the susceptibility of FL to inference attacks extracting confidential
information about the used private training data. Secure aggregation [23, 36,
51, 15, 33] effectively defends against those attacks by prohibiting access to
individual updates. However, existing schemes incur significant computation
and communication overhead [51]. To the best of our knowledge, only Chen et
al. [33] and Beguier et al. [14] combine gradient compression with secure
aggregation. While [33] combines sketching [108] with differential privacy and
the SegAgg protocol [23], the work of [14] combines quantization [17] with
additive secret-sharing, but with non-optimal client-server communication
overhead. More detailed comparisons among secure aggregation schemes for FL
can be found in [51, 87].

Poisoning Attacks & Defenses. Next to privacy issues, FL has also been shown
vulnerable to manipulations by malicious clients [9, 10, 49, 112, 131].
Targeted attacks (also called backdoor attacks) aim at manipulating the
inference results for specific attacker-chosen input samples [9, 131]. In
contrast, untargeted poisoning attacks [10, 49, 112] reduce the accuracy of
the global model in general. As untargeted attacks are considered to be more
severe (given they are harder to detect, cf. §5), we focus on untargeted
attacks in the scope of this work.

##  2 Problem Statement

In this section, we define the precise problem of secure quantized aggregation
for FL, which we address in our work. For doing so, we first introduce the
necessary preliminaries on FL and quantization schemes, formalize the
functionality we want to compute securely, and finally define our threat and
system model for common (cross-device) FL scenarios.

###  2.1 Aggregation for Federated Learning

Google introduced federated learning (FL) as a distributed machine learning
(ML) paradigm in 2016 [73, 89]. In FL, $N$ data owners collaboratively train a
ML model $G$ with the help of a central aggregator $\mathsf{S}$ while keeping
their input data  _locally private_. In each training iteration $t$, the
following three steps are executed:

  1. 1.

The server $\mathsf{S}$ randomly selects $\mathsf{n}$ out of $N$ available
clients and provides the most recent global model $G^{t}$.

  2. 2.

Each selected client $\mathsf{C}_{i}$, $i\in[\mathsf{n}]$, sets its local
model $w_{i}^{t+1}=G^{t}$ and improves it using its local dataset $D_{i}$ for
$E$ epochs (i.e., local optimization steps):

$\displaystyle w_{i}^{t+1}\leftarrow
w_{i}^{t+1}-\eta_{\mathsf{C}_{i}}\frac{\partial
L(w_{i}^{t+1},B_{i,e})}{\partial w_{i}^{t+1}},$ (1)

where $L$ is a loss function, $\eta_{\mathsf{C}_{i}}$ is the clients’ learning
rate, and $B_{i,e}\subseteq D_{i}$ is a batch drawn from $D_{i}$ in epoch $e$,
where $e\in[E]$. After finishing the local training, $\mathsf{C}_{i}$ sends
its local update $w_{i}^{t+1}$ to $\mathsf{S}$.

  3. 3.

The server updates to a new global model $G^{t+1}$ by combining all
$w_{i}^{t+1}$ with an aggregation rule $f_{\textit{agg}}$:

$\displaystyle G^{t+1}\leftarrow G^{t}-\eta_{\mathsf{S}}\cdot
f_{\textit{agg}}(w_{1}^{t+1},\ldots,w_{\mathsf{n}}^{t+1}),$ (2)

where $\eta_{\mathsf{S}}$ is the server’s learning rate. The most commonly
used aggregation rule, which we also focus on, is $\mathsf{FedAvg}$ [89]. It
averages the local updates as follows:

$\displaystyle\mathsf{FedAvg}(w_{1}^{t+1},\ldots,w_{\mathsf{n}}^{t+1})=\sum_{i=1}^{\mathsf{n}}\frac{|D_{i}|}{\mathsf{n}}w_{i}^{t+1}$
(3)

This process is repeated until some stopping criterion is met (e.g., a fixed
number of training iterations or a certain accuracy is reached).

###  2.2 Stochastic Quantization

Quantization is a central building block in FL, where data transmission over
the network is often a bottleneck. Thus, compressing the (thousands or
millions of) gradients is essential to adhere to client bandwidth constraints,
reducing training time, and allowing better inclusion and scalability. We now
review desired properties and constructions of quantization schemes that will
play a key role in our system design.

Unbiasedness. A well-known and desired design property of gradient compression
techniques is being unbiased. That is, for an estimate $\hat{w}$ of a gradient
$w\in\mathbb{R}^{d}$, being unbiased means that $\mathbb{E}[\hat{w}]=w$.
Unbiasedness is desired because it guarantees that the mean’s estimation mean
squared error (MSE) decays linearly with respect to the number of clients,
which can be substantial in FL. In FL and other optimization techniques based
on stochastic gradient descent (SGD) and its variants (e.g., [89, 83, 67]),
the MSE measure (or normalized MSE, a.k.a. NMSE, cf. §3.2) is indeed the
quantity of interest since it affects the convergence rate and often the final
accuracy of the models. In fact, provable convergence rates for the non-convex
compressed SGD-based algorithms have a linear dependence on the NMSE.
Accordingly, to keep the estimates unbiased, modern quantization techniques
employ stochastic quantization (SQ) and its variants to compress the
gradients.

1-bit SQ. Our focus is on the appealing communication budget of a single bit
for each gradient entry, resulting in a 32$\times$ compression ratio compared
to regular 32-bit floating point entries. Indeed using 1-bit quantization has
been the focus of many recent works concerning distributed and FL network
efficiency (e.g., [123, 17, 121, 111, 61]). These works repeatedly
demonstrated that a budget of 1-bit per coordinate is sufficient to achieve
model accuracy that is competitive to that of a non-compressed baseline.

In particular, 1-bit SQ (i.e., SQ using two quantization values) can be done
as follows: For a vector $X$ with $m$ dimensions, the client sends each
coordinate as
$\sigma_{i}=\textit{Bernoulli}(\frac{X_{i}-\mathsf{s}_{X}^{min}}{\mathsf{s}_{X}^{max}-\mathsf{s}_{X}^{min}})$,
where $\mathsf{s}_{X}^{max}=\max(X)$ and $\mathsf{s}_{X}^{min}=\min(X)$. It is
then reconstructed by the receiver as
$\vec{{X}}_{\sigma}^{i}=\mathsf{s}_{X}^{min}+\vec{\sigma}_{X}^{i}\cdot(\mathsf{s}_{X}^{max}-\mathsf{s}_{X}^{min})$.
This simple technique results in an unbiased quantization as desired, i.e.,
$\mathds{E}[\vec{{X}}_{\sigma}^{i}]=\mathds{E}[\mathsf{s}_{X}^{min}+\vec{\sigma}_{X}^{i}\cdot(\mathsf{s}_{X}^{max}-\mathsf{s}_{X}^{min})]=X_{i}$.
However, SQ-based techniques’ MSE is known to be sensitive to gradient
coordinates’ range (i.e., the difference between the largest and smallest
coordinates, $\mathsf{s}_{X}^{max}-\mathsf{s}_{X}^{min}$). Generally, and
specifically in FL, neural network gradients are constantly increasing in size
and can have significant differences in the magnitude of the different
coordinates (e.g., several orders of magnitude).

Pre-processing via Random Rotations. To deal with possible limitations of
vanilla SQ, recent state-of-the-art works suggest to  _randomly rotate_ the
input vector prior to SQ [120]. That is, the clients and the aggregator draw
rotation matrices according to some known distribution; the clients then send
the quantization of the rotated vectors while the aggregator applies the
inverse rotation on the estimated rotated vector. Intuitively, the coordinates
of a randomly rotated vector are identically distributed, and thus the
expected difference between the coordinates is smaller, allowing for a more
accurate quantization. For $\mathsf{n}$ clients and a gradient with
$\mathsf{m}$ coordinates, this approach achieves a NMSE111The normalized MSE
is the mean’s estimate MSE normalized by the mean clients’ gradient squared
norms of $O(\frac{\log\mathsf{m}}{\mathsf{n}})$ using $O(\mathsf{m})$ bits,
which asymptotically improves over the $O(\frac{\mathsf{m}}{\mathsf{n}})$ NMSE
bound of vanilla SQ. The computational complexity, on the other hand, is
increased from $O(\mathsf{m})$ to $O(\mathsf{m}\log\mathsf{m})$ when utilizing
the randomized Hadamard transform for rotations.

Pre-processing via Kashin’s Representation. The rotation approach was recently
improved using Kashin’s representation [28, 85, 109]. Roughly speaking, it
allows representing an $\mathsf{m}$-dimensional vector using a slightly larger
vector with $\lambda\cdot\mathsf{m}$ smaller coefficients ($\lambda>1$). It
can be shown that applying SQ to the Kashin coefficients allows for an optimal
NMSE of $O(\frac{1}{\mathsf{n}})$ using $O(\lambda\cdot\mathsf{m})$ bits.
Compared with [120], Kashin’s representation yields a lower NMSE bound by a
factor of $\log\mathsf{m}$ at the cost of increasing the computational
complexity by the same factor [12, 28].

Other Approaches. We acknowledge the existence of additional recent advances
in gradient quantization (e.g., [123, 122, 43, 12]). However, these techniques
do not allow aggregating gradients in their compressed form and therefore are
less applicable to our framework.

Linear SQ Techniques. A key requirement of being able to perform secure
aggregation  _efficiently_ is being able to aggregate client gradients in
their compressed (i.e., quantized) form. A natural way to achieve this is
using “global scales”. Namely, prior to quantization, clients securely learn
the maximal and the minimal value across all gradients, i.e., each client uses
$\mathsf{s}^{max}=\max_{c}\\{\mathsf{s}_{X_{c}}^{max}\\}$ and
$\mathsf{s}^{min}=\min_{c}\\{\mathsf{s}_{X_{c}}^{min}\\}$222This approach
resembles “scaler sharing” in TernGrad [126].. This way, summing the
compressed vectors (i.e., their $\sigma$ indicators) and then decompressing
the sum (i.e., scaling) is equal to decompressing each vector individually
(i.e., scaling) and then computing their sum. Hereinafter, quantization
techniques having this property are called “linear”.

The “global scales” approach is appealing due to its simplicity. However, it
has several drawbacks: (1) it requires a preliminary communication stage, (2)
it reveals the global extreme values (even if they are computed securely
across all clients), and (3) the reconstruction error (i.e., the NMSE) is
increased as it now depends on the extreme values across all round
participants. Accordingly, we also consider a second approach where each
client continues to use its own “local scales”. Since plainly using individual
scales is not “linear”, i.e., it does not allow for aggregating the quantized
gradients efficiently without decoding them, to realize this approach, we use
a known approximation [14] and adapt it to our setting (cf. §4.1.3).

While in this work we focus on the mentioned vanilla SQ, SQ with random
rotation as well as SQ with Kashin’s representation, our framework seamlessly
supports any “linear” quantization scheme, namely, any quantization technique
that allows for aggregation in a compressed form.

###  2.3 MPC for Secure Aggregation

Secure computation in the form of multi-party computation (MPC) allows a set
of parties to privately evaluate any efficiently computable function on
confidential inputs. This paradigm can be utilized to securely run the FedAvg
aggregation algorithm [51, 97, 94, 45]: The set of selected FL clients uses
information-theoretically secure additive secret sharing to distribute their
sensitive inputs among a set of MPC servers, which resemble a distributed
aggregator. The MPC servers securely add the received shares and reconstruct
the public result from the resulting shares. In the next iteration, the public
model is distributed to a new set of clients chosen at random, and the process
is repeated until the desired accuracy is attained. A visualization of this
outsourced MPC setting for secure aggregation is provided in Fig. 1.

Client $C_{i}$2\. Compute
$\textit{agg}=$$\mathsf{FedAvg}(w_{1}^{t+1},\ldots,w_{\mathsf{n}}^{t+1})$1\.
$\langle w_{i}^{t+1}\rangle_{1}$1\. $\langle w_{i}^{t+1}\rangle_{2}$1\.
$\langle w_{i}^{t+1}\rangle_{3}$3\. $G^{t+1}\leftarrow
G^{t}-\eta_{\mathsf{S}}\cdot\textit{agg}$ Figure 1: Secure aggregation in FL
for $\mathsf{n}$ clients using outsourced MPC; $\langle
w_{i}^{t+1}\rangle_{j}$ denotes share $j$ of gradient $w_{i}^{t+1}$ that
client $C_{i}$ has in round $t+1$; $G^{t}$ is the model of the previous round
and $\eta_{\mathsf{S}}$ the server-side learning rate.

In the remainder of this paper, we work towards a secure aggregation for FL
using FedAvg on  _quantized_ inputs. In the following, we give our assumptions
in terms of the threat model and refine the description of our system model.

Semi-Honest Servers. The MPC servers are assumed to be semi-honest. This
means, they follow the protocol specification, but may try to learn additional
information from the protocol messages that they receive. This well-
established assumption [6, 63, 91, 97, 100, 21, 57] is motivated by the fact
that companies who run FL with a secure aggregation scheme try to actively
protect their clients’ data but want to make sure that someone who breaks into
their systems cannot get plaintext access to the data that is being processed.
Additionally, this assumption is justified as organizations usually cannot
afford the reputational and monetary risk when being caught betraying their
users’ trust. The protocols that we design provide this security guarantee in
a dishonest majority setting, where data is protected even when an adversary
$\mathcal{A}$ corrupts more than $50\%$ of the involved servers.

Malicious Clients. On the contrary, we consider that some clients might behave
maliciously by negatively affecting the quality of the global model with
manipulated updates (known as poisoning attacks, cf. §5). This assumption
stems from the fact that there are significantly less incentives for clients
to behave honestly. Also, due to the sheer number of clients in cross-device
FL, it is hard to verify their reputation.

Preprocessing Model. We focus mainly on MPC in the preprocessing model [42,
40, 70, 13, 41]. This means, we try to shift as much computation and
communication as possible to a  _data-independent preprocessing_ or  _offline_
phase that can be executed at an arbitrary point in time before the actual
computation. This gives several advantages. For example, in a cloud
environment, service providers can exploit cheap spot instances. Furthermore,
it guarantees faster results when the  _data-dependent online phase_ of the
protocol is executed.

Shared Randomness. We assume that clients and MPC servers have access to a
shared randomness source, e.g., by agreeing on a PRNG seed. Such a
configuration has been widely employed in MPC protocols [6, 52, 31, 92, 75] as
well as in ML systems [120, 11] to optimize communication.

###  2.4 Secure Quantized Aggregation

To introduce the problem of secure quantized aggregation, without loss of
generality, we consider a simple stochastic binary quantization scheme to
begin with. In this scheme, a $\mathsf{m}$-dimensional vector of the form
$\vec{X}=\\{x_{1},\ldots,x_{\mathsf{m}}\\}$ comprising of $\ell$-bit values
will be quantized to obtain a triple
$\vec{{X}}_{\sigma}=(\vec{\sigma}_{X},\mathsf{s}_{X}^{min},\mathsf{s}_{X}^{max})$.
Here, $\vec{\sigma}_{X}$ is an $\mathsf{m}$-dimensional binary vector with a
zero at an index indicating the value $\mathsf{s}_{X}^{min}$ and a one
indicating the value $\mathsf{s}_{X}^{max}$. Also, $\mathsf{s}_{X}^{min}$ and
$\mathsf{s}_{X}^{max}$ correspond to the minimum and maximum values in the
vector $\vec{X}$. With this binary quantization, the quantized value at the
$i$th dimension, denoted by $\vec{{X}}_{\sigma}^{i}$, can be written as

$\vec{{X}}_{\sigma}^{i}=\mathsf{s}_{X}^{min}+\vec{\sigma}_{X}^{i}\cdot(\mathsf{s}_{X}^{max}-\mathsf{s}_{X}^{min}).$
(4)

See §2.2 for more concrete details of the scheme. Before going into the
details of aggregation, we provide some of the basic notation that will be
utilized throughout the paper.

Notation. $\vec{\mathbf{Y}}_{\sf\alpha\times\beta}$ denotes a matrix of
dimension $\alpha\times\beta$ with $\vec{\mathbf{Y}}_{i}$ being the $i$th row
and $\vec{\mathbf{Y}}^{j}$ being the $j$th column. An element in the $i$th row
and $j$th column is denoted by ${\mathbf{Y}}_{i}^{j}$. Also, ${\sf
Agg\mbox{-}R}(\vec{\mathbf{Y}}_{\sf\alpha\times\beta})$ returns a row vector
corresponding to an aggregate of the rows of $\vec{\mathbf{Y}}$. Likewise,
${\sf Agg\mbox{-}C}(\vec{\mathbf{Y}}_{\sf\alpha\times\beta})$ returns an
aggregate of the columns of $\vec{\mathbf{Y}}$.

Given $\vec{\mathbf{U}}_{\sf\alpha\times\beta}$ and
$\vec{\mathbf{V}}_{\sf\alpha\times 1}$, we use
$\vec{\mathbf{U}}\circ\vec{\mathbf{V}}$ to denote the column-wise Hadamard
product. Similarly, $\vec{\mathbf{U}}\oplus\vec{\mathbf{V}}$ denote the sum of
two matrices in a column-wise fashion. Concretely, for
$\vec{\mathbf{M}}_{\sf\alpha\times\beta}=\vec{\mathbf{U}}\circ\vec{\mathbf{V}}$
and
$\vec{\mathbf{N}}_{\sf\alpha\times\beta}=\vec{\mathbf{U}}\oplus\vec{\mathbf{V}}$,
we have

${\mathbf{M}}_{i}^{j}={\mathbf{U}}_{i}^{j}\cdot{\mathbf{V}}_{i}^{1}~{}~{}~{}\text{and}~{}~{}~{}{\mathbf{N}}_{i}^{j}={\mathbf{U}}_{i}^{j}+{\mathbf{V}}_{i}^{1},~{}~{}~{}\text{where
}i\in[\alpha],j\in[\beta].$

Quantized Aggregation. To perform aggregation on quantized inputs, a set of
$\mathsf{n}$ clients first locally prepares their quantized triples,
$(\vec{\sigma}_{X},\mathsf{s}_{X}^{min},\mathsf{s}_{X}^{max})$, corresponding
to their locally trained ML model updates (i.e., gradients) and submits to a
parameter server for aggregation. Let $\mathsf{m}$ be the dimension of the
underlying ML model. The quantized triples can then be consolidated to a
matrix triple of the form
$(\vec{\mathbf{B}}_{\sf\mathsf{n}\times\mathsf{m}},\vec{\mathbf{U}}_{\sf\mathsf{n}\times
1},\vec{\mathbf{V}}_{\sf\mathsf{n}\times 1})$. Here, $\vec{\mathbf{B}}$ is a
binary matrix that corresponds to the $\vec{\sigma}_{X}$ vector of the
clients. Similarly, $\vec{\mathbf{U}}$ and $\vec{\mathbf{V}}$ correspond to
the $\mathsf{s}_{X}^{min}$ and $\mathsf{s}_{X}^{max}$ values of the above-
mentioned triple. The aggregate of the quantized inputs is defined as

$\vec{\mathbf{X}}_{\sf 1\times\mathsf{m}}={\sf
Agg\mbox{-}R}\left(\vec{\mathbf{U}}_{\sf\mathsf{n}\times 1}\ ~{}\oplus~{}\
\vec{\mathbf{B}}_{\sf\mathsf{n}\times\mathsf{m}}\circ(\vec{\mathbf{V}}_{\sf\mathsf{n}\times
1}-\vec{\mathbf{U}}_{\sf\mathsf{n}\times 1})\right).$ (5)

Ideal Functionality. To address the aforementioned problem using secure
computation in the form of MPC, we model it as an ideal functionality
$\mathcal{F}_{\mathsf{SecAgg}}$, which is provided in Fig. 2.4. We consider a
set of $\tau$ servers to which the clients secret-share their quantized
updates and the goal is to compute the aggregate of the inputs as shown in Eq.
5. Let $\langle\cdot\rangle$ denote the underlying secret sharing scheme.
Looking ahead, we will use linear secret sharing techniques for MPC, in which
linear operations such as addition and subtraction are local. As a result, we
will concentrate on efficiently computing the column-wise Hadamard product.

$\mathcal{F}_{\mathsf{SecAgg}}$ interacts with all the $\tau$ servers in
$\mathcal{S}$ and an adversary $\mathcal{A}$ that controls a subset of the
servers in $\mathcal{S}$. Input: $\mathcal{F}_{\mathsf{SecAgg}}$ receives
$\langle\cdot\rangle$-shares of the matrix triple of the form
$(\vec{\mathbf{B}}_{\sf\mathsf{n}\times\mathsf{m}},\vec{\mathbf{U}}_{\sf\mathsf{n}\times
1},\vec{\mathbf{V}}_{\sf\mathsf{n}\times 1})$ from the honest servers in
$\mathcal{S}$, while the adversary $\mathcal{A}$ provides the
$\langle\cdot\rangle$-shares on behalf of the corrupt servers. Here
${\mathbf{B}}_{i}^{j}\in\\{0,1\\}$ and
${\mathbf{U}}_{i}^{j},{\mathbf{V}}_{i}^{j}\in\mathbb{Z}_{2^{\ell}}$.
Computation: $\mathcal{F}_{\mathsf{SecAgg}}$ reconstructs
$(\vec{\mathbf{B}},\vec{\mathbf{U}},\vec{\mathbf{V}})$ from its
$\langle\cdot\rangle$-shares. – Set $\vec{\mathbf{S}}_{\sf\mathsf{n}\times
1}=\vec{\mathbf{V}}_{\sf\mathsf{n}\times
1}-\vec{\mathbf{U}}_{\sf\mathsf{n}\times 1}$ and compute
$\vec{\mathbf{W}}_{\sf\mathsf{n}\times\mathsf{m}}=\vec{\mathbf{B}}_{\sf\mathsf{n}\times\mathsf{m}}\circ\vec{\mathbf{S}}_{\sf\mathsf{n}\times
1}$. – Compute
$\vec{\mathbf{X}}_{\sf\mathsf{n}\times\mathsf{m}}=\vec{\mathbf{U}}_{\sf\mathsf{n}\times
1}\oplus\vec{\mathbf{W}}_{\sf\mathsf{n}\times\mathsf{m}}$. – Compute
$\vec{\mathbf{Y}}_{\sf 1\times\mathsf{m}}={\sf
Agg\mbox{-}R}(\vec{\mathbf{X}}_{\sf\mathsf{n}\times\mathsf{m}})$, i.e.,
$\vec{\mathbf{Y}}^{j}=\sum_{i=1}^{\mathsf{n}}{\mathbf{X}}_{i}^{j}$ for
$j\in[\mathsf{m}]$. Output: $\mathcal{F}_{\mathsf{SecAgg}}$ computes
$\langle\cdot\rangle$-shares of $\vec{\mathbf{Y}}$ and sends the respective
shares to the servers in $\mathcal{S}$. Figure 2: Ideal functionality for
semi-honest secure quantized aggregation for linear stochastic binary
quantization.

##  3 Basic Approach

As a warm-up, we start with solving a simplified secure quantized aggregation
problem. For this, we assume that all the clients use the same set of scales
for quantization, denoted by $\mathsf{s}_{G}^{min}$ and
$\mathsf{s}_{G}^{max}$. In this case, it is sufficient to compute

$\vec{\mathbf{X}}_{\sf 1\times\mathsf{m}}=\mathsf{s}_{G}^{min}\ ~{}\oplus~{}\
{\sf
Agg\mbox{-}R}\left(\vec{\mathbf{B}}_{\sf\mathsf{n}\times\mathsf{m}}\right)\circ(\mathsf{s}_{G}^{max}-\mathsf{s}_{G}^{min})$
(6)

as the aggregation result. This corresponds to the “global scales” approach
discussed in §2.2. When $\mathsf{s}_{G}^{min}=0$ and $\mathsf{s}_{G}^{max}=1$,
this can also be viewed as an instance of privacy-preserving aggregate
statistics computation, as demonstrated in the works of Prio [36] and Prio+
[2].

The Problem of Share Conversion. For all of the operations required to compute
Eq. (6) (i.e., addition, subtraction, and multiplication), there are well-
known and efficient MPC protocols available. However, one difficulty arises
from the fact that for minimal communication overhead, in a simple additive
secret sharing scheme, clients will share the binary matrix
$\vec{\mathbf{B}}_{\sf\mathsf{n}\times\mathsf{m}}$ over $\mathbb{Z}_{2}$,
meaning each bit $\mathsf{b}$ will be split into $\tau$ Boolean shares
$\mathsf{b}_{1},\dots,\mathsf{b}_{\tau}$ such that
$\mathsf{b}=\mathsf{b}_{1}\oplus\dots\oplus\mathsf{b}_{\tau}$. This way, for
each bit in $\vec{\mathbf{B}}_{\sf\mathsf{n}\times\mathsf{m}}$, each client
only has to transfer a single bit to each MPC server. (We will later discuss
how the client-server communication in our setting can be reduced from $\tau$
bits to a single bit.) Unfortunately, to perform the operation ${\sf
Agg\mbox{-}R}$ over secret-shared values, the MPC servers first must convert
these Boolean-shared bits into arithmetic shares over a larger ring
$\mathbb{Z}_{2^{\ell}}$. Prior works solve this problem either by using a
naive and costly standard conversion technique [2] or require the clients to
provide inputs already in arithmetically shared form [14], which we want to
avoid due to the targeted cross-device FL setting where low client-server
communication overhead is crucial.

In this section, we first discuss the naive standard conversion technique and
focus on how to optimize the communication and computation costs using an
_approximate_ method. We later describe our full system considering private
local scales and further optimizations in §4.

###  3.1 Secure Bit Aggregation

This section discusses methods for computing as well as estimating a bit’s
value and generating its arithmetic sharing from its Boolean shares. To begin
with, consider the case of bit $\mathsf{b}$ represented using two Boolean
shares $\mathsf{b}_{1},\mathsf{b}_{2}\in\\{0,1\\}$, such that
$\mathsf{b}=\mathsf{b}_{1}\oplus\mathsf{b}_{2}$. Note that when embedding
$\mathsf{b}_{1}$ and $\mathsf{b}_{2}$ in a larger field/ring333The bit (either
$0$ or $1$) is treated as a ring element in $\mathbb{Z}_{2^{\ell}}$ in our
protocols., it holds that
$\mathsf{b}=\mathsf{b}_{1}+\mathsf{b}_{2}-2\mathsf{b}_{1}\mathsf{b}_{2}$.
Similarly, for
$\mathsf{b}=\mathsf{b}_{1}\oplus\mathsf{b}_{2}\oplus\mathsf{b}_{3}$,
$\mathsf{b}=\mathsf{b}_{1}+\mathsf{b}_{2}+\mathsf{b}_{3}-2\mathsf{b}_{1}\mathsf{b}_{2}-2\mathsf{b}_{1}\mathsf{b}_{3}-2\mathsf{b}_{2}\mathsf{b}_{3}+4\mathsf{b}_{1}\mathsf{b}_{2}\mathsf{b}_{3}$
holds true. In fact, this concept can be generalized to an arbitrary number of
shares, denoted by $\mathsf{q}$, as discussed below. For
$\mathsf{b}=\oplus_{i=1}^{\mathsf{q}}\mathsf{b}_{i}$, let
$\mathcal{Q}=\\{\mathsf{b}_{i}\\}_{i\in[\mathsf{q}]}$ denote the set of all
$\mathsf{q}$ shares of $\mathsf{b}$, and $\tilde{\mathsf{b}}_{i}$ the
arithmetic equivalent of the share $\mathsf{b}_{i}$. Let $2^{\mathcal{Q}}$ be
the powerset of $\mathcal{Q}$ and $\mathcal{Q}^{|c|}$ the set of all size-$c$
subsets in $2^{\mathcal{Q}}$, that is,
$2^{\mathcal{Q}}=\sum_{i=0}^{q}\mathcal{Q}^{|i|}$. The arithmetic equivalent
of $\mathsf{b}$, denoted by $\tilde{\mathsf{b}}$, is given as

$\displaystyle\tilde{\mathsf{b}}$
$\displaystyle=\smashoperator[]{\sum_{\\{\mathsf{b}_{e}\\}\in\mathcal{Q}^{|1|}}^{}}\tilde{\mathsf{b}}_{e}~{}-~{}2~{}\cdot~{}\smashoperator[]{\sum_{\\{\mathsf{b}_{e_{1}},\mathsf{b}_{e_{2}}\\}\in\mathcal{Q}^{|2|}}^{}}\tilde{\mathsf{b}}_{e_{1}}\tilde{\mathsf{b}}_{e_{2}}~{}+~{}4~{}\cdot~{}\smashoperator[]{\sum_{\\{\mathsf{b}_{e_{1}},\mathsf{b}_{e_{2}},\mathsf{b}_{e_{3}}\\}\in\mathcal{Q}^{|3|}}^{}}\tilde{\mathsf{b}}_{e_{1}}\tilde{\mathsf{b}}_{e_{2}}\tilde{\mathsf{b}}_{e_{3}}\ldots+(-2)^{\mathsf{q}-1}~{}\cdot~{}\smashoperator[]{\prod_{\\{\mathsf{b}_{e_{1}},\ldots,\mathsf{b}_{e_{q}}\\}\in\mathcal{Q}^{|q|}}^{}}\tilde{\mathsf{b}}_{e}$
$\displaystyle=\sum\limits_{k=1}^{\mathsf{q}}(-2)^{k-1}\smashoperator[]{\sum_{\\{\mathsf{b}_{e_{1}},\ldots,\mathsf{b}_{e_{k}}\\}\in\mathcal{Q}^{|k|}}^{}}\tilde{\mathsf{b}}_{e_{1}}\tilde{\mathsf{b}}_{e_{2}}\ldots\tilde{\mathsf{b}}_{e_{k}}$
(7)

For the analysis, we divide Eq. (3.1) into three terms: Sum
($\mathsf{term_{s}}$), Middle ($\mathsf{term_{m}}$), and Product
($\mathsf{term_{p}}$) as shown in Eq. (8) below. (Note that
$\mathcal{Q}^{|q|}=\mathcal{Q}$).

$\tilde{\mathsf{b}}=\underbrace{\smashoperator[]{\sum_{\\{\mathsf{b}_{e}\\}\in\mathcal{Q}^{|1|}}^{}}\tilde{\mathsf{b}}_{e}}_{\text{Sum
Term}:~{}\mathsf{term_{s}}}+\underbrace{\sum\limits_{k=2}^{\mathsf{q}-1}(-2)^{k-1}\smashoperator[]{\sum_{\\{\mathsf{b}_{e_{1}},\ldots,\mathsf{b}_{e_{k}}\\}\in\mathcal{Q}^{|k|}}^{}}\tilde{\mathsf{b}}_{e_{1}}\tilde{\mathsf{b}}_{e_{2}}\ldots\tilde{\mathsf{b}}_{e_{k}}}_{\text{Middle
Term}:~{}\mathsf{term_{m}}}+\underbrace{(-2)^{\mathsf{q}-1}\prod\limits_{\mathsf{b}_{e}\in\mathcal{Q}}\tilde{\mathsf{b}}_{e}}_{\text{Product
Term}:~{}\mathsf{term_{p}}}$ (8)

Our Approach. Performing this conversion in MPC requires many additions and
multiplications. While linear operations like additions can be calculated for
“free” in most MPC protocols, non-linear operations such as multiplications
require some form of communication between the MPC servers. Hence, computing
the middle term is costly, especially when there is a large number of shares
involved. Instead, we investigate a novel approximation approach: To
approximate $\tilde{\mathsf{b}}$ in Eq. (8), we keep the sum and product terms
unchanged and replace only the middle term. At a high level, the idea is to
replace $\mathsf{term_{m}}$ in Eq. (8) with its expected value
$\mathds{E}[\mathsf{term_{m}}]$ (that depends on $\mathsf{q}$) such that the
approximate value of $\tilde{\mathsf{b}}$, denoted by $\hat{\mathsf{b}}$,
retains $\mathds{E}[\hat{\mathsf{b}}]=\mathsf{b}$. The expectation of
$\mathsf{term_{s}}$ and $\mathsf{term_{p}}$ in Eq. (8) is first calculated,
and $\mathds{E}[\mathsf{term_{m}}]$ is inferred using the fact that
$\mathds{E}[\hat{\mathsf{b}}]=\mathsf{b}$. This analysis is summarised in Lem.
3.1.

######  Lemma 3.1 (Expected Values).

Given a bit $\mathsf{b}=\oplus_{i=1}^{\mathsf{q}}\mathsf{b}_{i}$ and
$b=\mathsf{term_{s}}+\mathsf{term_{m}}+\mathsf{term_{p}}$ with

$\displaystyle\mathsf{term_{s}}$
$\displaystyle=\smashoperator[]{\sum_{\\{\mathsf{b}_{e}\\}\in\mathcal{Q}^{|1|}}^{}}\tilde{\mathsf{b}}_{e},~{}~{}\mathsf{term_{m}}=\sum\limits_{k=2}^{\mathsf{q}-1}(-2)^{k-1}\smashoperator[]{\sum_{\\{\mathsf{b}_{e_{1}},\ldots,\mathsf{b}_{e_{k}}\\}\in\mathcal{Q}^{|k|}}^{}}\tilde{\mathsf{b}}_{e_{1}}\tilde{\mathsf{b}}_{e_{2}}\ldots\tilde{\mathsf{b}}_{e_{k}},$
$\displaystyle\mathsf{term_{p}}$
$\displaystyle=(-2)^{\mathsf{q}-1}\prod\limits_{\mathsf{b}_{e}\in\mathcal{Q}}\tilde{\mathsf{b}}_{e},$

we have $\mathds{E}[\mathsf{term_{s}}\mid\mathsf{b}]=\mathsf{q}/2$,
$\mathds{E}[\mathsf{term_{m}}\mid\mathsf{b}]=(\mathsf{q}\mbox{-}1)\
\mathrm{mod}\ 2-\mathsf{q}/2$, and
$\mathds{E}[\mathsf{term_{p}}\mid\mathsf{b}]=\mathsf{b}-(\mathsf{q}\mbox{-}1)\
\mathrm{mod}\ 2$.

###### .

For the analysis, we use the truth table of $\mathsf{b}$, denoted by
$T_{\mathsf{b}}$, which has $2^{\mathsf{q}}$ rows. Half of the rows in
$T_{\mathsf{b}}$ correspond to $\mathsf{b}=0$, while the other half correspond
to $\mathsf{b}=1$. The truth table for three shares ($\mathsf{q}=3$) is given
in Tab. 1 as a reference.

$\mathsf{b}$ | $\mathsf{b}_{1}$ | $\mathsf{b}_{2}$ | $\mathsf{b}_{3}$ | $\mathsf{term_{s}}$ | $\mathsf{term_{m}}$ | $\mathsf{term_{p}}$ | $\tilde{\mathsf{b}}$
---|---|---|---|---|---|---|---
0 | 0 | 0 | 0 | 0 | 0 | 0 | 0
1 | 0 | 0 | 1 | 1 | 0 | 0 | 1
1 | 0 | 1 | 0 | 1 | 0 | 0 | 1
0 | 0 | 1 | 1 | 2 | -2 | 0 | 0
1 | 1 | 0 | 0 | 1 | 0 | 0 | 1
0 | 1 | 0 | 1 | 2 | -2 | 0 | 0
0 | 1 | 1 | 0 | 2 | -2 | 0 | 0
1 | 1 | 1 | 1 | 3 | -6 | 4 | 1

Table 1: Truth table for
$\mathsf{b}=\mathsf{b}_{1}\oplus\mathsf{b}_{2}\oplus\mathsf{b}_{3}$. The rows
corresponding to $\mathsf{b}=0$ are highlighted. $\tilde{\mathsf{b}}$ denotes
the arithmetic equivalent of $\mathsf{b}$.

_Sum Term $(\mathsf{term_{s}})$:_ For each row of the form
$(\mathsf{b}_{1},\ldots,\mathsf{b}_{\mathsf{q}})$ in $T_{\mathsf{b}}$,
$\mathsf{term_{s}}$ equals
$\tilde{\mathsf{b}}_{1}+\ldots+\tilde{\mathsf{b}}_{\mathsf{q}}$, which can be
interpreted as the number of $\tilde{\mathsf{b}}_{i}$’s selected out of the
$\mathsf{q}$ possible. Furthermore, there are a total of
$\binom{\mathsf{q}}{k}$ rows with sums equal to $k$, with $k$ being odd
corresponding to the row for $\mathsf{b}=1$ and $k$ being even corresponding
to the row for $\mathsf{b}=0$. As a result, given $\mathsf{b}=0$, the
expectation of the sum term can be calculated as the product of
$1/2^{\mathsf{q}-1}$ (corresponding to rows in $T_{\mathsf{b}}$ with
$\mathsf{b}=0$) and the sum of terms of the form $k\cdot\binom{\mathsf{q}}{k}$
with $k$ being even. Using Lem. B.1 in App. B.1, we get

$\displaystyle\mathds{E}[\mathsf{term_{s}}\mid(\mathsf{b}=0)]$
$\displaystyle=\frac{1}{2^{\mathsf{q}-1}}\cdot\sum\limits_{k=0}^{\lfloor\mathsf{q}/2\rfloor}2k\binom{\mathsf{q}}{2k}=\frac{1}{2^{\mathsf{q}-1}}\cdot\mathsf{q}\cdot
2^{\mathsf{q}-2}=\mathsf{q}/2.$

Similarly, we obtain
$\mathds{E}[\mathsf{term_{s}}\mid(\mathsf{b}=1)]=\mathsf{q}/2$. To summarize,
we have $\mathds{E}[\mathsf{term_{s}}\mid\mathsf{b}]=\mathsf{q}/2$.

_Product Term $(\mathsf{term_{p}})$:_ The product of all the $\mathsf{q}$
shares will be $1$ only if all the shares are $1$, otherwise it will be $0$.
Moreover, all shares of $\mathsf{b}$ being $1$ correspond to $\mathsf{b}=1$ if
$\mathsf{q}$ is odd, and $\mathsf{b}=0$ otherwise. Now, when $\mathsf{q}$ is
odd then $\mathsf{term_{p}}=(-2)^{\mathsf{q}-1}$ with probability
$\frac{1}{2^{\mathsf{q}-1}}$ (when all the shares of $\mathsf{b}$ are $1$,
given that at least one share is 1 as we are in the case $b=1$), and $0$
otherwise. In this case, we can write

$\displaystyle\mathds{E}[\mathsf{term_{p}}\mid(\mathsf{b}=0\wedge\text{$\mathsf{q}$
is odd})]$ $\displaystyle=\frac{1}{2^{\mathsf{q}-1}}\cdot
0~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}=0$
$\displaystyle\mathds{E}[\mathsf{term_{p}}\mid(\mathsf{b}=1\wedge\text{$\mathsf{q}$
is odd})]$
$\displaystyle=\frac{1}{2^{\mathsf{q}-1}}\cdot(-2)^{\mathsf{q}-1}=1$

Similarly, the case for even $\mathsf{q}$ can be written as

$\displaystyle\mathds{E}[\mathsf{term_{p}}\mid(\mathsf{b}=0\wedge\text{$\mathsf{q}$
is even})]$
$\displaystyle=\frac{1}{2^{\mathsf{q}-1}}\cdot(-2)^{\mathsf{q}-1}=-1$
$\displaystyle\mathds{E}[\mathsf{term_{p}}\mid(\mathsf{b}=1\wedge\text{$\mathsf{q}$
is even})]$ $\displaystyle=\frac{1}{2^{\mathsf{q}-1}}\cdot
0~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}~{}=0$

The above observation can be summarized as
$\mathds{E}[\mathsf{term_{p}}\mid\mathsf{b}]=\mathsf{b}-(\mathsf{q}\mbox{-}1)\
\mathrm{mod}\ 2$.

_Middle Term $(\mathsf{term_{m}})$:_ Given
$\mathds{E}[\mathsf{b}]=\mathsf{b}$,
$\mathds{E}[\mathsf{term_{s}}\mid\mathsf{b}]$ and
$\mathds{E}[\mathsf{term_{p}}\mid\mathsf{b}]$, the expectation of
$\mathsf{term_{m}}$ can be calculated as

$\displaystyle\mathds{E}[\mathsf{term_{m}}\mid\mathsf{b}]$
$\displaystyle=\mathds{E}[\mathsf{b}]-\mathds{E}[\mathsf{term_{s}}\mid\mathsf{b}]-\mathds{E}[\mathsf{term_{p}}\mid\mathsf{b}]$
$\displaystyle=\mathsf{b}-\mathsf{q}/2-(\mathsf{b}-(\mathsf{q}\mbox{-}1)\
\mathrm{mod}\ 2)$ $\displaystyle=(\mathsf{q}\mbox{-}1)\ \mathrm{mod}\
2-\mathsf{q}/2.$

This concludes the proof of Lem. 3.1. ∎

Our Approximation. With the aforementioned observations, the approximate
arithmetic equivalent of $\mathsf{b}$, denoted by $\hat{\mathsf{b}}$, is as
follows:

$\hat{\mathsf{b}}=\underbrace{\smashoperator[]{\sum_{\mathsf{b}_{e}\in\mathcal{Q}}^{}}\tilde{\mathsf{b}}_{e}}_{\mathsf{term_{s}}}+\underbrace{\left((\mathsf{q}\mbox{-}1)\
\mathrm{mod}\
2-\frac{\mathsf{q}}{2}\right)}_{\mathsf{term_{m}^{a}}}+\underbrace{(-2)^{\mathsf{q}-1}\prod\limits_{\mathsf{b}_{e}\in\mathcal{Q}}\tilde{\mathsf{b}}_{e}}_{\mathsf{term_{p}}}$
(9)

While $\mathsf{term_{s}}$ is kept because it only involves linear operations
on the shares of $\mathsf{b}$ (which are free in MPC for any linear secret
sharing scheme), we observe that $\mathsf{term_{p}}$ is required to keep the
expected values for $\mathsf{b}=0$ and $\mathsf{b}=1$ different. This is
evident from Lem. 3.1 where $\mathds{E}[\mathsf{term_{p}}\mid\mathsf{b}]$ is
the only term that depends on $\mathsf{b}$.

In general, if a term that depends on all the $\mathsf{q}$ shares of
$\mathsf{b}$ is missing from the approximation, we get
$\mathds{E}[\mathsf{b}=0]=\mathds{E}[\mathsf{b}=1]$. The intuition is that
only such a term can differentiate between $\mathsf{b}=0$ and $\mathsf{b}=1$,
while all other terms will be symmetrically distributed. For instance,
consider $\mathsf{q}=3$ and let
$\tilde{\mathsf{b}}=c_{1}\tilde{\mathsf{b}}_{1}+c_{2}\tilde{\mathsf{b}}_{2}+c_{3}\tilde{\mathsf{b}}_{3}+c_{4}\tilde{\mathsf{b}}_{1}\tilde{\mathsf{b}}_{2}+c_{5}\tilde{\mathsf{b}}_{2}\tilde{\mathsf{b}}_{3}+c_{6}\tilde{\mathsf{b}}_{1}\tilde{\mathsf{b}}_{3}+c_{7}$
for some random combiners $c_{i}\in\mathbb{Z}_{2^{\ell}}$ and $i\in[7]$. Using
the truth table $T_{\mathsf{b}}$ given in Tab. 1, it is easy to verify that

$\mathds{E}[\tilde{\mathsf{b}}=0]=\mathds{E}[\tilde{\mathsf{b}}=1]=\frac{1}{4}\cdot(2c_{1}+2c_{2}+2c_{3}+c_{4}+c_{5}+c_{6}+4c_{7})$
(10)

This argument can be generalized to any value of $\mathsf{q}$.

######  Claim 3.2.

The approximate arithmetic equivalent $\hat{\mathsf{b}}$ in Eq. (9) preserves
the expectation of the exact bit $\mathsf{b}$ in Eq. (3.1), i.e.,
$\mathds{E}[\hat{\mathsf{b}}=0]=0$ and $\mathds{E}[\hat{\mathsf{b}}=1]=1$.

###### Proof.

The proof is straightforward as we replace the middle term
($\mathsf{term_{m}}$) in Eq. (3.1) with its expected value
$\mathsf{term_{m}^{a}}$. ∎

In App. B.2.1, we provide an analysis of the efficiency gains achieved by our
approximation, showing that the number of cross terms that must be securely
computed using MPC is reduced exponentially in the number of shares
$\mathsf{q}$.

###  3.2 Accuracy Evaluation

In §3.1, we showed that our approximate bit conversion preserves the
expectation of the exact bits. However, we also want to understand the
concrete accuracy impact on the aggregation result due to the increased
variance. For this, we simulate the aggregation of random vectors
$\vec{v}_{i}$ with dimension $d$ drawn from a $(0,1)$-log-normal
distribution.444We use this distribution for preliminary measurements as it
was commonly observed in neural network gradients (e.g., [35]). Then, we
measure the normalized mean square error (NMSE) when comparing the averaged
aggregation result agg computed on secret-shared and quantized inputs to the
plain averaged aggregation
$\textit{agg}_{\textit{orig}}=\sum_{i}^{\mathsf{n}}\vec{v}_{i}/\mathsf{n}$.
Concretely, we measure

$\textit{NMSE}=\frac{\lVert\textit{agg}_{\textit{orig}}-\textit{agg}\rVert_{2}^{2}}{\sum_{i}^{\mathsf{n}}\lVert\vec{v}_{i}\rVert_{2}^{2}/\mathsf{n}},$
(11)

where agg is computed using various linear quantization schemes with global
scales (1) with an exact bit-to-arithmetic conversion and (2) with our
approximation enabled. Our results shown in Fig. 3 are the average of 10
trials for each experiment with $\mathsf{q}=3$ shares (representing a three-
server dishonest majority setting using the masked evaluation technique that
we will introduce in §4). Consistently, we observe that applying our
approximation increases the NMSE by about three orders of magnitude for
stochastic quantization without rotation, and by about one and a half orders
of magnitude for rotation-based algorithms. In Fig. 17 in App. B.2.3, we
additionally provide an evaluation for the case of local scales, which we will
use in our final system design, showing that the error can be significantly
reduced. Furthermore, as we will show in §4.2, the error is still so small
that the impact on the accuracy in common FL settings is negligible.

$10^{-3}$$10^{1}$$10^{5}$NMSE SQx$d=2^{10}$Exactx$d=2^{15}$Approx.x$d=2^{20}$
---

$10^{0}$$10^{2}$$10^{4}$$10^{-3}$$10^{1}$$10^{5}$NMSE HSQnumber of clients $\mathsf{n}$ |  $10^{0}$$10^{2}$$10^{4}$NMSE KSQnumber of clients $\mathsf{n}$
---|---

Figure 3: NMSE comparison between exact and approximation-based aggregation
for vanilla SQ, SQ using the randomized Hadamard transform (HSQ), and SQ using
Kashin’s representation (KSQ) for global scales with $\mathsf{q}=3$ shares and
various vector dimensions $d$ and number of clients $\mathsf{n}$.

##  4 Our System: ScionFL

In this section, we present our system ScionFL in detail from an MPC
standpoint. We present the underlying sharing semantics, client interaction
with MPC servers, and methods for performing secure aggregation of client
updates. We begin by introducing the masked evaluation technique, which is
used to improve our system’s real-time performance.

Masked Evaluation. In our MPC protocols, we use the masked evaluation
technique [55, 16, 32, 88, 119, 75], which enables the costly  _data-
independent_ calculations to be completed in a preprocessing phase, thus
enabling a fast and efficient  _data-dependent_ online phase (cf. §2.3). In
this model, the secret-share of every element
$\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$, denoted by $\langle\mathsf{v}\rangle$,
is associated with two values: a random mask
${\lambda}_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$ and a masked value
$\mathsf{m}_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$ such that
$\mathsf{v}=\mathsf{m}_{\mathsf{v}}+{\lambda}_{\mathsf{v}}$. While
${\lambda}_{\mathsf{v}}$ is split and distributed as $\mathsf{q}$ shares
similar to the general case discussed in §3.1, $\mathsf{m}_{\mathsf{v}}$ is
given to all MPC servers555Due to differences in the underlying setting, there
may be minor differences in how the values $\mathsf{m}_{\mathsf{v}}$ and
${\lambda}_{\mathsf{v}}$ are distributed among the servers.. Since
${\lambda}_{\mathsf{v}}$ is random and independent of $\mathsf{v}$, all
operations involving ${\lambda}_{\mathsf{v}}$ values alone can be computed
during the preprocessing phase.

Masked Bit Conversion and Injection. With the masked evaluation technique, the
arithmetic equivalent $\tilde{\mathsf{b}}$ for a bit
$\mathsf{b}=\mathsf{m}_{\mathsf{b}}\oplus{\lambda}_{\mathsf{b}}$ can be
obtained as

$\displaystyle\tilde{\mathsf{b}}=\mathsf{m}_{\mathsf{b}}\oplus{\lambda}_{\mathsf{b}}=\mathsf{M}_{\mathsf{b}}+(1-2\mathsf{m}_{\mathsf{b}})\cdot{\Lambda}_{\mathsf{b}},$
(12)

where $\mathsf{M}_{\mathsf{v}}$ and ${\Lambda}_{\mathsf{v}}$ denote the
arithmetic equivalents of $\mathsf{m}_{\mathsf{v}}$ and
${\lambda}_{\mathsf{v}}$, respectively. Note that ${\Lambda}_{\mathsf{b}}$ can
be computed from ${\lambda}_{\mathsf{b}}$ during the preprocessing phase using
techniques discussed in §3.1, including our novel approximation from §3.1.
Similarly, given $\mathsf{s}=\mathsf{M}_{\mathsf{s}}+{\Lambda}_{\mathsf{s}}$,
the value $\mathsf{b}\cdot\mathsf{s}$ can be obtained as

$\displaystyle\mathsf{b}\cdot\mathsf{s}$
$\displaystyle=(\mathsf{M}_{\mathsf{b}}+(1-2\mathsf{m}_{\mathsf{b}})\cdot{\Lambda}_{\mathsf{b}})\cdot(\mathsf{M}_{\mathsf{s}}+{\Lambda}_{\mathsf{s}})$
$\displaystyle=\mathsf{M}_{\mathsf{b}}\mathsf{M}_{\mathsf{s}}+\mathsf{M}_{\mathsf{b}}{\Lambda}_{\mathsf{s}}+(1-2\mathsf{m}_{\mathsf{b}})\cdot({\Lambda}_{\mathsf{b}}\mathsf{M}_{\mathsf{s}}+{\Lambda}_{\mathsf{b}}{\Lambda}_{\mathsf{s}}).$
(13)

As shown in Eq. (4), the servers need to additionally compute
${\Lambda}_{\mathsf{b}}{\Lambda}_{\mathsf{s}}$ in the preprocessing phase.

Client Interaction. Before going into the details of aggregation among the
$\tau$ MPC servers, we discuss input sharing and the reconstruction of the
aggregated vector for clients.

To generate the $\langle\cdot\rangle$-shares of a value
$\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$ owned by client $\mathsf{C}$, it first
non-interactively computes the additive shares of the mask
${\lambda}_{\mathsf{v}}$ using the shared randomness setup discussed in §1.
The masked value is then computed as
$\mathsf{m}_{\mathsf{v}}=\mathsf{v}-{\lambda}_{\mathsf{v}}$ and sent to a
single designated MPC server, say $\mathsf{S}_{1}$. The input sharing is
completed when $\mathsf{S}_{1}$ sends $\mathsf{m}_{\mathsf{v}}$ to all
remaining MPC servers. For Boolean values (i.e., $\mathbb{Z}_{2}$) the
procedure is similar except that addition/subtraction is replaced with XOR and
multiplication with AND. We use $\langle\cdot\rangle^{\bf B}$ to denote the
secret sharing over the domain $\mathbb{Z}_{2}$.

After the servers have received all inputs in $\langle\cdot\rangle$-shared
form, they instantiate the $\mathcal{F}_{\mathsf{SecAgg}}$ functionality
specified in Fig. 2.4 and obtain the aggregated vectors in
$\langle\cdot\rangle$-shared form. Recall from §2.1 that the values to be
aggregated in our case correspond to FL gradients, and the aggregated result
can also be made public. As a result, the servers reconstruct the aggregated
result towards a chosen server, say $\mathsf{S}_{1}$, which updates the global
model according to Eq. (3). In the next iteration, $\mathsf{S}_{1}$
distributes the updated global model to a fresh set of clients, and the
process is repeated.

From a client’s perspective, it is only interacting with one server (apart
from a one-time shared-randomness setup), as it is the case in a privacy-free
variant in which clients communicate with a single parameter server for
aggregation [89].

MPC Protocols. We provide the full MPC protocols for inner product
computation, multiplication, and bit-to-arithmetic conversion in App. B.1.2,
which are utilized in a black-box fashion in this section.

###  4.1 MPC-based Aggregation

We now discuss two approaches for instantiating
$\mathcal{F}_{\mathsf{SecAgg}}$ using MPC protocols that operate on secret-
shared values. Recall from Eq. (5) that the MPC servers for the aggregation of
quantized values possess $\langle\cdot\rangle$-shares of matrices
$\vec{\mathbf{U}}_{\sf\mathsf{n}\times 1}$ and
$\vec{\mathbf{V}}_{\sf\mathsf{n}\times 1}$ along with the
$\langle\cdot\rangle^{\bf B}$-shares of
$\vec{\mathbf{B}}_{\sf\mathsf{n}\times\mathsf{m}}$.

####  4.1.1 Approach I

A naive instantiation of $\mathcal{F}_{\mathsf{SecAgg}}$ would be to have the
servers convert binary shares of the matrix $\vec{\mathbf{B}}$ to their
arithmetic shares first, as in Prio+ [2]. This is possible in MPC with a bit-
to-arithmetic conversion protocol [92, 102, 2, 75], denoted by $\Pi_{\sf
BitA}$, which computes the arithmetic shares of $\mathsf{b}\in\mathbb{Z}_{2}$
from its Boolean sharing. Once the arithmetic shares are generated, the
servers use an instance of an inner-product protocol, denoted by $\Pi_{\sf
IP}$, on each of the $\mathsf{m}$ columns of matrix $\vec{\mathbf{B}}$ with
the column vector $(\vec{\mathbf{V}}_{\sf\mathsf{n}\times
1}-\vec{\mathbf{U}}_{\sf\mathsf{n}\times 1})$ computed locally to obtain the
row aggregate. They complete the protocol by adding a row aggregate of
$\vec{\mathbf{U}}$ to each column of the resultant matrix computed in the
previous step. The formal protocol $\Pi_{\sf SecAgg}^{\text{\Romannum{1}}}$ is
given in Fig. 4.1.1.

1. Locally compute $\langle\vec{\mathbf{S}}_{\sf\mathsf{n}\times 1}\rangle=\langle\vec{\mathbf{V}}_{\sf\mathsf{n}\times 1}\rangle-\langle\vec{\mathbf{U}}_{\sf\mathsf{n}\times 1}\rangle$. 2. Compute $\langle\vec{\mathbf{B}}\rangle=\Pi_{\sf BitA}(\langle\vec{\mathbf{B}}\rangle^{\bf B})$. 3. Compute $\langle\vec{\mathbf{W}}^{j}\rangle=\Pi_{\sf IP}(\langle\vec{\mathbf{B}}^{j}\rangle,\langle\vec{\mathbf{D}}\rangle)$, for each $j\in[\mathsf{m}]$. 4. Locally compute $\langle\vec{\mathbf{Z}}_{\sf 1\times 1}\rangle={\sf Agg\mbox{-}R}(\langle\vec{\mathbf{U}}_{\sf\mathsf{n}\times 1}\rangle)$. 5. Locally compute $\langle\vec{\mathbf{Y}}_{\sf 1\times\mathsf{m}}\rangle=\langle\vec{\mathbf{Z}}_{\sf 1\times 1}\rangle\oplus\langle\vec{\mathbf{W}}_{\sf 1\times\mathsf{m}}\rangle$. Figure 4: Secure aggregation – Approach 1.

As shown in Fig. 4.1.1, $\Pi_{\sf SecAgg}^{\text{\Romannum{1}}}$ invokes
$\Pi_{\sf BitA}$ for each bit in matrix $\vec{\mathbf{B}}$, resulting in
$\mathsf{n}\cdot\mathsf{m}$ invocations. Using the masked evaluation technique
[76, 119], the online communication of this approach can be made independent
of the dimension $\mathsf{n}$, which in our case corresponds to the number of
clients.

####  4.1.2 Approach II

We use the bit injection protocol [92, 102, 74], denoted by $\Pi_{\sf BI}$,
which computes the arithmetic sharing of $\mathsf{b}\cdot\mathsf{s}$ given the
Boolean sharing of $\mathsf{b}\in\mathbb{Z}_{2}$ and the arithmetic sharing of
$\mathsf{s}\in\mathbb{Z}_{2^{\ell}}$. Given
$\langle\vec{\mathbf{M}}_{\sf\alpha\times 1}\rangle^{\bf B}$ and
$\langle\vec{\mathbf{N}}_{\sf\alpha\times 1}\rangle$, the high-level idea is
to effectively combine the $\Pi_{\sf BitA}$ and $\Pi_{\sf IP}$ protocol to a
slightly modified instance of $\Pi_{\sf BI}$ that directly computes the sum
[76, 119] (denoted by
$\sum_{i=1}^{\alpha}{\mathbf{M}}_{i}^{1}\cdot{\mathbf{N}}_{i}^{1}$) instead of
the individual positions. This can be achieved following Eq. (4) and the
details appear in Fig. B.1.2 in §B.1.2. One significant advantage of this
technique is that online communication is no longer dependent on the number of
clients $\mathsf{n}$. $\Pi_{\sf SecAgg}^{\text{\Romannum{2}}}$ denotes the
resulting protocol and the formal details are given in Fig. 4.1.2.

1. Locally compute $\langle\vec{\mathbf{S}}_{\sf\mathsf{n}\times 1}\rangle=\langle\vec{\mathbf{V}}_{\sf\mathsf{n}\times 1}\rangle-\langle\vec{\mathbf{U}}_{\sf\mathsf{n}\times 1}\rangle$. 2. Compute $\langle\vec{\mathbf{W}}^{j}\rangle=\Pi_{\sf BI}(\langle\vec{\mathbf{B}}^{j}\rangle^{\bf B},\langle\vec{\mathbf{D}}\rangle)$, for each $j\in[\mathsf{m}]$. 3. Locally compute $\langle\vec{\mathbf{Z}}_{\sf 1\times 1}\rangle={\sf Agg\mbox{-}R}(\langle\vec{\mathbf{U}}_{\sf\mathsf{n}\times 1}\rangle)$. 4. Locally compute $\langle\vec{\mathbf{Y}}_{\sf 1\times\mathsf{m}}\rangle=\langle\vec{\mathbf{Z}}_{\sf 1\times 1}\rangle\oplus\langle\vec{\mathbf{W}}_{\sf 1\times\mathsf{m}}\rangle$. Figure 5: Secure aggregation – Approach 2.

####  4.1.3 Approach III using SepAgg

In a closely related work [14], the authors combine the SIGNSGD compression
technique of [17] with additive secret sharing for FL. Unlike our work, which
investigates secure aggregation using various linear quantization algorithms
in a cross-device environment, they aim for a cross-silo setting in which
clients distribute arithmetically shared values to servers rather than single
bits. In terms of client-server communication, this indicates an overhead of
factor $\log_{2}2\mathsf{n}$, where $\mathsf{n}$ is the number of involved
participants each round.

However, the authors of [14] introduce an interesting approximation called
“SepAgg” for computing the averaged inner product between bits and scales:

$\frac{1}{\mathsf{n}}\sum_{i}^{\mathsf{n}}\vec{\sigma}_{X}^{i}\cdot\vec{\mathsf{s}}_{X}^{i}\approx\frac{1}{\mathsf{n}^{2}}\left(\sum_{i}^{\mathsf{n}}\vec{\sigma}_{X}^{i}\right)\left(\sum_{i}^{\mathsf{n}}\vec{\mathsf{s}}_{X}^{i}\right).$
(14)

We adopt the SepAgg method to our setting to compute ${\sf
Agg\mbox{-}R}(\vec{\mathbf{B}}\circ(\vec{\mathbf{V}}-\vec{\mathbf{U}}))$ in
Eq. (5). In particular, we aggregate the matrices $\vec{\mathbf{B}}$ and
$(\vec{\mathbf{V}}-\vec{\mathbf{U}})$ independently and then perform one
secure multiplication per coordinate, with the other operations being linear
and free in our MPC protocol. As a result, we can utilize linear quantization
schemes with local scales at the cost of global scales (ignoring the overhead
for global scales to securely determine $\mathsf{s}_{X}^{min}$ and
$\mathsf{s}_{X}^{min}$ across all participants). The formal protocol $\Pi_{\sf
SecAgg}^{\text{\Romannum{3}}}$ utilizing SepAgg appears in Fig. 4.1.3.

1. Locally compute $\langle\vec{\mathbf{S}}_{\sf 1\times 1}\rangle={\sf Agg\mbox{-}R}(\langle\vec{\mathbf{V}}_{\sf\mathsf{n}\times 1}\rangle-\langle\vec{\mathbf{U}}_{\sf\mathsf{n}\times 1}\rangle)$. 2. Compute $\langle\vec{\mathbf{T}}^{j}\rangle=\Pi_{\sf BitA}^{\sf sum}(\langle\vec{\mathbf{B}}^{j}\rangle^{\bf B})$, for each $j\in[\mathsf{m}]$. 3. Compute $\langle\vec{\mathbf{W}}^{j}\rangle=\Pi_{\sf Mult}(\langle\vec{\mathbf{T}}^{j}\rangle,\langle\vec{\mathbf{S}}\rangle)$, for each $j\in[\mathsf{m}]$. 4. Locally compute $\langle\vec{\mathbf{Z}}_{\sf 1\times 1}\rangle={\sf Agg\mbox{-}R}(\langle\vec{\mathbf{U}}_{\sf\mathsf{n}\times 1}\rangle)$. 5. Locally compute $\langle\vec{\mathbf{Y}}_{\sf 1\times\mathsf{m}}\rangle=\langle\vec{\mathbf{Z}}_{\sf 1\times 1}\rangle\oplus\frac{1}{\mathsf{n}}\cdot\langle\vec{\mathbf{W}}_{\sf 1\times\mathsf{m}}\rangle$. Figure 6: Secure aggregation – Approach 3 (SepAgg [14]).

Accuracy Evaluation. We next provide strong empirical evidence that applying
SepAgg for SQ with preprocessing preserves the linear NMSE decay with respect
to the number of clients (i.e., unbiased estimates). For this, we run a
simulation similar to the one described in §3.2. Here, we compare the NMSE
computed as in Eq. (11) for an aggregation agg (1) a regular dot product
between converted bits and scales and (2) with SepAgg. Note that here we do
not apply our approximate conversion presented in §3.1 to study the effect of
SepAgg in isolation. Our results shown in Fig. 7 are the average of 10 trials
for each experiment. While for smaller vector dimensions, we observe a visible
effect for SQ without preprocessing, there is only a minor difference for the
other two quantization schemes, and sometimes the NMSE for SepAgg is even
smaller than for the exact computation.

$10^{-3}$$10^{-1}$$10^{1}$NMSE SQx$d=2^{10}$Exactx$d=2^{15}$SepAggx$d=2^{20}$
---

$10^{0}$$10^{2}$$10^{4}$$10^{-3}$$10^{-1}$$10^{1}$NMSE HSQnumber of clients $\mathsf{n}$ |  $10^{0}$$10^{2}$$10^{4}$NMSE KSQnumber of clients $\mathsf{n}$
---|---

Figure 7: NMSE comparison between exact and SepAgg-based aggregation for
vanilla SQ, SQ using the randomized Hadamard transform (HSQ), and SQ using
Kashin’s representation (KSQ) for various vector dimensions $d$ and number of
clients $\mathsf{n}$.

Formally proving that applying SepAgg after different preprocessing
techniques, such as random rotation and Kashin’s representation, results in an
unbiased aggregation is a significant theoretical challenge. We leave this
intriguing endeavor for future work.

Communication Costs. We provide a detailed analysis of theoretical and
concrete communication costs for each of our three approaches outlined in
§4.1.1 to §4.1.3 in App. B.2.4.

###  4.2 Performance Evaluation

We implement an extensive end-to-end FL evaluation and MPC simulation
framework. We first describe our implementation, then the parameters used for
our accuracy evaluation, and finally the obtained results.

Implementation. Our implementation is written in Python based on the PyTorch
ML framework. Hence, it supports multi-GPU acceleration, also for the MPC
simulation. A subset of this framework was already used for measuring the
accuracy of our approximate bit conversion (cf. §3.2) and SepAgg (cf. §4.1.3),
and we will describe extensions in §5.1.2 to incorporate evaluations of
poisoning attacks and defenses.

On a high-level, our frameworks provides a simple CLI to run FL training tasks
and observe the resulting training as well as test accuracy. Upon execution,
the framework distributes training data among the specified number of virtual
clients that locally perform optimization. The server(s) performs aggregation
using FedAvg. When the MPC simulation is enabled, the clients’ input will be
secret-shared before aggregation and the protocol described in §4.1.3 will be
locally executed. Note that here our goal is not to assess the run-time
performance of the MPC protocol but rather precisely measure the impact on the
accuracy. Our implementation supports all exact and approximate secure
aggregation variants described in this paper.

Parameters. We evaluate the accuracy on the following standard FL tasks for
image classification: training (1) LeNet on MNIST [80] for 1000 rounds and (2)
ResNet9 on CIFAR-10 [77] for 8000 rounds. For all tasks, we set a client batch
size of 8, a learning rate of 0.05, and perform 5 local client train steps per
round. For MNIST, we run training using $N\in\\{200,1000,5000\\}$ clients and
choose $10\%$ of the clients at random per round. Due to the memory
constraints of our system (that simulates all clients at once), we restrict
training for CIFAR10 to $N=1000$ clients and select $\mathsf{n}=40$ per round.
As we observed a significant loss in accuracy for plain SQ in our accuracy
evaluation for approximate bit conversion as well as SepAgg (cf. §3.2), we
focus our evaluation on more accurate linear quantization schemes, i.e., HSQ
and KSQ. For the MPC simulation of our approximate secure aggregation
following Approach-III (cf. Fig. 4.1.3), we choose a three-server dishonest
majority setting.

Figure 8: Validation accuracy for training LeNet on the MNIST data set for
$N\in\\{200,1000,5000\\}$ clients when selecting $10\%$ of the clients at
random per round ($\mathsf{n}$) for SQ with Hadamard (HSQ, left) and with
Kashin’s representation (KSQ, right); “exact” denotes the insecure baseline,
“approx” the simulation of our MPC-based approximate secure aggregation
including SepAgg (cf. Fig. 4.1.3).

Results. The results for the MNIST/LeNet training are given in Fig. 8.
Validation accuracy for our approximate version converges to almost the same
final accuracy as the insecure exact aggregation. Specifically, in the final
round of training, the difference between the two is diminished to $0.77\%$
and $0.33\%$ for HSQ and KSQ for $N=5000$, respectively. Similar results can
be observed for CIFAR10/ResNet9 in Fig. 9. However, here the difference
between the exact and approximate version with $3.14\%$ in the final round for
KSQ is higher. This gap is expected due to the significantly lower number of
clients per round, for which our approximate bit conversion and SepAgg
technique result in a comparatively high NMSE over the baseline (cf. Figs. 3
and 7). We expect this effect to vanish for a real cross-device setting with
thousands of participants per round (due to the demonstrated linear decay of
the NMSE when increasing $\mathsf{n}$), which we unfortunately cannot simulate
with complex network architectures due to hardware limitations. Additionally,
one may use a  _hybrid_ approach, where training is conducted with the
approximate version for the initial rounds until a baseline accuracy is
reached, whereas secure exact training (potentially including only the SepAgg
[14] approximation but not our approximate bit-to-arithmetic conversion) is
used for fine tuning up to the desired target accuracy.

Figure 9: Validation accuracy for training ResNet9 on the CIFAR10 data set for
$N=1000$ clients with random $\mathsf{n}=40$ selected per round for
quantization techniques and protocols as in Fig. 8.

In Tab. 2, we additionally compare the exact inter-server MPC communication
cost for a naive MPC implementation of the exact computation to our optimized
approximate version including SepAgg. As we can see, we improve the offline
communication by factor $\approx 15\times$. For the online communication, we
can see a wide range of improvement factors from $22\times$ to $547\times$ for
MNIST with $\mathsf{n}=500$. This highlights the positive impact when
utilizing the SepAgg approach for aggregating an increasingly large number of
rows non-interactively. Note that there are slight differences in
communication overhead for HSQ and KSQ. This is because for an efficient GPU-
friendly implementation of the randomized Hadamard transform, which we use for
both rotating the gradients in HSQ and for calculating Kashin’s coefficients
in KSQ, we require that the gradients’ size are a power of 2. In App. B.1.1,
we detail how we can minimize the resulting overhead by dividing the gradients
into chunks, and we also give the exact number of bits per gradient that we
assume in our calculations for each algorithm.

|  |  | Naive Exact (cf. Fig. 4.1.1) | Our Approx. (cf. Fig. 4.1.3)
---|---|---|---|---
Benchmark | $\mathsf{n}$ | Method | Offline | Online | Offline | Online
MNIST/ LeNet | 20 | HSQ | 572.89 | 11.47 | 58.26 | 0.52
KSQ | 644.50 | 12.90 | 65.54 | 0.59
MNIST/ LeNet | 100 | HSQ | 2864.46 | 57.34 | 187.49 | 0.52
KSQ | 3222.51 | 64.51 | 210.93 | 0.59
MNIST/ LeNet | 500 | HSQ | 14322.28 | 286.72 | 833.64 | 0.52
KSQ | 16112.56 | 322.56 | 937.85 | 0.59
CIFAR10/ ResNet9 | 40 | HSQ | 87079.45 | 1743.26 | 6883.13 | 39.85
KSQ | 100828.84 | 2018.51 | 7969.94 | 46.14

Table 2: Inter-server communication per round for our benchmarks for different
numbers of clients $\mathsf{n}$ in MiB.

##  5 Defending Untargeted Poisoning Attacks

Beyond data privacy threats, FL was also shown to be vulnerable to
manipulations affecting the inference service quality a model is trained for.
Recall from Eq. (1) in §2.1 that in FL, each training iteration $t$ consists
of participating clients submitting their locally computed gradients to a
central aggregator, who combines them to obtain the global model for the
following iteration. An adversary $\mathcal{A}$ who controls a fraction of the
participating clients, on the other hand, can alter their local models or
model updates and send these malformed updates for aggregation, affecting the
characteristics of the final global model [113, 49, 127, 9, 19, 112]. This
highlights the need for effective “defense measures” capable of thwarting such
attacks. There are a plethora of such attacks and defenses in the FL
literature and, we give an overview of the state-of-the-art works that are
closely related to ours in App. §A.5.

We focus on defending against  _untargeted poisoning attacks_ , in which the
attacker attempts to damage the trained model’s performance for a large number
of test inputs, typically resulting in a final global model with a high error
rate [49, 112, 10]. These types of attacks pose a significant threat to the
deployment of FL for two reasons: (1) Untargeted attacks are particularly
difficult to detect because, ignorant of the attack, service providers are
unaware that they could have achieved a greater accuracy. (2) Even a minor
drop in accuracy can cause enormous (competitive) damage [113].

Min-Max Attack [112]. Most proposed untargeted poisoning attacks on FL use the
(unrealistic) assumption that the adversary $\mathcal{A}$ is aware of either
the aggregation rule [49] or all benign updates [10]. However, the  _Min-Max_
attack proposed by Shejwalkar and Houmansadr [112] defies this assumption and
constitutes the state-of-the-art attack. This attack prevents the
manipulations from being detected by allowing the adversary to compute
representative benign updates using some clean training data and then using
those in the attack to limit the maximum distance of the manipulated update to
any other update by the maximum distances of any two benign updates. This
ensures that the malicious gradients are sufficiently similar to the set of
benign gradients. We refer to [112, §IV] for more specifics on the attack.

In addition to removing the assumptions about the adversary’s knowledge, the
authors experimentally demonstrate that this attack outperforms the then-
state-of-the-art poisoning attack [10] for almost all tested datasets.
However, since all of the benchmarks in [10, 112] were performed on FL schemes
without quantization, the impact of the  _Min-Max_ attack on quantized FL
schemes is unclear. Hence, we initially test the attack’s effectiveness in our
framework using the open-sourced
code666https://github.com/vrt1shjwlkr/NDSS21-Model-Poisoning as the baseline.
As will be discussed in §5.1.2, we observe that the attacks are effective even
in the context of quantization. As a result, we design a defense called
ScionFL-Aura against untargeted poisoning attacks, which we detail next.

###  5.1 Our Defense: ScionFL-Aura

From an intuitive standpoint, the adversary in an untargeted poisoning attack
seeks to manipulate the global update with malicious updates to deviate it as
much as possible from the result of an ideal benign training while evading
potentially deployed detection mechanisms. This baseline observation was also
used by earlier proposed defense mechanisms [112, 97], however, those cannot
be combined trivially with ScionFL without having to de-quantize all updates
and running expensive secure computation machinery.

In this section, we first outline the general design of ScionFL-Aura and show
its effectiveness against the  _Min-Max_ attack [112]. Then, in §5.1.3, we
outline how to efficiently instantiate it in an MPC-friendly manner to reduce
communication overhead over the baseline approach.

####  5.1.1 Approach

ScionFL-Aura uses a hybrid approach by combining ideas from existing FL
defenses based on ${\sf L}_{2}$-norm [9, 97, 118] and cosine similarity [97,
29]. Several works like [97] compute these metrics for each pair of clients,
resulting in expensive computations. In contrast, we first aggregate all
updates, including the poisoned ones, to produce the vector $\vec{X}^{\sf
agg}$, which we then utilize as the reference.

At a high level, scaling based on the ${\sf L}_{2}$-norm of the gradient
vectors is used at first to bound the impact of malicious contributions that
are potentially overlooked (i.e., not filtered) in later stages. In a second
step, local updates that significantly deviate from the average update
direction are considered to be manipulated and, thus, excluded. Concretely,
ScionFL-Aura consists of the following steps:

  1. 1.

_${\sf L}_{2}$ -norm-based Scaling._ In this step, the ${\sf L}_{2}$-norm of
each gradient vector is compared against a public threshold multiplied with
the average of the ${\sf L}_{2}$-norms. Let $\mu_{\sf th}$ denote the
threshold and ${\sf L}_{2}^{\sf avg}$ denote the average of the ${\sf
L}_{2}$-norms across all clients. If ${\sf L}_{2}^{X}>\mu_{\sf th}\cdot{\sf
L}_{2}^{\sf avg}$ for a gradient vector $\vec{X}$, the vector is scaled by a
factor of $\mu_{\sf th}\cdot{\sf L}_{2}^{\sf avg}/{\sf L}_{2}^{X}$.777Scaling
a quantized vector requires simply scaling the scales (cf.§2.4). This ensures
that no gradient has an ${\sf L}_{2}$-norm greater than $\mu_{\sf th}\cdot{\sf
L}_{2}^{\sf avg}$.

  2. 2.

_Cosine-distance-based Filtering._ This step involves computing the cosine
distance of each gradient from the reference vector $\vec{X}^{\sf agg}$
discussed above. Following that, another round of aggregation is performed on
the updated vectors, but without the top-$\psi$ vectors with the highest
cosine distances, which are considered malicious. In this case, $\psi$ is
either a known bound (i.e., defined in advance by the service provider) or an
accepted percentile determined based on an assumed attacker ratio that follows
a normal distribution.

Alg. 1 provides the formal details of our defense scheme, including support
for quantized aggregation. Note that we use an optimizer with momentum for
FedAvg which ensures that even if the majority of clients picked at random in
a training round happens to be malicious, the optimization is still is based
on benign contributions from the previous round. App. B.3 provides details on
the sub-protocols utilized in our defense algorithm given in Alg. 1.

Algorithm 1 Our Defense: ScionFL-Aura

1:procedure ScionFL-
Aura($\\{\vec{\sigma}_{X_{i}},\mathsf{s}_{X_{i}}^{min},\mathsf{s}_{X_{i}}^{max}\\}_{i\in[\mathsf{n}]}$)

2:// Gradient Aggregation including poisoned ones.

3: $\vec{X}^{\sf
agg}\leftarrow\textsc{Aggregate}(\\{\vec{\sigma}_{X_{i}},\mathsf{s}_{X_{i}}^{min},\mathsf{s}_{X_{i}}^{max}\\}_{i\in\mathsf{n}})$

4:// ${\sf L}_{2}$-norm Computation

5: ${\sf L}_{2}^{\sf avg}\leftarrow 0$

6: for $k\leftarrow 1$ to $\mathsf{n}$ do

7: ${\sf
L}_{2}^{k}\leftarrow\textsc{L2-NormQ}(\vec{\sigma}_{X_{k}},\mathsf{s}_{X_{k}}^{min},\mathsf{s}_{X_{k}}^{max})$

8: ${\sf L}_{2}^{\sf avg}\leftarrow{\sf L}_{2}^{\sf avg}+{\sf L}_{2}^{k}$

9: end for

10:// ${\sf L}_{2}$-norm based Scaling

11: ${\sf L}_{2}^{\sf avg}\leftarrow{\sf L}_{2}^{\sf avg}/\mathsf{n}$ //
Average of ${\sf L}_{2}$-norms

12: for $k\leftarrow 1$ to $\mathsf{n}$ do

13: if ${\sf L}_{2}^{k}>\mu_{\sf th}\cdot{\sf L}_{2}^{\sf avg}$ then

14: $\mathsf{s}_{X_{k}}^{min}\leftarrow\mathsf{s}_{X_{k}}^{min}\cdot(\mu_{\sf
th}\cdot{\sf L}_{2}^{\sf avg})/{\sf L}_{2}^{k}$

15: $\mathsf{s}_{X_{k}}^{max}\leftarrow\mathsf{s}_{X_{k}}^{max}\cdot(\mu_{\sf
th}\cdot{\sf L}_{2}^{\sf avg})/{\sf L}_{2}^{k}$

16: end if

17: end for

18:// Cosine-distance based Filtering

19: for $k\leftarrow 1$ to $\mathsf{n}$ do

20:
$\theta^{k}\leftarrow\textsc{Cosine}((\vec{\sigma}_{X_{k}},\mathsf{s}_{X_{k}}^{min},\mathsf{s}_{X_{k}}^{max}),\vec{X}^{\sf
agg})$

21: end for

22: $\mathcal{X}\leftarrow\textsc{Top\mbox{-}K}(\vec{\theta},\psi)$ // Returns
$k$ for which $\theta^{k}>\psi$

23:// Aggregation of filtered updates

24: $\vec{X}^{\sf
aggd}\leftarrow\textsc{Aggregate}(\\{\vec{\sigma}_{X_{i}},\mathsf{s}_{X_{i}}^{min},\mathsf{s}_{X_{i}}^{max}\\}_{i\in[\mathsf{n}],i\notin\mathcal{X}})$

25:end procedure

####  5.1.2 Effectiveness

To analyze the effectiveness of ScionFL-Aura, we test it against the  _Min-
Max_ attack [112].

Setup. Each training involves $N=50$ clients while – as in [112] – $20\%$ of
them are corrupted.888[113] points out that assuming more than $1\%$ of
corrupted clients is unrealistic for most scenarios. However, in our
experiments the attack failed to notably reduce the accuracy with such a low
corruption level. Thus, we tested against $20\%$ of corrupted clients as in
the original attack paper [112]. Per training iteration, a random subset of
$\mathsf{n}=10$ clients is chosen to train the global model. Each client
$\mathsf{C}$ runs its local training for 10 iterations with batches of $B=128$
samples and a learning rate of $\eta_{\mathsf{C}}=0.1$. The defense threshold
$\mu_{\sf th}$ is set to $3$ and the momentum is $0.9$.

Figure 10: Effect of  _Min-Max_ attack [112] on training ResNet9 with CIFAR10
with and without our defense ScionFL-Aura assuming $20\%$ of $N=50$ clients
are corrupted. The number of attackers included in the global update varies
even without defense due to random client selection.

Experimental Results. Our results when training ResNet9 on CIFAR10 (1) without
an attack, (2) under attack without defense, and (3) under attack with
ScionFL-Aura in place are given in Fig. 10. We compare the attack’s effect
when no compression is in place as well as when applying SQ with the
randomized Hadamard transform (HSQ) or with Kashin’s representation (KSQ).
Next to the ResNet9 architecture, we also provide results for training VGG11
in App. §B.3.2. As shown in Fig. 10, our re-implementation of the  _Min-Max_
attack substantially reduces the validation accuracy by up to $20\%$ when no
defense is in place. This is in line with [112], where the authors report an
accuracy degradation between $10.1\%$ and $42.1\%$ for CIFAR10, depending on
the network architecture and the aggregation scheme. Furthermore, our
experiments show that quantization does not significantly change the impact of
the attack. When our defense ScionFL-Aura is enabled, we can remove more than
half of the malicious updates in each training iteration compared to when no
defense is in place. In fact, quantization supports our defense as the
additional noise added to synchronized malicious updates overturns the
attackers’ ability of staying just below the detection threshold. As a result,
compared to unprotected training, the validation accuracy decreases by at most
$7.7\%$ for HSQ and $10.7\%$ for KSQ.

####  5.1.3 MPC-friendly Variant

A naive secure realization of ScionFL-Aura outlined in Alg. 1 utilizing MPC
will yield an inefficient solution, particularly over a ring architecture.
This is due to some of the algorithm’s non-MPC friendly primitives, which are
discussed below.

  1. 1.

_(Line 5 in Alg. 1)._ The computation of ${\sf L}_{2}$-norm within L2-NormQ
(cf. Alg. 3 in App. B.3) involves calculating the square root of a ring
element, which corresponds to a decimal value. To alleviate this, we ask the
clients to submit the ${\sf L}_{2}$-norm of their gradient vectors and the MPC
servers verify them. To be more specific, the provided ${\sf L}_{2}$-norm is
squared and compared to a squared-${\sf L}_{2}$-norm computed by the MPC
servers via a secure comparison protocol [30, 86].

  2. 2.

_(Lines 11 & 12 in Alg. 1)._ When using ${\sf L}_{2}$-norm scaling, the scales
of the gradient vector must be bounded if the corresponding ${\sf L}_{2}$-norm
is greater than the limit. In particular, the procedure entails dividing the
vector by its ${\sf L}_{2}$-norm. Because division is expensive in MPC over
rings, we ask the client to submit the reciprocal of the ${\sf L}_{2}$ norm as
well, similar to the method suggested above. The provided value is validated
by multiplying it by the ${\sf L}_{2}$ norm supplied by the client and
checking whether the product is a $1$.

  3. 3.

_(Line 16 in Alg. 1)._ The calculation of the cosine-distance between the
gradient vector and the reference $\vec{X}^{\sf agg}$ requires computing the
${\sf L}_{2}$-norm of $\vec{X}^{\sf agg}$ and dividing by it, as shown in
Cosine in Alg. 4. However, cosine distances are used to filter out the
top-$\psi$ vectors with the highest cosine distance, as shown in Alg. 1 (Line
18). As a result, we may safely disregard the division by the ${\sf
L}_{2}$-norm of $\vec{X}^{\sf agg}$ when computing the cosine distance for our
purpose.

In addition to the aforementioned optimizations, we notice that most of the
values computed as part of the $\vec{X}^{\sf agg}$ computation in the
Aggregate function (Line 2 in Alg. 1) can be reused in the next steps, thus
lowering the overhead of the defense scheme over simple aggregation.

##  6 Conclusion

We propose ScionFL, the first protocol for secure aggregation that supports
any linear quantization scheme. Furthermore, we designed the first approximate
MPC protocol for bit-to-arithmetic conversions, which might be of interest for
a wide range of other applications that can tolerate or even desire noise in
their computation. Additionally, we designed a novel defense named ScionFL-
Aura against state-of-the-art untargeted model poisoning attacks and outlined
its efficient implementation in MPC. As part of future work, we plan to
implement and evaluate ScionFL as well as ScionFL-Aura in an established MPC
framework.

## Acknowledgments

This project received funding from the European Research Council (ERC) under
the European Union’s Horizon 2020 research and innovation program (grant
agreement No. 850990 PSOTI). It was co-funded by the Deutsche
Forschungsgemeinschaft (DFG) within SFB 1119 CROSSING/236615297 and GRK 2050
Privacy & Trust/ 251805230, by the German Federal Ministry of Education and
Research and the Hessen State Ministry for Higher Education, Research and the
Arts within ATHENE, and by the Private AI Collaborative Research Institute,
funded by Intel, Avast, and VMware.

## References

  * [1] J. Aas and T. Geoghegan.  Introducing ISRG Prio Services for Privacy Respecting Metrics.  https://www.abetterinternet.org/post/introducing-prio-services/.
  * [2] S. Addanki, K. Garbe, E. Jaffe, R. Ostrovsky, and A. Polychroniadou.  Prio+: Privacy Preserving Aggregate Statistics via Boolean Shares.  In SCN, 2022.
  * [3] A. F. Aji and K. Heafield.  Sparse communication for distributed gradient descent.  In EMNLP, 2017.
  * [4] D. Alistarh, T. Hoefler, M. Johansson, N. Konstantinov, S. Khirirat, and C. Renggli.  The Convergence of Sparsified Gradient Methods.  In NeurIPS, 2018.
  * [5] S. Andreina, G. A. Marson, H. Möllering, and G. Karame.  BaFFLe: Backdoor Detection via Feedback-based Federated Learning.  In IEEE ICDCS, 2021.
  * [6] T. Araki, J. Furukawa, Y. Lindell, A. Nof, and K. Ohara.  High-Throughput Semi-Honest Secure Three-Party Computation with an Honest Majority.  In ACM CCS, 2016.
  * [7] G. Asharov, S. Halevi, Y. Lindell, and T. Rabin.  Privacy-Preserving Search of Similar Patients in Genomic Data.  PETS, 2018, 2018.
  * [8] G. Asharov, Y. Lindell, T. Schneider, and M. Zohner.  More efficient oblivious transfer and extensions for faster secure computation.  In ACM CCS, 2013.
  * [9] E. Bagdasaryan, A. Veit, Y. Hua, D. Estrin, and V. Shmatikov.  How To Backdoor Federated Learning.  In AISTATS, 2020.
  * [10] G. Baruch, M. Baruch, and Y. Goldberg.  A Little Is Enough: Circumventing Defenses For Distributed Learning.  In NeurIPS, 2019.
  * [11] R. B. Basat, M. Mitzenmacher, and S. Vargaftik.  How to Send a Real Number Using a Single Bit (And Some Shared Randomness).  In ICALP, 2021.
  * [12] R. B. Basat, S. Vargaftik, A. Portnoy, G. Einziger, Y. Ben-Itzhak, and M. Mitzenmacher.  QUIC-FL: Quick Unbiased Compression for Federated Learning.  2022\.  https://arxiv.org/abs/2205.13341.
  * [13] C. Baum, I. Damgrd, T. Toft, and R. W. Zakarias.  Better Preprocessing for Secure Multiparty Computation.  In ACNS, 2016.
  * [14] C. Beguier, M. Andreux, and E. W. Tramel.  Efficient Sparse Secure Aggregation for Federated Learning.  2020\.  https://arxiv.org/abs/2007.14861.
  * [15] J. H. Bell, K. A. Bonawitz, A. Gascón, T. Lepoint, and M. Raykova.  Secure Single-Server Aggregation with (Poly)Logarithmic Overhead.  In ACM CCS, 2020.
  * [16] A. Ben-Efraim, M. Nielsen, and E. Omri.  Turbospeedz: Double Your Online SPDZ! Improving SPDZ Using Function Dependent Preprocessing.  In ACNS, 2019.
  * [17] J. Bernstein, Y. Wang, K. Azizzadenesheli, and A. Anandkumar.  SIGNSGD: Compressed Optimisation for Non-Convex Problems.  In ICML, 2018.
  * [18] A. Beznosikov, S. Horváth, P. Richtárik, and M. Safaryan.  On Biased Compression for Distributed Learning.  2020\.  https://arxiv.org/abs/2002.12410.
  * [19] A. N. Bhagoji, S. Chakraborty, P. Mittal, and S. B. Calo.  Analyzing Federated Learning through an Adversarial Lens.  In ICML, 2019.
  * [20] P. Blanchard, E. M. E. Mhamdi, R. Guerraoui, and J. Stainer.  Machine Learning with Adversaries: Byzantine Tolerant Gradient Descent.  In NeurIPS, 2017.
  * [21] F. Boemer, R. Cammarota, D. Demmler, T. Schneider, and H. Yalame.  MP2ML: a mixed-protocol machine learning framework for private inference.  In ARES, 2020.
  * [22] F. Boenisch, A. Dziedzic, R. Schuster, A. S. Shamsabadi, I. Shumailov, and N. Papernot.  When the Curious Abandon Honesty: Federated Learning Is Not Private.  2021\.  https://arxiv.org/abs/2112.02918.
  * [23] K. A. Bonawitz, V. Ivanov, B. Kreuter, A. Marcedone, H. B. McMahan, S. Patel, D. Ramage, A. Segal, and K. Seth.  Practical Secure Aggregation for Privacy-Preserving Machine Learning.  In ACM CCS, 2017.
  * [24] E. Boyle, G. Couteau, N. Gilboa, Y. Ishai, L. Kohl, and P. Scholl.  Efficient Pseudorandom Correlation Generators: Silent OT Extension and More.  In CRYPTO, 2019.
  * [25] B. Bozdemir, S. Canard, O. Ermis, H. Möllering, M. Önen, and T. Schneider.  Privacy-preserving Density-based Clustering.  In ACM ASIA CCS, 2021.
  * [26] L. Braun, D. Demmler, T. Schneider, and O. Tkachenko.  MOTION - A Framework for Mixed-Protocol Multi-Party Computation.  ACM Trans. Priv. Secur., 2022.
  * [27] M. Byali, H. Chaudhari, A. Patra, and A. Suresh.  FLASH: Fast and Robust Framework for Privacy-preserving Machine Learning.  PETS, 2020.
  * [28] S. Caldas, J. Konečný, H. B. McMahan, and A. Talwalkar.  Expanding the Reach of Federated Learning by Reducing Client Resource Requirements.  2018\.  http://arxiv.org/abs/1812.07210.
  * [29] X. Cao, M. Fang, J. Liu, and N. Z. Gong.  Fltrust: Byzantine-robust federated learning via trust bootstrapping.  In NDSS, 2021.
  * [30] O. Catrina and A. Saxena.  Secure Computation with Fixed-Point Numbers.  In FC, 2010.
  * [31] H. Chaudhari, A. Choudhury, A. Patra, and A. Suresh.  ASTRA: High Throughput 3PC over Rings with Application to Secure Prediction.  In ACM CCSW@CCS, 2019.
  * [32] H. Chaudhari, R. Rachuri, and A. Suresh.  Trident: Efficient 4PC Framework for Privacy Preserving Machine Learning.  In NDSS, 2020.
  * [33] W. Chen, C. A. Choquette-Choo, P. Kairouz, and A. T. Suresh.  The Fundamental Price of Secure Aggregation in Differentially Private Federated Learning.  In ICML, 2022.
  * [34] J. H. Cheon, A. Kim, M. Kim, and Y. S. Song.  Homomorphic Encryption for Arithmetic of Approximate Numbers.  In ASIACRYPT. Springer, 2017.
  * [35] B. Chmiel, L. Ben-Uri, M. Shkolnik, E. Hoffer, R. Banner, and D. Soudry.  Neural gradients are near-lognormal: improved quantized and sparse training.  In ICLR, 2021.
  * [36] H. Corrigan-Gibbs and D. Boneh.  Prio: Private, Robust, and Scalable Computation of Aggregate Statistics.  In USENIX NSDI, 2017.
  * [37] G. Couteau, P. Rindal, and S. Raghuraman.  Silver: Silent VOLE and Oblivious Transfer from Hardness of Decoding Structured LDPC Codes.  In CRYPTO, 2021.
  * [38] R. Cramer, I. Damgrd, D. Escudero, P. Scholl, and C. Xing.  SPDZ2${}^{\mbox{k}}$: Efficient MPC mod 2${}^{\mbox{k}}$ for Dishonest Majority.  In CRYPTO, 2018.
  * [39] I. Damgrd, D. Escudero, T. K. Frederiksen, M. Keller, P. Scholl, and N. Volgushev.  New Primitives for Actively-Secure MPC over Rings with Applications to Private Machine Learning.  In IEEE S&P, 2019.
  * [40] I. Damgård, M. Keller, E. Larraia, V. Pastro, P. Scholl, and N. P. Smart.  Practical Covertly Secure MPC for Dishonest Majority - Or: Breaking the SPDZ Limits.  In ESORICS, 2013.
  * [41] I. Damgård, C. Orlandi, and M. Simkin.  Yet Another Compiler for Active Security or: Efficient MPC Over Arbitrary Rings.  In CRYPTO, 2018.
  * [42] I. Damgrd, V. Pastro, N. Smart, and S. Zakarias.  Multiparty computation from somewhat homomorphic encryption.  In CRYPTO, 2012.
  * [43] P. Davies, V. Gurunanthan, N. Moshrefi, S. Ashkboos, and D. Alistarh.  New bounds for distributed mean estimation and variance reduction.  In ICLR, 2021.
  * [44] D. Demmler, T. Schneider, and M. Zohner.  ABY - A Framework for Efficient Mixed-Protocol Secure Two-Party Computation.  In NDSS, 2015.
  * [45] Y. Dong, X. Chen, K. Li, D. Wang, and S. Zeng.  FLOD: oblivious defender for private byzantine-robust federated learning with dishonest-majority.  In ESORICS, 2021.
  * [46] T. Elahi, G. Danezis, and I. Goldberg.  PrivEx: Private Collection of Traffic Statistics for Anonymous Communication Networks.  In ACM CCS, 2014.
  * [47] Z. Erkin, J. R. Troncoso-Pastoriza, R. L. Lagendijk, and F. Pérez-González.  Privacy-Preserving Data Aggregation in Smart Metering Systems: An Overview.  IEEE Signal Process. Mag., 2013.
  * [48] D. Escudero, S. Ghosh, M. Keller, R. Rachuri, and P. Scholl.  Improved Primitives for MPC over Mixed Arithmetic-Binary Circuits.  In CRYPTO, 2020.
  * [49] M. Fang, X. Cao, J. Jia, and N. Z. Gong.  Local Model Poisoning Attacks to Byzantine-Robust Federated Learning.  In USENIX Security, 2020.
  * [50] J. Fei, C. Ho, A. N. Sahu, M. Canini, and A. Sapio.  Efficient sparse collective communication and its application to accelerate distributed deep learning.  In ACM SIGCOMM Conference, 2021.
  * [51] H. Fereidooni, S. Marchal, M. Miettinen, A. Mirhoseini, H. Möllering, T. D. Nguyen, P. Rieger, A. Sadeghi, T. Schneider, H. Yalame, and S. Zeitouni.  SAFELearn: Secure Aggregation for private FEderated Learning.  In IEEE S&P Workshops, 2021.
  * [52] J. Furukawa, Y. Lindell, A. Nof, and O. Weinstein.  High-Throughput Secure Three-Party Computation for Malicious Adversaries and an Honest Majority.  In EUROCRYPT, 2017.
  * [53] K. Ganju, Q. Wang, W. Yang, C. A. Gunter, and N. Borisov.  Property Inference Attacks on Fully Connected Neural Networks using Permutation Invariant Representations.  In ACM CCS, 2018.
  * [54] O. Goldreich, S. Micali, and A. Wigderson.  How to Play any Mental Game or A Completeness Theorem for Protocols with Honest Majority.  In ACM STOC, 1987.
  * [55] S. D. Gordon, S. Ranellucci, and X. Wang.  Secure Computation with Low Communication from Cross-Checking.  In ASIACRYPT, 2018.
  * [56] V. Goyal, H. Li, R. Ostrovsky, A. Polychroniadou, and Y. Song.  ATLAS: Efficient and Scalable MPC in the Honest Majority Setting.  In CRYPTO, 2021.
  * [57] A. Hegde, H. Möllering, T. Schneider, and H. Yalame.  SoK: Efficient Privacy-preserving Clustering.  PETS, 2021.
  * [58] E. Hesamifard, H. Takabi, M. Ghasemi, and R. N. Wright.  Privacy-preserving Machine Learning as a Service.  PETS, 2018.
  * [59] M. Ion, B. Kreuter, A. E. Nergiz, S. Patel, S. Saxena, K. Seth, M. Raykova, D. Shanahan, and M. Yung.  On Deploying Secure Computing: Private Intersection-Sum-with-Cardinality.  In IEEE EuroS&P, 2020.
  * [60] N. Ivkin, D. Rothchild, E. Ullah, V. Braverman, I. Stoica, and R. Arora.  Communication-efficient Distributed SGD with Sketching.  In NeurIPS, 2019.
  * [61] R. Jin, Y. Huang, X. He, H. Dai, and T. Wu.  Stochastic-Sign SGD for Federated Learning with Theoretical Guarantees.  2020\.  https://arxiv.org/abs/2002.10940.
  * [62] M. Joye and B. Libert.  A Scalable Scheme for Privacy-Preserving Aggregation of Time-Series Data.  In FC, 2013.
  * [63] C. Juvekar, V. Vaikuntanathan, and A. Chandrakasan.  GAZELLE: A low latency framework for secure neural network inference.  In USENIX Security, 2018.
  * [64] S. Kadhe, N. Rajaraman, O. O. Koyluoglu, and K. Ramchandran.  FastSecAgg: Scalable Secure Aggregation for Privacy-Preserving Federated Learning.  2020\.  https://arxiv.org/abs/2009.11248.
  * [65] P. Kairouz, H. B. McMahan, B. Avent, A. Bellet, M. Bennis, and et al.  Advances and Open Problems in Federated Learning.  Found. Trends Mach. Learn., 2021.
  * [66] S. Kamara and M. Raykova.  Secure outsourced computation in a multi-tenant cloud.  In IBM Workshop on Cryptography and Security in Clouds, 2011.
  * [67] S. P. Karimireddy, S. Kale, M. Mohri, S. J. Reddi, S. U. Stich, and A. T. Suresh.  SCAFFOLD: Stochastic Controlled Averaging for Federated Learning.  In ICML, 2020.
  * [68] M. Keller, E. Orsini, and P. Scholl.  MASCOT: Faster Malicious Arithmetic Secure Computation with Oblivious Transfer.  In ACM SIGSAC, 2016.
  * [69] M. Keller, V. Pastro, and D. Rotaru.  Overdrive: Making SPDZ Great Again.  In EUROCRYPT, 2018.
  * [70] M. Keller, P. Scholl, and N. P. Smart.  An architecture for practical actively secure MPC with dishonest majority.  In ACM CCS, 2013.
  * [71] D. Kim, Y. Son, D. Kim, A. Kim, S. Hong, and J. H. Cheon.  Privacy-preserving Approximate GWAS computation based on Homomorphic Encryption.  2019\.  https://eprint.iacr.org/2019/152.
  * [72] V. Kolesnikov and T. Schneider.  Improved Garbled Circuit: Free XOR Gates and Applications.  In ICALP, 2008.
  * [73] J. Konečný, H. B. McMahan, F. X. Yu, P. Richtárik, A. T. Suresh, and D. Bacon.  Federated Learning: Strategies for Improving Communication Efficiency.  2016\.  http://arxiv.org/abs/1610.05492.
  * [74] N. Koti, M. Pancholi, A. Patra, and A. Suresh.  SWIFT: Super-fast and robust privacy-preserving machine learning.  In USENIX Security, 2021.
  * [75] N. Koti, S. Patil, A. Patra, and A. Suresh.  MPClan: Protocol suite for privacy-conscious computations, 2022.  https://eprint.iacr.org/2022/675.
  * [76] N. Koti, A. Patra, R. Rachuri, and A. Suresh.  Tetrad: Actively Secure 4PC for Secure Training and Inference.  In NDSS, 2022.
  * [77] A. Krizhevsky.  Learning multiple layers of features from tiny images.  Technical report, 2009.
  * [78] K. Kursawe, G. Danezis, and M. Kohlweiss.  Privacy-Friendly Aggregation for the Smart-Grid.  In PETS, 2011.
  * [79] M. Lam, G. Wei, D. Brooks, V. J. Reddi, and M. Mitzenmacher.  Gradient disaggregation: Breaking privacy in federated learning by reconstructing the user participant matrix.  In ICML, 2021.
  * [80] Y. LeCun, L. Bottou, Y. Bengio, and P. Haffner.  Gradient-based learning applied to document recognition.  Proc. IEEE, 1998.
  * [81] K. H. Li, P. P. B. de Gusmão, D. J. Beutel, and N. D. Lane.  Secure aggregation for federated learning in flower.  In ACM International Workshop on Distributed Machine Learning, 2021.
  * [82] L. Li, W. Xu, T. Chen, G. B. Giannakis, and Q. Ling.  RSA: Byzantine-Robust Stochastic Aggregation Methods for Distributed Learning from Heterogeneous Datasets.  In AAAI, 2019.
  * [83] T. Li, A. K. Sahu, M. Zaheer, M. Sanjabi, A. Talwalkar, and V. Smith.  Federated Optimization in Heterogeneous Networks.  In MLSys, 2020.
  * [84] Y. Lindell, B. Pinkas, N. P. Smart, and A. Yanai.  Efficient Constant Round Multi-party Computation Combining BMR and SPDZ.  In CRYPTO, 2015.
  * [85] Y. Lyubarskii and R. Vershynin.  Uncertainty principles and vector quantization.  IEEE Trans. Inf. Theory, 2010.
  * [86] E. Makri, D. Rotaru, F. Vercauteren, and S. Wagh.  Rabbit: Efficient Comparison for Secure Multi-Party Computation.  In FC, 2021.
  * [87] M. Mansouri, M. Önen, W. Ben Jaballah, and M. Conti.  SoK: Secure aggregation based on cryptographic schemes for federated Learning.  In PETS, 2023.
  * [88] S. Mazloom, P. H. Le, S. Ranellucci, and S. D. Gordon.  Secure parallel computation on national scale volumes of data.  In USENIX Security, 2020.
  * [89] B. McMahan, E. Moore, D. Ramage, S. Hampson, and B. A. y Arcas.  Communication-Efficient Learning of Deep Networks from Decentralized Data.  In AISTATS, 2017.
  * [90] L. Melis, C. Song, E. D. Cristofaro, and V. Shmatikov.  Exploiting Unintended Feature Leakage in Collaborative Learning.  In IEEE S&P, 2019.
  * [91] P. Mishra, R. Lehmkuhl, A. Srinivasan, W. Zheng, and R. A. Popa.  Delphi: A cryptographic inference service for neural networks.  In USENIX Security, 2020.
  * [92] P. Mohassel and P. Rindal.  ABY${}^{\mbox{3}}$: A Mixed Protocol Framework for Machine Learning.  In ACM CCS, 2018.
  * [93] P. Mohassel and Y. Zhang.  SecureML: A System for Scalable Privacy-Preserving Machine Learning.  In IEEE S&P, 2017.
  * [94] A. Mondal, Y. More, P. Ramachandran, P. Panda, H. Virk, and D. Gupta.  Scotch: An Efficient Secure Computation Framework for Secure Aggregation.  2022\.  https://arxiv.org/abs/2201.07730.
  * [95] J. Münch, T. Schneider, and H. Yalame.  VASA: Vector AES Instructions for Security Applications.  In ACM ACSAC, 2021.
  * [96] M. Nasr, R. Shokri, and A. Houmansadr.  Comprehensive Privacy Analysis of Deep Learning: Passive and Active White-box Inference Attacks against Centralized and Federated Learning.  In IEEE S&P, 2019.
  * [97] T. D. Nguyen, P. Rieger, H. Chen, H. Yalame, H. Möllering, H. Fereidooni, S. Marchal, M. Miettinen, A. Mirhoseini, F. Koushanfar, A.-R. Sadeghi, T. Schneider, and S. Zeitouni.  FLAME: Taming Backdoors in Federated Learning.  In USENIX Security, 2022.
  * [98] A. E. Ouadrhiri and A. Abdelhadi.  Differential Privacy for Deep and Federated Learning: A Survey.  IEEE Access, 2022.
  * [99] A. Patra, P. Sarkar, and A. Suresh.  Fast Actively Secure OT Extension for Short Secrets.  In NDSS, 2017.
  * [100] A. Patra, T. Schneider, A. Suresh, and H. Yalame.  ABY2.0: Improved Mixed-Protocol Secure Two-Party Computation.  In USENIX Security, 2021.
  * [101] A. Patra, T. Schneider, A. Suresh, and H. Yalame.  SynCirc: Efficient Synthesis of Depth-Optimized Circuits for Secure Computation.  In IEEE HOST, 2021.
  * [102] A. Patra and A. Suresh.  BLAZE: Blazing Fast Privacy-Preserving Machine Learning.  In NDSS, 2020.
  * [103] R. A. Popa, A. J. Blumberg, H. Balakrishnan, and F. H. Li.  Privacy and accountability for location-based aggregate statistics.  In ACM CCS, 2011.
  * [104] A. Pyrgelis, C. Troncoso, and E. D. Cristofaro.  Knock Knock, Who’s There? Membership Inference on Aggregate Location Data.  In NDSS, 2018.
  * [105] M. S. Riazi, M. Samragh, H. Chen, K. Laine, K. E. Lauter, and F. Koushanfar.  XONN: XNOR-based Oblivious Deep Neural Network Inference.  In USENIX Security, 2019.
  * [106] P. Richtárik, I. Sokolov, and I. Fatkhullin.  EF21: A New, Simpler, Theoretically Better, and Practically Faster Error Feedback.  In NeurIPS, 2021.
  * [107] D. Rotaru and T. Wood.  MArBled Circuits: Mixing Arithmetic and Boolean Circuits with Active Security.  In INDOCRYPT, 2019.
  * [108] D. Rothchild, A. Panda, E. Ullah, N. Ivkin, I. Stoica, V. Braverman, J. Gonzalez, and R. Arora.  FetchSGD: Communication-Efficient Federated Learning with Sketching.  In ICML, 2020.
  * [109] M. Safaryan, E. Shulgin, and P. Richtárik.  Uncertainty Principle for Communication Compression in Distributed and Federated Learning and the Search for an Optimal Compressor.  2020\.  https://arxiv.org/abs/2002.08958.
  * [110] S. Sav, A. Pyrgelis, J. R. Troncoso-Pastoriza, D. Froelicher, J.-P. Bossuat, J. S. Sousa, and J.-P. Hubaux.  POSEIDON: Privacy-preserving federated neural network learning.  In NDSS, 2021.
  * [111] F. Seide, H. Fu, J. Droppo, G. Li, and D. Yu.  1-bit stochastic gradient descent and its application to data-parallel distributed training of speech DNNs.  In INTERSPEECH, 2014.
  * [112] V. Shejwalkar and A. Houmansadr.  Manipulating the Byzantine: Optimizing Model Poisoning Attacks and Defenses for Federated Learning.  In NDSS, 2021.
  * [113] V. Shejwalkar, A. Houmansadr, P. Kairouz, and D. Ramage.  Back to the Drawing Board: A Critical Evaluation of Poisoning Attacks on Production Federated Learning.  In IEEE S&P, 2022.
  * [114] R. Shokri, M. Stronati, C. Song, and V. Shmatikov.  Membership Inference Attacks Against Machine Learning Models.  In IEEE S&P, 2017.
  * [115] J. So, B. Güler, and A. S. Avestimehr.  Turbo-Aggregate: Breaking the Quadratic Aggregation Barrier in Secure Federated Learning.  IEEE J. Sel. Areas Inf. Theory, 2021.
  * [116] S. U. Stich, J.-B. Cordonnier, and M. Jaggi.  Sparsified SGD with Memory.  In NeurIPS, 2018.
  * [117] I. Stoica and S. Shenker.  From cloud computing to sky computing.  In ACM HotOS ’21: Workshop on Hot Topics in Operating Systems, 2021\.
  * [118] Z. Sun, P. Kairouz, A. T. Suresh, and H. B. McMahan.  Can you really backdoor federated learning?  In NeurIPS FL Workshop, 2019.
  * [119] A. Suresh.  MPCLeague: Robust MPC Platform for Privacy-Preserving Machine Learning.  PhD Thesis, 2021.  https://arxiv.org/abs/2112.13338.
  * [120] A. T. Suresh, F. X. Yu, S. Kumar, and H. B. McMahan.  Distributed Mean Estimation with Limited Communication.  In ICML, 2017.
  * [121] H. Tang, S. Gan, A. A. Awan, S. Rajbhandari, C. Li, X. Lian, J. Liu, C. Zhang, and Y. He.  1-bit Adam: Communication Efficient Large-Scale Training with Adam’s Convergence Speed.  In ICML, 2021.
  * [122] S. Vargaftik, R. B. Basat, A. Portnoy, G. Mendelson, Y. Ben-Itzhak, and M. Mitzenmacher.  EDEN: Communication-Efficient and Robust Distributed Mean Estimation for Federated Learning.  In ICML, 2022.
  * [123] S. Vargaftik, R. Ben-Basat, A. Portnoy, G. Mendelson, Y. Ben-Itzhak, and M. Mitzenmacher.  DRIVE: One-bit Distributed Mean Estimation.  In NeurIPS, 2021.
  * [124] J. Wang, Z. Charles, Z. Xu, G. Joshi, H. B. McMahan, and et al.  A Field Guide to Federated Optimization.  2021\.  https://arxiv.org/abs/2107.06917.
  * [125] L. Wang, S. Xu, X. Wang, and Q. Zhu.  Eavesdrop the Composition Proportion of Training Labels in Federated Learning.  2019\.  http://arxiv.org/abs/1910.06044.
  * [126] W. Wen, C. Xu, F. Yan, C. Wu, Y. Wang, Y. Chen, and H. Li.  TernGrad: Ternary Gradients to Reduce Communication in Distributed Deep Learning.  In NeurIPS, 2017.
  * [127] H. Xiao, B. Biggio, G. Brown, G. Fumera, C. Eckert, and F. Roli.  Is Feature Selection Secure against Training Data Poisoning?  In ICML, 2015.
  * [128] C. Yang, J. So, C. He, S. Li, Q. Yu, and S. Avestimehr.  LightSecAgg: Rethinking Secure Aggregation in Federated Learning.  2021\.  https://arxiv.org/abs/2109.14236.
  * [129] A. C.-C. Yao.  Protocols for Secure Computations (Extended Abstract).  In FOCS, 1982.
  * [130] D. Yin, Y. Chen, K. Ramchandran, and P. L. Bartlett.  Byzantine-Robust Distributed Learning: Towards Optimal Statistical Rates.  In ICML, 2018.
  * [131] Z. Zhang, A. Panda, L. Song, Y. Yang, M. W. Mahoney, P. Mittal, K. Ramchandran, and J. Gonzalez.  Neurotoxin: Durable Backdoors in Federated Learning.  In ICML, 2022.

##  Appendix A Related Work & Background Information

In this section, we review additional related work in the area of compression
techniques, (approximate) MPC, secure aggregation, and FL attacks as well as
defenses.

###  A.1 Additional Compression Techniques

In this work, we focus on quantization as a means to reduce bandwidth. We
nevertheless briefly overview some additional techniques considered for FL
gradient compression.

Sparsification. Some works consider sparsifying the gradients (e.g., [50, 116,
3, 73]). Quantization is mostly orthogonal to such techniques as it can be
applied to the sparsified gradients. Namely, sparsification is designed to
reduce the number of entries, whereas quantization reduces the number of bits
used to represent each entry.

Client-side Memory-based Techniques. Some compression techniques, including
Top-$k$ [116] and sketching [60], rely on client-side memory and error-
feedback [111, 4, 106, 18] to ensure convergence. We consider the cross-device
FL setup where clients are stateless (e.g., a client may appear only once
during a training procedure). Therefore, client-side-memory-based techniques
are mostly designed for the cross-silo FL setup and are less applicable to
cross-device FL.

Entropy Encodings. Some techniques use entropy encoding such as arithmetic
encoding and Huffman encoding (e.g., [120, 122, 4]). While such techniques are
appealing in their bandwidth-to-accuracy trade-offs, it is unclear how to
allow for an efficient secure aggregation with such techniques as gradients
must be decoded before being averaged. Also, such techniques usually incur a
higher computational overhead at the clients than fixed-length
representations.

Finally, an additional review of current state-of-the-art gradient compression
techniques and some open challenges can be found in [65, 73, 124].

###  A.2 Secure Multi-party Computation

The field of secure multi-party computation (MPC) started with the seminal
work of Yao [129] in 1982. It enables to securely compute arbitrary functions
on private inputs without leaking anything beyond what can be inferred from
the output. Since then, the field of MPC has seen a variety of advancements of
used primitives effectively improving communication and computation
efficiency, e.g., [72, 8, 24, 48, 95]. Also, tailored efficient optimizations
for varying number of computation parties have been explored, e.g., [44, 100,
31, 32, 76, 101]. Moreover, MPC research considers different assumptions
regarding adversarial behavior such as the well-known semi-honest [44, 26] and
malicious security model [39, 68, 70, 69]) as well as numbers of corrupted
computation parties (e.g., honest majority [54, 56] or dishonest majority/full
threshold security [38, 70, 26, 100, 44]). Beyond running the computation
among several non-colluding parties, another well-established system model
(which we use in our work) is outsourcing, where the data owners secret-share
their private input data among a set of non-colluding computing parties which
then run the private computation on their behalf. In this scenario, the a
semi-honest MPC protocol also protects against malicious behavior of data
owners [66].

###  A.3 Approximate Secure Computation

To improve efficiency of MPC, few works already considered approximations of
the exact computation. Such approximations in MPC include using integer or
fixed-point instead of floating-point operations (too many works to cite),
approximations in genomic computation [7], and in privacy-preserving machine
learning such as for division [30], activation functions [93, 58, 27], and
completely changing the classifier to be MPC-friendly [105]. Also, for FHE,
approximations are used such as in the approximate HE scheme CKKS [34], which
is implemented in the HEAAN library999https://github.com/snucrypto/HEAAN and
was used for approximate genomic computations in [71]. In this work, we
propose for the first time to use approximations to substantially improve
efficiency of FL when combined with MPC and give detailed evaluations on the
errors introduced thereby.

###  A.4 Secure Aggregation & Inference Attacks

Performing secure aggregation without revealing anything about the aggregated
input values beyond what can be inferred from the output was already
investigated more than 10 years ago, for example, in the context of smart
metering, e.g., [47, 78]. It has come a long way since then, resulting in
practical solutions for real-world applications nowadays.

For example, Prio [36] introduces secure protocols for aggregate statistics
such as sum, mean, variance, standard deviation, min/max, and frequency. It
uses additive arithmetic secret sharing, offers full-threshold security among
a small set of servers running the secure computation, and validates inputs to
protect against malicious clients. Prio+ [2] optimizes client computation and
communication compared to [36] with a Boolean secret sharing-based client
input validation and an additional conversion from Boolean to arithmetic
sharing. In our work, we optimize the naive bit-to-arithmetic conversion
presented in [2] for our $\mathcal{F}_{\mathsf{SecAgg}}$ protocol (cf. §4.1).
Bell et al. [15] propose the first secure aggregation protocols in both the
semi-honest and malicious security model (tolerating server and client
corruptions) with poly-logarithmic client communication and computation. Popa
et al. [103] specifically focus on secure location-based aggregation
statistics, Joye et al. [62] on time-series data, and PrivEx [46] on traffic
data in anonymous communication.

Inference attacks. In FL, clients share locally trained model updates with a
central party to contribute to the training of a global model. However,
sharing those local models makes the system vulnerable to data leakage. Even a
semi-honest central server can learn confidential information about the used
private training data by analyzing the received local model updates [22, 79,
96].

A common countermeasure against inference attacks is to use secure
aggregation. As FL poses specific challenges such as a large number of clients
and drop-out tolerance, tailored secure aggregation protocols for FL have been
proposed [23, 51, 15, 110, 64, 115]. Those hide individual updates, ensuring
that the server has only access to global updates, hence, effectively
prohibiting the analysis of individual updates for inference attacks. The
first scheme, SegAgg [23], combines secret sharing with authenticated
symmetric encryption, but requires 4 communication rounds per training
iteration among servers and client. Similar issues can also be observed for
other existing secure aggregation protocols for FL as they incur significant
computation and communication overhead: Fereidonni et al. [51] compare several
secure aggregation protocols with respect to efficiency and practicality.
Mansouri et al. [87] give a SoK of secure aggregation schemes w.r.t. their
suitability for FL.

To the best of our knowledge, only Chen et al. [33] and Beguier et al. [14]
have considered both compression and secure aggregation in combination for FL.
Specifically, Chen et al. [33] combine SegAgg [23] with sparse random
projection and count-sketching [108] for compression. Moreover, they add noise
using a distributed discrete Gaussian mechanism to generate a differential
private output. Beguier et al. [14] combine arithmetic secret-sharing with
Top-$k$ sparsification [116] and 1-bit quantization [17]. As pointed out in
§A.1, both sketching and sparsification are suboptimal for our envisioned
cross-device setting given that they require memory and error-feedback on the
client side. In contrast, we focus on a dynamic scenario where clients might
drop-out at any time and may contribute only once to the training. [14] offers
are more efficient secure aggregation than using SepAgg [23], but we further
improve client-side communication thanks to our (approximated) secure bit
aggregation (cf. §3).

###  A.5 Poisoning Attacks & Defenses

Poisoning attacks can be categorized into untargeted and targeted attacks
based on the goals of the attacker [49]. In the former case, the attacker aims
to corrupt the global model so that it reduces or even destroys the
performance of the trained model for a large number of test inputs, yielding a
final global model with a high error rate [49, 112, 10]. In the latter case,
the attacker aims to activate attacker-defined triggers that cause a victim
model to do targeted misclassifications, which can then be activated in the
inference phase [19, 118]. Notably, other classification results without the
trigger behave normally and main task accuracy remains high. The second class
of attacks is sometimes also referred to as  _backdoor attacks_ [9]. As
discussed in §5, we consider only untargeted poisoning following the argument
in [113]: This class of attacks is particularly challenging as service
providers may not notice they are under attack given they do not know which
accuracy is achievable in a fresh training of a new model. Also, even small
accuracy reductions can lead to serious economical losses.

Below, we detail three state-of-the-art untargeted poisoning attacks, LIE
[10], Fang [49], and Shejwalkar et al. [112], which are most relevant to our
work.

_Little is Enough (LIE) attack[10]._ In LIE [10], malicious clients manipulate
their local updates by adding noise drawn from the normal distribution to the
gradients of “clean” updates they created following the normal training
process to cause a disorientation. LIE is assuming independent and identically
distributed (iid) data and was tested against various robust aggregations such
as trimmed-mean [130].

_Fang et al.[49]._ The authors of [49] formulate their untargeted poisoning
attack as an optimization problem where the manipulated updates aim at
maximally disorienting the global model from the benign direction. However,
they assume the adversary to either know or guess the deployed (robust)
aggregation mechanism. Additionally, the attack was shown to be ineffective
for iid as well as severely unbalanced non-iid training datasets [112].

_Shejwalkar and Houmansadr[112]._ The attacks of Shejwalkar and Houmansadr
[112] follow a similar idea as [49]: they maximize the distances between
benign and malicious updates while using the evasion of outlier-based
detection mechanisms as a boundary. Concretely, they formalize the “Min-Max”
optimization problem as follows:

$\displaystyle\operatorname*{argmax}_{\gamma}\
\max_{i\in[n]}\lVert\nabla^{m}-\nabla_{i}\rVert_{2}\leq\max_{i,j\in[n]}\lVert\nabla_{i}-\nabla_{j}\lVert_{2}$
(15)
$\displaystyle\nabla^{m}=\mathsf{f}_{\mathsf{avg}}(\nabla_{\\{i\in[n]\\}})+\gamma\nabla^{p},$
(16)

where $\mathsf{f}_{\mathsf{avg}}(\nabla_{\\{i\in[n]\\}})$ is the average
gradient and $\gamma$ $\nabla^{p}$ is the adversary’s perturbation vector,
i.e., either the inverse unit vector of the (simulated) benign gradients, the
inverse average standard deviations, or the average gradient with flipped sign
of all updates. For details, we refer to §IV in [112].

Note that although the authors of [112] suggest several flavours of their
attack based on different levels of adversarial knowledge, we compare to their
Min-Max attack as it (1) does not make the unrealistic assumption that an
adversary knows defenses in place and (2) it is more destructive than LIE [10]
for almost all datasets [112]. We do not consider Fang et al. [49]’s attack as
it requires the guess of the robust aggregation rule, i.e., defense mechanism,
which is unrealistic in a real-world deployment. Taking those considerations
into account, we evaluate the robustness of ScionFL-Aura against the state-of-
the-art Min-Max attack of [112] in §5.1.2.

Poisoning Defenses. As simple parameter-wise averaging is very sensitive to
outliers and, thus, can easily hamper accuracy, Byzantine-robust defenses aim
to make FL robust against (untargeted) attacks. To do so, Krum [20] selects
only one local update, namely the one with the closest $n-m-2$ local updates
as update for the global model, where $n$ is the number of clients and $m$ the
number of anticipated malicious clients. Multi-krum [20] extends this idea to
a selection of $c$ (instead of just one) updates. Median [130] is an another
coordinate-wise aggregation selecting the coordinate-wise median of each
update parameter. A straightforward idea to assess (to some extent) if a
specific gradient is malicious is to use an auxiliary dataset (rootset) at the
aggregator to validate the performance of the updated global model [29, 45,
82]. FLTrust [29] and FLOD [45] use the ReLU-clipped cosine-similarity/Hamming
distance between each received update and the aggregator-computed baseline
update based on the auxiliary dataset. RSA [82] uses an $\ell_{1}$-norm-based
regularization, which is also comparing to the aggregator-computed baseline
update. The recently proposed Divider and Conquer (DnC) aggregation [112]
combines dimensionality reduction using random sampling with an outlier-based
filtering.

The so far discussed poisoning defenses are not compatible with secure
aggregation protocols in a straight-forward manner or lead to an intolerable
overhead. Only two works, namely FLAME [97] and BaFFLe [5] simultaneously
consider both threats. Concretely, FLAME [97] uses a density-based clustering
to remove updates with significantly different cosine distances (i.e.,
different directions) combined with clipping (for more subtle
manipulations).101010As FLAME contains some similar components as ScionFL-
Aura, we give a detailed comparison in §B.3.3. BaFFLe [5] introduces a
feedback loop enabling a subset of clients to evaluate each global model
update, while being compatible with arbitrary secure aggregation schemes.

In our work, we combine (1) communication efficiency due to quantization, (2)
data privacy due to secure aggregation, and (3) robustness due to a novel
poisoning defense.

##  Appendix B Additional Information

This section provides additional details for our constructions. We begin with
some preliminary information and details about the Hadamard and Kashin
quantization techniques. This will be followed by information about the
underlying MPC scheme used in our work, and finally, additional information
about our framework, including benchmarks.

###  B.1 Preliminaries

######  Lemma B.1 (Expected Values).

Given $n,p\in\mathbb{Z}$, we have

  1. 1.

$\sum\limits_{p=0}^{n}p\cdot\binom{n}{p}=n\cdot 2^{n-1}.$

  2. 2.

$\sum\limits_{p=0}^{\lfloor
n/2\rfloor}2p\cdot\binom{n}{2p}=\sum\limits_{p=0}^{\lfloor
n/2\rfloor}(2p+1)\cdot\binom{n}{2p+1}=n\cdot 2^{n-2}.$

###### Proof.

Consider the binomial formula for $(1+y)^{n}$, given by

$\sum\limits_{p=0}^{n}\binom{n}{p}y^{p}=(1+y)^{n}$ (17)

Differentiating Eq. (17) with respect to $y$ will give

$\sum\limits_{p=0}^{n}\binom{n}{p}p\cdot y^{p-1}=n\cdot(1+y)^{n-1}$ (18)

Substituting $y=1$ in Eq. (18) gives the first result (1). Similarly, setting
$y=-1$ in Eq. (18) gives

$\sum\limits_{p=0}^{n}(-1)^{p-1}p\cdot\binom{n}{p}=0$ (19)

Combining Eq. (19) with the first result (1) will give the second result (2).
∎

####  B.1.1 Overhead of HSQ and KSQ Quantization

For being able to use an efficient GPU-friendly implementation of the
randomized Hadamard transform, which we use for both rotating the gradients in
HSQ and for calculating Kashin’s coefficients in KSQ, we require that the
gradients’ size to be a power of 2. A simple solution to meet this requirement
is padding. For example, for the LeNet architecture with $\approx 60k$
parameters, we can pad the gradient to $2^{16}=65536$ entries with a small
resulting overhead of $\approx 6.2\%$ (i.e., using $\approx 1.06$ bits per
coordinate instead of 1). However, a more sophisticated approach is to divide
the gradient into decreasing power-of-two-sized chunks and inflate only the
last (smallest) chunk.111111The size of the last chunk is kept above some
threshold, e.g., $2^{9}$ to keep the overhead of the scales small. For
example, for the LeNet architecture, we can decompose it into chunks of size
$32768,16384,8192,4096,512$, that sum up to $61952$ (with an additional
overhead of two floats per chunk) with a resulting overhead of only $\approx
1.44\%$. Also, for Kashin’s representation, we use $\lambda=1.15$ for each
chunk (an extra $15\%$ of space) as used in previous works (e.g., [123]). To
summarize, we state these resulting overheads in Tab. 3.

Architecture | $n$ | SQ | HSQ | KSQ
---|---|---|---|---
LeNet | 61706 | 61706 | 62272 | 73024
ResNet9 | 4903242 | 4903242 | 4915456 | 5767424
ResNet18 | 11220132 | 11220132 | 11272192 | 12583040

Table 3: Exact number of bits used for different network architectures and
quantization schemes compared to the baseline number of coordinates $n$.

####  B.1.2 MPC Protocols

In this section, we go over the details of the underlying MPC protocols used
in our scheme. We consider three MPC servers,
$\mathcal{S}=\\{\mathsf{S}_{1},\mathsf{S}_{2},\mathsf{S}_{3}\\}$, to which the
clients delegate the aggregation computation, as shown in Fig. 1. All the
operations are carried out in either an $\ell$-bit ring,
$\mathbb{Z}_{2^{\ell}}$, or a binary ring, $\mathbb{Z}_{2}$. Before we go into
the protocols, we provide additional details regarding the masked evaluation
scheme [84, 16, 119] discussed in §4, starting with the sharing semantics.

Sharing Semantics. We use two different sharing schemes in our protocols:

  1. 1.

_$[\cdot]$ -sharing._ A value $\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$ is said to
be $[\cdot]$-shared among MPC servers in $\mathcal{S}$, if each server
$\mathsf{S}_{i}$, for $i\in[3]$, holds
$\mathsf{v}_{i}\in\mathbb{Z}_{2^{\ell}}$ such that
$\mathsf{v}_{1}+\mathsf{v}_{2}+\mathsf{v}_{3}=\mathsf{v}$.

  2. 2.

_$\langle\cdot\rangle$ -sharing._ In this sharing, every
$\mathsf{v}\in\mathbb{Z}_{2^{\ell}}$ is associated with two values: a random
mask ${\lambda}_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$ and a masked value
$\mathsf{m}_{\mathsf{v}}\in\mathbb{Z}_{2^{\ell}}$, such that
$\mathsf{v}=\mathsf{m}_{\mathsf{v}}+{\lambda}_{\mathsf{v}}$. Here, the share
of an MPC server is defined as a tuple of the form
$(\mathsf{m}_{\mathsf{v}},[{\lambda}_{\mathsf{v}}])$.

Handling Decimal Values. While the MPC protocol that we utilize is designed
over a ring architecture, the underlying FL algorithms handle decimal numbers.
To address this compatibility issue, we employ the well-known Fixed-Point
Arithmetic (FPA) technique [30, 93, 92], which encodes a decimal number in
$\ell$-bits using the 2’s complement representation. The sign bit is
represented by the most significant bit, while the $\mathsf{f}$ least
significant bits are kept for the fractional component. We use $\ell=32$ bit
values with $\mathsf{f}=16$ in this work.

We will now go over the MPC protocols used in our scheme. The protocols are
presented in a generic manner because our approach is not restricted to any
specific MPC setting. Hence, some of the sub-protocols are treated as black-
boxes that can be instantiated using any efficient protocols in the underlying
MPC setting. Also, we assume that the protocols’ inputs are in
$\langle\cdot\rangle$-shared form, and that the output is generated in
$\langle\cdot\rangle$-shared form among the MPC servers.

Inner Product Computation. Given two $\mathsf{d}$-sized column vectors
$\vec{\mathbf{X}}$ and $\vec{\mathbf{Y}}$, protocol $\Pi_{\sf IP}$ computes
the inner product of the two vectors, defined as
$z=\vec{\mathbf{X}}\odot\vec{\mathbf{Y}}=\sum_{i=1}^{\mathsf{d}}{\mathbf{X}}_{i}^{1}\cdot{\mathbf{Y}}_{i}^{1}$.
For simplicity, consider the multiplication of two values
$x,y\in\mathbb{Z}_{2^{\ell}}$ as per the $\langle\cdot\rangle$-sharing
semantics. We have

$\displaystyle z=xy$
$\displaystyle=(\mathsf{m}_{x}+{\lambda}_{y})(\mathsf{m}_{x}+{\lambda}_{y})$
$\displaystyle=\mathsf{m}_{x}\mathsf{m}_{y}+\mathsf{m}_{x}{\lambda}_{y}+\mathsf{m}_{y}{\lambda}_{x}+{\lambda}_{x}{\lambda}_{y}.$

Since the ${\lambda}$ values are independent of the underlying secret, the
servers can compute $[\cdot]$-shares of the term ${\lambda}_{x}{\lambda}_{y}$
during preprocessing. This enables the servers to locally compute
$[\cdot]$-shares of $z$ during the online phase.

Preprocessing: 1. Execute $\Pi_{\sf IP}^{\sf
Pre}([\vec{\mathbf{{\lambda}_{X}}}],[\vec{\mathbf{{\lambda}_{Y}}}])$ to obtain
$[{\gamma}_{z}]$ with
${\gamma}_{z}=\vec{\mathbf{{\lambda}_{X}}}\odot\vec{\mathbf{{\lambda}_{Y}}}$.
2. Execute $\Pi_{\sf Tr}()$ to generate $([r],\langle
r/2^{\mathsf{f}}\rangle)$. Online: 1. $\mathsf{S}_{j}$, for $j\in[\tau]$,
locally computes the following ($\Delta=1$ if $j=1$, else $0$): •
$[(z-r)]_{j}=\Delta\cdot(\mathsf{m}_{\vec{\mathbf{X}}}\odot\mathsf{m}_{\vec{\mathbf{Y}}})+\mathsf{m}_{\vec{\mathbf{X}}}\odot[{\lambda}_{\vec{\mathbf{Y}}}]_{j}+\mathsf{m}_{\vec{\mathbf{Y}}}\odot[{\lambda}_{\vec{\mathbf{X}}}]_{j}+[{\gamma}_{z}]_{j}-[r]_{j}$.
2. $\mathsf{S}_{j}$, for $j\in[\tau]$, sends $[(z-r)]_{j}$ to
$\mathsf{S}_{1}$, who computes $(z-r)$ and sends to all the servers. 3.
Locally compute $\langle z\rangle=\langle(z-r)/2^{\mathsf{f}}\rangle+\langle
r/2^{\mathsf{f}}\rangle$. Figure 11: Inner product protocol.

In addition to the above observation, since we operate over FPA
representation, truncation [30, 93] must be performed in order to keep the
result $z$ in FPA format after a multiplication. For this, we use the
truncation pair method [92], wherein a tuple of the form
$(r,r/2^{\mathsf{f}})$ is generated in $\langle\cdot\rangle$-shared form among
the servers during the preprocessing. Then, with very high probability, we
have

$z/2^{\mathsf{f}}=(z-r)/2^{\mathsf{f}}+r/2^{\mathsf{f}}.$

Hence, during the online phase, servers publicly open the value $(z-r)$ and
apply the above transformation to obtain the $\langle\cdot\rangle$-shares of
truncated $z$, completing the protocol.

Now, in the case of the inner-product, the task can be split into $\mathsf{d}$
multiplications and the result obtained accordingly. Furthermore, because the
desired result is the sum of the individual multiplication results, servers
can sum them and communicate in a single shot, saving communication cost
[100]. The formal protocol appears in Fig. B.1.2.

Bit-to-Arithmetic Protocol. Given the Boolean sharing of
$\mathsf{b}\in\mathbb{Z}_{2}$, protocol $\Pi_{\sf BitA}$ computes the
arithmetic sharing of the bit $\mathsf{b}$ over $\mathbb{Z}_{2^{\ell}}$. As
shown in Eq. 12, the arithmetic equivalent $\tilde{\mathsf{b}}$ for a bit
$\mathsf{b}=\mathsf{m}_{\mathsf{b}}\oplus{\lambda}_{\mathsf{b}}$ can be
obtained as

$\displaystyle\tilde{\mathsf{b}}=\mathsf{m}_{\mathsf{b}}\oplus{\lambda}_{\mathsf{b}}=\mathsf{M}_{\mathsf{b}}+(1-2\mathsf{m}_{\mathsf{b}})\cdot{\Lambda}_{\mathsf{b}}.$

Here, $\mathsf{M}_{\mathsf{b}}$ and ${\Lambda}_{\mathsf{b}}$ denote the
arithmetic equivalents of $\mathsf{m}_{\mathsf{b}}$ and
${\lambda}_{\mathsf{b}}$ respectively. In our protocol shown in Fig. B.1.2,
MPC servers invoke $\Pi_{\sf BitA}^{\sf Pre}$ protocol on the Boolean
$[\cdot]$-shares of ${\lambda}_{\mathsf{b}}$ in the preprocessing phase to
obtain its respective arithmetic shares. This enables the servers to locally
compute an additive sharing of $\tilde{\mathsf{b}}$ during the online phase,
as shown above. The rest of the steps proceed similar to the case with inner-
product protocol and we omit the details.

To instantiate $\Pi_{\sf BitA}^{\sf Pre}$, we use SPDZ-style computations [68,
107], where oblivious transfer (OT) instances [8, 99, 24, 37] are used among