# Federated Learning is Better with
Non-Homomorphic Encryption

Konstantin Burlachenko  AI Initiative, KAUSTThuwalSaudi Arabia ,  Abdulmajeed
Alrowithi  Saudi Data and AI AuthorityRiyadhSaudi Arabia ,  Fahad Ali Albalawi
Saudi Data and AI AuthorityRiyadhSaudi Arabia and  Peter Richtárik  AI
Initiative, KAUSTThuwalSaudi Arabia

(2023)

###### Abstract.

Traditional AI methodologies necessitate centralized data collection, which
becomes impractical when facing problems with network communication, data
privacy, or storage capacity. Federated Learning (FL) offers a paradigm that
empowers distributed AI model training without collecting raw data. There are
different choices for providing privacy during FL training. One of the popular
methodologies is employing Homomorphic Encryption (HE) - a breakthrough in
privacy-preserving computation from Cryptography. However, these methods have
a price in the form of extra computation and memory footprint. To resolve
these issues, we propose an innovative framework that synergizes permutation-
based compressors with Classical Cryptography, even though employing Classical
Cryptography was assumed to be impossible in the past in the context of FL.
Our framework offers a way to replace HE with cheaper Classical Cryptography
primitives which provides security for the training process. It fosters
asynchronous communication and provides flexible deployment options in various
communication topologies.

Federated Learning, Privacy Preserving Machine Learning, Asynchronous
Training, Security, Optimization, AES, CKKS.

King Abdullah University of Science and Technology

††journalyear: 2023††copyright: rightsretained††conference: Proceedings of the
4th International Workshop on Distributed Machine Learning; December 8, 2023;
Paris, France††booktitle: Proceedings of the 4th International Workshop on
Distributed Machine Learning (DistributedML ’23), December 8, 2023, Paris,
France††doi: 10.1145/3630048.3630182††isbn: 979-8-4007-0447-5/23/12

###  1\. Introduction

Effective machine learning models necessitate vast training data from diverse
sources (Zhang et al., 2020). However, such data, often dispersed across
various entities, faces sharing restrictions due to privacy concerns (Jiang et
al., 2021; Liu et al., 2022). Federated learning (FL) provides a viable
solution, enabling collaborative global model training without exposing
sensitive information (McMahan et al., 2017; Kairouz et al., 2021). FL
algorithms bifurcate into cross-device FL, involving big amount of devices,
and cross-silo FL, typically engaging several distinct organizations (Liu et
al., 2022). In both cases, preserving the privacy of clients’ datasets is
significant. FL strives to ensure confidentiality by retaining private data on
the client side, yet it falls short of providing substantial privacy
assurance. Model parameters and derived quantities from it, transmitted from
clients to a server, may embed sensitive data (see Appendix E.1). Detailed
information about privacy methods for FL is presented in Appendix D. We
briefly discuss two of them.

Differential Privacy (DP) is an approach to assess the privacy of a specific
Algorithm provided by Dwork et al. (2006a, b). DP algorithms ensure that, for
any set of training examples, no attacker, no matter how powerful, can not
learn much more information about a single training example than they could if
this example had been excluded from the training data. Despite offering
privacy protection for individual users, integrating DP with FL could amplify
communication overhead, diminish accuracy. When striving for strong privacy
guarantees in scenarios where the user count is small (which is possible in
cross-silo settings) the noise impact from DP technics makes training
challenging. Understanding the convergence of SGD with DP is an active
research topic (Chen et al., 2020).

While DP statistically hides the training data, Homomorphic Encryption (HE)
provides means to perform computation operations under encrypted numbers from
$\mathbb{Z}^{d}$, $\mathbb{R}^{d}$, $\mathbb{B}^{d}$ without decryption,
protecting input and output from execution part. Therefore HE can be used for
aggregating encrypted gradients (Liu et al., 2019; Aono et al., 2017) in a
server that clients do not trust, given that master has a public key.

###### Classical Cryptography in FL

Classical Cryptography operates on the binary representation of data. It does
not preserve even linear relations in a homomorphic way. The fact of
exhibiting poor algebraic properties is an underlying reason why using
Classical Cryptography was considered challenging by previous research papers
(Kaissis et al., 2020; Jain and Cherukuri, 2023). In these works, authors
stated that Advanced Encryption Standard (AES) (Daemen and Rijmen, 2001) is
not suitable for FL or is challenging.

###### Communication Compression in FL

Numerous compression methods such as quantization (Wen et al., 2017; Safaryan
and Richtárik, 2019), sparsification (Wangni et al., 2018; Alistarh et al.,
2018), and dithering (Alistarh et al., 2017; Horvóth et al., 2022) have been
explored to mitigate communication cost during FL training. However, these
techniques necessitate secure server-side aggregation, and there are no
guarantees that communication reduction techniques and techniques aimed to
preserve privacy or security are combinable.

###### Research Contributions

We discovered that recently proposed permutated correlated compressors
(Szlendak et al., 2021) PermK exhibit properties essential for using Classical
Cryptography in FL while preserving the ability of Communication Compression.
In our work, we introduce a framework that provides privacy and secure
preserving training process to FL applications in which previously HE methods
have been used. Summary of our contributions:

  1. (1)

We addressed the challenge previously mentioned in (Kaissis et al., 2020; Jain
and Cherukuri, 2023) that usage of AES is challenging in FL.

  2. (2)

We demonstrated the operational advantages of the proposed privacy and secure
aware optimization Alg. 3 over HE in the setting in which HE is typically
applied in FL.

  3. (3)

We illustrated the framework’s capability to train ResNet-18 (He et al.,
2016a) DL model in CIFAR-10, and carried the discussion of potential benefits
for DL in Appendix I.

  4. (4)

We demonstrated a possibility of computation communication overlap and
handling compute heterogeneity in Appendix H.2. Deployment flexibility in
communication topologies is discussed in Appendix J.

To support readers with various backgrounds we provide (i) glossary in
Appendix A; (ii) details about AES in Appendix F; (iii) overview of privacy
mechanisms in FL in Appendix D, discussion about the difference between
privacy and security in Appendix E.2; (iv) overview of CKKS in Appendix G (see
Table of Content at p.Appendix).

###  2\. Problem Formulation

In this work, we develop a practical communication efficient privacy and
secure aware framework for FL training.

###### Requirements for Optimization Objective

From the perspective of machine learning (ML), our objective is to select a
function from a parameterized function class $\mathcal{F}$ indexed by
$x\in\mathbb{R}^{d}$, by solving the following optimization problem:

(1)
$\textstyle\min\limits_{x\in\mathbb{R}^{d}}\left\\{f(x)\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{1}{n}\sum\limits_{i=1}^{n}f_{i}(x)\right\\},$

Here, $n\in\mathbb{N}$ represents the number of clients, and
$x\in\mathbb{R}^{d}$ denotes the $d$ parameters or weights of a model
$\hat{F}(\cdot;x)\in\mathcal{X}\to\mathcal{Y}$ that need to be learned across
all $n$ clients. The function $f_{i}:\mathbb{R}^{d}\to\mathbb{R}$ provides the
score criteria for using the model $\hat{F}(\cdot;x)$ on the client’s $i$
data. In the context of FL the functions $f_{i}$ typically represented as:

(2) $\textstyle
f_{i}(x)=\frac{w_{i}}{n_{i}}\sum\limits_{j=1}^{n_{i}}\left(\mathcal{L}_{ij}(b_{ij},\hat{F}(a_{ij};x))+R_{i}(x)\right),$

Here, $n_{i}\in\mathbb{R}$ denotes the number of data points at client
$i\in[n]$, and $(a_{ij},b_{ij})\in\mathcal{X}\times\mathcal{Y}$ represent the
input-output pairs at client $i$. The function
$\mathcal{L}_{ij}(y_{\mathrm{real}},y_{\mathrm{pred}}):\mathcal{Y}\times\mathcal{Y}\to\mathbb{R}$
is a loss function that scores prediction, $R_{i}:\mathbb{R}^{d}\to\mathbb{R}$
is the regularization function used for parameter $x$ at client $i$. The
weight $w_{i}\in\mathbb{R}$ encodes knowledge about the role of client $i$.
For example: (i)
$w_{i}\stackrel{{\scriptstyle\text{def}}}{{=}}{\left(n_{i}\cdot
n\right)}/{\left(\sum_{i=1}^{n}n_{i}\right)}$ corresponds to a case when all
data points are equally important; (ii)
$w_{i}\stackrel{{\scriptstyle\text{def}}}{{=}}1$ corresponds to a case when
all devices are equally important. We aim to solve Problem 1 under the next
requirements:

###### Security Requirements for the FL Training Procedure.

  1. (A)

Clients never transfer the training data to the master.

  2. (B)

Clients do not trust communication devices.

  3. (C)

Detect attempts of message tampering by adversaries.

  4. (D)

Clients distrust a server to store information that could compromise the
training data.

  5. (E)

Preventing competitor worker interference.

  6. (F)

Limit memory traffic from clients to the master.

  7. (G)

Overlapping communication and computing in clients because separate physical
devices implement it.

###### Assumptions for applying our framework

(i) $f(x)$ is differentiable in training variable $x\in\mathbb{R}^{d}$; (ii)
Clients trust each other through the established key; (iii)
$\mathrm{dom}(f)=\mathbb{R}^{d}$.

###### Real-world scenarios for applying our framework

(a) An individual using multiple IoT devices and wants to train an ML model
via servers provided by a third-party company. In reality, engineers in the
companies may have unlimited access to server software facilities and this
social aspect should be considered while making a decision about sending plain
messages to servers; (b) In cross-device settings several IoT mutually trusted
clients perform FL training, but still there is a need to have a master: some
client is temporarily unavailable and updates should be buffered; applied
steps need to be stored to reconstruct the optimization trajectory for further
statistical tests, but IoT devices do not have the needed storage capacity;
the training should be restarted in critical system failures; (c) We want to
train FL model without a physical master in a situation when communication
topology effectively supports broadcasting. Our framework can be instantiated
in this regime (see Appendix J).

###  3\. Framework of Security Aware FL with Permuted Compressors

The Distributed Compressed Gradient Descent (DCGD (Baseline)) (Khirirat et
al., 2018), presented as (Algorithm 1,  Option B), enables the use of
independent unbiased compressors $\mathcal{C}_{i}$ if
$\mathbb{E}\left[\|\mathcal{C}_{i}(x)-x\|^{2}\right]\leq w\|x\|^{2}$. If
$w\neq 0$ this algorithm does not induce variance for a $\mu$-strongly convex
objective $f$ only in a specific (overparameterized) mode: $\nabla
f_{i}(x)=0,\forall i\in[n]$. If $\mathcal{C}_{i}(\nabla
f_{i}(x))\stackrel{{\scriptstyle\text{def}}}{{=}}\nabla f_{i}(x)$, it
reconstitutes distributed Gradient Descent (GD). One line of research involves
removing variance from the use of compressors. For instance, MARINA (Gorbunov
et al., 2021) and COFIG/FRECON (Zhao et al., 2021) do not induce variance when
using unbiased independent compressors, while EF21 (Richtárik et al., 2021)
avoids inducing variance from any independent contractive compressors. In all
these algorithms, the logic in the master starts to include extra state
updates based on obtaining messages from clients. But this is what we aim to
avoid. Thus, the development of our framework is based on stateless DCGD
(Baseline). For plain DCGD (Baseline) we have two issues: (a) In Line 6, the
algorithm sends sparsified information about $\nabla f_{i}(x)$ to the master,
which is insecure; (b) In Line 8, the master computes the average of
$g_{i}^{k}\in\mathbb{R}^{d}$, but the master should not obtain
$g_{i}^{k}=\nabla f_{i}(x^{k})$ or quantities that are subject to
reconstruction attacks (see Appendix E.1). One way to address these problems
is to use the HE schemes. The current practical state-of-the-art HE scheme
which works $\mathbb{R}^{d}$ is the CKKS (Cheon et al., 2017). The CKKS scheme
is the most prevalent for ML applications (Lauter et al., 2022) and is a
practical one. As we will demonstrate in experiments, the CKKS carries an
approximation error that arises due to the scheme being lossy by design. See
Appendix G, D for details about CKKS and HE.

1: Parameters: step size $\gamma>0$, iterate $x^{0}\in\mathbb{R}^{d}$,
clients’ compressors $\mathcal{C}_{i}$
Option A: Clients negotiate a secret key
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}sk}$

2: for $k=0,1,2,\ldots$ do

3: for all workers $i\in\\{1,2,\dots,n\\}$ in parallel do

4: Compute and compress local gradient $g_{i}^{k}=\mathcal{C}_{i}^{k}(\nabla
f_{i}(x^{k}))$

5: Option A: Send tuple
$m_{i}^{k}=({nonce}_{i},{mac}_{i},\tilde{g}_{i}^{k})={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Enc}(g_{i}^{k},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}sk})$
to master, $\tilde{g}_{i}^{k}$ is encryption of $g_{i}^{k}$

6: Option B: Send $g_{i}^{k}$ to master as message $m_{i}^{k}$

7: end for

8: Master collects the messages from clients
$G^{k}=(m_{1}^{k},\dots,m_{n}^{k})$

9: Option A: Master broadcasts $G^{k}\in\mathbb{R}^{dn+|nonce|n+|mac|n}$ to
workers

10: Option B: Master computes the aggregate
$\hat{g}^{k}=\frac{1}{n}\sum_{i=1}^{n}g_{i}^{k}$,
$g_{i}^{k}\stackrel{{\scriptstyle\text{def}}}{{=}}m_{i}^{k}$

11: Option B: Master broadcasts $\hat{g}^{k}\in\mathbb{R}^{d}$ to all $n$
workers

12: for all workers $i\in\\{1,2,\dots,n\\}$ in parallel do

13: Option A: From ${G}^{k}$ unpack ${mac}_{j}$ and
$\tilde{g}_{j}^{k}\in\mathbb{R}^{d},\forall j\in[n]$;
${g}_{j}^{k}={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Decrypt}(\tilde{g}_{j}^{k},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}sk})$;
$Verify({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}sk},{g}_{j}^{k},mac_{j})$

14: Option A: Workers computes the aggregate
$\hat{g}^{k}=\frac{1}{n}\sum_{i=1}^{n}g_{i}^{k}$

15: Option B: Workers obtain $\hat{g}^{k}$ from master during round $k$.

16: Compute the next iterate $x^{k+1}={x^{k}-\gamma\hat{g}^{k}}$

17: end for

18: end for

Algorithm 1 DCGD with  Naive usage of AES (A) and  Baseline (B)

1: Parameters: Dimension of opt. problem $d>0$, number of clients $n>0$.

2: U.a.r. generate permutation $z$ of sequence $[d]=\\{1,2,\dots,d\\}$

3: Split z into $n$ buckets, where each bucket has a size at least
$B=\left\lfloor\frac{d}{n}\right\rfloor$

4: Each bucket $b_{i}$ is initialized with $\\{z_{(i\cdot
B)-B+1},\dots,z_{(i\cdot B)}\\},1\leq i\leq n$

5: Compute the residual $t=d-n\cdot\left\lfloor\frac{d}{n}\right\rfloor$

6: Sample without replacement $t$ clients from $n$ as a set $S$, $|S|=t$

7: Scan the set $S=\\{s_{1},\dots,s_{k},\dots,s_{t}\\}$ and update
$b_{s_{k}}=b_{s_{k}}\cup z_{d-t+k}$

8: Setup compression $\mathcal{C}=(\mathcal{C}_{1},\dots,\mathcal{C}_{n})$:
$[\mathcal{C}_{i}(x)]_{j}=n\cdot x_{j}\cdot I(j\in b_{i})$

Algorithm 2 Sampling of Correlated Permutation Compressors (PermK)
configuration ($d>n$)

1: Parameters: learning rate $\gamma>0$, start iterate
$x^{0}\in\mathbb{R}^{d}$
All clients negotiate a secret key
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}sk}$. All
clients and master negotiate a ${seed}$ for pseudo-random number generator
(PRG).

2: for $k=0,1,2,\ldots$ do

3: for all workers $i\in\\{1,2,\dots,n\\}$ in parallel do

4: Generate permutation compressor $\mathcal{C}_{i}^{k}(\cdot;{seed})$ for
round $k$ at worker $i$ with Algorithm 2 using the known $seed$.

5: Compute and compress local gradient $g_{i}^{k}=\mathcal{C}_{i}^{k}(\nabla
f_{i}(x^{k}))$

6: Represent $g_{i}^{k}\in\mathbb{R}^{d}$ in sparse form.

7: Send
$m_{i}^{k}=({nonce}_{i},{mac}_{i},\hat{g}_{i}^{k})={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Enc}(g_{i}^{k},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}sk})$
to the master.

8: end for

9: Master concatenates the message ${G}^{k}=concat(m_{1}^{k},\dots,m_{n}^{k})$

10: Master broadcasts the compressed aggregate ${G}^{k}$ to all workers

11: for all workers $i\in\\{1,2,\dots,n\\}$ in parallel do

12: Reconstruct indices from (PRG) for all compressors
$\mathcal{C}_{1}^{k},\dots,\mathcal{C}_{n}^{k}$ with Algorithm 2 using the
known ${seed}$.

13: for all block of coordinates $b\in\\{1,2,\dots,n\\}$ in parallel do

14: Obtain part of $G^{k}$ corresponds to $m_{b}^{k}$

15: Unpack ${nonce}_{b}$, ${mac}_{b}$, $\hat{g}_{b}^{k}$, and
${g}_{b}^{k}={\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Decrypt}(\tilde{g}_{b}^{k},{\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}sk})$

16:
$Verify({\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}sk},\hat{g}_{b}^{k},{mac}_{b})$.
If no - halt the training process.

17: Compute the next iterate
$x_{b}^{k+1}={x_{b}^{k}-\frac{\gamma}{n}\cdot\hat{g}_{b}^{k}}$

18: end for

19: end for

20: end for

Algorithm 3 DCGD/PermK/AES, $d\geq n$

The clients need to send in parallel $n$ encrypted messages to the master.
Since clients trust each other, symmetric key encryption is a natural option
to use. In the world of symmetric ciphers, we have decided to use a block
cipher, specifically the industry-standard AES (Daemen and Rijmen, 1999),
instead of stream ciphers like SALSA (Bernstein, 2008). The choice was made
due to the advantages of block ciphers, as: (i) hardware support within CPU
111AES support: Intel x86 Westmere, AMD x86 Bulldozer, ARM Cortex-A53; (ii)
the provision of multiple security levels ($128,192,256$ bits); (iii) the
necessary flexibility to work with available parts of the vector $G^{k}$ (In
coming Algorithm 3). The AES block-cipher provides security for a single
16-byte block. The Modes of Operation provide a way to use AES for more than
one block. Message Authentication Code (MAC) provides guarantees from
tampering. In our work, we used AES/EAX mode of operation. For details about
AES see Appendix F.

The naive way to use AES is to use Algorithm 1,  (Option A). It solves
problems with an untrusted server and channels. Without knowing $sk$, the
untrusted party cannot join the training procedure. Due to the use of MAC
(Lines 5, 13), the training process verifies the integrity and protects
against malicious attacks. To provide semantic security against a chosen-
plaintext attack (CPA) and have the ability to use $sk$ in a distributed way,
we employ random $nonce$ based selection. It eliminates the need for client
coordination in a $nonce$ selection if $nonce$ is big enough such as $128$
bits. Details about the role of $nonce$ in block ciphers are presented in
Appendix F.

With this Algorithm 1 Option-A, solves (A)–(E). However, this strategy has two
big downsides: (1) Computation at Lines 13 and 14 is repeated by all clients
with complexity per client $\mathcal{O}(dn)$; (2) Amount of information from
the master in Line 9 is $\mathcal{O}(dn)$, not $\mathcal{O}(d)$. We pay this
price due to the use of AES, which does not allow to perform aggregation in
the server. From one point of view, the natural way is to perform averaging
for vectors in $\mathbb{R}^{d}$ in the master (Line 10), but on another side,
we perform bit-wise operations (Line 5) inside AES cipher. There is no way to
connect it from the first point of view, but we have discovered how to do it!

The PermK correlated compressor from work (Szlendak et al., 2021) possesses a
compelling property that has yet to be recognized. The correlated compressors
operate interdependently for clients and the schema was outlined in Algorithm
2. Let $\mathcal{C}_{1},\dots,\mathcal{C}_{n}:\mathbb{R}^{d}\to\mathbb{R}^{d}$
be randomized PermK compressors, then

$\mathbb{E}\left[\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}(v_{i})\right]=\frac{1}{n}\sum_{i=1}^{n}v_{i},\forall
v_{i}\in\mathbb{R}^{d}.$

If $d\geq n$, then $\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}(v_{i})$ fulfills
the variance bound:

$\mathbb{E}\left[\left\|\frac{1}{n}\sum_{i=1}^{n}\mathcal{C}_{i}(v_{i})-\frac{1}{n}\sum_{i=1}^{n}v_{i}\right\|^{2}\right]\leq\frac{1}{n}\sum_{i=1}^{n}\left\|v_{i}\right\|^{2}-\left\|\frac{1}{n}\sum_{i=1}^{n}v_{i}\right\|^{2}$

.

This compressor is used in our DCGD/PermK Algorithm 3. Its unbiasedness
property ensures the absence of systematic errors and the variance bound
guarantees that if we are in an overparameterized setting and $x^{k}\to
x^{*}$, then the estimator’s variance will decay to zero, which should remove
any oscillation behavior near the solution. The crucial property of DCGD/PermK
is that the aggregation of compressed gradients can be replaced by
concatenation, which is algebraic monoid for
$(\mathbb{R}^{*},\mathrm{concat})$, and not the algebraic group. Scaling an
encrypted vector by $\frac{1}{n}$ is unfeasible in the master, but this can be
delegated to the iterate update Algorithm 3, Line 17. We can use non-secure
pseudo-random generators as (Matsumoto and Nishimura, 1998) for sampling
indices because they are independent of the input.

###  4\. The Resilience for Attacks

In chosen-plaintext-attack (CPA), an attacker may adaptively ask for the
encryption $(e_{1},\dots)$ of arbitrary messages $(m_{1},\dots)$ to obtain the
ability to correctly guess from the set of two encrypted cipher-texts
$\\{E_{1},E_{2}\\}$ which encryption belongs to which message in the set
$\\{M_{1},M_{2}\\}$, given that attacker knows the set $\\{M_{1},M_{2}\\}$.
CKKS and AES in EAX mode of operation (Bellare et al., 2004) are secure
against CPA.

In a chosen-ciphertext-attack (CCA), the attacker has unlimited access to a
decryption oracle, with the same goal as in CPA. All HE schemas cannot achieve
CCA security (Fauzi et al., 2022). It has been proved that AES/EAX is secure
against CCA (Bellare et al., 2004).

The algorithms executed in general-purpose microprocessors from an execution
point of view are a stream of instructions. However, the energy consumption
for different operations is different (Horowitz, 2014). It leads to the
possibility of side-channel attacks, where the attacker can use information
about physical leakages when the number (or type) of operations is some
function of secret key or plaintext. The AES block cipher and Operation Modes
perform the same stream of operation types (see Appendix F). In CKKS
polynomial multiplication, encoding, decoding, and randomization can lead to a
trace to plain message (Aydin et al., 2022) using side-channel attacks. During
the past time from standardization of AES the works targeted to protect AES
from side-channel attacks have been carried (Rahaman and Hossain, 2008),
(Gross et al., 2017).

Protecting HE libraries from side-channel attacks is an open question. For
example, according to (Aydin et al., 2022) the HE implementation in a
reference  SEAL library (Chen et al., 2017) and any derived libraries such as
TenSEAL (Benaissa et al., 2021) requires protection against side-channel
attacks. The work describes how to exploit an asymmetry in ciphertext
generation and decrease the security level from $2^{128}$ to $2^{4.4}$ for
Brakerski/Fan-Vercauteren(BFV) (Fan and Vercauteren, 2012) Ring Learning With
Error (RLWE) (see Appendix G.1). Therefore, protection from side-channel
attacks for AES can be considered to be more well-developed.

###  5\. Experiments

We made an experimental comparison of several optimization algorithms with
different compression and security methods. In Table
LABEL:tbl:list_of_optimization_algos presented in Appendix B we summarized
their qualitative aspects.

####  5.1. Synthetic Experiments

We’re going to illustrate the advantages of employing block cipher AES (see
Appendix F), as opposed to the CKKS (see Appendix G). The experiments were
conducted on a simulated environment using  FL_PyTorch (Burlachenko et al.,
2021). Details on the computing environment are in Appendix E.1. We configured
the CKKS to offer security guarantees as AES with $128$ bit ($16$ bytes) key.
In this case, the size of public and private keys for CKKS has a lower bound
$420\,000$ bytes (see Appendix G for underlying reason). During usage of CKKS,
the public key should be reported somehow to the master once. As we will see
while using DCGD/PermK/AES no key at all should be reported to master for
master to operate. Therefore the key size can be a problem for CKKS already
when the volume of communicated information is far smaller than $0.42\cdot
10^{6}$ Bytes. In our experiments, we ignore the overhead from key
negotiations between parties.

###### Optimization Problem and Experimental Setup

In our synthetically controlled experiments, we consider a specific smooth
convex optimization problem which is obtained from Equation 1 via
$f_{i}(x)=\frac{1}{n_{i}}\|A_{i}x-b_{i}\|^{2}$,
$A_{i}\in\mathbb{R}^{n_{i}\times d},b_{i}\in\mathbb{R}^{d}$.

###### Case 1: Distributed GD with/without AES/CKKS

We conducted experiments with $d=1000$, $n=50$, and $n_{i}=12$. In our
designed experimental setup we filled the Hessian $\nabla^{2}f(x)$ such that
its nonzero eigenvalues lie uniformly in $[1.0,10.0]$, therefore $L_{f}=10$.
We used the maximum theoretical constant step size $\gamma=1/L_{f}$ for GD.
Fig. 1 (a) shows the impact of IEEE-754 FP16, FP32, and FP64 formats. It shows
that GD/AES does not hurt float arithmetic. However, GD/AES increases traffic
between the master and clients by a factor of $n$ as we see from Fig. 1 (b)
and increases wall clock time by a factor of 1.7 as in Fig. 1 (c). Next, Fig.
2 compares GD with AES and CKKS. According to Fig. 2 (a), GD/CKKS and FP64
arithmetic, it’s possible to obtain $|\nabla f(x^{k})|^{2}\approx 10^{-9}$,
when GD/AES attains $|\nabla f(x^{k})|^{2}\approx 10^{-23}$. From Fig. 2 (b),
(c) we see that GD/CKKS increases load from master slightly compared to
GD/AES, but increases the load from clients by $\times 10^{4}$. As per Fig. 2
(d), CKKS is approximately $\times 3$ slower compared to AES. Using GD/AES is
reasonable only if $d$ and $n$ are small.

(a) (a)

(b) (b)

(c) (c)

Figure 1. Synthesized Linear Regression in interpolation mode, $n_{i}=12$,
$n=50$, $d=1000$. No compression. Th. step sizes.

(a) (a)

(b) (b)

(c) (c)

(d) (d)

Figure 2. Synthesized Linear Regression in interpolation mode, $n_{i}=12$,
$n=50$, $d=1000$. No compression. Th. step sizes.

###### Case 2: DCGD with AES/CKKS

In this experiment, we employ DCGD with RandK sparsification compressor to
analyze the possibility of gradient sparsification while preserving client’s
privacy from the master. To compress $\nabla f_{i}(x)$ each client creates a
set $S_{i}\subset\\{1,2,\dots,d\\}$ of size $K$ chosen uniformly at random,
and compute $C(\nabla
f_{i}(x))\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{d}{K}\sum_{j\in
S_{i}}[\nabla f_{i}(x)]_{j}\cdot e_{j}$, where $e_{j}$ are unit vectors of
standard basis of $\mathbb{R}^{d}$. Results are presented in Fig. 3, and Fig.
4. Fig. 3 (a) and Fig. 4 (a) demonstrates that using AES does not lead to
numerical issues, whereas CKKS for FP64 does. In GD, the master broadcasts a
vector from $\mathbb{R}^{d}$ in each round. For DCGD/RandK/AES, if clients can
reconstruct sparsified indices, then the master has to broadcast $d=K\cdot
n=\frac{1}{5}\cdot n$ encrypted scalars and $32n$ bytes from employing nonce,
and mac for privacy and integrity. This process reduces the number of bits
transmitted from the master to the clients by a factor $\times 5$, compared to
standard GD/AES, as depicted in Fig. 3 (b) and Fig. 1 (b). Fig. 4 (c) shows
that CKKS does not leverage the sparsity. For HE schemas, encoding of any two
vectors (e.g. sparse and dense) should be indistinguishable due to semantic
security requirements. However, from a computational perspective, ignoring
sparsity is sometimes highly impractical, and this gap presents an open
research question for HE. Fig. 4 (b) highlights that AES adapts to any bit
representation of scalars. In contrast,  TenSEAL (Benaissa et al., 2021)
implementation of CKKS does not exhibit this property.

(a) (a)

(b) (b)

(c) (c)

Figure 3. Synthesized Linear Regression in interpolation, $n_{i}=12$, $n=50$,
$d=1000$. Compressors: RandK[$K=0.2d$]. Th. step sizes.

(a) (a)

(b) (b)

(c) (c)

(d) (d)

Figure 4. Synthesized Linear Regression in interpolation, $n_{i}=12$, $n=50$,
$d=1000$. Compressors: RandK [$K=0.2d$]. Th. step sizes.

###### Case 3: DCGD with PermK

Both GD/AES and DCGD/AES require a significant amount of data to be sent from
the master to the clients. In the case of using correlated compressors as
PermK, all clients do not intersect in supports of sparsified gradients by
design. The encryption of the global direction can be obtained by
concatenating encrypted messages from clients. When using PermK, clients do
not need to perform any aggregation on their side, and decryption of the whole
global direction obtained from master can be done in $\mathcal{O}(d)$
independent on $n$. We aim to find an approximate $\gamma$ for DCGD/PermK. We
generated $5$ problems with matrices $A_{i}\sim U[0,1)^{n_{i}\times d}$,
projected $A=[A_{1},\dots,A_{n}]^{\top}$ to have $L_{f}=10$, and computed
$b_{i}\stackrel{{\scriptstyle\text{def}}}{{=}}A_{i}x_{\mathrm{fixed}}$. We
tested various step sizes demonstrated in Fig. 5. We found that using a step
size $\gamma\geq\frac{1}{2L_{f}}=0.05$ led to divergence, as shown in Fig. 5
(a), (b). From Fig. 5 (a), we see that the method exhibits linear convergence
without oscillation near the solution, similar to DCGD with RandK (Here
$\nabla f_{i}(x^{*})=0,\forall i\in[n]$, because $d>n_{i}\cdot n$). From Fig.
5 (c), we see that the variance of the optimization path using fixed step size
$\gamma=0.007$ and fixed $d,n_{i},n,L_{f}$ is negligible.

(a) (a)

(b) (b)

(c) (c)

Figure 5. Tuning step size $\gamma$ without decay for DCGD/PermK. Synthesized
Linear Regression in interpolation, $5$ launches, FP64.

###### Comparison of DCGD/PermK/AES and GD/CKKS

Fig. 6 compares GD, GD/CKKS, GD/PermK with GD/AES, GD/PermK/AES. We see that
the CKKS schema does not leverage the sparsity of vectors, making
sparsification-based compression ineffective in reducing communication during
privacy-preserving training. Therefore, there is no benefit from using RandK
for DCGD/CKKS, and it’s better to use vanilla GD. For GD, we used theoretical
step size, which in practice is extremely tight. If communication isn’t free,
Fig. 6 (a) and Fig. 6 (d) suggest that CKKS is impractical in settings where
client-master communication is a bottleneck. Fig. 6 (b) shows that GD/AES does
not increase client-to-master traffic but does significantly increase master-
to-client traffic, as seen in Fig. 6 (d). If communication is free, Fig. 6 (c)
shows that the best convergence in terms of rounds is attained for GD or
GD/AES with preserving security. If communication is free, GD/CKKS remains
suboptimal due to the approximate nature of floating-point operations in CKKS.
Suppose the key metric is convergence in $\|{\nabla f(x^{k})}\|$ relative to
the number of bits from client to master. Fig. 6 (b) shows that GD/CKKS uses
approximately $0.6\cdot 10^{7}$ bits per client after the first round of
optimization. DCGD/PermK/AES with this transfers can attain $\|{\nabla
f(x)}\|^{2}\approx 10^{-20}$.

(a) (a)

(b) (b)

(c) (c)

(d) (d)

Figure 6. Linear Regression in an interpolation. DCGD use tuned step size. GD,
GD/CKKS, GD/AES use theoretical.

(a)

(b)

(c)

(d)

Figure 7. ResNet-18 in CIFAR-10, $n=10$, $d=11\,181\,642$. DCGD/PermK/AES and
FedAvg.

####  5.2. Image Classification Application

We evaluated the applicability of using DCGD/PermK/AES on Deep Neural Networks
training. We used the ResNet-18 architecture (He et al., 2016b) and trained it
on the CIFAR-10 dataset (Krizhevsky and Hinton, 2009), which consists of
$60\,000$ images across $10$ classes with a resolution of $32\times 32$
pixels. We used ResNet-18 implementation from TorchVision library, part of the
PyTorch (Paszke et al., 2019). The model size $d=11,181,642$. For Optimization
Problem 1, we used a standard cross-entropy loss for $\mathcal{L}_{ij}$ terms
in Equation 2. Next, we distributed the dataset uniformly across $n=10$
clients, with each client participating in every round. Global learning rate
$0.1$, local learning rate $0.1$, local weight decay $5\cdot 10^{-4}$, number
of rounds $5\,000$. During each round, clients evaluate $\nabla f_{i}(x)$
using a fixed 10% subset of each client’s local data points. In FL, there are
cases where clients cannot store a large number of data points (e.g., high-
resolution images, recorded voice in IoT devices) due to storage limitations.
Our experiment simulates this scenario. We compared our implementation with
FedAvg (McMahan et al., 2017), where no compression or encryption is
performed. We tracked during training communicated message size, accuracy, and
convergence. Our reported metrics in Fig. 7 are computation framework and
communication topology independent. In these experiments, we did not carry out
an analysis of the spent time for communication, compression, and AES
encryption/decryption, because the actual numbers are highly implementation
dependent quantities.

In DCGD/PermK/AES, the message size from the client to the master contains
$\left\lceil\frac{d}{10}\right\rceil=1,118,165$ parameters with $4$ bytes each
one. The overhead from AES-128/EAX Operation Mode is $32$ bytes per single
message, which is negligible. Fig. 7 shows that the message size was reduced
from $42.65$ (for FedAvg) MBytes to $4.26$ MBytes (for DCGD/PermK). We cannot
launch CKKS with security guarantees as AES-128 in our environment due to
memory overhead. In Appendix 5.1, we demonstrated that problems start
appearing in CKKS with AES-128 security guarantees already for $d=10^{6}$. For
a discussion about extra flexibility in Training DL models see Appendix I.

###  6\. Deployment Flexibility

The Physical Network Topologies describes the arrangement of the computation
and routing devices. In a Mesh topology, every pair of nodes is connected with
a dedicated link. It has high bandwidth and fault tolerance but requires a lot
of cables. In this setting, the DCGD/PermK is the natural choice. The
Algorithm 3 can be observed as a series of broadcast operations to
reconstitute the optimization step. The benefits to other topologies are
discussed in Appendix J.

In Appendix H.2, we present the refined scheduled communication and
computation plan that utilizes the possibility of computation communication
overlap and handling computation heterogeneity during training Linear
Regression. The modeled situation that we studied contained $5$ clients (one
of them is a straggler) which all are connected to the master with a shared
channel. We demonstrated that the actual execution plan can be refined. The
possible gained speedup for GD is $\times 1.31$, for DCGD/PermK is $\times
3.33$. The DCGD/PermK has flexibility to start several compute operations
during waiting the straggler, which are limited for GD.

###  7\. Conclusions

We proposed a novel secure FL framework that uses symmetric-key encryption
with permutation compressors to protect the gradients during communication and
simultaneously compress them. We conducted experiments on real and synthetic
data. Additional studies about the effect of problem dimension, overlapping
communication and computation, and deployment options in various network
topologies are presented in Appendices H, J. Our work opens a new possibility
for applying Classical Cryptography to FL and challenges some existing claims
about its limitations. Possible future research and current limitations are
described in Appendix M.

### References

  * (1)
  * pyc (2014) 2014\.  PyCryptodome.  https://pypi.org/project/pycryptodome/.  Accessed: 2023-05-10.
  * Abadi et al. (2016) Martín Abadi, Paul Barham, Jianmin Chen, Zhifeng Chen, Andy Davis, Jeffrey Dean, Matthieu Devin, Sanjay Ghemawat, Geoffrey Irving, Michael Isard, et al. 2016\.  $\\{$TensorFlow$\\}$: A System for $\\{$Large-Scale$\\}$ Machine Learning. In _12th USENIX symposium on operating systems design and implementation (OSDI 16)_. 265–283.
  * Alistarh et al. (2017) Dan Alistarh, Demjan Grubic, Jerry Li, Ryota Tomioka, and Milan Vojnovic. 2017.  QSGD: Communication-efficient SGD via gradient quantization and encoding.  _Advances in neural information processing systems_ 30 (2017).
  * Alistarh et al. (2018) Dan Alistarh, Torsten Hoefler, Mikael Johansson, Nikola Konstantinov, Sarit Khirirat, and Cédric Renggli. 2018.  The convergence of sparsified gradient methods.  _Advances in Neural Information Processing Systems_ 31 (2018).
  * Aono et al. (2017) Yoshinori Aono, Takuya Hayashi, Lihua Wang, Shiho Moriai, et al. 2017\.  Privacy-preserving deep learning via additively homomorphic encryption.  _IEEE Transactions on Information Forensics and Security_ 13, 5 (2017), 1333–1345.
  * Aydin et al. (2022) Furkan Aydin, Emre Karabulut, Seetal Potluri, Erdem Alkim, and Aydin Aysu. 2022.  Reveal: Single-trace side-channel leakage of the seal homomorphic encryption library. In _2022 Design, Automation & Test in Europe Conference & Exhibition (DATE)_. IEEE, 1527–1532.
  * Barak et al. (2001) Boaz Barak, Oded Goldreich, Rusell Impagliazzo, Steven Rudich, Amit Sahai, Salil Vadhan, and Ke Yang. 2001.  On the (im) possibility of obfuscating programs. In _Advances in Cryptology—CRYPTO 2001: 21st Annual International Cryptology Conference, Santa Barbara, California, USA, August 19–23, 2001 Proceedings_. Springer, 1–18.
  * Bellare et al. (2004) M Bellare, P Rogaway, and D Wagner. 2004.  The EAX Mode of Operation (A Two-Pass Authenticated Encryption Scheme Optimized for Simplicity and Efficiency) 3017 (2004), 389–407, Fast Software Encryption.  _Lecture Notes in Computer Science_ (2004).
  * Benaissa et al. (2021) Ayoub Benaissa, Bilal Retiat, Bogdan Cebere, and Alaa Eddine Belfedhal. 2021.  Tenseal: A library for encrypted tensor operations using homomorphic encryption.  _arXiv preprint arXiv:2104.03152_ (2021).
  * Bernstein (2008) Daniel J Bernstein. 2008\.  The Salsa20 family of stream ciphers.  _New stream cipher designs: the eSTREAM finalists_ (2008), 84–97.
  * Bhowmick et al. (2018) Abhishek Bhowmick, John Duchi, Julien Freudiger, Gaurav Kapoor, and Ryan Rogers. 2018.  Protection against reconstruction and its applications in private federated learning.  _arXiv preprint arXiv:1812.00984_ (2018).
  * Blum et al. (2003) Avrim Blum, Adam Kalai, and Hal Wasserman. 2003.  Noise-tolerant learning, the parity problem, and the statistical query model.  _Journal of the ACM (JACM)_ 50, 4 (2003), 506–519.
  * Bogdanov et al. (2011) Andrey Bogdanov, Dmitry Khovratovich, and Christian Rechberger. 2011\.  Biclique cryptanalysis of the full AES. In _Advances in Cryptology–ASIACRYPT 2011: 17th International Conference on the Theory and Application of Cryptology and Information Security, Seoul, South Korea, December 4-8, 2011. Proceedings 17_. Springer, 344–371.
  * Boneh and Shoup (2020) Dan Boneh and Victor Shoup. 2020.  A graduate course in applied cryptography.  _Draft 0.5_ (2020).
  * Burlachenko et al. (2021) Konstantin Burlachenko, Samuel Horváth, and Peter Richtárik. 2021.  Fl_pytorch: optimization research simulator for federated learning. In _Proceedings of the 2nd ACM International Workshop on Distributed Machine Learning_. 1–7.
  * Chen et al. (2017) Hao Chen, Kim Laine, and Rachel Player. 2017.  Simple encrypted arithmetic library-SEAL v2. 1. In _Financial Cryptography and Data Security: FC 2017 International Workshops, WAHC, BITCOIN, VOTING, WTSC, and TA, Sliema, Malta, April 7, 2017, Revised Selected Papers 21_. Springer, 3–18.
  * Chen et al. (2020) Xiangyi Chen, Steven Z Wu, and Mingyi Hong. 2020.  Understanding gradient clipping in private sgd: A geometric perspective.  _Advances in Neural Information Processing Systems_ 33 (2020), 13773–13782.
  * Cheon et al. (2017) Jung Hee Cheon, Andrey Kim, Miran Kim, and Yongsoo Song. 2017\.  Homomorphic encryption for arithmetic of approximate numbers. In _Advances in Cryptology–ASIACRYPT 2017: 23rd International Conference on the Theory and Applications of Cryptology and Information Security, Hong Kong, China, December 3-7, 2017, Proceedings, Part I 23_. Springer, 409–437.
  * Cohen and Nissim (2018) Aloni Cohen and Kobbi Nissim. 2018.  Linear program reconstruction in practice.  _arXiv preprint arXiv:1810.05692_ (2018).
  * Costan and Devadas (2016) Victor Costan and Srinivas Devadas. 2016.  Intel SGX explained.  _Cryptology ePrint Archive_ (2016).
  * Daemen and Rijmen (1999) Joan Daemen and Vincent Rijmen. 1999.  AES proposal: Rijndael.  _NIST AES Proposal_ (1999).
  * Daemen and Rijmen (2001) Joan Daemen and Vincent Rijmen. 2001.  Reijndael: The advanced encryption standard.  _Dr. Dobb’s Journal: Software Tools for the Professional Programmer_ 26, 3 (2001), 137–139.
  * Dinur and Nissim (2003) Irit Dinur and Kobbi Nissim. 2003.  Revealing information while preserving privacy. In _Proceedings of the twenty-second ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems_. 202–210.
  * Dwork et al. (2006a) Cynthia Dwork, Krishnaram Kenthapadi, Frank McSherry, Ilya Mironov, and Moni Naor. 2006a.  Our data, ourselves: Privacy via distributed noise generation. In _Annual International Conference on the Theory and Applications of Cryptographic Techniques_. Springer, 486–503.
  * Dwork et al. (2006b) Cynthia Dwork, Frank McSherry, Kobbi Nissim, and Adam Smith. 2006b.  Calibrating noise to sensitivity in private data analysis. In _Theory of cryptography conference_. Springer, 265–284.
  * Ellson et al. (2002) John Ellson, Emden Gansner, Lefteris Koutsofios, Stephen C North, and Gordon Woodhull. 2002\.  Graphviz—open source graph drawing tools. In _Graph Drawing: 9th International Symposium, GD 2001 Vienna, Austria, September 23–26, 2001 Revised Papers 9_. Springer, 483–484.
  * Fan and Vercauteren (2012) Junfeng Fan and Frederik Vercauteren. 2012.  Somewhat practical fully homomorphic encryption.  _Cryptology ePrint Archive_ (2012).
  * Fauzi et al. (2022) Prastudy Fauzi, Martha Norberg Hovd, and Håvard Raddum. 2022.  On the IND-CCA1 security of FHE schemes.  _Cryptography_ 6, 1 (2022), 13.
  * Gentry (2009) Craig Gentry. 2009\.  _A fully homomorphic encryption scheme_.  Stanford university.
  * Gorbunov et al. (2021) Eduard Gorbunov, Konstantin P Burlachenko, Zhize Li, and Peter Richtárik. 2021.  MARINA: Faster non-convex distributed learning with compression. In _International Conference on Machine Learning_. PMLR, 3788–3798.
  * Gross et al. (2017) Hannes Gross, Stefan Mangard, and Thomas Korak. 2017\.  An Efficient Side-Channel Protected AES Implementation with Arbitrary Protection Order. In _Topics in Cryptology – CT-RSA 2017_ , Helena Handschuh (Ed.). Springer International Publishing, Cham, 95–112.
  * He et al. (2016a) K. He et al. 2016a.  Deep Residual Learning for Image Recognition. In _CVPR_. 770–778.
  * He et al. (2016b) Kaiming He, Xiangyu Zhang, Shaoqing Ren, and Jian Sun. 2016b.  Deep residual learning for image recognition. In _Proceedings of the IEEE conference on computer vision and pattern recognition_. 770–778.
  * Horowitz (2014) Mark Horowitz. 2014\.  1.1 computing’s energy problem (and what we can do about it). In _2014 IEEE International Solid-State Circuits Conference Digest of Technical Papers (ISSCC)_. IEEE, 10–14.
  * Horvóth et al. (2022) Samuel Horvóth, Chen-Yu Ho, Ludovit Horvath, Atal Narayan Sahu, Marco Canini, and Peter Richtárik. 2022.  Natural compression for distributed deep learning. In _Mathematical and Scientific Machine Learning_. PMLR, 129–141.
  * Jain and Cherukuri (2023) Nimish Jain and Aswani Kumar Cherukuri. 2023.  Revisiting Fully Homomorphic Encryption Schemes.  _arXiv preprint arXiv:2305.05904_ (2023).
  * Jang et al. (2022) Kyungbae Jang, Anubhab Baksi, Hyunji Kim, Gyeongju Song, Hwajeong Seo, and Anupam Chattopadhyay. 2022.  Quantum analysis of aes.  _Cryptology ePrint Archive_ (2022).
  * Jia et al. (2019) Zhihao Jia, Matei Zaharia, and Alex Aiken. 2019\.  Beyond Data and Model Parallelism for Deep Neural Networks.  _Proceedings of Machine Learning and Systems_ 1 (2019), 1–13.
  * Jiang et al. (2021) Zhifeng Jiang, Wei Wang, and Yang Liu. 2021.  Flashe: Additively symmetric homomorphic encryption for cross-silo federated learning.  _arXiv preprint arXiv:2109.00675_ (2021).
  * Kairouz et al. (2021) Peter Kairouz, H Brendan McMahan, Brendan Avent, Aurélien Bellet, Mehdi Bennis, Arjun Nitin Bhagoji, Kallista Bonawitz, Zachary Charles, Graham Cormode, Rachel Cummings, et al. 2021\.  Advances and open problems in federated learning.  _Foundations and Trends® in Machine Learning_ 14, 1–2 (2021), 1–210.
  * Kaissis et al. (2020) Georgios A Kaissis, Marcus R Makowski, Daniel Rückert, and Rickmer F Braren. 2020.  Secure, privacy-preserving and federated machine learning in medical imaging.  _Nature Machine Intelligence_ 2, 6 (2020), 305–311.
  * Kasiviswanathan et al. (2013) Shiva Prasad Kasiviswanathan, Mark Rudelson, and Adam Smith. 2013\.  The power of linear reconstruction attacks. In _Proceedings of the twenty-fourth annual ACM-SIAM symposium on Discrete algorithms_. SIAM, 1415–1433.
  * Khirirat et al. (2018) Sarit Khirirat, Hamid Reza Feyzmahdavian, and Mikael Johansson. 2018\.  Distributed learning with compressed gradients.  _arXiv preprint arXiv:1806.06573_ (2018).
  * Kluczniak and Santato (2023) Kamil Kluczniak and Giacomo Santato. 2023.  On Circuit Private, Multikey and Threshold Approximate Homomorphic Encryption.  _Cryptology ePrint Archive_ (2023).
  * Krizhevsky (2014) Alex Krizhevsky. 2014\.  One weird trick for parallelizing convolutional neural networks.  _arXiv preprint arXiv:1404.5997_ (2014).
  * Krizhevsky and Hinton (2009) Alex Krizhevsky and Geoffrey Hinton. 2009.  _Learning multiple layers of features from tiny images_.  Technical Report 0. University of Toronto, Toronto, Ontario.
  * Lauter et al. (2022) Kristin Estella Lauter, Wei Dai, and Kim Laine. 2022\.  _Protecting Privacy Through Homomorphic Encryption_.  Springer.
  * Li et al. (2019) Chen Li, Yifan Sun, Lingling Jin, Lingjie Xu, Zheng Cao, Pengfei Fan, David Kaeli, Sheng Ma, Yang Guo, and Jun Yang. 2019\.  Priority-based PCIe scheduling for multi-tenant multi-GPU systems.  _IEEE Computer Architecture Letters_ 18, 2 (2019), 157–160.
  * Linnainmaa (1970) Seppo Linnainmaa. 1970\.  _The representation of the cumulative rounding error of an algorithm as a Taylor expansion of the local rounding errors_.  Ph. D. Dissertation. Master’s Thesis (in Finnish), Univ. Helsinki.
  * Liu et al. (2019) Changchang Liu, Supriyo Chakraborty, and Dinesh Verma. 2019\.  Secure model fusion for distributed learning using partial homomorphic encryption.  _Policy-Based Autonomic Data Governance_ (2019), 154–179.
  * Liu et al. (2022) Ken Liu, Shengyuan Hu, Steven Z Wu, and Virginia Smith. 2022\.  On privacy and personalization in cross-silo federated learning.  _Advances in Neural Information Processing Systems_ 35 (2022), 5925–5940.
  * Matsumoto and Nishimura (1998) Makoto Matsumoto and Takuji Nishimura. 1998.  Mersenne twister: a 623-dimensionally equidistributed uniform pseudo-random number generator.  _ACM Transactions on Modeling and Computer Simulation (TOMACS)_ 8, 1 (1998), 3–30.
  * McMahan et al. (2017) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017\.  Communication-efficient learning of deep networks from decentralized data. In _Artificial intelligence and statistics_. PMLR, 1273–1282.
  * Microsoft (2021) Microsoft. 2021\.  Microsoft SEAL.  https://github.com/microsoft/SEAL.  Version 4.1.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ 32 (2019).
  * Pinto and Santos (2019) Sandro Pinto and Nuno Santos. 2019.  Demystifying arm trustzone: A comprehensive survey.  _ACM computing surveys (CSUR)_ 51, 6 (2019), 1–36.
  * Rahaman and Hossain (2008) Mohammad Zahidur Rahaman and Mohammad Akram Hossain. 2008.  Side channel attack prevention for AES smart card. In _2008 11th International Conference on Computer and Information Technology_. IEEE, 376–380.
  * Regev (2009) Oded Regev. 2009\.  On lattices, learning with errors, random linear codes, and cryptography.  _Journal of the ACM (JACM)_ 56, 6 (2009), 1–40.
  * Richtárik et al. (2021) Peter Richtárik, Igor Sokolov, and Ilyas Fatkhullin. 2021\.  EF21: A new, simpler, theoretically better, and practically faster error feedback.  _Advances in Neural Information Processing Systems_ 34 (2021), 4384–4396.
  * Rivest et al. (1978) Ronald L Rivest, Len Adleman, Michael L Dertouzos, et al. 1978\.  On data banks and privacy homomorphisms.  _Foundations of secure computation_ 4, 11 (1978), 169–180.
  * Rumelhart et al. (1986) David E Rumelhart, Geoffrey E Hinton, and Ronald J Williams. 1986.  Learning representations by back-propagating errors.  _nature_ 323, 6088 (1986), 533–536.
  * Safaryan and Richtárik (2019) Mher Safaryan and Peter Richtárik. 2019.  On stochastic sign descent methods.  (2019).
  * Spurgeon (2000) Charles E Spurgeon. 2000\.  _Ethernet: the definitive guide_.  " O’Reilly Media, Inc.".
  * Szlendak et al. (2021) Rafał Szlendak, Alexander Tyurin, and Peter Richtárik. 2021.  Permutation compressors for provably faster distributed nonconvex optimization.  _arXiv preprint arXiv:2110.03300_ (2021).
  * Wangni et al. (2018) Jianqiao Wangni, Jialei Wang, Ji Liu, and Tong Zhang. 2018\.  Gradient sparsification for communication-efficient distributed optimization.  _Advances in Neural Information Processing Systems_ 31 (2018).
  * Wen et al. (2017) Wei Wen, Cong Xu, Feng Yan, Chunpeng Wu, Yandan Wang, Yiran Chen, and Hai Li. 2017.  Terngrad: Ternary gradients to reduce communication in distributed deep learning.  _Advances in neural information processing systems_ 30 (2017).
  * Zhang et al. (2020) Chengliang Zhang, Suyi Li, Junzhe Xia, Wei Wang, Feng Yan, and Yang Liu. 2020\.  Batchcrypt: Efficient homomorphic encryption for cross-silo federated learning. In _Proceedings of the 2020 USENIX Annual Technical Conference (USENIX ATC 2020)_.
  * Zhao et al. (2019) Chuan Zhao, Shengnan Zhao, Minghao Zhao, Zhenxiang Chen, Chong-Zhi Gao, Hongwei Li, and Yu-an Tan. 2019.  Secure multi-party computation: theory, practice and applications.  _Information Sciences_ 476 (2019), 357–372.
  * Zhao et al. (2021) Haoyu Zhao, Konstantin Burlachenko, Zhize Li, and Peter Richtárik. 2021.  Faster rates for compressed federated learning with client-variance reduction.  _arXiv preprint arXiv:2112.13097_ (2021).

## Appendix

###### Contents

  1. 1 Introduction
  2. 2 Problem Formulation
  3. 3 Framework of Security Aware FL with Permuted Compressors
  4. 4 The Resilience for Attacks
  5. 5 Experiments
    1. 5.1 Synthetic Experiments
    2. 5.2 Image Classification Application
  6. 6 Deployment Flexibility
  7. 7 Conclusions
  8. A Glossary
  9. B Compared Optimization Algorithms
  10. C Computing and Software Environment
  11. D Overview of Existing Privacy Mechanisms in Context of FL
  12. E Discussions
    1. E.1 The Imperative of Safeguarding Against Eavesdropping
    2. E.2 Privacy and Security
  13. F Usage of AES cipher during Distributed Training
    1. F.1 AES Block Cipher
    2. F.2 Internals of AES Block Cipher
    3. F.3 Apply AES Block Cipher for more than one input block
    4. F.4 Apply AES with Integrity Guarantees
    5. F.5 Chosen Ciphertext Attack CCA and Authentication
    6. F.6 Using AES with EAX Operation Mode in our paper
  14. G Homomorphic Encryption with CKKS
    1. G.1 Learning With Errors Problem and REGEV09 Algorithm as a Concrete Example of SWHE
    2. G.2 Introduction to CKKS
    3. G.3 Description of processes inside CKKS
    4. G.4 CKKS Configuration Equivalent to AES-128
  15. H Extra Experiments
    1. H.1 Exploring Problem Dimension
    2. H.2 Compute and Communication Overlap for DCGD/PermK
      1. H.2.1 Background in Network Communication
      2. H.2.2 Network Communication Model
      3. H.2.3 CPU-based Computation in Clients
      4. H.2.4 Background in Modern Central Processing Unit
      5. H.2.5 Modeling of Computation
      6. H.2.6 The Optimization Problem
      7. H.2.7 Implementation Benefits of DCGD/PermK
      8. H.2.8 Scheduling of Clients and Master Computation and Communication with Critical Path Method
      9. H.2.9 Critical Path Method Iterative Refinement
      10. H.2.10 Results of Scheduling and Refinement for GD and DCGD/PermK/AES
  16. I Flexibility in Training Deep Learning Models
    1. I.1 Introduction to Gradient Oracle Computation with Backpropagation
    2. I.2 Examples of Parallelization inside Backpropagation
    3. I.3 Research Opportunities for Parallelization in Backpropagation from DCGD/PermK
  17. J Flexibility of DCGD/PermK for Different Communication Topologies
    1. J.1 Potential Benefits in Point-to-point Topology
    2. J.2 Potential Benefits in Bus Topology
    3. J.3 Potential Benefits in Star Topology
    4. J.4 Potential Benefits in Ring Topology
    5. J.5 Potential Benefits in Mesh Topology
    6. J.6 Potential Benefits in Tree Topology
  18. K Acknowledgements
  19. L Reproducibility
  20. M Limitations and Future Research

###  Appendix A Glossary

Our work is multidiscipline. To make our paper more readable for researchers
with different backgrounds, we have constructed this Glossary.

Table 1. General Terminology Term |  Meaning
---|---
FL |  Federated Learning.
GD |  Gradient Descent.
DCGD |  Distributed Compressed Gradient Descent.
TEE |  Trusted Execution Environments.
DP |  Differential Privacy.
MPC |  The term is overloaded. In the context of Federated Learning literature typically means Multi-Party Computation.
HE |  Homomorphic Encryption.
IoT |  The collective network of connected devices.
Table 2. Optimization Terminology Term |  Meaning
---|---
$d$ |  Dimension of optimization variable.
$n$ |  Number of clients/agents/devices.
$f_{i}$ |  Local Loss function on client number $i$.
$f$ |  Objective function with we want to minimize with image $\mathbb{R}$ and domain $\mathbb{R}^{d}$.
$\gamma$ |  Step size of learning rate.
$x$ |  Trainable or Optimization variable from $\mathbb{R}^{d}$.
$x^{k}$ |  Trainable or Optimization variable at most outer loop of optimization algorithm number $k$.
round |  The iteration in the outermost loop of the optimization algorithm.
$e_{i}$ |  The vector from $\mathbb{R}^{d}$ whose i-th component is equal $1$ while all the others are zeros.
u.a.r. |  uniformly at random.
r.v. |  random variable.
p.d.f. |  probability distribution function.
$\mathbb{E}[.]$ |  Expectation of some Random Variable.
PermK |  Permutated correlated compressors.
Master |  Entity in FL which performs aggregation and other forms of reductions.
Table 3. Discrete Math Terminology Term |  Meaning
---|---
Algebra |  Set of elements and defined operations on set which lead to elements of the same set.
Monoid |  Any algebra with the binary, associative operation, which also has a neutral element. Example - concatenation.
Group |  Any algebra with the binary, associative operation, with a neutral element and each element has an inverse.
Ring |  Algebra with summation, and multiplication. A summation is a commutative group, multiplication is a monoid. Multiplication is distributive with respect to summation. In Ring without extra assumptions can have a situation such that $a\neq 0$, $b\neq 0$, but $ab=0$.
Polynomial |  $p(x)=p_{0}+p_{1}\cdot x+p_{2}\cdot x^{2}+\dots$.
$K[x]$ |  Let K be some field. The set of all polynomials with coefficients in some field $K$. It is called commutative called the polynomial ring over $K$. In the Ring of polynomials $K[X]$ there is no division in general similar to Algebra $N$. However, it’s possible to perform division with residual. One basis for such set is $\\{1,x,x^{2},\dots\\}$.
$Z[X]$ |  Integer polynomial rings over commutative ring $Z$ is denoted as $Z[X]$. This is the set of polynomials whose coefficients are integers and polynomials depend only on one variable.
$P[x]/(x^{2}+1)$ |  This notation means polynomials which are obtained in the following way. We take the polynomial ring $P[x]$ and perform modulus division by the polynomial $x^{2}+1$. This modulus arithmetic restricts obtained polynomials to have a power less than $2$. Such a ring is an example of a quotient ring.
Unity Roots |  Roots of unity are roots of the following equation $Z^{n}=1$. If $Z\in\mathbb{C}$ the roots are: $z_{k}=\exp(2\pi ki/n)$ for $k=0,1,2,\dots,n-1$.
GCD |  The greatest common divisor (GCD) of two or more integers, that are not zero, is the largest positive integer that divides each of the integers. For example $\gcd(8,12)=4$.
Homomorphism |  Homomorphism of two groups $G_{1}$ and $G_{2}$ is a mapping $f:G_{1}\to G_{2}$ between two groups, such that $\forall x,y\in G_{1}$ the following holds: $f(x*y)=f(x)*f(y)$
Isomomorphism |  Isomomorphism of groups $G_{1}$ and $G_{2}$ is a mapping $f:G_{1}\to G_{2}$ between two groups, such $\forall x,y\in G_{1}$ the following holds: $f(x*y)=f(x)*f(y)$ and $f$ is bijection mapping. From the point of view of Algebraic structures, two isomorphic groups are the same, even if they have different natures of their elements.
Table 4. Cryptography Terminology Term |  Meaning
---|---
FHE |  Fully Homomorphic Encryption.
SWHE |  Somewhat Homomorphic Encryption.
LFHE |  Leveled Fully Homomorphic Encryption.
CKKS |  Cheon-Kim-Kim-Song Homomorphic Encryption schema, which is formally only SWHE.
AES |  Advanced Encryption Standard.
sk |  Secret Key.
pk |  Public Key.
Symmetric Encryption |  Encryption schema in which secret and public key is the same.
PRP |  Pseudo Random Permutation.
PRF |  Pseudo Random Function.
MAC |  Message Authentication Code.
CRC |  Cyclic Redundancy Check.
CPA |  Chosen plaintext attack.
CCA |  Chosen ciphertext attack.
CTR |  Counter Mode Randomized.
CBC |  Cipher Block Chaining.
EAX |  Encrypt then Authenticate then Translate Mode.
LWE |  The Learning With Errors search problem to find a solution to a noisy system of linear equations in a finite field.
RLWE |  The Ring Learning With Errors search problem. Find a solution to a noisy system of the linear equation when an underlying algebra is a polynomial over a ring.
Integer Lattice |  It is a set of points which correspond to all possible linear combinations with integer coefficients of the $n$ vectors $b_{i}\in\mathbb{R}^{d}$, i.e. it the set $\\{x:x=\sum_{i=1}^{n}{\alpha}_{i}b_{i},{\alpha}_{i}\in\mathbb{Z}\\}$.
Table 5. Systems and Communication Terminology Term |  Meaning
---|---
DRAM |  Dynamic Random Access Memory.
GPU |  Graphics Processing Unit.
FP |  Float point format.
FP16, FP32, FP64 |  Float point format with a specified number of bits per single scalar.
CUDA |  Compute Unified Device Architecture.
CPU |  Central Processing Unit.
AVX |  Advanced Vector Extensions.
NIC |  Network Interface Controller.

###  Appendix B Compared Optimization Algorithms

In our work, we made a comparison of several optimization algorithms with
different compression and security methods. In Table
LABEL:tbl:list_of_optimization_algos below we summarize their qualitative and
qualitative features.

Table 6. Compared Optimization Algorithms with Compression and Privacy Mechanisms Name |  Description
---|---
1\. GD [FP16|FP32|FP64] |  Algorithm 1, Baseline ( B), $\mathcal{C}_{i}(x)\stackrel{{\scriptstyle\text{def}}}{{=}}x$.

Gradient Descend. In this algorithm, clients in a distributed way compute the
gradient for the function $f_{i}$ defined in Equation 2 in the current
iterate. Master obtains gradients from the clients and averages them. The
master broadcasts the result directly to all clients. The specified Floating-
Point format is used to represent both data and trainable variables in all
clients and during aggregation in the master.

Quantitative and qualitative characteristics: (1) It’s completely insecure
(see Appendix E.1). (2) Volume information from clients to master is
$\mathcal{O}(dn)$ bytes per round. (3) Broadcasted information from master to
clients is $\mathcal{O}(d)$ bytes per round. For details on why information
about $\nabla f_{i}(x;D_{i})$ can potentially reveal information about dataset
$D_{i}$ see discussion in Apeendix E.1.
2\. GD [FP16|FP32|FP64]/AES-128 |  Algorithm 1, Naive usage of AES ( A), $\mathcal{C}_{i}(x)\stackrel{{\scriptstyle\text{def}}}{{=}}x$.

Gradient Descend with symmetric AES encryption which uses a key size of  $128$
bits ($16$ bytes). In this algorithm, clients in a distributed way compute the
gradient for the function $f_{i}$ defined in Equation 2 in the current
iterate. Then clients encrypt computed $\nabla f_{i}(x)$ in parallel. After
that Master collects the encoded gradients as a communication hub.
Unfortunately master can not perform any algebraic operations, because $\nabla
f_{i}(x)$are encrypted, and the master needs to broadcast all directions to
the clients. The specified Floating-Point format is used to represent both
data and trainable variables in all clients and during aggregation in the
master. During using AES/EAX there exists a fixed negligible overhead from
using EAX Mode Operation Mode of $32$ bytes in each client to master
communication information transfer. Specifically, this Mode Operation includes
the following overheads: Nonce \- a random $16$-byte value, and the Tag \-
$16$-byte message authentication code.

Quantitative and qualitative characteristics: (1) Master cannot average
obtained encrypted clients’ local gradient. (2) Volume information from
clients to master is $\mathcal{O}(dn+32n)$ bytes per round. (3) Broadcasted
information from master to clients is $\mathcal{O}(dn+32n)$ bytes per round.
For details about AES see Apeendix F.
3\. DCGD [FP16|FP32|FP64]/AES-128/RandK |  Algorithm 1, Naive usage of AES ( A), $\mathcal{C}_{i}(x)\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{d}{k}\sum_{i\in S}x_{i}\cdot e_{i},S\sim_{u.a.r}\\{s:s\in 2^{[d]},|s|=k\\}$.

Distributed Compressed Gradient Descend with symmetric AES encryption which
uses a key size of  $128$ bits ($16$ bytes), and with using RandK sparsifier.
In this algorithm, clients in a distributed way compute the gradient for the
function $f_{i}$ defined in Equation 2 in the current iterate. After this
clients compress them by selecting $k$ components from $d$ u.a.r. Then clients
use a sparse bitwise representation of the sparsified gradient and encode non-
zero values with AES/EAX mode of operation. Then clients encrypt computed
$\mathcal{C}(\nabla f_{i}(x))$ in parallel. After that Master collects the
encoded gradients as a communication hub. Unfortunately master can not perform
any algebraic operations, because $\nabla f_{i}(x)$are encrypted, and the
master needs to broadcast all directions to the clients. The specified
Floating-Point format is used to represent both data and trainable variables
in all clients and during aggregation in the master. During using AES/EAX
there exists a fixed negligible overhead from using EAX Mode Operation Mode of
$32$ bytes in each client to master communication information transfer.
Specifically, this Mode Operation includes the following overheads: Nonce \- a
random $16$-byte value, and the Tag \- $16$-byte message authentication code.
The implementation of RandK sparsifier in the case of using a pseudo-random
generator can be implemented in a way that no indices should be transferred
during training because they can be reconstituted.

Quantitative and qualitative characteristics: (1) Master cannot average
obtained encrypted and compressed clients’ local gradient. (2) Volume
information from clients to master is $\mathcal{O}(kn+32n)$ bytes per round.
(3) Broadcasted information from master to clients is $\mathcal{O}(kn+32n)$
bytes per round. (4) Fundamentally there is some redundancy induced by the
inability to perform aggregation in the master.
4\. GD [FP16|FP32|FP64]/CKKS |  Algorithm 1, Baseline ( B), $\mathcal{C}_{i}(x)\stackrel{{\scriptstyle\text{def}}}{{=}}x$. Extra encryption is carried via employing CKKS.

In this algorithm, clients in a distributed way compute the gradient for the
function $f_{i}$ defined in Equation 2 in the current iterate. After this each
client using the public key in CKKS schema performs encryption of gradient
vectors. Master obtains the encoded gradients from the clients. Then master
using a public key performs aggregation and relinearization to reduce the size
of a ciphertext after arithmetic operations. After this master broadcast
aggregated gradient estimator. Clients using private (secret) keys perform for
decryption of the encrypted direction from the master and then make a step.

Quantitative and qualitative characteristics: (1) CKKS encryption considerably
increases ciphertext space. The volume of information from clients to master
$\mathcal{O}(C\cdot dn)$ bytes, where $C$ is a constant which depends on $d$,
security level, degree of the used polynomial, and cardinality of space
$\mathbb{Z}_{q}$ to represent integer coefficient of two transferred
polynomials after encoding. (2) Size of public and private key to guarantee
AES-128 for CKKS is approximately $420\,000$ bytes, while for AES-128 the key
size is $16$ bytes. In some tasks this key size is negligible, in some tasks,
it is not. For details see Appendix G. (3) CKKS does not operate on the level
of bits only and can operate only with fp64 float point format in  TenSeal
implementation. Therefore there is no possibility of using less precision in
combination with CKKS. For details about CKKS see Appendix G.
5\. DCGD [FP16|FP32|FP64]/RandK/CKKS |  Algorithm 1, Baseline ( B), $\mathcal{C}_{i}(x)\stackrel{{\scriptstyle\text{def}}}{{=}}\frac{d}{k}\sum_{i\in S}x_{i}\cdot e_{i},S\sim_{u.a.r}\\{s:s\in 2^{[d]},|s|=k\\}$. Extra encryption is carried via employing CKKS.

Distributed Compressed Gradient Descend with CKKS. In this algorithm, clients
in a distributed way compute the gradient for the function $f_{i}$ defined in
Equation 2 in the current iterate. After this clients compress them by
selecting $k$ components from $d$ u.a.r. After this each client using the
public key in CKKS schema performs encryption of sparsified gradient vectors.
Master obtains the encoded gradients from the clients. Then master using a
public key performs aggregation and relinearization to reduce the size of a
ciphertext after arithmetic operations. After this master broadcast aggregated
gradient estimator. Clients using private (secret) keys perform for decryption
of the encrypted direction from the master and then make a step.

Quantitative and qualitative characteristics: (1) CKKS encryption considerably
increases ciphertext space. The volume of information from clients to master
$\mathcal{O}(C\cdot dn)$, where $C$ is a big constant which depends on $d$,
security level, degree of the used polynomial, and cardinality of space
$\mathbb{Z}_{q}$ to represent integer coefficient of two transferred
polynomials after encoding. For details see Appendix G. (2) Size of public and
private key to guarantee AES-128 for CKKS is approximately $420\,000$ bytes,
while for AES-128 the key size is $16$ bytes. In some tasks this key size is
negligible, in some tasks, it is not. For details see Appendix G. (3) CKKS
does not operate on the level of bits only and can operate only with fp64
float point format in  TenSeal implementation. Therefore there is no
possibility of using less precision in combination with CKKS. (4) The CKKS
does not support linear operations over sparse vectors from $\mathbb{R}^{d}$.
For HE schemas, encoding of any two vectors (e.g. sparse and dense) should be
indistinguishable due to semantic security requirements. However, from a
computational perspective, ignoring sparsity is sometimes highly impractical.
This gap presents an open research question for HE.
6\. DCGD [FP16|FP32|FP64]/PermK/AES |  Algorithm 3.

Distributed Compressed Gradient Descend with using PermK sparsifier. In this
algorithm, clients in a distributed way compute gradients in the current
iterate. After this clients compress them by selecting $k$ components from $d$
jointly via using Algorithm 2. Then clients send a sparse bitwise
representation of the sparsified gradient. Master collects the encoded
gradients as a communication hub. The PermK compressor garantees that what is
needed to perform at master is only concatenation. Therefore the algorithm can
be implemented in practice in situations when the master can store, but cannot
compute. The specified floating-point format is used to represent both data
and trainable variables. The implementation of PermK in the case of using a
pseudo-random generator can be implemented in a way, that no indices should be
transferred during training because they can be reconstituted and negotiation
between clients should be carried in runtime if clients have negotiated
initial seed.

Quantitative and qualitative characteristics: (1) There is $32$ byte overhead
during message transfers compared to DCGD/RandK. (2) The current
implementation works only in case $d\geq n$, when DCGD/RandK and GD/CKKS do
not require this (3) Volume information from clients to master is
$\mathcal{O}(d+32n)$ bytes per round. (4) Broadcasted information from master
to clients is $\mathcal{O}(d+32n)$ bytes per round.
7\. DCGD [FP16|FP32|FP64]/PermK |  Algorithm 3 in which ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Encrypt}(x)\stackrel{{\scriptstyle\text{def}}}{{=}}x$, ${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}Decrypt}(x)\stackrel{{\scriptstyle\text{def}}}{{=}}x$.

Distributed Compressed Gradient Descend with using PermK sparsifier. In this
algorithm, clients in a distributed way compute gradients in the current
iterate. After this clients compress them by selecting $k$ components from $d$
jointly via using Algorithm 2. Then clients send a sparse bitwise
representation of the sparsified gradient. Master collects the encoded
gradients as a communication hub. The PermK compressor garantees that what is
needed to perform at master is only concatenation. Therefore the algorithm can
be implemented in practice in situations when the master can store, but cannot
compute. The selected floating point format is used to represent both data and
trainable variables. The implementation of PermK in case of using a pseudo-
random generator can be implemented in a way, that no indices should be
transferred during training because they can be reconstituted and negotiation
between clients should be carried in runtime if clients have negotiated
initial seed.

Quantitative and qualitative characteristics: (1) The current implementation
works only in case $d\geq n$ only, when DCGD/RandK and GD/CKKS does not
require this. (2) This algorithm ignores privacy and security aspects. (3)
Volume information from clients to master is $\mathcal{O}(d+32n)$ bytes per
round. (4) Broadcasted information from master to clients is
$\mathcal{O}(d+32n)$ bytes per round.

###  Appendix C Computing and Software Environment

We conducted numerical experiments using the Python software suite  FL_PyTorch
(Burlachenko et al., 2021), running on Python 3.9. The target machine is a
server-grade system operating on Ubuntu 18.04 and Linux Kernel v5.4.0-148. It
is equipped with a 48-core Intel(R) Xeon(R) Gold 6246 CPU (2 sockets with 24
cores per socket) running at 3.3 GHz. The machine is equipped with 256 GBytes
of DDR4 DRAM system memory operating at 2.9GHz. The installed CPU does not
support both the AVX512FP16 Instruction Set Architecture
222https://www.intel.com/content/www/us/en/content-details/669773/intel-
avx-512-fp16-instruction-set-for-intel-xeon-processor-based-products-
technology-guide.html \- Intel AVX-512 FP16 Instruction Set and it does not
support FP16 arithmetic. The machine also has an NVIDIA GeForce RTX 3090 GPU
built on Ampere microarchitecture with 24 GBytes of<EMAIL_ADDRESS>GPU memory.
This GPU supports the CUDA Compute Capability 8.6. and as a consequence,
supports the FP16 arithmetic, which is supported for devices with Compute
Capability 5.3. and higher. 333https://docs.nvidia.com/cuda/cuda-c-
programming-guide/index.html#features-and-technical-specifications \- NVIDIA
Specification for Compute Capabilities. Numerical experiments with FP16
arithmetic were carried out in this GPU.

We have patched  FL_PyTorch to include necessary functionality from the
TenSeal (Benaissa et al., 2021) library version 0.3.14 and PyCryptodome (pyc,
2014) version 3.17. The experiment’s scheduler for computation and
communication from Appendix H.2 generates text descriptions in dot graphviz
format. Finally, we used Graphviz 8.0.5 (Ellson et al., 2002) to generate a
directed graph from this description.

###  Appendix D Overview of Existing Privacy Mechanisms in Context of FL

###### Trusted Execution Environments (TEE)

The TEE brings the idea of handling self-isolation of processes more seriously
than it has been done in the Operation Systems before. An example of the
particular implementation of this idea is ARM TrustZone (Pinto and Santos,
2019) and Intel SGX (Costan and Devadas, 2016), where both technologies have
been implemented at the hardware level. Such technologies allow the protection
of memory from reading and writing operations not only from another process in
the Operation System (OS) but also from the kernel of the OS by itself. The
goal of TEE:

TEE protects the execution environment from illegal intervention, which will
defect training.

###### Differential Privacy (DP)

The goal of DP is to ensure statistical analysis does not hurt the privacy
aspect. The intuitive definition can be as follows: "An algorithm A is
differentially private if an observer seeing its output cannot tell if a
particular individual’s data was used in the computation." DP criteria assess
the private property of the algorithm, but it does not dictate how this
functionality should be implemented. In general, as more noise is appending
the data or derived quantities from the data that are released publicly, the
algorithm starts to be more DP, but from another side, the statistical
properties of the data for the purpose of solving original task start to be
loosed.

###### Definition 1 (Approximate Differential Privacy).

An algorithm $M:\mathcal{X}^{n}\to\mathcal{Y}$ satisfies approximate
$(\varepsilon,\delta)$ \- DP if $\forall X,X^{\prime}\in\mathcal{X}^{n}$ such
that datasets are different in one point (neighboring datasets denoted as
$X\sim X^{\prime}$) and $\forall T\subseteq\mathcal{Y}$ the following holds:

$P[M(X)\in T]\leq\exp(\varepsilon)P[M(X^{\prime})\in T]+\delta$

The definition 1 is a relaxation of pure-DP, first proposed by Dwork et al. in
(Dwork et al., 2006a) in 2006. The pure-DP was given by in (Dwork et al.,
2006b), requiring $\delta=0$. The Approximate DP possesses weaker privacy
guarantees but allows the addition of less noise.

DP-ERM aims to output $\hat{\theta}$, which is $(\varepsilon,\delta)$ \- DP
with respect to the training dataset $D$. To do that, there are three types of
approaches: (1) Output perturbation; (2) Objective perturbation; (3) Gradient
perturbation. Algorithms that solves that DP-ERM problem are quantified by
expected excess empirical risk
$\mathbf{E}[\mathcal{L}_{erm}(\hat{\theta},D)-\mathcal{L}_{erm}(\theta_{erm}^{*},D)]$,
and for DP-RM problem by expected population risk
$\mathbf{E}[\mathcal{L}_{rm}(\hat{\theta},D)-\mathcal{L}_{rm}(\theta_{rm}^{*},D)]$.
These quantities are sometimes named as utility.
The goal of DP:

DP protects output of algorithms so that users’ data are not leaking from
Algorithm execution.

One important classification in DP algorithms targeted to distributed
environments is their separation into two classes: Centralized and Local
Differential Private settings. In the centralized model, a client trusts
curator (or master) and DP protection mechanism are applied in master. In the
local model, each individual applies a differential private mechanism to their
own data before sending it to an untrusted curator (or master). Centralized
models have lower privacy loss, since the noise is added only once at the end
of the process such as aggregation at master. However, the centralized model
also requires more trust in the aggregator.

###### Aggregation with Multi-Party Computation (MPC)

The MPC is a sub-field of Cryptography concerned with the problem of having a
set of parties that compute an agreed function of their private inputs. The
goal of secure multi-party computation (MPC) is to enable independent data
owners who do not trust each other or any common third party to jointly
compute a function that depends on all of their private inputs. MPC protocols
are typically implemented with (a) Secret sharing \- in this case, it requires
a lot of total communication rounds to compute the average across $n$ clients;
(b) Garbled circuits \- in this case there both communication and computation
overhead is added to the training (Zhao et al., 2019). The goal of MPC:

MPC allows for protecting inputs for the algorithm at the cost of
communication.

###### Homomorphic Encryption (HE)

Homomorphic Encryption (HE) enables numerical computation on encrypted data,
e.g. aggregating vectors from $\mathbb{R}^{d}$. However, the result can only
be decrypted with the private key. The concept dates back to 1978 when R. L.
Rivest et al. (Rivest et al., 1978) proposed this but without a complete
solution. HE allows any device party to compute functions on encrypted data
using only a public key and encrypt the result. HE aims to hide the plaintext
input and output from the executor, who only sees the encrypted versions of
it. This is possible with HE. On the other hand, obfuscation is the process of
encrypting the program (function $f$), not the input or output from the
caller. Obfuscation is impossible under weak technical conditions (Barak et
al., 2001).

Fully Homomorphic Encryption (FHE) allows any computable algorithm to be
executed on encrypted data without any restrictions on the binary operations.
The first FHE scheme was proposed by Craig Gentry (Gentry, 2009), based on
lattices and a novel bootstrapping technique. Let $c_{i}$ be the encryption of
message $m_{i}$, and $c$ be the result of evaluating a function
$\hat{f}(c_{1},\dots c_{n})$, which should decrypt to $m=f(m_{1},\dots
m_{n})$. In his Ph.D. thesis, C. Gentry listed some requirements that any FHE
scheme should satisfy, which we summarize below:

  1. (1)

Correctness: Decryption should always recover the correct evaluation of the
function, i.e., $P({Decrypt(c)=f(m_{1},m_{2},\dots)}=1)$.

  2. (2)

Semantic security: The encryption of any two messages should be
computationally indistinguishable.

  3. (3)

Efficiency: Decryption should not be more expensive than evaluating the
function itself.

  4. (4)

Compactness: Ciphertexts should have a polynomial size in the security
parameter, independent of the size of the function evaluated.

  5. (5)

Security: The best-known attack should have exponential complexity in the
security parameter, i.e., $\Omega({2^{k}})$ ($k$ is a security parameter).

  6. (6)

Feasibility: Key generation, encryption, and decryption should have polynomial
complexity in the security parameter.

By C.Gentry, only algorithms that allow executing any computable algorithm on
encrypted data that satisfies properties (1) - (6) can be called FHE. The FHE
with this requirement can firstly be hard to construct, and secondary in
practice, they may not be computationally efficient. To mitigate these issues,
two main strategies are the following:

  * •

Somewhat Homomorphic Encryption (SWHE). One way to make FHE more efficient in
practice is to restrict the class of functions that can be evaluated. This
leads to Somewhat Homomorphic Encryption, which can handle functions from
restricted classes (e.g. they are low-degree polynomials).

  * •

Leveled FHE (LFHE). Another way is to limit the depth of the binary circuit
that represents the function. This leads to a notion of Leveled FHE, which can
handle arbitrary functions represented by boolean circuits but with a fixed
bound on the circuit depth.

Challenges of applying HE for training Machine Learning models and scientific
computation:

  1. (1)

The HE adds noise to the plaintext to ensure security. The challenge is to
manage it with error-correction techniques, as it typically grows after each
arithmetic operation.

  2. (2)

The HE cannot perform random access on encrypted data without revealing
information.

  3. (3)

The HE cannot exploit the advantages of Random Access Machines, which can
compute some algorithms faster than binary circuits, e.g., Binary Search.

  4. (4)

The HE does not support multiple keys natively. Originally, it was designed as
a single-private-key system.

  5. (5)

The HE does not obfuscate the function itself, only the input and output. As
mentioned, obfuscation is impossible under weak conditions (Barak et al.,
2001).

  6. (6)

The HE works on binary circuits or functional schemas. This class of
representation is Turing Complete, assuming we can create circuits of
different levels for different inputs. The pure FHE operations are
computationally intensive and currently for practical purposes the SWHE and
LFHE schemas should be considered instead.

  7. (7)

The HE methods require large ciphertext sizes.

  8. (8)

Choosing the right HE scheme for a given machine learning task is not trivial.

The goal of HE:

HE allows meaningful manipulation under encrypted data without revealing it.

###  Appendix E Discussions

####  E.1. The Imperative of Safeguarding Against Eavesdropping

Assume that during training with first-order optimization method, each client
$i$ discloses the following information at each iteration $k\in{1,\dots,K}$:

$\dfrac{\partial f_{i}(x^{k})}{\partial
x_{j}}\stackrel{{\scriptstyle\text{def}}}{{=}}\lim_{dx_{j}\to
0}\dfrac{f_{i}(x^{k}+e_{k}\cdot{dx}_{j};{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{i}})-f(x^{k};{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{i}})}{{dx}_{j}}.$

If $f_{i}$ is twice differentiable and has bounded Hessians near point
$x^{k}$, the knowledge of partial derivative approximates the following
equality: $\dfrac{\partial f_{i}(x^{k})}{\partial x_{j}}\cdot
dx_{j}\approx{f_{i}(x^{k}+e_{j}\cdot{dx}_{j};{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{i}})-f(x^{j};{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{i}})}$.
In the last approximate equality, $e_{j}$ is a unit norm vector of the
standard basis of $\mathbb{R}^{d}$. Let’s assume that:

  1. (1)

The $f_{i}(x)$ is linear with respect to
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{i}}$ in
original form, or there exists a bijective change of variable
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{i}\to{D_{i}}^{\prime}}$
such that $f_{i}(x)$ is linear in
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{i}^{\prime}}$.

  2. (2)

Iterates $x^{k}$ are uniformly distributed in $\mathbb{R}^{d}$.

Under these assumptions, a training process might reveal sensitive
information. Indeed, if an adversary obtains this information, then
information about partial derivative provides noisy response linear function
in ${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{i}}$.
This general setting has been studied by (Dinur and Nissim, 2003). Authors
demonstrated that there exist linear attacks that could, with high
probability, expose
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{i}}$.

Specifically, let’s denote the length of
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{i}}$ is
equal to $N$ bits. Let’s assume adversarial obtains $K$ noisy answers (for a
single partial derivative) with an additive error of $E=o(\sqrt{N})$ to each
answer. Having $K\geq\theta(N^{2}/E^{2})$, such adversarial queries can reveal
information about
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{i}}$
with high probability. The hidden constant is around $256$ but can be
improved. A single full gradient $\nabla
f_{i}(x;{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}D_{i}})$
provides $d$ equations instead of $1$ for each response. This demonstrates
that in specific modes the pretty big amount of partial derivative already
reveals enough information to reconstruct the client’s dataset. Such attacks
are not only in theoretical interest but can be practically mounted (Cohen and
Nissim, 2018), (Kasiviswanathan et al., 2013).

####  E.2. Privacy and Security

As we have described in Appendix D, different mechanisms can be used for FL to
provide privacy for different aspects training process. Each mechanism has a
specific target of protection (such as input, output, execution, or
communication channel) and a specific adversary model. The precise meaning of
protection is defined by rigorous formalization and the details are crucial.
For example, DP protects the output of an algorithm so that it does not reveal
sensitive information about the input data, while MPC protects the input data
from being exposed to other parties during computation. Recent research papers
on FL deployments have mostly used Local DP (Bhowmick et al., 2018), or a
combination of MPC and centralized DP.

In contrast, the proposed design in our work can be understood as a mechanism
for providing security for the training process rather than privacy. The
response obtained from the server by the client is computed securely and
accurately with protection against attacks on the server or the communication
channels to the server. The notion of privacy covers the guarantee that the
target of protection can participate in an algorithm without being observed by
unauthorized parties. Security, on the other hand, can be considered as a more
holistic concept that specifies: the algorithm or protocol, how personal
information and derived quantities are protected, the type and strength of
attacks that are resisted, and the requirement of having a secret key to
access the data. Sometimes, a complex security protocol may not be feasible or
desirable for certain situations, and a privacy mechanism that is less
comprehensive but more flexible may be a better choice.

###  Appendix F Usage of AES cipher during Distributed Training

This section overviews the current state-of-the-art block cipher AES and
explains how it can be used for symmetric key encryption in scenarios where
multiple client messages must be encrypted and decrypted securely.

####  F.1. AES Block Cipher

A block cipher is a fundamental cryptographic primitive that transforms a
fixed-length block of bits into another block of the same length using a
secret key. The AES is today’s most widely used secure block cipher. Some CPUs
have hardware support for it. Examples of CPUs with x86 instruction set
architecture that support AES in the hardware level are Intel Westmere, AMD
Bulldozer, and ARM AARCH64 instruction set architecture example is ARM
Cortex-A53.

AES block cipher supports three key sizes: $128$, $192$, or $256$. The key
size determines the level of security and the computational cost of the
encryption and decryption operations. The key space $K$ for AES-128 has size
of $|K|=2^{128}$. The input message space $M$ and the output cipher text space
$C$ of the block cipher AES for all types of keys have the same size equal to
$128$ bits. Therefore cardinality of $M$ and $C$ is equal to
$|M|=|C|=2^{128}$.

For each key $k\in K$, the AES block cipher maps $M\to C$ with a bijective
function, with $M=C$, and $|M|=|C|\leq\infty$. Essentially, the key $k$ is a
selector of bijective mapping or permutation. Each key realizes the
permutation of the input message. If we assume that each of two distinct keys
$k_{1},k_{2}\in K$ implements different bijective mappings $M\to C$, then the
number of permutations that AES can realize is $|K|=2^{128}$. Even though it’s
a big number, this is much smaller than $2^{128}!$, all possible permutations
if input and output are $128$ bits in length. In the Cryptography community,
the block cipher AES is sometimes observed as a primitive that implements a
Pseudo Random Permutation (PRP). In other words, this means that for a fixed
key, it defines a permutation. The discrepancy between the number of all
possible permutations and the number of PRPs that AES can realize is elegantly
resolved in the Cryptography community. It is resolved by introducing the
notion of a Secure PRP. The algorithm which implements PRP implements a Secure
PRP if an adversary from observing the realization of permutation $f$ cannot
distinguish by using an arbitrarily tractable algorithm between two events:

  1. (1)

The permutation function $f:M\to M$ is chosen uniformly at random from all
possible $M!$ permutations.

  2. (2)

The permutation function $f:M\to M$ is chosen as one of the permutations that
block cipher $\mathrm{BlockCipher}(\cdot,k):M\to M$ with $k\sim_{u.a.r}K$ can
realize.

By the current status in Cryptography, the AES is believed to be a secure PRP.
Having two input and output pairs, adversarial may wish to derive the secret
key. The brute force search on AES-128 is computationally infeasible because
$2^{128}$ is too large to enumerate. The best-known attack on the full version
of AES-128 that can recover the complete key has a complexity of $2^{126}$
(Bogdanov et al., 2011). The AES-128 is secure against brute force search and
also against linear and quantum attacks (Jang et al., 2022).

####  F.2. Internals of AES Block Cipher

The AES block cipher has $10$ rounds for AES-128 and $14$ rounds for AES-256.
The key is expanded into $11$ or $15$ subkeys of $128$ bits in length each.
Subkeys are used in each round. Each round consists of four invertible steps:
key addition (in the sense of exclusive boolean or, which we will denote as
XOR), byte substitution, row shift, and column mix. These steps transform a
$4\times 4$ matrix of bytes representing each round’s input. Byte substitution
adds non-linearity, row shift rotates each row cyclically, and column mix
applies a linear transformation to each column. The last subkey is used for a
final key addition (XOR) to mask the output. The AES decryption reverses the
encryption steps. The AES has different implementations for different devices
and code size requirements. All occurred transformations are stateless;
consequently, the AES block cipher is stateless.

####  F.3. Apply AES Block Cipher for more than one input block

The AES is a secure block cipher, but it is a bad idea to use the same key $k$
to encrypt multiple blocks deterministically. This breaks the notion of
Semantic Security, which essentially means that adversarial can deduce some
information from analyzing sequences of ciphertexts from the block cipher
(e.g. adversarial can, from observing $c_{1}=c_{2}$ conclude that
$m_{1}=m_{2}$, even adversarial does not know exactly values $m_{1},m_{2}$).
To preserve Semantic Security, the encryption should have protection from
chosen-plaintext-attack, which informally denotes this kind of attack.

Formally, in chosen-plaintext-attack (CPA) an attacker may adaptively ask for
the encryption $(e_{1},e_{2},\dots)$ of arbitrary messages
$(m_{1},m_{2},\dots)$ of his choice. The attacker’s goal is to obtain the
ability to correctly guess from two obtained encryption $\\{e_{a},e_{b}\\}$
from experiment $A$ and experiment $B$ which encryption belongs to which
message from the set $\\{m_{a},m_{b}\\}$. The attacker does not know
encryption of $\\{m_{a},m_{b}\\}$ in advance, and the attacker does not know
which plain message has been used in which experiment. In the context of this
attack, the advantage of adversarial is defined as:

${ADV}_{cpa}=|P(\\{\mathrm{ExperimentA\,uses\,}m_{a}\\})-P(\\{\mathrm{ExperimentB\,uses\,}m_{b}\\})|.$

Fundamentally, there are two ways to provide security against CPA attacks:

  1. (1)

Increase ciphertext space and allow encryption to work randomly. This is the
underlying reason why CKKS is CPA secure. The downside of this is that
ciphertext space is increasing.

  2. (2)

Augment key space $K$ with extra counter, named as a nonce from a nonce space
$N$. The clients who perform encryption guarantee that the pair $(key,nonce)$
is unique during the life of the $k$. The $nonce$ is open to everybody.

Next, there are two different ways to select nonce in nonce-based protection
against CPA attacks:

  1. (1)

Deterministic counter. In this mode, a single deterministic integer counter is
used. Sometimes there is no need to send nonce itself with ciphertext during
communication if the receiver of ciphertext can recover counter from other
information.

  2. (2)

Randomized counter. If encryption happens on several devices, the coordination
of nonce complicates the process. One way around this is to select
$nonce\sim_{u.a.r.}N$, where $N$ is sufficiently large, e.g. $|N|>2^{128}$.
Such nonce space size will guarantee that we expect to obtain during the
sampling at least one collision after sampling $\sqrt{2|N|}+1=2^{64}$ due to
the famous Birthday Paradox.

The two popular ways to use nonce-based encryption for AES, also known as
Operation Modes, are the following:

  1. (1)

Nonce-based Cipher Block Chaining Mode (CBC). In this schema, the input
message is split into buckets. These inputs are substituted into AES block
cipher, but the inputs themselves are masked before encryption. The first
plaintext bucket is masked (via XOR) with nonce. Other plaintext buckets are
masked (via XOR) with the output from AES block cipher operated in the
previous block. The output of this mechanism is the public nonce and sequence
of encrypted input buckets. It can be proved that AES/CPA secure with
advantage ${ADV}_{cpa}\leq 1/2^{32}$ if use CBC for $2^{48}$ AES ($128$ bits)
blocks. If nonce is generated with non-secure PRG, then it should be firstly
encrypted by itself with secure AES Block to generate secure nonce.

  2. (2)

Randomized Counter Mode (CTR). The input message is split into buckets. But in
this mode, the mask for each bucket $i$ is generated with AES block cipher
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\sf\small{AES}}(k,nonce+i)$.
The input bucket is masked with this value
${\color[rgb]{0,0,1}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,1}\sf\small{AES}}(k,nonce+i)$
via XOR operation. It can be shown to guarantee CPA security with the
advantage $1/2^{32}$ for it the number of transferred messages with AES should
be at most $2^{64}$ AES Blocks. In addition, this operation mode is more
flexible in contrast to CBC because this mode does not require any padding and
can be implemented by discarding not needed bits in the last bucket.

The CKKS and AES in EAX mode of operation (Bellare et al., 2004) are secure
against CPA attacks.

####  F.4. Apply AES with Integrity Guarantees

The CPA security and operations mode solve security against eavesdropping, but
they don’t provide integrity of the delivered messages. Message Authentication
Code(MAC) is Cryptography protected analogous to (non-secure) Cyclic
Redundancy Check (CRC), which is used in Networking communication to protect
from random (not adversarial) noise in communication channels. The goal of MAC
is that the value of MAC coupled with a ciphertext guarantees that the message
has not been modified during the transfer by the adversary. The signing
algorithm for generating MAC tag takes a plain message $m$ and secret key $k$
as input. The signature is added to the transferred message with the public
nonce. Adversarial without a secret key $k$ cannot produce valid
$(Message,Mac)$ pairs in such a way that it will pass the verification
algorithm. The verification algorithm takes as input the secret key $k$,
decrypted message $m$, and MAC value $tag$. In practice, nonce and MAC are
typically $16$ bytes long. If the optimization algorithm already requires
sending far more than $2$ elements of $\mathbb{R}$ encoded in IEEE-754 FP64
format then this overhead is negligible during the training.

Two popular constructions to provide integrity in the context of AES are the
following:

  1. (1)

Encrypted CBC-MAC. The input message is split into $16$ bytes buckets. After
this, the first bucket is plugged into AES as input. Output from this block is
masked with XOR with the next input $16$ byte bucket. After the XOR operation
is finished, the output of XOR is plugged into the next AES block as input,
and the process repeats in a chaining fashion. It is important to notice that
all AES blocks use the same key $k$. Finally, the last output is plugged into
one more AES block as input, which uses another key $k^{\prime}$ and schema
releases MAC tag.

  2. (2)

Nested MAC. In this approach, the message is split into $16$ bytes buckets.
After this, the first AES block obtains as input this first bucket and $k$ is
used as a secret key. The output of this AES block is used as a key for the
next block, and data for this AES block is the next input bucket. After
processing all messages, the last output is plugged into the last AES block as
input, but for the last AES block, another secret key $k^{\prime}$ should be
used similarly as in CBC-MAC.

For using CBC-MAC and Nested MAC securely, the number of signed messages (of
arbitrary length) should be on the order of $2^{64}$ AES $128$-bits blocks.
For details, please check the analysis of these schemes.

####  F.5. Chosen Ciphertext Attack CCA and Authentication

In a chosen ciphertext attack (CCA), the attacker has access to a decryption
oracle and can decrypt any ciphertext of his choice. Also, the attacker can
access encryption oracles and obtain encryption of arbitrary messages of his
choice. Adversarial aims to break semantic security in the CPA sense. To
provide the CCA security, the two processes Encrypt and MAC should be
performed sequentially, and typically it’s preferable to perform them in this
order. In our paper, we have used EAX, which is CTR mode for encryption
combined with CMAC for integrity purposes.

####  F.6. Using AES with EAX Operation Mode in our paper

We use AES encryption with EAX mode, which produces a triple as output:

$\langle m=C_{i}(\nabla f(x^{t})\in\mathbb{R}^{d}(16/32/64\cdot
d\,\mathrm{bits}),nonce\in
N(128\,\mathrm{bits}),Tag(128\,\mathrm{bits},ciphertext)\rangle$

.

The ciphertext has the same bit length as the original message. Because EAX
mode employs CTR for stream encryption, it does not require any padding. The
$nonce$ is a random 16-byte value, and the $Tag$ is a $16$ byte message
authentication code. As it has been mentioned in Section 4, the CKKS and all
HE schemas cannot achieve CCA security (Fauzi et al., 2022). For AES/EAX, it
has been proved in (Bellare et al., 2004) that it’s secure against CCA
attacks. Cryptography is an area of science by itself. Readers for can gain
more information about Classical Cryptography from (Boneh and Shoup, 2020).

###  Appendix G Homomorphic Encryption with CKKS

####  G.1. Learning With Errors Problem and REGEV09 Algorithm as a Concrete
Example of SWHE

The security of the CKKS scheme depends mainly on the hardness of the Learning
With Errors(LWE) problem which we will overview next. The "Learning with
errors" search problem represents was analyzed in (Regev, 2009). For this work
Oded Regev has obtained a Gödel prize in 2018:

$\displaystyle\mathrm{find}\,s\in\mathbb{Z}_{q}^{n}$
$\displaystyle\mathrm{such\,that:}\,s^{T}\mathbf{A}+e^{T}$
$\displaystyle=b\,\mathrm{where}\,e\,\mathrm{is\,r.v.}$

Parameters have the following properties:

  * •

The $q$ is a prime number.

  * •

$m>n$.

  * •

$\mathbf{A}\in\mathbb{Z}_{q}^{n\times m}$ is a random matrix drawn u.a.r. from
$\mathbb{Z}_{q}^{n\times m}$.

  * •

$\beta\in\mathbb{R}$.

  * •

$e\in\mathbb{Z}_{q}^{m}$ is small (in terms of $L_{2}$ norm) r.v. For r.v. $e$
there is no assumption about its distribution. The only one constraint is that
$e\neq 0$.

As can be observed from the description LWE problem operates on a system of
over-determined sets of equations. When $e=0$ the system can be solved via
Gaussian elimination, but when $e\neq 0$ we believe it’s a hard search
problem. Specifically, Theorem 1 from (Regev, 2009) makes a connection between
LWE and the search problem in integer lattices via the following theorem:

Instance of LWE problems with parameter $n$ is as hard as the Short Integer
Solution Problem.

The best well-known solution for solving the LWE problem works in the
following time: ${q}^{\mathcal{O}\left({n}/{\log(n)}\right)}$ (Blum et al.,
2003).

There exists a variation of the LWE problem named as Decision Learning With
Errors problem. In theory, it has been shown that Decisional LWE is as hard as
LWE. In usual LWE we can not find a solution for a noisy set of linear
equations effectively based on knowledge of $A$ and $b$. In Decisional LWE the
adversaries can not from observing tuple $(\mathbf{A},b)$ distinguish the
following two scenarios:

  1. (1)

The tuple $(\mathbf{A},b)$ has been generated completely uniformly at random.
In some sense, there are no real hidden linear dependence structures between
columns of $A$ and $b$.

  2. (2)

The tuple $(\mathbf{A},b)$ in fact has a specific structure
$(\mathbf{A}=\mathbf{A},b=\mathbf{A}^{T}s+e)$.

The LWE problem provides a way to publish a lot of perturbated linear
equations in variable $s$ in the form of $s^{T}\mathbf{A}+e^{T}=b$, and
essentially hide $s\in\mathbb{Z}^{n}$ from parties who do not know exactly
$e$.

Next, we will describe concrete examples of using this idea. The method
described next represents a symmetric Somewhat Homomorphic Encryption (SWHE)
Learning With Errors (LWE) based scheme known as REGEV09. The method was
proposed in 2009 at work (Regev, 2009). Its security properties are based on
hardness to solve the decisional LWE.

###### KeyGen.

$s\in\mathbb{Z}_{q}^{n}\sim U$ is a secret key, $q$ is a prime, $n$ is a
secure parameter.

###### Encrypt.

Encryption is working bit by bit. The message that we encrypt without loss of
generality can be considered as $m\in\\{0,1\\}$. The algorithm for encryption
produces ciphertext as $c=(a,b)\in\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}$ via
following rules:

  1. (1)

$e\in\mathbb{Z}$ is a "short" noise generated from some distribution,
satisfied constraint $|e|<q/4$).

  2. (2)

$a\in\mathbb{Z}_{q}^{n}$ is a random vector sampled uniformly from its domain.

  3. (3)

$b\stackrel{{\scriptstyle\text{def}}}{{=}}\langle
a,s\rangle+e+(m\cdot\left\lfloor q/2\right\rfloor)|\mod q$.

  4. (4)

The released ciphertext $c=(a,b)\in\mathbb{Z}_{q}^{n}\times\mathbb{Z}_{q}$

###### Decrypt.

Decryption happens via using the following formula which involves function
${round}_{a}(x)$ which round to $0$ or $a$ depends on what is more close to
$x$.

$\displaystyle\hat{m}$ $\displaystyle=$
$\displaystyle\dfrac{round_{q/2}\left(b-(\langle
a,s\rangle\pmod{q})\right)}{q/2}$ $\displaystyle=$
$\displaystyle\dfrac{round_{q/2}({\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{(\langle
a,s\rangle+e+m\cdot\left\lfloor q/2\right\rfloor)}}-\langle
a,s\rangle)}{q/2}=\dfrac{{round_{q/2}(e+{\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{m}}\cdot\left\lfloor
q/2\right\rfloor))}}{q/2}.$

For decryption to work correctly, we need to have $e\in(-\left\lfloor
q/4\right\rfloor,\left\lfloor q/4\right\rfloor)$. Now let’s verify that this
formula works correctly: If
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{m=0}}$,
and because $|e|<\left\lfloor q/4\right\rfloor$ $\implies\hat{m}=0$. If
${\color[rgb]{1,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{1,0,0}{m=1}}$,
and because $|e|<\left\lfloor q/4\right\rfloor\implies e>-\left\lfloor
q/4\right\rfloor$ $\implies\hat{m}=1$.

###### HE Add.

We add two ciphertext messages $c_{i}=(a_{i},b_{i}),i\in\\{0,1\\}$ by
components:

$(a_{1}+a_{2},b_{1}+b_{2})=(a_{1}+a_{2},\langle
a_{1}+a_{2},s\rangle+(e_{1}+e_{2})+(m_{1}+m_{2})\left\lfloor
q/2\right\rfloor\pmod{q}.$

This schema is SWHE and homomorphic additive. In the worst case error is
doubled in each addition operation of each bit. If the adversary listens to
the channel, he can collect $(a,b)$ for each transferred bit and construct
$\mathbf{A}=[a_{1},a_{2},\dots]$ and the right-hand side $b$. But encoding of
ciphertext directly follows LWE problem description with additive error
correction code $e+m\cdot\left\lfloor q/2\right\rfloor$. By properties of the
Decision LWE Problem, adversaries can not get any information from it because
data distribution $(\mathbf{A},b)$ is indistinguishable from a uniform.

####  G.2. Introduction to CKKS

There are different variants of FHE, LFHE, and SWHE, but most of them operate
on boolean or integer arithmetic. In our paper, we compare DCGD/PermK/AES
against GD with Cheon-Kim-Kim-Song (CKKS) (Cheon et al., 2017) schema. This
schema allows approximate arithmetic on encrypted real and complex numbers and
dense linear vectors.

The CKKS schema violates property (1) of FHE from Appendix D, and it is
specialized to work with these two linear spaces $\mathbb{R}^{d}$ and
$\mathbb{C}^{d}$. Therefore, CKKS is an SWHE scheme. Still, it is sufficient
for most Machine Learning problems that operate on real spaces during the
training phase, and it is the most popular schema in Machine Learning
applications that require HE. Supporting multiple keys (MK) with privacy
guarantees is an active research topic (Kluczniak and Santato, 2023). None of
MK-CKKS possible schemas are currently implemented in  TenSEAL (Benaissa et
al., 2021) or  SEAL (Microsoft, 2021) libraries. In our work, we used the
classical single-key CKKS scheme for comparison because it’s suitable for our
setting.

As we mentioned, the CKKS scheme allows us to perform HE computations on
vectors of complex and real values. CKKS provides ways to perform element-wise
addition, multiplication, and rotation of elements in encrypted form. The CKKS
uses three different keys:

  * •

Public key. The public key in CKKS schema is used for the encryption of plain
messages.

  * •

Relinearization key. Relinearization key reduces the size of a ciphertext
after arithmetic operations on ciphertexts.

  * •

Private(secret) key. The private (secret) key is used for decryption of
encrypted messages.

To perform arithmetic operations on encrypted vectors on the master device,
the master should know the public key and the master should know the
relinearization keys to reduce the size of a ciphertext after arithmetic
operations. The public key in CKKS schema is used for encryption and can be
shared with the master. However, a private(secret) key is used for decryption
and must be kept confidential from the master if clients do not trust the
master. The security of the scheme depends on the hardness of the Ring
Learning With Errors (RLWE) problem. The RLWE is a generalization of LWE
problem, but instead of using $\mathbb{Z}_{q}^{n}$ field, it is based on
underlying algebra which is polynomials over a ring. RLWE inherits useful
properties of hardness from LWE, but it is more space efficient. For an
overview of LWE see Appendix G.1.

####  G.3. Description of processes inside CKKS

The schematic process of how CKKS operates is depicted in Fig.8. The general
schema of CKKS consists of several steps.

###### First Step.

Firstly, a vector of values $m\in\mathbb{R}^{N/2}$ on which we want to perform
certain computations is encoded into a plaintext polynomial $p(x)$. This is
necessary because encryption, decryption, and other mechanisms work on
polynomial commutative rings. In the case of encoding into polynomials from
$\mathbb{Z}[X]/(X^{N}+1)$, the encoding process is reversible. In the original
paper, (Cheon et al., 2017) this process is carried out using canonical
embedding. This embedding is carried in such a way that if evaluate the
obtained polynomial from $\mathbb{Z}[X]/(X^{N}+1)$ at the roots of cyclotomic
polynomial $X^{N}+1$ we will recover entries of the original message of
$n\in\mathbb{R}^{N/2}$.

###### Second Step.

Next, the actual encryption part encrypted the plain polynomial with integer
coefficients via a public key into polynomial
$(c0,c1)\in(Z_{q}[x]/(X^{N}+1))^{2}$. The $q$ is a modulus number in the CKKS
scheme. Here $q=\prod_{i=1}^{L}q_{i}$, where $q_{i}$ are prime numbers. So $q$
is not necessarily a prime number, but it is chosen to be a product of several
prime numbers. To carry encryption the public key in the form of
$Z_{q}[X]/(X^{N}+1))$ after specific transformation is used. It means that the
size of the public key in bits is approximately equal to $N\cdot q$. To have
AES-128 security level for CKKS the key size is at least equal to $420$
KBytes.

###### Third Step.

Next, the algebraic operations are carried on encrypted messages
$(c_{0},c_{1})$ by specific rules which we will not go deep into.

###### Fourth Step.

After carrying out the arithmetic operation, the result will be from the same
space $(c0,c1)\in(Z_{q}(x)/(x^{N}+1))^{2}$. To carry decryption the private
key in the form of $Z_{q}[X]/(X^{N}+1))$ after a specific transformation is
used. Therefore it means that the size of the private key in bits is
approximately equal to $N\cdot q$. To have AES-128 security level the key size
at least equal should be equal to $420$ KBytes.

###### Fifth Step.

Finally during decoding, a message from space $(Z_{q}(x)/(x^{N}+1))^{2}$ to
plain text in $Z[x]/(x^{N}+1)$ and finally perform decoding into
$\mathbb{R}^{N/2}$.

####  G.4. CKKS Configuration Equivalent to AES-128

To provide privacy grantees similar to AES-128 encryption: $N$ should satisfy
this condition $N>16384$, and $q=\prod_{i=1}^{K}q_{i}$ should be at least
$438$ bits long. This ensures that the security parameter $N$, $q$ is large
enough to provide sufficient security. These details can be found in the
reference implementation of Microsoft Research  SEAL Library
444https://github.com/microsoft/SEAL/blob/master/native/src/seal/util/hestdparms.h
\- Microsoft Research SEAL Library.. This is an underlying reason why CKKS has
a more memory requirement compared to AES-128. The encoding consists of $2$
polynomials with $2\max(d,N)$ coefficients, and each coefficient is not 32
(for FP32) or 64 (for FP64) bits long, but it’s essentially $q=438$ bits long.
In addition, when input/output vectors do not match $N$ CKKS/HE requires
performing chunking of input and output - it requires additional operations to
maintain the correctness and efficiency of the computation.

In all our experiments, we used the following CKKS configuration inside
TenSeal (Benaissa et al., 2021) library version 0.3.14. For this library to
obtain AES-128, we have used the recommended configuration:

  1. (1)

Polynomial degree: $2^{14}=16\,384$

  2. (2)

Coefficient modulus: $q_{1},q_{2},q_{3},q_{4},q_{5}=(60,30,30,30,60)$ bits,
which corresponds to $q$ size of $210$ bits. This configuration is
recommended, by  TenSeal for AES-128 security level.

  3. (3)

Scale factor: $2^{30}$

  4. (4)

Scheme type: CKKS

Input message $m\in\mathbb{R}^{N/2}$ Encode message $m\in\mathbb{R}^{N/2}$
into $m^{\prime}\in\mathbb{Z}[x]/(x^{N}+1)$ Encrypt message
$m^{\prime}\in\mathbb{Z}[x]/(x^{N}+1)$ into
$m^{\prime\prime}\in\left(\mathbb{Z}_{q}[x]/(x^{N}+1)\right)^{2}$ Computation
on encrypted messages
$\left(m_{1}^{\prime\prime},m_{2}^{\prime\prime},\dots\right)$. CKKS allows to
perform: addition, multiplication, and rotation.Decrypt
$m^{\prime\prime}\in\left(\mathbb{Z}_{q}[x]/(x^{N}+1)\right)^{2}$ into
$m^{\prime}\in\mathbb{Z}[x]/(x^{N}+1)$Decode message
$m^{\prime}\in\mathbb{Z}[x]/(x^{N}+1)$ into $m\in\mathbb{R}^{N/2}$ Output
message $m\in\mathbb{R}^{N/2}$ Figure 8. A high-level view of operations
inside the CKKS schema.

###  Appendix H Extra Experiments

####  H.1. Exploring Problem Dimension

This experiment investigates the impact of problem dimension
$d\in\\{10^{3},10^{4},10^{5}\\}$. Fig. 9 shows that the CKKS overhead from
encryption is $\times 10^{3}$ more both in master to client, and client to
master communication direction compare to DCGD/PermK/AES. With $d=10^{6}$ the
memory footprint for CKSS configured to guarantee the same guarantees as
AES-128 in the master to store $n=50$ encrypted gradients is $46$ GBytes,
rendering storage of such information in the master challenging. The best
convergence relative to the volume of information sent to the master is
achieved with DCGD/PermK. The behavior of DCGD/PermK and DCGD/PermK/AES is
indistinguishable for $d>10K$. Despite the ciphertext size being the same as
the input when using AES, proper use of AES block ciphers for communication
requires the addition of a Message Authentication Code (MAC) for protection
against malicious errors and a unique pseudo-random identifier (nonce). Each
of these adds an overhead of $16$ bytes. It explains different behavior
observed for DCGD/PermK and DCGD/PermK/AES at $d=1K$ in Fig. 9.

Given that, DCGD/PermK/AES emerges as a more viable alternative to CKKS in FL
context, in the setting when HE previously has been applied.

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

(i)

(j) (a) $d=1\,000$

(k) (b) $d=10\,000$

(l) (c) $d=100\,000$

Figure 9. Linear Regression in interpolation, $n=50$, $n_{i}=12$, compute
FP64. Tuned $\gamma=0.007$ for DCGD. Theoretical $\gamma$ for GD.

####  H.2. Compute and Communication Overlap for DCGD/PermK

In this experiment, we simulated a compute and communication environment with
realistic assumptions and evaluated the performance of DCGD/PermK. We ignored
overheads from the Operating System (OS) and its components (drivers, kernel,
services). Firstly, we provide background on Network Communication and System
Architecture to justify our modeling choices.

#####  H.2.1. Background in Network Communication

###### Communication Bandwidth During Master Client Communication

We consider a scenario where clients are connected to the master via the
Internet. These devices are called end systems or hosts in the context of a
communication network. The communication between end systems is facilitated by
intermediate routing devices, such as routers and switches, connected by
links. Internet communication is based on packet switching, which means that
exchange messages $m$ are divided into smaller units called packets. Then,
they are delivered with the best effort through the communication network
without reserving a path(circuit) from sender to receiver in advance.

The bandwidth of a link is the maximum rate at which data can be transferred
over it and is measured in bits/second. This rate depends on various factors
and generally can vary over time. It depends on:

  1. (1)

The distance between the linked devices.

  2. (2)

The type of physical medium for carrying the signal.

  3. (3)

The number of packets in the queue to transfer in routing devices.

  4. (4)

The probability that clients on the Internet will use the same link
simultaneously.

  5. (5)

The probability that a packet will be dropped in a routing device.

  6. (6)

The number of clients attached to the link.

We can distinguish between two types of bandwidth:

  1. (1)

Instantaneous bandwidth \- bandwidth at a specific moment of time.

  2. (2)

Average bandwidth \- average bandwidth over a complete message transfer.

If the information flows from client to master via a directed path across $N$
links, then the effective bandwidth of the path is determined by the minimum
bandwidth among all links:

$B_{\mathrm{transfer}}=\min_{i\in[N]}B_{i}$

.

The link with this minimum bandwidth is called the bottleneck link.

###### Communication Delays During Master Client Communication

The delay of a single link device is the actual time it takes for a bit of
data to travel from one link device to the next. The delay consists of several
components:

  1. (1)

Processing delay is the time required to examine the packet header and
determine where to forward the packet in a link device with several output
ports.

  2. (2)

Transmission delay, which is the time required for the router to push out the
packet into the link, without considering the propagation of signal by itself.

  3. (3)

Propagation delay is the time required for the signal to travel along the
physical medium.

  4. (4)

Queuing delay is the time required for a packet to wait in the output buffer
if the link output port is busy.

  5. (5)

Loss delay is the time required for a packet to be retransmitted if it is
dropped due to buffer overflow or errors due to medium.

Suppose a client and a server are connected by $N$ links sequentially, and the
information flows through them in a directed path. In that case, the total
delay for transferring a single package over this path is given by the sum of
all delays along each link over the path:

$\tau_{\mathrm{delay}}=\sum_{i=1}^{N}\tau_{\mathrm{delay},i}.$

#####  H.2.2. Network Communication Model

As we have seen, the total delay and bandwidth vary, even for the fixed
topology of connecting the master and clients. According to 555Speedtest
Global Index in the average download bandwidth across the globe is
$B=41.54\,\mathrm{MBps}$ and communication latency is $RTT=28\,\mathrm{ms}$.
The delay time for communication with messages $m\in\mathbb{R}^{d}$ where each
component is represented by $bpp$ bits per component from master to client is
modeled in the following way:

$\tau_{delay}=\frac{RTT}{2}+\frac{d}{B}\cdot bpp.$

Here, $B$ is the bandwidth (or throughput) of the communication channel
between the master and the client. We assume it’s constant. Next, $RTT$ is the
time for a small packet to travel from client to server and back. It is only
an approximation; for example, it does not model Packet Loss Delay. The worst-
case maximum delay is very difficult even to estimate. We assume that $RTT/2$
and $B$ are not changing during training. However, in real communication
networks, the path from client to master the exact communication path can
change over time.

In reality, a Network Interface Controller (NIC) implements network
communication in a local computing device, and it is typically connected with
a PCI-Express bus as an external input/output device to the whole local
computation system. For modern PCI-Express buses such as PCI-E v5, the
bandwidth, even for a single physical lane x1, is in the order of $4000.0$
MBps, and latency for this bus and latency is on the order of $35\cdot
10^{-3}$ ms. It means that in context when devices are communicated via the
Internet, the effect of delays from PCI-Express is negligible, or at least it
does not represent the bottleneck both in terms of bandwidth and latency. The
same holds for involving communication time to transfer data from CPU to DRAM
memory. Modern DDR5 memory has a bandwidth of $51200$ MBps, and latency is
measured in the order of nanoseconds. It means that what is represented as a
bottleneck from a communication point of view (both in terms of latency and
bandwidth) with the server is the connection to though NIC installed in the
client.

#####  H.2.3. CPU-based Computation in Clients

To evaluate the compressed gradient $C_{i}(\nabla f_{i}(x))$ in a client,
different algorithms can be used, such as analytical, numerical, symbolic, and
methods that leverage automatic differentiation. These algorithms need to run
on some device that can execute them efficiently. We will focus on the
execution aspects of modern Central Processing Units (CPUs), which are the
most flexible devices from a programming perspective. CPUs have multiple cores
that contain various components that work together to execute algorithms.

#####  H.2.4. Background in Modern Central Processing Unit

###### Instruction Decode

In this stage, the CPU decodes the instructions and obtains information about
the input, output, and operation type. Then, it splits the instructions into
micro operations and puts them into the Operation Issue Queue. This stage may
introduce some complexities. One complexity is that some CPUs can decode
multiple instructions simultaneously and issue them in parallel. This is
called a multi-issue (or superscalar) design, which aims to exploit
instruction-level parallelism by executing independent instructions
concurrently. Another complexity is that the CPU with out of order issue
capability can execute instructions whenever they are ready, regardless of the
original order.

###### Operation Issue Queue

This is a hardware queue where decoded instructions, in the form of micro-
operations, are stored. The queue has a minimum length that can accommodate
the longest sequence of micro-operations for any instruction in the CPU’s
instruction set.

###### Control Unit (CU)

The CU operates at the level of micro-operations and performs the following
functions: (a) selecting the way to connect electrical components using
multiplexers and demultiplexers; (b) turning on/off different electronic
components; and (c) controlling the control lines of electronic components.

###### Multiplexers and Demultiplexers

During pipeline execution, intermediate inputs and results are stored in the
latches of electrical components. To route signals within the CPU,
multiplexers, and demultiplexers are utilized. Signals propagate through the
component once all the components are connected, and data is applied to the
input ports. The results are then produced when the enabled control signal
reaches the electrical component.

###### Adder and Multiplier

The adders and multipliers are electrical circuits that perform addition or
multiplication when turned on. The input for these devices is read from the
intermediate buffer of the electronic component(latches). The typical input
source (after intermediate routing with multiplexers and demultiplexers) is
the Register File.

###### Register File

The Register File is a storage unit that holds all the registers in the CPU.
It has multiple ports that allow parallel access to it. The Load and Store
Units may have direct access to the Register File.

###### Load and Store Units (LS)

The Execution pipeline sends requests to the LS units for memory access. The
LS units can access the Register File, the TLB for address translation, and
the Memory Cache.

###### Translation Lookaside Buffer (TLB)

To read code or data from memory in the user space or kernel space of the OS,
the first step is to find the actual physical address of the specific memory
location. This operation occurs for every instruction of a program. Without
the TLB, the virtual addressing mechanism would require several accesses to
different page tables, significantly increasing the time needed. The TLB is a
cache that stores the mapping between virtual page numbers and physical frame
numbers, speeding up the address translation process for memory access. The
TLB relies on the locality of code and data in most algorithms.

###### CPU Memory Cache

The CPU Memory Cache is a fast storage unit that holds frequently accessed
data and instructions. It is used to reduce the latency of accessing the DRAM
memory. The Load and Store Units have access to the Cache. Modern high-end
systems support three levels of Cache. The L1 cache is typically split between
data and instructions, and it is the closest to the CPU. The L2 and L3 caches
are larger and slower, and they can be shared by multiple cores. The cache
implementation varies across different CPUs, depending on the trade-offs
between speed, potential conflicts, hardware complexity, cache replacement
policy, and power consumption. If the data is not available in the Cache, then
the CPU Cache requests a block of memory from the Memory Controller (MU),
which accesses the DRAM memory. When data from DRAM is stored in multiple CPU
caches, it fundamentally means that data may be stored in several places. In
this situation, another aspect becomes important: (a) cache consistency, which
essentially means that all copies of DRAM cache lines should be the same in
all caches in the system; (b) cache coherence which essentially means that any
read of memory returns the most recent update anywhere in the system.

###### DRAM Memory Controller (MC)

The DRAM Memory Controller is a device that manages access to the main DRAM
memory Chips. It is used to fetch data from the Main Memory when it is not
available in the CPU cache. The Memory Controller returns the data to the
caches in blocks of a fixed size, called Cache Lines, and typically it is $64$
bytes. The Memory Controller is also responsible for running the memory bus
transactions, which are the transfers of data between the MC and DRAM memory
chips. The Memory Controller is typically implemented in the hardware as a
device that is shared by multiple cores.

###### DRAM Memory Chips

Memory chips are devices that store data in binary form. They are usually
specified by the number of bits stored and the number of bits accessed in one
read or write operation. For example, a common DRAM chip 4Gbx1 means that it
can store 4G bits and access one bit at a time. To protect data from
corruption, extra logic may store bits for Error Correction Codes (ECC).

###### Input and Output Buses

Input and Output buses serve as pathways connecting external devices to the
CPU. Examples of I/O buses include SATA, USB, and PCI-Express. For example,
PCI-Express is commonly used to communicate with devices such as graphics
cards and network cards. Communication with such external devices can be
achieved using Direct Memory Access (DMA) or Programmed Input-Output (PIO).
DMA enables devices to transfer data directly to or from memory without
involving the CPU, while PIO requires the CPU to issue commands and wait for
data. DMA is more efficient and faster than PIO but necessitates additional
hardware support.

#####  H.2.5. Modeling of Computation

We model clients’ compute capability by assuming that they have a computation
device similar to Intel-Xeon-E5-2666-v3 CPU 666Intel Xeon Processor E5-2660 v3
Specification. We assume that the computation device of the client and the
master is represented by a CPU with $10$ CPU cores, working at frequency
$3.2\,GHz$, CPU support hyper-threading with executing $2$ computation works
per core, we assume that Multiply - Add (MAD) operation is possible which
effectively doubles compute throughput. There are $2$ functional units (FU) or
compute ports per core for Floating Point arithmetic in such a device. We
assume that add, subtract, and multiply operations for float numbers require a