# Privacy-Preserving Aggregation for Decentralized Learning with Byzantine-
Robustness

Ali Reza Ghavamipour, Benjamin Zi Hao Zhao, Oğuzhan Ersoy, Fatih Turkmen

###### Abstract

Decentralized machine learning (DL) has been receiving an increasing interest
recently due to the elimination of a single point of failure, present in
Federated learning setting. Yet, it is threatened by the looming threat of
Byzantine clients who intentionally disrupt the learning process by
broadcasting arbitrary model updates to other clients, seeking to degrade the
performance of the global model. In response, robust aggregation schemes have
emerged as promising solutions to defend against such Byzantine clients,
thereby enhancing the robustness of Decentralized Learning. Defenses against
Byzantine adversaries, however, typically require access to the updates of
other clients, a counterproductive privacy trade-off that in turn increases
the risk of inference attacks on those same model updates.

In this paper, we introduce SecureDL, a novel DL protocol designed to enhance
the security and privacy of DL against Byzantine threats. SecureDL facilitates
a collaborative defense, while protecting the privacy of clients’ model
updates through secure multiparty computation. The protocol employs efficient
computation of cosine similarity and normalization of updates to robustly
detect and exclude model updates detrimental to model convergence. By using
MNIST, Fashion-MNIST, SVHN and CIFAR-10 datasets, we evaluated SecureDL
against various Byzantine attacks and compared its effectiveness with four
existing defense mechanisms. Our experiments show that SecureDL is effective
even in the case of attacks by the malicious majority (e.g., 80% Byzantine
clients) while preserving high training accuracy.

##  1 Introduction

The traditional approach to training a machine learning model has been the
aggregation of training dataset to a central server and performing the
training locally on this server. However centralization is challenging when
the data is geographically dispersed across fleets of devices or workers,
which is further coupled with the increasing concerns around data privacy. In
response, researchers have proposed alternatives to centralized learning as a
means to train machine learning models locally (i.e., data locality) while
preserving privacy [34].

Collaborative machine learning is a paradigm shift enabling diverse entities
to collaboratively train models with improved accuracy and robustness, while
maintaining privacy of collaborators. This approach is particularly beneficial
when data centralization is impractical due to privacy, bandwidth, or
regulatory constraints. Arguably, the most well-known approach of
collaborative machine learning is Federated Learning (FL) [37]. FL features a
central server which aggregates the individual model updates obtained from
collaborators who train their models locally using their own private dataset.
However, FL places an inherent trust in the central server, a potential single
point of failure [34, 8, 19], that may result with the overlooking of
potential issues related to security and computational efficiency.

Decentralized Learning (DL) is another approach that has gained popularity as
a scalable and communication-efficient alternative to existing collaborative
learning paradigms. Compared to FL schemes [34], DL eliminates the need for
having a central aggregator which in turn enhances client’s privacy and
prevents issues related to single point of failure [11, 49, 26]. We illustrate
the structural differences between FL and DL in Figure 1. Specifically, DL
implements the global model training by aggregating the model parameters on-
device with peer-to-peer message exchanges between clients (similar to gossip-
based algorithms over random networks [25]), instead of centralized
aggregation. In DL, every client actively updates its own model by using local
data and updates received from its neighbors that results with optimized
learning in terms of model accuracy and convergence speed.

Figure 1: Collaborative learning system in a Federated (left) and
decentralized fashion.

Given all these benefits, DL systems are particularly more susceptible to
privacy attacks, both under passive and active security models, with distinct
privacy challenges compared to those encountered in FL [41]. More
specifically, the architecture of DL broadens the attack surface, allowing any
client within the system to perform privacy attacks, or result with more data
leakages.

In both FL and DL, the collaborative nature of these systems exposes them to
significant risks from Byzantine adversaries. These adversaries can exploit
the system by compromising genuine clients, thereby submitting updates that
can undermine the model’s integrity. Specifically, they can launch poisoning
attacks in the form of data poisoning—tainting the local training data [6]—or
model poisoning [17, 5]—altering the updates sent to the central model. Such
manipulations can drastically affect the global model’s accuracy, leading to
large number of incorrect predictions. This vulnerability highlights the
pressing need for enhanced security protocols to protect the collaborative
learning process from these adversarial threats.

Table 1: Comparison of SecureDL with the existing robust aggregation schemes
and their main defense mechanisms. Abbreviations: EucD: Euclidean distance,
PerC: Performance Check, CosS: Cosine Similarity, Coord: Coordinate-wise
operations, Norm: Normalization.

Rules | Main defense mechanisms |  # Byzantine tolerance |  Privacy
---|---|---|---
EucD | PerC | CosS | Coord | Norm
DKrum | ✓ |  |  |  |  |  | $B<{n}/{2}$
---
No
BRIDGE |  |  |  | ✓ |  |  | $B<{n}/{2}$
---
No
MOZI | ✓ | ✓ |  |  |  | $B\leq n-1$ | No
DMedian |  |  |  | ✓ |  |  | $B<{n}/{2}$
---
No
SecureDL |  |  | ✓ |  | ✓ | $B\leq n-1$ | Yes

Numerous techniques have been developed to prevent such poisoning attacks
(mainly for FL) including coordinate-wise median [56], geometric median [10],
trimmed-mean [52], and Krum [7] as part of the defenses against both passive
and active attackers, that are also applicable to the decentralized learning
context [16, 55, 43, 24]. Despite the progress, a limitation of these methods
is their reliance on clients receiving model updates directly from their
collaborators, and thus observing the models of (or be observed by) other
clients which may compromise privacy if certain security measures are not in
place. This consequently breaches a core tenant of DL[41] that aims to provide
privacy protection for each collaborator’s model without the need of an
aggregator.

In this paper, we present SecureDL, a privacy-preserving protocol to train
machine learning models in a decentralized manner. To the best of our
knowledge, SecureDL is the first such protocol that is also resilient to
Byzantine attacks. By employing a robust defense mechanism against Byzantine
clients based on Cosine-similarity and normalization that are coupled with a
secret sharing mechanism, SecureDL allows clients to collaboratively identify
malicious updates while maintaining the privacy of each clients’ model
updates.

The core of SecureDL is the Byzantine-resilient aggregation mechanism, where
each received update is scrutinised prior to aggregation, specifically, with
careful characterization of the update direction. Additionally, SecureDL
ensures the coherence of updates from each client by calibrating their
magnitude, aligning them within the same norm. To achieve these
functionalities, we use a mix of secure comparison, inversion, square rooting
and normalization operations in addition to the basic addition and
multiplication over secret shared data.

Our proposed protocol guarantees that each client only accesses the aggregated
value of the received model updates, significantly mitigating the privacy
attack surface in DL even when majority of the clients are dishonest.

Thus, the main contributions of the paper are as follows:

  * •

We introduce SecureDL, a novel privacy-preserving and Byzantine-resilient
decentralized learning method that utilizes secure multiparty computation.

  * •

We provide theoretical analysis regarding privacy guarantees offered by
SecureDL and the impact of the changes we made on the model convergence of the
overall training process.

  * •

We empirically compare the resilience of SecureDL against a suite of state-of-
the-art Byzantine attacks with the existing defenses over MNIST, Fashion-
MNIST, SVHN and CIFAR-10 datasets.

  * •

We perform a thorough empirical analysis to assess overheads imposed by our
secure aggregation protocol, to clearly characterize the cost of privacy
protection on system performance in terms of computational time and network
communications.

Additionally, we release the source code111The source code will be publicly
available upon acceptance. of SecureDL framework to stimulate further research
in privacy-preserving and Byzantine-resilient decentralized learning.

##  2 Related work

Several strategies have been developed to combat Byzantine attacks in
Federated training environments where a central server manages the training
[7, 10, 21, 53]. These Byzantine-resistant optimization algorithms utilize
robust aggregation rules to amalgamate model updates from all clients, thereby
safeguarding the training against disruptions caused by malicious actors. Some
methods, highlighted in [44] and [13], focus on distance-based techniques.
Another method involves coordinate-wise defenses, which scrutinize updates at
the client coordinate level to identify anomalies. However, these can also be
vulnerable to more subtle attacks [3]. Other strategies, referenced in [48, 9,
54], adopt performance-based criteria.

Distance-based methods [56] aim to exclude updates that significantly deviate
from the benign clients’ average, whereas coordinate-wise defenses look for
irregularities in each coordinate of the updates. Despite their effectiveness,
these strategies face challenges from sophisticated attacks, as described in
[3], where Byzantine clients craft updates that are malicious yet appear
similar in distance to benign gradients. In contrast, performance-based
filtering, which is employed to assess each client’s model updates, often
leads to more favorable results. However, it’s important to note that these
approaches rely on an auxiliary dataset located at the server [9].

"While significant advancements have been made in creating Byzantine-robust
training algorithms for federated learning (FL), exploration of Byzantine
resilience in DL has been less extensive. However, strides have been made to
enhance Byzantine resilience within DL, with proposals such as ByRDiE [55] and
BRIDGE [16], both of which adapt the Trimmed-median approach from FL to DL.
ByRDiE leverages the coordinate descent optimization algorithm, while BRIDGE
implements Stochastic Gradient Descent (SGD) for learning. However, [23]
states that both approaches, ByRDiE and BRIDGE, remain susceptible to
sophisticated Byzantine attacks."

In response to these vulnerabilities, Mozi [22] was developed as a Byzantine-
resilient algorithm for decentralized learning. It employs a two-stage process
to improve convergence, combining Euclidean distance-based selection with
performance validation using training samples. Subsequently, UBAR [23] merges
performance-based and distance-based strategies to counter Byzantine clients,
with each client relying on its local dataset. This combination enables UBAR
to effectively address the Byzantine attacks described in [21]. Further in
this field, Basil [14] emerged as a fast, computationally efficient Byzantine-
robust algorithm. It is distinguished by its sequential processing, memory
assistance, and performance-based criteria. Designed for operation within a
logical ring architecture, Basil effectively filters out Byzantine users,
demonstrating robustness and operational efficiency. While performance-based
algorithms like UBAR and Basil have achieved greater success compared to
distance-based ones, they also introduce significant privacy risks due to
their direct access to model updates.

In our study, we have implemented the Median, Krum methods, termed ‘DMedian’
and ‘DKrum’, Mozi and BRIDGE specifically for comparison with our proposed
protocol. This choice allows us to evaluate the effectiveness of these methods
against Byzantine clients within decentralized learning environments. Here, we
discuss them in more details.

BRIDGE:  The implementation of Trimmed-Mean in BRIDGE involves excluding
extreme values from the received model updates, allowing the remaining local
model updates to contribute to the final average. Additionally, the network
should be structured to withstand up to $b$ Byzantine clients. Using a trim
parameter $k<\frac{n}{2}$, the server discards the highest and lowest $k$
values, then computes the mean of the remaining $n-2k$ values for the global
model update. To be effective against malicious clients, $k$ must be at least
equal to their number, allowing Trim-mean to manage up to nearly $50\%$
malicious clients.

Mozi:  This protocol uses a distance-based metric to filter estimates based on
Euclidean distance, effectively narrowing down the pool of model updates to
those contributors who are most likely benign, thereby enhancing the
reliability of the collective input. This is followed by a performance-based
stage, where the protocol evaluates the loss of these estimates, refining the
aggregation to include only those with superior performance.

Krum:  In this approach, each client $i$ is assigned a score $s_{i}$,
calculated by summing the squared Euclidean distances between its update
$\boldsymbol{w}_{i}$ and the updates from other clients. The scoring formula
is
$s_{i}=\sum_{\boldsymbol{w}_{j}}\left\|\boldsymbol{w}_{j}-\boldsymbol{w}_{i}\right\|_{2}^{2}$,
where $\boldsymbol{w}_{j}$ are the updates from a selected set of $n-f-2$
clients. Here, $n$ represents the total number of clients in the network, and
$f$ is the number of Byzantine clients, which are potentially malicious
clients. This selection of $n-f-2$ clients is crucial, as it involves choosing
the updates that are closest to $\boldsymbol{w}_{i}$ in Euclidean distance,
effectively filtering out potential outliers or malicious updates. Krum then
selects the client with the lowest score to provide the global model update,
ensuring the model’s resilience against adversarial actions in a scenario with
up to $f$ malicious clients.

Median:  The Median aggregation technique, as described in [56], chooses the
median value of parameters as the consolidated global model, treating each
parameter independently. For every $j$-th model parameter, the server ranks
the corresponding parameters from $m$ local models, where $m$ is the number of
participating models. The $j$-th parameter of the global model is then
determined by the median of these ranked values:

$\text{Global }w_{j}=\text{Median}(w_{1j},w_{2j},\ldots,w_{mj}).$

The median method can tolerate up to $\frac{n}{2}-1$ Byzantine clients, where
$n$ is the total number of clients in the network. This resilience stems from
the fact that as long as the majority of the values are from honest clients,
the median will be derived from these honest values, ensuring the integrity of
the global model despite the presence of the Byzantine clients.

##  3 Preliminaries

In this section, we provide the necessary background on decentralized learning
and introduce the secure building blocks used in this paper.

###  3.1 Learning in a Decentralized Setting

In decentralized learning system, each client ($c$) from the group $C$
directly communicates with a selected group known as their neighbors
$\mathbf{N}(c)$. These connections can be either static, formed at the
beginning, or dynamic, changing over time. The network of clients forms an
undirected graph $G=\left\\{C,\cup_{c\in C}\mathbf{N}(c)\right\\}$, where the
vertices represent clients and the edges indicate the connections between
them[34].

In a formal setting, client $c$ in the set $C$ owns a private dataset
$D_{i}=\left\\{\left(x_{i},y_{i}\right)\right\\}_{i}$ drawn from a hidden
distribution $\xi_{i}$ and combining the private datasets would produce the
global dataset $D$ with distribution $\xi$. Each client begins with a shared
set of model parameters denoted as $w^{0}$.

The aim of the training process is to identify the optimal parameters, denoted
as $\mathbf{w}^{*}$, for a machine learning model. These parameters are sought
to minimize the expected loss across the entire global dataset $D$:

$\mathbf{w}^{*}=\underset{\theta}{\arg\min}\frac{1}{|\mathbf{N}(c)|}\sum_{n_{i}\in\mathbf{N}(c)}\underbrace{\mathbb{E}_{s_{i}\sim
D_{i}}\left[\mathcal{L}\left(\theta;s_{i}\right)\right]}_{\mathcal{L}_{i}}$
(1)

where for each client $n_{i}$ in the network, $\mathbb{E}_{s_{i}\sim
D_{i}}\left[\mathcal{L}\left(\theta;s_{i}\right)\right]$ calculates the
expected loss for that client’s dataset $D_{i}$, where $s_{i}$ is a sample
from $D_{i}$. Thus, the formula aims to find the model parameters $\theta$
that minimize the average expected loss across all clients in the network.

1

2

Input : Initial model parameters $w_{c}^{0}$ for $c\in C$

Local training data of the client $c$: $X_{c}$ for $c\in C$

3 for  _$t\in[0,1,\ldots]$_ do

4 Local optimization step:

5 for  _$c\in C$_ do

6 Sample $x_{c}^{t}$ from $X_{c}$

7 Update parameters:
$w_{c}^{t+\frac{1}{2}}=w_{c}^{t}-\eta\nabla_{w_{c}^{t}}(x_{c}^{t},w_{c}^{t})$

8

9 Communication with neighbors:

10 for  _$c\in C$_ do

11 for  _$u\in\mathbf{N}(c)\setminus\\{c\\}$_ do

12 Send $w_{c}^{t+\frac{1}{2}}$ to $u$

13 Receive $w_{c}^{t+\frac{1}{2}}$ from $u$

14

15

16 Model updates aggregation:

17 for  _$c\in C$_ do

18
$w_{c}^{t+1}=\frac{1}{|\mathbf{N}(c)|}\sum_{c\in\mathbf{N}(c)}w_{c}^{t+\frac{1}{2}}$

19

20

Algorithm 1 Decentralized Learning Protocol

This process continues through several stages until reaching a predetermined
stopping point. The stages are as follows:

  1. 1.

At step $t$, each client $c$ carries out gradient descent on their model
parameters, leading to an interim model update, symbolized as $w_{c}^{t+1/2}$.

  2. 2.

Then, the clients exchange their interim model updates $w_{c}^{t+1/2}$ with
their neighbors $\mathbf{N}(c)$. Concurrently, they also acquire the updates
from these neighbors.

  3. 3.

Finally, the clients merge the updates received from their neighbors with
their own, and use this combined update to modify their local state. A basic
approach to aggregation involves averaging all the updates received.
Mathematically, this is represented as
$w^{t+1}=\frac{1}{\left|\mathbf{N}(c)\right|}\sum_{c\in\mathbf{N}(c)}w_{c}^{t+1/2}$.

Algorithm 1 presents the complete DL training procedure.

###  3.2 Secret Sharing

The principle of secret sharing involves methods for distributing a secret
value, denoted as $x$, among $n$ entities, resulting in shares
$x_{1},\ldots,x_{n}$. Each participant $P_{i}$ receives a uniformly random
share $x_{i}$ (under modulo $p$) of the concealed value over a specific $p$.
To reconstruct the original secret $x$ from its distributed shares, the
parties collaboratively pool their shares $x_{1},\ldots,x_{n}$ and apply a
reconstruction process, involving summing the shares modulo $p$
($x=(x_{1}+x_{2}+\cdots+x_{n})\mod p$), thereby retrieving $x$.

Building upon this foundational concept, our work develops protocols centered
on n-out-of-n additive secret sharing. We also conduct secure computations on
additive shares modulo $2^{k}$ within a larger ring modulo $2^{k+s}$, where
$\sigma=s-\log(s)$ is the statistical security parameter. In cases without
ambiguity, we use $[\\![x]\\!]$ to represent $[\\![x]\\!]_{2^{k}}$,
specifically in this work where we choose $k=32$.

####  3.2.1 Performing Addition and Multiplication on Shares

Various protocols have been developed to perform operations on shared secrets
values. This study focuses on addition and multiplication as key functions.
Our notational conventions align with those detailed in [46].

Secretly shared values $[\\![x]\\!]$ and $[\\![y]\\!]$ can be directly added
as
$[\\![x]\\!]+[\\![y]\\!]=([\\![x]\\!]_{1}+[\\![y]\\!]_{1},\ldots,[\\![x]\\!]_{n}+[\\![y]\\!]_{n})$.
However, multiplying secret shared values requires network interaction and
distinct methodologies for each security environment.

In a dishonest majority setting, the Beaver triples technique [4] is used for
multiplication operations. This method involves pre-distributing shares
($[\\![a]\\!]$, $[\\![b]\\!]$, $[\\![c]\\!]$) of a multiplication triple
$(a,b,c)$, where $a$ and $b$ are generated uniformly randomly, and $c=a\cdot
b$. Once the shares of the inputs and the triple are received, each
computation party computes $[\\![\delta]\\!]$ = $[\\![x]\\!]$ \- $[\\![a]\\!]$
and $[\\![\epsilon]\\!]$ = $[\\![y]\\!]$ \- $[\\![b]\\!]$ locally and then
reveals $[\\![\delta]\\!]$ and $[\\![\epsilon]\\!]$ to other parties. The
parties can reconstruct $\delta$ and $\epsilon$ using these shares. Since $a$
and $b$ are generated uniformly random, revealing the shares of $\delta$ and
$\epsilon$ does not compromise the security of the protocol. Each party then
locally computes:

$[\\![w]\\!]_{i}=[\\![c]\\!]_{i}+\epsilon\cdot[\\![b]\\!]_{i}+\delta\cdot[\\![a]\\!]_{i}+\epsilon\cdot\delta$

where $[\\![w]\\!]_{i}$ is a share of the multiplication result calculated by
computation party i.

####  3.2.2 Secure Comparison Protocol

In the context of secret sharing, a secure comparison protocol enables the
comparison of additive shares without revealing the underlying private values.
It determines if one value is greater, lesser, or equal to another, producing
a binary result that preserves the confidentiality of the inputs. This
protocol is crucial for privacy-sensitive applications, ensuring that only the
outcome of the comparison is disclosed, thereby maintaining the integrity and
secrecy of each party’s input.

In this work, we have implemented the secure comparison protocol as described
by Makri et al. [36]. Their protocol ensures perfect security over the
arithmetic ring $\mathbb{Z}_{M}$ for positive integers in the range
$\left[0,2^{l}-1\right]$, where $l\in\mathbb{N}$ and $2^{l+1}<M=2^{k}$. The
protocol’s adaptability to different arithmetic models and its effectiveness
in settings with a dishonest majority are its key strengths.

The basic idea of the protocol is that the sum of two secret shared values
$a,b\in\mathbb{Z}_{M}$ modulo $M$ is less than $a$ and less than (LT) $b$, iff
$a+b$ is reduced by $M$ :

$\displaystyle(a+b)\bmod M$ $\displaystyle=a+b-M\cdot\mathrm{LT}(a+b\bmod
M,a)$ $\displaystyle=a+b-M\cdot\mathrm{LT}(a+b\bmod M,b)$

The protocol’s online phase involves minimal rounds and arithmetic operations,
while the offline phase requires additional resources such as edaBits [15].

####  3.2.3 Inversion Operation

Our multi-party computation framework does not support inversion operations
natively; therefore, we adopt an iterative approximation approach, akin to the
method proposed by Nardi [39]. This strategy enables us to facilitate
inversion using basic operations such as addition and multiplication,
effectively circumventing the need for direct inversion over secret share
inputs.

The core concept revolves around identifying a value $B$ that serves as the
inverse of a specific value $X$. To achieve this, we define a function $f(x)$
aimed at determining $B$ by setting $f(x)=0$ when $x=B$, essentially making
$B$ the solution that satisfies the inverse relationship for $X$. The function
is formulated as follows:

$f(x)=X^{-1}-B$

For determining the root of $f(x)$, the Newton-Raphson method [1] is
suggested. This results in a stable numerical iterative approximation
represented as:

$\displaystyle B_{s+1}=2B_{s}-B_{s}M_{s}\quad B_{0}=c^{-1}$ $\displaystyle
M_{s+1}=2M_{s}-M_{s}^{2}\quad M_{0}=c^{-1}X$

where $c$ is a constant, and $M_{s}=B_{s}\times A$, with $B_{s}$ converging to
the approximate inverse of $X$ after about 15 iterations [18].

####  3.2.4 Square Root Computation

In our protocol, computing square roots is essential but not directly feasible
in our implemented multi-party computation framework due to the lack of native
support. We overcome this by employing an approximation technique rooted in
the Newton-Raphson method, enabling square root calculation through just
multiplication and addition [45].

The Newton-Raphson method refines an initial approximation of a square root
through an iterative process involving a function and its derivative. For
computing the square root of a number $Y$, the method utilizes the function
$f(x)=x^{2}-Y$, aiming to identify an $x$ that satisfies $f(x)=0$. The method
updates the approximation iteratively as follows:

$\displaystyle B_{s+1}=2B_{s}-B_{s}M_{s}\quad B_{0}=c^{-1}$ $\displaystyle
M_{s+1}=2M_{s}-M_{s}^{2}\quad M_{0}=c^{-1}X$

where $x_{n}$ is the current guess and $x_{n+1}$ is the updated guess.
Starting from an initial guess $x_{0}$, the method iteratively applies this
update. The quotient $\frac{Y}{x_{n}}$ offers an increasingly accurate
approximation of the square root of $Y$ when averaged with $x_{n}$. After a
sufficient number of iterations (15 iterations in our implementation), $x_{n}$
converges to the square root of $Y$.

####  3.2.5 Preprocessing

Our protocol is designed to be compatible with Message Authentication Codes
(MACs) and Beaver triples generation, following approaches similar to those in
[29]. Our implementation necessitates multiplication triples over
$\mathbb{Z}_{2^{k}}$, where $k$ is a parameter of the protocol. For the secure
comparison protocol, when $k=1$, our protocol incorporates an optimized
variant of the two-party TinyOT protocol [50]. For larger choices of $k$ (
$k=32$ in this work), we base our costs on the MASCOT protocol [30], noting
that despite MASCOT’s communication complexity being in $O(k^{2})$, it still
offers the lowest costs for all the table sizes we have considered,
particularly with $k=32$.

In our analysis, we concentrate primarily on the dynamics of the online phase
of the protocol. We omit the details of the offline phase, encompassing the
generation and distribution of MACs and Beaver triples, which can be found in
[12].

##  4 Threat model

We assume that two distinct entities are involved in the training: semi-honest
and malicious parties:

Semi-honest clients:  Semi-honest clients are fundamentally non-malicious, but
exhibit an elevated level of curiosity (also known as Honest-but-Curious
clients). These clients strictly follow the established protocols of the
system but try to infer additional information about other clients from the
exchanged messages. This behavior, while not explicitly harmful, raises
genuine concerns regarding data privacy and confidentiality within the system
[41].

Byzantine clients:  The second type of entities are Byzantine clients who are
defined by their inherent malevolence. Unlike semi-honest clients, Byzantines
display no commitment to the established protocols and are known for their
unpredictable malicious actions. Their objective is to disrupt the learning
process or introduce biases into the model that is being trained. They may do
this by transmitting arbitrary, misleading, or false information to other
clients. Furthermore, multiple Byzantine clients may collude to maximize the
efficacy of either poisoning or inference attacks.

###  4.1 Problem Statement

In all collaborative learning environments, an honest client is not interested
in acquiring a specific model from another client. Rather, its objective is to
obtain an aggregated model update derived from a combination of multiple local
client datasets. Having access only to the aggregated model update offers two
crucial privacy benefits. Firstly, it prevents malicious attempts targeting
client models by masking details specific to individual local models,
effectively hindering adversaries from identifying and exploiting precise data
sources. Secondly, it diminishes the impact of any single client’s input by
combining contributions from multiple clients within the aggregated model.
This reduction in the prominence of individual contributions serves to obscure
their visibility, thus decreasing the likelihood of attacks that target unique
datasets.

In FL, a central server aggregates the model updates received from the
clients, relaying only the aggregated outcome to those clients. Thus, the
server is the only entity with access to each model’s (non-aggregated)
updates. Conversely, in DL, with a shift to a completely decentralized
training, the elimination of the central server increases the attack surface.
This increase is due to the need to distribute updates across neighboring
clients for on-client aggregation, contrasting sharply with FL. Therefore, in
DL, each client, with access to collaborator updates can potentially perform
privacy attacks against their collaborators such as inference attacks [41].

Moreover, the susceptibility of collaborative learning systems to Byzantine
client disruptions is a significant concern. In these systems, a single
Byzantine client has the potential to derail the entire learning process by
manipulating or corrupting shared models across the network [7, 47]. In FL
settings, various research studies have been conducted to enable the server to
detect and mitigate Byzantine threats. However, in DL, the absence of
centralized control within decentralized architectures presents unique
challenges. In a decentralized setting, each client in the network must
independently address these challenges, which complicates the detection and
mitigation of malicious activities.

In this study, our objective is to develop a DL method that maintains
Byzantine robustness against malicious clients without compromising accuracy
or efficiency. The Byzantine robustness of our protocol is achieved through a
privacy-preserving aggregation rule. This rule prevents clients from accessing
other clients’ data in plain form; instead, only aggregated values are
revealed to them.

##  5 SecureDL

This section presents a detailed explanation of the secure aggregation rule
within SecureDL. The approach we take for aggregation is illustrated in Figure
2.

Given the existence of Byzantine clients within the network, it becomes
essential to acknowledge the capability of compromised clients to prevent the
convergence of the global model. In light of this, our proposed aggregation
rule underlines the significance of evaluating both the magnitude and the
directional alignment of local model updates concerning the global model of
each client.

Byzantine clients manipulate model update directions, steering the global
model away from its intended trajectory. This strategic deviation impedes the
model’s convergence. The resulting angular disparity between the model updates
from these malicious clients and the global model of the receivers of those
updates exceeds that of benign clients. In SecureDL, the direction of received
model updates is evaluated against the global model of the receiving client
using the cosine similarity metric. This metric is widely recognized for its
ability to compute the angular difference between two vectors. The cosine
similarity between these two vectors $\mathbf{w}_{a}$ and $\mathbf{w}_{b}$ is
expressed as:

$Cosine(\mathbf{w}_{a},\mathbf{w}_{b})=\frac{\mathbf{w}_{a}\cdot\mathbf{w}_{b}}{\|\mathbf{w}_{a}\|\|\mathbf{w}_{b}\|}.$

In our protocol, we tackle the challenge of computing cosine similarity in a
decentralized learning environment while preserving the privacy of the input
vectors. Here, direct access to complete model updates is restricted, and
clients should only have access to the aggregated model updates, necessitating
an innovative approach for accurate similarity measurement. Our solution
leverages collaborative client efforts to execute secure vectorized
operations, alongside specialized computations for square roots and
inversions, to calculate cosine similarities between additive secret-shared
model update vectors $[\\![\mathbf{w}_{a}]\\!]$ and
$[\\![\mathbf{w}_{b}]\\!]$.

The computation of cosine similarity within our secure framework involves
several complex operations, as detailed in Algorithm 2. Initially, we utilize
the Beaver multiplication protocol for securely computing the dot product
between two model updates. This crucial step allows for the multiplication of
values without directly revealing them to any party. For the calculation of
each model update’s norm, we square each vector’s elements, sum these squares,
and compute the square root of this sum, a process elaborated in Section 3.2.4
for square root computation. Following this, leveraging the inversion function
introduced in Section 3.2.3, we compute the inversion of the product of these
norms. This sequence of operations—dot product computation, norm calculation,
and inversion—ensures the accurate and secure calculation of cosine
similarity, adhering to the privacy and security requirements outlined in our
protocol.

Figure 2: The illustration of SecureDL aggregation rule. The model update of
$Client_{0}$, denoted as $w_{0}$, obtains the updates from other clients
($w_{1}$, $w_{2}$, and $w_{3}$). In image A, the protocol discards any model
update with a negative cosine value. Image B depicts $Client_{0}$ normalizing
the received models based on its own model’s magnitude. ImageC shows the final
accepted model update after normalization.

1

2

Input : Two secret-shared vectors $[\\![\mathbf{w}_{a}]\\!]$ and
$[\\![\mathbf{w}_{b}]\\!]$.

Output : The cosine similarity $[\\![\text{cosine}]\\!]$ between the vectors
$[\\![\mathbf{w}_{a}]\\!]$ and $[\\![\mathbf{w}_{b}]\\!]$.

3

$[\\![\text{dotProduct}]\\!]\leftarrow[\\![\mathbf{w}_{a}]\\!]\odot[\\![\mathbf{w}_{b}]\\!]$

// Vector dot product

4

// Compute the norm of vector $\mathbf{w}_{a}$ using vectorized operations

5
$[\\![\mathbf{w}_{a}^{2}]\\!]\leftarrow[\\![\mathbf{w}_{a}]\\!]\times[\\![\mathbf{w}_{a}]\\!]$

6 $[\\![\text{sum}_{a}]\\!]\leftarrow\sum_{i=1}^{n}[\\![w_{ai}^{2}]\\!]$

7
$[\\![\text{norm}_{a}]\\!]\leftarrow\text{ComputeSquareRoot}([\\![\text{sum}_{a}]\\!])$

8

// Compute the norm of vector $\mathbf{w}_{b}$ using vectorized operations

9
$[\\![\mathbf{w}_{b}^{2}]\\!]\leftarrow[\\![\mathbf{w}_{b}]\\!]\times[\\![\mathbf{w}_{b}]\\!]$

10 $[\\![\text{sum}_{b}]\\!]\leftarrow\sum_{i=1}^{n}[\\![w_{bi}^{2}]\\!]$

11
$[\\![\text{norm}_{b}]\\!]\leftarrow\text{ComputeSquareRoot}([\\![\text{sum}_{b}]\\!])$

12

$[\\![\text{denom}]\\!]\leftarrow\text{ComputeInverse}([\\![\text{norm}_{a}]\\!]\times[\\![\text{norm}_{b}]\\!])$

// Element-wise multiplication for norms and then inversion

13
$[\\![\text{cosine}]\\!]\leftarrow[\\![\text{dotProduct}]\\!]\times[\\![\text{denom}]\\!]$

14

return _$[\\![\text{cosine}]\\!]$_

Algorithm 2 Cosine Similarity Computation

This streamlined computation facilitates the efficient isolation of model
updates that fall below a certain similarity threshold, thereby enhancing the
robustness of the decentralized learning process. It is important to highlight
that the results of the cosine similarity computation remain in a secret-
shared form. This necessitates a method for comparing these results with a
threshold without reconstructing the secret-shared value. To address this, we
employ a secure comparison protocol, as described in Section 3.2.2, which
securely enables the decision to accept or discard a model update. This
protocol allows for the comparison of secret-shared cosine similarity scores
against a predefined threshold in a manner that upholds the privacy and
integrity of the data. Our method not only meets the secure framework’s
privacy requirements but also facilitates a more effective evaluation of model
update contributions, ensuring the inclusion of only those that are closely
aligned with the overall model direction, without having direct access to the
model updates.

Moreover, Byzantine adversaries have the ability to significantly magnify the
magnitudes of local model updates in compromised clients, thereby exerting a
substantial impact on the receiver’s global model update. To mitigate this,
our approach involves the normalization of each received model update,
aligning it with the magnitude of the receiver’s model update. This process
involves adjusting the scale of received model updates to ensure their
magnitudes match with that of the receiver client’s model update within the
vector space. To achieve this normalization effectively, we employ
L2-normalization techniques.

The L2-normalization of model update $\mathbf{w}_{a}$ with respect to receiver
$\mathbf{w}_{b}$ can be mathematically expressed as:

$Norm(\mathbf{w}_{a},\mathbf{w}_{b})=\mathbf{w}_{a}\times\frac{\lVert\mathbf{w}_{b}\rVert_{2}}{\lVert\mathbf{w}_{a}\rVert_{2}}$

where $\lVert\mathbf{w}_{b}\rVert_{2}$ and $\lVert\mathbf{w}_{a}\rVert_{2}$
represent the L2 norms (or Euclidean norms) of the model update vectors
$\mathbf{w}_{b}$ and $\mathbf{w}_{a}$, respectively. This normalization method
balances the effect of each local model update on the overall global model. It
lessens the influence of larger updates and increases the impact of smaller
ones. By giving more weight to these smaller updates, we can reduce the effect
of harmful updates, leading to a stronger global model.

In our secure computation framework, we achieve privacy-preserving L2
normalization using accurate approximations. In the first step, as outlined in
the Algorithm 3, clients jointly and securely calculate the norms of the
reference model update and received model update vectors. This process begins
with squaring each vector component, summing these squares, and then securely
computing the square root to obtain the vectors’ magnitudes in Euclidean
space. The procedure emphasizes the collaborative effort and complexity
inherent in our framework, highlighting the advanced protocols employed to
ensure privacy.

To normalize one vector relative to another, we use the inversion protocol to
compute the inverse of one vector’s norm. This step is crucial for adjusting
the magnitude of the received model update to match that of the receiver
clients, maintaining consistency with the client’s global model without
revealing private information. The final normalization step involves scaling
the original vector by a computed ratio, ensuring the resulting vector
maintains its direction. At the same time, its magnitude is adjusted relative
to the reference vector.

1

Input : Secret-shared vectors $[\\![\mathbf{w}_{a}]\\!]$ and
$[\\![\mathbf{w}_{b}]\\!]$.

Output : L2-normalized vector $[\\![\mathbf{w}_{a}^{\prime}]\\!]$ relative to
$[\\![\mathbf{w}_{b}]\\!]$.

2

// Vector norm computation

3
$[\\![\mathbf{w}_{a}^{2}]\\!]\leftarrow[\\![\mathbf{w}_{a}]\\!]\times[\\![\mathbf{w}_{a}]\\!]$

4 $[\\![\text{sum}_{a}]\\!]\leftarrow\sum_{i=1}^{n}[\\![w_{ai}^{2}]\\!]$

5
$[\\![\lVert\mathbf{w}_{a}\rVert_{2}]\\!]\leftarrow\text{ComputeSquareRoot}([\\![\text{sum}_{a}]\\!])$

6

// Vector norm computation

7
$[\\![\mathbf{w}_{b}^{2}]\\!]\leftarrow[\\![\mathbf{w}_{b}]\\!]\times[\\![\mathbf{w}_{b}]\\!]$

8 $[\\![\text{sum}_{b}]\\!]\leftarrow\sum_{i=1}^{n}[\\![w_{bi}^{2}]\\!]$

9
$[\\![\lVert\mathbf{w}_{b}\rVert_{2}]\\!]\leftarrow\text{ComputeSquareRoot}([\\![\text{sum}_{b}]\\!])$

10

11$[\\![\lVert\mathbf{w}_{a}\rVert_{2}^{-1}]\\!]$ $\leftarrow$
ComputeInverse($[\\![\lVert\mathbf{w}_{a}\rVert_{2}]\\!]$)

12

// Compute the ratio for normalization

13 $[\\![r]\\!]$ $\leftarrow$ $[\\![\lVert\mathbf{w}_{b}\rVert_{2}]\\!]$
$\times$ $[\\![\lVert\mathbf{w}_{a}\rVert_{2}^{-1}]\\!]$

14

// Normalize the vector $[\\![\mathbf{w}_{a}]\\!]$ by the computed ratio

15 $[\\![\mathbf{w}_{a}^{\prime}]\\!]$ $\leftarrow$ $[\\![\mathbf{w}_{a}]\\!]$
$\times$ $[\\![r]\\!]$

16

17return _$[\\![\mathbf{w}_{a}^{\prime}]\\!]$_

Algorithm 3 ComputeL2Normalization

The complete SecureDL protocol is illustrated in Algorithm 4 where the
concluding step involves computing the mean of the normalized and global model
of the receiver clients. This entire process is repetitively applied across
$R_{g}$ global iterations to finalize the training process. A local learning
rate $\beta$, and a global learning rate $\alpha$ defines the relative size of
the updates for local update computation, and global aggregation respectively.
Rejection of updates is controlled by a configurable threshold $tau$.

1

2

Input : $n$ clients $C_{0},C_{1},\dots,C_{n-1}$ with local training datasets
$D_{i}$ for $i=0,1,\dots,n-1$

Number of global iterations: $R_{g}$

Threshold: $0<\tau<1$

Output : Global model $\mathbf{w}$ trained on all clients’ datasets for each
client

3

4Initialization step:

5 All clients start from the same initial model $w^{0}$.

6 for  _$r=1,2,\dots,R_{g}$_ do

7

8 Local training step:

9 Training local models

10 for  _every client $i$ in $\\{C_{0},C_{1},\dots,C_{n-1}\\}$_ do

11 $w_{i}=\text{LocalUpdate}(w^{r},D_{i},\beta)$

12 Send model update shares $\llbracket\mathbf{w}_{i}\rrbracket$ to all
clients

13

14 Aggregation step:

15 Updating their global model via aggregating the local model updates

16 for  _every client $i$ in $\\{C_{0},C_{1},\dots,C_{n-1}\\}$_ do

17 for  _every client $j$ in $\\{C_{0},C_{1},\dots,C_{n-1}\\}$_ do

18 if  _$i\neq j$_ then

19
$\llbracket\boldsymbol{cosine}_{ij}\rrbracket\leftarrow\text{Cosine}(\llbracket\mathbf{w}_{i}\rrbracket,\llbracket\mathbf{w}_{j}\rrbracket)=\frac{\langle\llbracket\mathbf{w}_{i}\rrbracket,\llbracket\mathbf{w}_{j}\rrbracket\rangle}{\|\llbracket\mathbf{w}_{i}\rrbracket\|\cdot\|\llbracket\mathbf{w}_{j}\rrbracket\|}$

20

21 if
_$\text{SecureComparison}(\llbracket\boldsymbol{cosine_{ij}}\rrbracket,\tau)$_
then

// Returns True if $cosine_{ij}<\tau$

22 $\llbracket\overline{w_{j}}\rrbracket=0$

23

24 else

25
$\llbracket\overline{\mathbf{w}_{j}}\rrbracket=Normalization(\llbracket\mathbf{w}_{i}\rrbracket,\llbracket\mathbf{w}_{j}\rrbracket)=\frac{\|\llbracket\mathbf{w}_{j}\rrbracket\|}{\|\llbracket\mathbf{w}_{i}\rrbracket\|}\cdot\llbracket\mathbf{w}_{i}\rrbracket$

26

27

28 Model updates aggregation:

29
$\llbracket\hat{\mathbf{w}}\rrbracket=\frac{1}{n}\left(\sum\limits_{\begin{subarray}{c}j=0\\\
j\neq
i\end{subarray}}^{n-1}\llbracket\overline{\mathbf{w}_{j}}\rrbracket+\llbracket\mathbf{w}_{i}\rrbracket\right)$

30

31

Algorithm 4 SecureDL

###  5.1 Convergence

In this section, we demonstrate a proof that SecureDL converges. Specifically,
for an arbitrary number of malicious updates, the difference between the model
learnt from SecureDL filtered updates and the optimal model under no attacks
is bounded. Our proof closely follows that presented in FLtrust [9], as beyond
the secure multi-party computation, the rejection of malicious updates on
shares of updates results in the overall computation of cosine similarity with
a known ‘good update’ and each received client’s update. Collectively, the
clients find a model $w$ from a global dataset $D$ defined previously in
Equation 1, where $D=\cup^{n}_{i=1}D_{i}$ is composed of the joint training
datasets from each decentralized client on which the expected loss function
$f(D,\mathbf{w})$ is minimized. We define $\mathbf{w}^{*}$ as the optimal
model for a given data distribution $\xi$.

We present several assumptions stated in similar cosine similarity based
detection schemes [9, 38] with which SecureDL adheres to satisfy Theorem 1:

######  Assumption 1.

The expected loss function $f(D,\mathbf{w})$ is $\mu$-strongly convex and
differentiable over $\mathbb{R}^{d}$ with L-Lipschitz continuous gradient.

This entails that for $\mathbf{w},\mathbf{\widehat{w}}\in\mathbb{R}^{d}$:

$\nabla f(D,\mathbf{\hat{w}})\geq\nabla f(D,\mathbf{w})+\langle\nabla
f(D,\mathbf{w}),\mathbf{\hat{w}}-\mathbf{w}\rangle)+\frac{\mu}{2}\|\mathbf{\hat{w}}-\mathbf{w}\|^{2},$
$\|\nabla f(D,\mathbf{w})-\nabla f(D,\mathbf{\widehat{w}})\|\leq
L^{\prime}\|\mathbf{w}-\mathbf{\widehat{w}}\|,$

where $\nabla$ represents the gradient and $\|\cdot\|$ represents the L2 norm.
and $\langle\cdot,\cdot\rangle$ represents the inner product of two vectors.
Further, the empirical loss function $f(D,\mathbf{w})$ is L1-Lipschitz
probabilistic.

######  Assumption 2.

The gradient of the empirical loss function $\nabla f(D,\mathbf{w})$, with
respect to $\mathbf{w}$, is bounded. Additionally, the gradient difference for
any $\mathbf{w}\in\mathbb{R}^{d}$ is bounded.

######  Assumption 3.

Each client’s local training dataset $D_{i}:=\\{\xi_{k}\\}_{k=1}^{n}$ is
independently drawn from the distribution $\xi$.

######  Assumption 4.

Approximations in the secure comparison and secure aggregation that result in
minute variations in update values are significantly smaller than expected
noise in local dataset variation, thereby negligibly impacting learning.

######  Theorem 1.

Suppose Assumption 1-4 hold and SecureDL uses $R_{g}=1$ and $\beta=1$. For an
arbitrary number of malicious clients, the difference between the global model
learnt by SecureDL and the optimal global model $\mathbf{w^{*}}$ under no
attacks is bounded. Formally, we have the following with probability at least
$1-\delta$:

$\|\mathbf{w^{t}}-\mathbf{w^{*}}\|\leq(1-\rho)^{t}\|\mathbf{w^{0}}-\mathbf{w^{*}}\|+12\alpha\Delta_{1}/\rho,$

where $\mathbf{w^{t}}$ is the model at the $t^{th}$ iteration, $\alpha$ is the
global learning rate, and both $\rho$, $\Delta_{1}$ as constants defined in
[9].

Notably when $|1-\rho|<1$, with a large number of iterations,
$\lim_{t\rightarrow\infty}\|\mathbf{w^{t}}-\mathbf{w^{*}}\|\leq
12\alpha\Delta_{1}/\rho$, and thus bounded.

###### Proof of Theorem 1.

With the assumptions mentioned in Section 5.1 and Theorem 1, adopted for
SecureDL from [9], we can demonstrate SecureDL’s model under attack and the
optimal model is bounded. We refer the reader to [9] for the full proof of
Theorem 1 through Lemma 1, 2 and 3. We note that when considering this proof
for SecureDL’s update rejection, the aggregation criteria mirrors that of
FLtrust albeit with variation to the gradient scaling parameter $\varphi$ in
Lemma 1. Specifically, FLtrust scales each normalized gradient $\bar{g_{i}}$
by the cosine similarity $cosine_{i}$ for a given client update $i$ in set
$\mathcal{S}$, whose $cosine_{i}$ is positive, As such FLtrust’s scaling
parameter is
$\varphi_{i}=\frac{ReLu(cosine_{i})}{\sum_{j\in\mathcal{S}}ReLu(cosine_{j})}$,
where $ReLu$ is the rectified linear unit activation function. On the other
hand, in SecureDL, the gradient is not scaled by $cosine_{i}$, instead
retaining it’s normalized magnitude of 1, better represented by the binary
$step$ activation above a given threshold $\tau$, as such,
$\varphi_{i}=\frac{Step(cosine_{i},\tau)}{|\mathcal{S}|}$, where $0<\tau<1$,
thereby satisfying $0<\varphi_{i}<1$, and
$\displaystyle\sum_{j\in\mathcal{S}}\varphi=1$. With this variation on Lemma
1, SecureDL satisfies Lemma 1, 2, 3, and Theorem 1 remains valid for SecureDL,
and thus the model obtained by SecureDL shall converge. While we refer the
reader to [9] for the full proof of Theorem, we shall in the next section
empirically demonstrate SecureDL’s convergence over 3 distinct datasets. ∎

###  5.2 Privacy analysis

In this section, we show that SecureDL protocol achieves privacy-preserving
aggregation. We provide the privacy analysis using the simulation based proof
technique [20, 35]. In simulation based proof, the privacy is guaranteed by
showing that there is a polynomial-time simulator that simulates the view of
the adversary such that the adversary cannot distinguish the simulated view
from the real one. The (computational) indistinguishability ensures that the
adversary does not learn any information about the honest clients since even
the simulator does not have any private information belongs to the honest
parties. Below, we present an informal statement of this principle; the formal
analysis is given in Appendix A.

######  Theorem 2 (Privacy w.r.t Semi-Honest Behavior).

Consider an $n$-party secure multi-party computation protocol $\Pi$, designed
to compute a function $f$ over inputs
$\bar{x}:=\left(x_{1},\ldots,x_{n}\right)$ utilizing the SecureDL algorithm.
The protocol involves $n$ parties, $P_{1},P_{2},\ldots,P_{n}$, each holding an
additive share of their private inputs. The protocol $\Pi$ is said to
privately compute the function $f(\bar{x})$ in the presence of at least one
honest party and potentially colluding parties, if for every subset of honest
parties $I\subseteq[n]$, with $I=\left\\{i_{1},\ldots,i_{t}\right\\}$, there
exists a probabilistic polynomial-time simulator $S_{I}$. The output
distribution of $S_{I}$ and the actual view of the parties in $I$ during the
protocol’s execution, $\operatorname{View}_{I}^{\Pi}(\bar{x})$, are required
to be computationally indistinguishable
($\stackrel{{\scriptstyle\text{perf}}}{{\equiv}}$) across all possible inputs
$\bar{x}$, where:

$\\{S_{I}(\bar{x},f_{I}(\bar{x}))\\}_{\bar{x}}\stackrel{{\scriptstyle\text{perf}}}{{\equiv}}\\{\operatorname{View}_{I}^{\Pi}(\bar{x})\\}_{\bar{x}}.$

where $f_{I}(\bar{x})$ denotes the subsequence of function outputs relevant to
the subset $I$, specifically $f_{i_{1}}(\bar{x}),\cdots,f_{i_{t}}(\bar{x})$,
and $\operatorname{View}_{I}^{\Pi}(\bar{x})$ represents the collective view of
the subset $I$ during the execution of $\Pi$, encompassing all information
accessible to the parties in $I$.

SecureDL protocol achieves the privacy properties (under the semi-honest
model) by leveraging information theoretical security of the secret sharing
scheme in the aggregation method. It allows the construction of a simulation
that accurately mimics the adversary’s view without necessitating access to
the honest parties’ inputs. This ensures that the protocol can simulate the
adversary’s perspective in a manner that is computationally indistinguishable
from the actual computation, thereby maintaining the privacy of the inputs
against passive adversaries.

In the SecureDL protocol, we utilize several operations include
multiplication, addition, inversion, square root calculation, vector norm
computation, cosine similarity assessment, and L2 normalization. For each of
these functions, we have provided simulation-based proofs individually. The
utilization of randomness inherent in the secret sharing mechanism enables the
secure and consistent simulation of each component’s composition within the
protocol. This critical feature ensures that the output shares generated by
each function—despite being reused as inputs for subsequent operations—remain
indistinguishable to potential adversaries. Thus, the privacy and
confidentiality of data through the computation process are maintained,
effectively protecting against unauthorized disclosure and preserving the
privacy of the computational outcomes. Finally, we are able to provide a
simulator that simulates the view of an adversary (who can control up to $n-1$
clients) for the whole protocol, and prove Theorem 2.

Strengthening from semi-honest to Byzantine clients: Our implemented MPC
protocol is designed to provide security against semi-honest adversaries
within a dishonest majority setting over the ring $\mathbb{Z}_{2^{k}}$,
creating a robust framework for ensuring the privacy of computations against
passive attackers. As mentioned in Section 3.2.5, by using information-
theoretic secure and homomorphic Message Authentication Codes (MACs) given in
[12], we can prevent Byzantine adversaries to fabricate inconsistent
information about their (preprocessing) data.

##  6 Evaluation

We conducted a set of experiments to demonstrate the robustness of SecureDL in
the case of Byzantine adversaries and to measure the overhead introduced by
the changes to the training process. In what follows, we present the
experimental details and discuss the findings.

###  6.1 Experimental Setup

We implement SecureDL in Python leveraging the Pytorch framework [42] for
model training. All experiments are conducted on a compute cluster with a
Intel Xeon Platinum 8358 cpu, A100 GPU, and 128GB RAM networked locally.

####  6.1.1 Datasets

We evaluated our protocol using four popular deep learning datasets: MNIST
[32], Fashion-MNIST [51], SVHN [40] and CIFAR-10 [31] with independent and
identically distributed (IID) partitioning. We randomly split the training set
into subsets of a desired size (mostly evenly) and allocate each subset to
each client. The MNIST dataset contains 60,000 training and 10,000 testing
grayscale images of handwritten digits, each with a resolution of $28\times
28$ pixels. It is evenly distributed across ten classes, with each class
represented by 6,000 images in the training set and 1,000 in the test set.
Fashion-MNIST is a 10-class fashion image classification task, which has a
predefined training set of 60,000 fashion images and a testing set of 10,000
fashion images. The SVHN dataset, sourced from Google Street View house
numbers, includes 99,289 color images across ten classes. It comprises of
73,257 training and 26,032 testing images, all standardized to a resolution of
$28\times 28$ pixels. CIFAR-10, a collection of color images, offers a diverse
challenge with its 50,000 training and 10,000 testing examples spread across
ten distinct classes. Each example in this dataset is a color image
representing one of these classes.

####  6.1.2 Model

We implemented two distinct model architectures to cater to the specific needs
of our datasets: a CNN for CIFAR-10 and SVHN, and an MLP for Fashion MNIST and
MNIST. Detailed in Table 2, the CNN architecture begins with a $3\times
32\times 32$ input layer, progressing through several convolutional layers
with Group Normalization (GN) and ReLU activations, interspersed with max
pooling and dropout rates ranging from 0.2 to 0.5, and concludes with a fully
connected output layer. This model is optimized with a learning rate of 0.002
and a batch size of 128, designed to efficiently process and learn from the
image data. For the simpler Fashion MNIST and MNIST datasets, the two-layer
MLP, employing sigmoid activations, is optimized with a learning rate of 0.01
and the same batch size, providing a tailored solution that addresses the
unique challenges of each dataset while ensuring effective learning outcomes.

Table 2: Model architecture for CIFAR10 dataset

Layer Type | Size / Type
---|---
Input | $3\times 32\times 32$
Conv+ GroupNorm + ReLU |  $3\times 3\times 32$ / GN(32)
Conv + GroupNorm + ReLU + Max Pool + Dropout(0.2) |  $3\times 3\times 32$ / GN(32)
Conv + GroupNorm + ReLU |  $3\times 3\times 64$ / GN(64)
Conv + GroupNorm + ReLU + Max Pool + Dropout(0.3) |  $3\times 3\times 64$ / GN(64)
Conv + GroupNorm + ReLU |  $3\times 3\times 128$ / GN(128)
Conv + GroupNorm + ReLU + Max Pool + Dropout(0.4) |  $3\times 3\times 128$ / GN(128)
Fully Connected + GroupNorm + ReLU + Dropout(0.5) | 128 / GN(128)
Fully Connected | 10

###  6.2 Attacks

Our experimental evaluation includes two primary categories of poisoning
strategies: data poisoning and local model manipulation. Within the realm of
data poisoning, our focus is on the widely recognized label flipping attack
[27]. In the context of local model manipulation, we explore various
approaches, including the sign flipping attack [28], Gaussian attack [33], and
the scaling attack [2]. We also consider scenarios that involve the mix of
these (different) attacks to understand their cumulative impact.

Sign-flipping attack (SF):  In order to implement this attack, we apply a
reversal by multiplying each update from a malicious client with $-1$,
effectively flipping the update vector’s direction. Thus, if the original
update vector is $\hat{w}_{i}^{k}$, the transmitted update becomes
$w_{i}^{k}=-1\times\hat{w}_{i}^{k}$. This attack disrupts the gradient descent
process and emphasizes the need for robust detection/protection strategies
against such manipulations.

Gaussian attack (noise):  Referred also as the noise attack, a Byzantine
client subtly interferes with the learning process in this attack by changing
its updates, $w_{i}^{k}$, to follow a Gaussian distribution. For our
experiments, the Gaussian distribution is characterized by a mean and variance
of $0.1$, simulating noise to evaluate the learning algorithm’s resilience
against these statistically designed disruptions.

Scaling attack (SA):  In this adversarial approach, a Byzantine client
dramatically increases the magnitude of its model’s weights prior to
aggregation. This action distorts the global model by injecting excessively
large weights, which, when averaged with the updates from benign clients, can
result in model divergence or significant skew.

Label Flipping attack (LF):  This attack assumes that attackers have
comprehensive control over the training process, allowing them to modify the
updates in real-time. Therefore, attackers might resort to altering the
training dataset instead of the update parameters. In the LF strategy, the
labels of training samples are inverted: a label $l$ is converted to $L-l-1$,
where $L$ denotes the total number of classes in the classification scenario,
and $l$ is any integer from 0 to $L-1$.

Combination Attack:  The Combination Attack merges multiple adversarial
techniques, such as sign-flipping, Gaussian, scaling, and label flipping
attacks, to create a disruptive effect on the learning process. In this
strategy, a Byzantine client may, for instance, simultaneously reverse and
scale its update vector, introduce Gaussian noise, and alter training dataset
labels. This multifaceted approach aims to test the model’s resilience and the
effectiveness of the defense mechanisms by combining the strengths of each
client attack type.

###  6.3 Attacks on Robust Aggregation Schemes

In this section, we delve into the comparative analysis of SecureDL against
decentralized aggregation schemes without privacy protection, as detailed in
Table 3. We focus on evaluating the accuracy of all involved schemes across
three diverse datasets CIFAR-10, SVHN and Fashion-MNIST. This investigation
aims to highlight the effectiveness of SecureDL in maintaining high levels of
accuracy even in the presence of Byzantine attacks.

Table 3: Accuracy comparison of existing decentralized robust aggregation
schemes against SecureDL under various attacks over SVHN, CIFAR-10 and
Fashion-MNIST datasets.

(a) CIFAR-10 dataset

# Client | N = 10
---|---
# Byzantine | 0 | 2 | 2 | 2 | 2 | 4
Attack type | W/O | SF | SA | Noise | LF | Combi
Mean | 84.21 | 53.83 | 13.43 | 16.32 | 60.27 | 10.16
DKrum | 82.20 | 73.55 | 74.3 | 73.32 | 72.95 | 73.52
BRIDGE | 83.28 | 81.86 | 81.57 | 81.26 | 81.34 | 80.07
MOZI | 83.36 | 82.06 | 81.96 | 81.64 | 82.56 | 79.45
DMedian | 83.52 | 80.36 | 77.64 | 82.64 | 80.29 | 80.75
SecureDL | 82.29 | 81.38 | 76.41 | 81.59 | 75.12 | 80.06

(b) SVHN dataset

# Client | N = 10
---|---
# Byzantine | 0 | 2 | 2 | 2 | 2 | 4
Attack type | W/O | SF | SA | Noise | LF | Combi
Mean | 95.65 | 21.34 | 22.39 | 19.99 | 94.82 | 55.35
DKrum | 93.57 | 93.67 | 93.43 | 93.71 | 93.80 | 93.84
BRIDGE | 95.45 | 95.34 | 95.34 | 95.37 | 95.38 | 94.98
MOZI | 95.46 | 95.57 | 95.39 | 95.40 | 95.44 | 94.94
DMedian | 95.24 | 94.96 | 94.67 | 95.29 | 94.86 | 94.71
SecureDL | 95.12 | 94.54 | 95.43 | 95.47 | 95.30 | 95.04

(c) Fashion-MNIST dataset

# Client | N = 10
---|---
# Byzantine | 0 | 2 | 2 | 2 | 2 | 4
Attack type | W/O | SF | SA | Noise | LF | Combi
Mean | 93.28 | 78.12 | 25.23 | 19.14 | 87.04 | 21.13
DKrum | 92.37 | 91.76 | 92.07 | 91.96 | 92.22 | 91.97
BRIDGE | 93.24 | 93.04 | 92.99 | 92.90 | 92.79 | 92.57
MOZI | 93.22 | 93.08 | 92.98 | 93.19 | 89.62 | 92.31
DMedian | 93.02 | 92.46 | 92.73 | 92.89 | 92.49 | 92.71
SecureDL | 93.23 | 92.86 | 92.25 | 92.99 | 90.30 | 92.93

In the CIFAR-10 dataset (Table 3(a)), the mean aggregation method (first row),
which does not provide any defense against Byzantine clients, clearly reveals
its vulnerability to various Byzantine attacks. The accuracy drops to 13.43%
under scaling attacks (SA) and 16.32% under Gaussian noise, significantly
highlighting its vulnerability. In contrast, SecureDL demonstrates robust
performance across the board, maintaining an accuracy of 76.41% against SA
and, impressively, 81.59% against noise, vastly outperforming the unprotected
mean method. It consistently demonstrates competitive resilience when
comparing SecureDL’s performance to other robust methods. Against SA,
SecureDL’s 76.41% is superior to DKrum’s 74.3% and closely trails behind
BRIDGE’s 81.57%, illustrating its effective mitigation strategies. Moreover,
SecureDL’s 81.59% accuracy under Gaussian noise surpasses DKrum’s 73.32% and
nearly matches BRIDGE at 81.26%. This evidence positions SecureDL as a strong
contender in ensuring model accuracy while providing resistance against a
broad spectrum of Byzantine attacks.

In the SVHN dataset (Table 3(b)), the mean aggregation method again
demonstrates its weaknesses, with accuracy falling to 21.34% under sign-
flipping attacks and dropping to 19.99% with Gaussian noise, highlighting its
struggles against complex attacks. In contrast, SecureDL stands out for its
strength, achieving a solid 94.54% accuracy against sign-flipping and
improving it to 95.47% against noise, significantly outperforming the mean
method. These results not only show SecureDL’s ability to fend off attacks but
also place it in close competition with other top methods such as MOZI and
BRIDGE. Its effectiveness is especially noticeable in combined attack
scenarios, where it maintains a 95.04% accuracy, showing its comprehensive
approach to defense.

Lastly, in the Fashion-MNIST dataset (Table 3(c)), the impact of Byzantine
attacks on mean aggregation becomes very apparent, with a drastic accuracy
fall to 25.23% under scaling attacks (SA) and a further dip to 19.14% when
faced with Gaussian noise. SecureDL, however, emerges as a formidable
contender, significantly mitigating the effects of these disruptions. It
maintains an impressive 92.25% accuracy against SA and 92.99% accuracy against
noise, demonstrating its superior defense capabilities. This performance
places SecureDL in a competitive stance with BRIDGE. The results show the
advantage of SecureDL over DMedian, especially in the case of multiple attack
types (i.e., combination attack ), where SecureDL achieves a remarkable 92.93%
accuracy.

Measurement | Time Overhead (seconds) on CIFAR-10 | Time Overhead (seconds) on MNIST
---|---|---
# Clients | 3 | 5 | 8 | 10 | 20 | 30 | 3 | 5 | 8 | 10 | 20 | 30
Cosine Similarity | 0.09 | 0.20 | 0.50 | 0.73 | 2.91 | 5.63 | 0.035 | 0.089 | 0.22 | 0.36 | 1.33 | 3.20
Secure Comparison | 0.013 | 0.039 | 0.089 | 0.147 | 0.56 | 1.11 | 0.013 | 0.035 | 0.096 | 0.14 | 0.55 | 1.06
L2-Normalization | 0.2 | 0.41 | 0.91 | 1.28 | 4.32 | 9.13 | 0.15 | 0.33 | 0.69 | 0.99 | 3.28 | 7.34

Table 4: Overhead measurements for protocol functions across client counts,
showcasing the CNN architecture over CIFAR-10 and the MLP over MNIST.

###  6.4 Impact of the fraction of Byzantine clients

Figure 3: Implications of varying the fraction of malicious clients in
different attack scenarios on MNIST dataset.

Figure 3 illustrates the performance of various DL aggregation schemes in
response to different attacks on the MNIST dataset, tracking the change in
accuracy as the proportion of malicious clients varies between 0 to 80%.

In the context of Noise and Label-flipping Attacks, the performance of
Byzantine robust aggregation rules varies significantly. DKrum, reflecting the
limitations of Krum’s scoring mechanism, shows a notable decrease in accuracy,
dropping to around 86% at a less than 50% malicious client level for both
attack types. This indicates its vulnerability in scenarios where the
proportion of malicious clients approaches its tolerance limit. BRIDGE,
employing Trimmed-Mean, demonstrates a similar trend with its accuracy falling
to 88%, indicative of its effective yet limited capacity to manage Byzantine
clients, aligning with its theoretical tolerance of nearly 50% malicious
clients. DMedian, influenced by the Median method’s approach, maintains
relatively higher accuracy (around 92%) but begins to decline as the number of
Byzantine clients approaches $\frac{n}{2}$. Mozi, utilizing a combination of
distance-based and performance-based filtering, exhibits commendable
resilience, maintaining over 94% accuracy in both attack scenarios. SecureDL,
our proposed method, stands out in these settings, closely matching or
slightly surpassing Mozi’s robustness, particularly with 80% of clients being
Byzantine, in decentralized networks with a significant presence of Byzantine
actors.

Under Sign-flipping and Scaling Attacks, we observe that DKrum’s accuracy,
echoing the limitations of its core selection process, declines to 86% at a
less than 50% malicious client fraction in both attacks, underscoring its
struggle in scenarios with a high concentration of Byzantine clients. The
coordinate-wise strategies like BRIDGE and DMedian, while demonstrating better
adaptability than DKrum, experience accuracy drops to 88% and 92%,
respectively. This indicates their challenges in maintaining performance
integrity when approaching their respective Byzantine tolerance limits. Mozi’s
method ensures a more stable performance, maintaining accuracy above 94% in
both attack types, thereby demonstrating its efficacy in filtering benign
contributions. SecureDL, however, emerges as a notably robust method in these
scenarios. Its consistent high accuracy, often slightly ahead of Mozi,
particularly under scaling attacks, reinforces its suitability for
decentralized learning models facing diverse Byzantine challenges. This
underscores SecureDL’s potential as a versatile and resilient choice in
environments with a broad range of Byzantine threats.

###  6.5 Computational and Communication Complexity

In the SecureDL protocol within a multi-party computation framework, the
computational complexity is shaped by several vital steps involving all
participating clients. Initially, each of the $n$ clients engage in additive
secret sharing, computing and distributing secret shares of their inputs to
the others, resulting in $n\times(n-1)$ computational and communication tasks
and yielding a complexity of $O(n^{2})$. This is followed by the computation
of cosine similarities, where clients jointly compute similarities between
it’s own model update and every other client’s update. This step involves
$n^{2}$ computations, with each of the $n$ clients jointly calculating
similarities with every other client’s update. This process, necessitated by
security requirements for separate computations despite identical calculations
between client pairs, contributes an overall complexity of $O(n^{2})$. The
protocol then involves secure comparisons of these cosine similarities against
a threshold maintaining the $O(n^{2})$ scaling. Finally, normalization,
dependent on the number of vectors accepted based on the threshold, involves
all clients and likely scales linearly with the number of clients,
contributing further to the $O(n^{2})$ complexity in the worst case.
Consequently, the cumulative complexity of the SecureDL protocol is determined
to be $O(n^{2})$, reflecting the quadratic scaling in computational demands
with the increase in the number of participating clients.

The overall communication complexity is influenced by multiple computational
steps, each with its own impact on the total communication requirements.
Initially, clients engage in secret sharing with linear complexity $O(n)$,
where $n$ is the number of clients. This is followed by the cosine similarity
computation and L2 normalization, each involving $k$ Beaver triple
multiplications per pairwise computation among the $n$ clients, resulting in a
significant communication load of $O(kn^{3})$ for each step. Additionally, the
protocol employs a secure comparison operation, which, based on the Rabbit
protocol’s complexity of $\mathcal{O}(\ell\log\ell)$ and being performed
$n^{2}$ times (once for each pair of clients), contributes significantly to
the communication complexity. Assuming that the bit length $\ell$ of the
integers involved is constant and not dependent on $n$, this step adds
$O(n^{2}\ell\log\ell)$ to the overall complexity. The final step,
normalization, similar to cosine similarity, also involves $k$ Beaver triple
multiplications for each of the $n^{2}$ computations, further contributing
$O(kn^{3})$. Therefore, when combining these complexities, the overall
communication complexity of the SecureDL protocol is dominated by the cosine
similarity, L2 normalization, and secure comparison steps, culminating in a
total complexity of approximately $O(kn^{3})$. This underlines the protocol’s
considerable communication demands, scaling cubically with the number of
clients due to the Beaver triple operations.

###  6.6 Efficiency of SecureDL

The detailed examination of SecureDL’s computational efficiency, as outlined
in Table 4, gives indications on the time overhead for critical protocol
functions—Cosine Similarity, Secure Comparison, and L2-Normalization—across a
broad spectrum of client configurations, from 3 to 30, within CIFAR-10 and
MNIST datasets. Here, we omit the SVHN and Fashion MNIST datasets as they use
the same model architectures with the other ones. In a nutshell, the results
show a consistent trend of increasing computational overhead with the
increasing number of clients in SecureDL. For instance, in the CIFAR-10
dataset, the execution time for Cosine Similarity dramatically increases from
0.09 seconds with just three clients to 5.63 seconds with 30 clients, marking
a substantial rise. L2-Normalization time exhibits a similar pattern,
escalating from 0.2 seconds for three clients to 9.13 seconds for thirty
clients, indicating the growing computational demands as the network size
expands. This upward trend in processing time is consistently observed, albeit
at lower absolute times, in the MNIST dataset, where the overhead for Cosine
Similarity grows from 0.035 seconds to 3.20 seconds, and for L2-Normalization,
from 0.15 seconds to 7.34 seconds as the client count increases from 3 to 30.

Crucially, the MNIST dataset evaluations were conducted over a simpler two-
layer MLP network. In contrast, the CIFAR-10 assessments utilized a more
complex model described in Table 2, clarifying the observed discrepancies in
time overheads between them. This distinction highlights the inherent
differences in dataset complexity and model architecture and emphasizes
SecureDL’s flexibility and effectiveness across varying computational
landscapes. By accommodating different network complexities, SecureDL
demonstrates a comprehensive capability to secure decentralized learning
environments, effectively balancing the dual demands of robust security
measures and computational efficiency.

##  7 Conclusion

In this paper, we present a decentralized machine learning approach called
SecureDL designed to enhance security and privacy in the face of Byzantine
attacks. By shifting the focus from traditional client update monitoring
methods to a more collaborative and secure approach, SecureDL makes the
decentralized learning framework more resilient against Byzantine and semi-
honest entities. Its innovative aggregation mechanism, which rigorously
scrutinizes each model update, ensures robust defense against adversarial
actions while preserving the privacy of individual clients.

The empirical evaluations of SecureDL across various datasets demonstrates its
effectiveness in providing a resilient defense mechanism against a spectrum of
attacks, pushing the envelope for decentralized learning. Furthermore, the
performance analysis of SecureDL sheds light to the impact of the privacy-
preserving changes to the overall training process while underlining the
efficiency of the proposed method. Our work contributes a vital piece to the
puzzle of protecting collaborative machine learning environments by propelling
the field forward with regards to critical security challenges and lays the
groundwork for future innovations.

## References

  * [1] Alan Agresti.  Categorical data analysis.  482, 2003.
  * [2] Eugene Bagdasaryan, Andreas Veit, Yiqing Hua, Deborah Estrin, and Vitaly Shmatikov.  How to backdoor federated learning.  In International conference on artificial intelligence and statistics, pages 2938–2948. PMLR, 2020.
  * [3] Gilad Baruch, Moran Baruch, and Yoav Goldberg.  A little is enough: Circumventing defenses for distributed learning.  Advances in Neural Information Processing Systems, 32, 2019.
  * [4] Donald Beaver.  Efficient multiparty protocols using circuit randomization.  In Annual International Cryptology Conference, pages 420–432. Springer, 1991.
  * [5] Arjun Nitin Bhagoji, Supriyo Chakraborty, Prateek Mittal, and Seraphin Calo.  Analyzing federated learning through an adversarial lens.  In International Conference on Machine Learning, pages 634–643. PMLR, 2019.
  * [6] Battista Biggio, Blaine Nelson, and Pavel Laskov.  Poisoning attacks against support vector machines.  arXiv preprint arXiv:1206.6389, 2012.
  * [7] Peva Blanchard, El Mahdi El Mhamdi, Rachid Guerraoui, and Julien Stainer.  Machine learning with adversaries: Byzantine tolerant gradient descent.  Advances in neural information processing systems, 30, 2017.
  * [8] Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečnỳ, Stefano Mazzocchi, Brendan McMahan, et al.  Towards federated learning at scale: System design.  Proceedings of machine learning and systems, 1:374–388, 2019.
  * [9] Xiaoyu Cao, Minghong Fang, Jia Liu, and Neil Zhenqiang Gong.  Fltrust: Byzantine-robust federated learning via trust bootstrapping.  arXiv preprint arXiv:2012.13995, 2020.
  * [10] Yudong Chen, Lili Su, and Jiaming Xu.  Distributed statistical machine learning in adversarial settings: Byzantine gradient descent.  Proceedings of the ACM on Measurement and Analysis of Computing Systems, 1(2):1–25, 2017.
  * [11] Hsin-Pai Cheng, Patrick Yu, Haojing Hu, Syed Zawad, Feng Yan, Shiyu Li, Hai Li, and Yiran Chen.  Towards decentralized deep learning with differential privacy.  In International Conference on Cloud Computing, pages 130–145. Springer, 2019.
  * [12] Ronald Cramer, Ivan Damgård, Daniel Escudero, Peter Scholl, and Chaoping Xing.  Spd$\mathbb{z}$${}_{\mbox{2${}^{\mbox{k}}$}}$: Efficient MPC mod 2${}^{\mbox{k}}$ for dishonest majority.  IACR Cryptol. ePrint Arch., page 482, 2018.
  * [13] Ahmed Roushdy Elkordy and A Salman Avestimehr.  Heterosag: Secure aggregation with heterogeneous quantization in federated learning.  IEEE Transactions on Communications, 70(4):2372–2386, 2022.
  * [14] Ahmed Roushdy Elkordy, Saurav Prakash, and Salman Avestimehr.  Basil: A fast and byzantine-resilient approach for decentralized training.  IEEE Journal on Selected Areas in Communications, 40(9):2694–2716, 2022.
  * [15] Daniel Escudero, Satrajit Ghosh, Marcel Keller, Rahul Rachuri, and Peter Scholl.  Improved primitives for mpc over mixed arithmetic-binary circuits.  In Advances in Cryptology–CRYPTO 2020: 40th Annual International Cryptology Conference, CRYPTO 2020, Santa Barbara, CA, USA, August 17–21, 2020, Proceedings, Part II 40, pages 823–852. Springer, 2020.
  * [16] Cheng Fang, Zhixiong Yang, and Waheed U Bajwa.  Bridge: Byzantine-resilient decentralized gradient descent.  arXiv preprint arXiv:1908.08098, 2019.
  * [17] Minghong Fang, Xiaoyu Cao, Jinyuan Jia, and Neil Gong.  Local model poisoning attacks to $\\{$Byzantine-Robust$\\}$ federated learning.  In 29th USENIX security symposium (USENIX Security 20), pages 1605–1622, 2020.
  * [18] Ali Reza Ghavamipour, Fatih Turkmen, and Xiaoqian Jiang.  Privacy-preserving logistic regression with secret sharing.  BMC Medical Informatics and Decision Making, 22(1):1–11, 2022.
  * [19] Ali Reza Ghavamipour, Fatih Turkmen, Rui Wang, and Kaitai Liang.  Federated synthetic data generation with stronger security guarantees.  In Proceedings of the 28th ACM Symposium on Access Control Models and Technologies, pages 31–42, 2023.
  * [20] Oded Goldreich.  Secure multi-party computation.  Manuscript. Preliminary version, 78(110), 1998.
  * [21] Rachid Guerraoui, Sébastien Rouault, et al.  The hidden vulnerability of distributed learning in byzantium.  In International Conference on Machine Learning, pages 3521–3530. PMLR, 2018.
  * [22] Shangwei Guo, Tianwei Zhang, Xiaofei Xie, Lei Ma, Tao Xiang, and Yang Liu.  Towards byzantine-resilient learning in decentralized systems.  arXiv preprint arXiv:2002.08569, 2020.
  * [23] Shangwei Guo, Tianwei Zhang, Han Yu, Xiaofei Xie, Lei Ma, Tao Xiang, and Yang Liu.  Byzantine-resilient decentralized stochastic gradient descent.  IEEE Transactions on Circuits and Systems for Video Technology, 32(6):4096–4106, 2021.
  * [24] Lie He, Sai Praneeth Karimireddy, and Martin Jaggi.  Byzantine-robust decentralized learning via self-centered clipping.  arXiv preprint arXiv:2202.01545, 2022.
  * [25] István Hegedűs, Gábor Danner, and Márk Jelasity.  Gossip learning as a decentralized alternative to federated learning.  In Distributed Applications and Interoperable Systems: 19th IFIP WG 6.1 International Conference, DAIS 2019, Held as Part of the 14th International Federated Conference on Distributed Computing Techniques, DisCoTec 2019, Kongens Lyngby, Denmark, June 17–21, 2019, Proceedings 19, pages 74–90. Springer, 2019.
  * [26] Chenghao Hu, Jingyan Jiang, and Zhi Wang.  Decentralized federated learning: A segmented gossip approach.  arXiv preprint arXiv:1908.07782, 2019.
  * [27] Malhar S Jere, Tyler Farnan, and Farinaz Koushanfar.  A taxonomy of attacks on federated learning.  IEEE Security & Privacy, 19(2):20–28, 2020.
  * [28] Sai Praneeth Karimireddy, Lie He, and Martin Jaggi.  Learning from history for byzantine robust optimization.  In International Conference on Machine Learning, pages 5311–5319. PMLR, 2021.
  * [29] Marcel Keller.  Mp-spdz: A versatile framework for multi-party computation.  In Proceedings of the 2020 ACM SIGSAC conference on computer and communications security, pages 1575–1590, 2020.
  * [30] Marcel Keller, Emmanuela Orsini, and Peter Scholl.  Mascot: faster malicious arithmetic secure computation with oblivious transfer.  In Proceedings of the 2016 ACM SIGSAC Conference on Computer and Communications Security, pages 830–842, 2016.
  * [31] Alex Krizhevsky, Geoffrey Hinton, et al.  Learning multiple layers of features from tiny images.  2009\.
  * [32] Yann LeCun.  The mnist database of handwritten digits.  http://yann. lecun. com/exdb/mnist/, 1998.
  * [33] Shenghui Li, Edith Ngai, and Thiemo Voigt.  Byzantine-robust aggregation in federated learning empowered industrial iot.  IEEE Transactions on Industrial Informatics, 19(2):1165–1175, 2021.
  * [34] Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu.  Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent.  Advances in neural information processing systems, 30, 2017.
  * [35] Yehuda Lindell.  How to simulate it–a tutorial on the simulation proof technique.  Tutorials on the Foundations of Cryptography: Dedicated to Oded Goldreich, pages 277–346, 2017.
  * [36] Eleftheria Makri, Dragos Rotaru, Frederik Vercauteren, and Sameer Wagh.  Rabbit: Efficient comparison for secure multi-party computation.  In International Conference on Financial Cryptography and Data Security, pages 249–270. Springer, 2021.
  * [37] Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas.  Communication-efficient learning of deep networks from decentralized data.  In AISTATS, pages 1273–1282, 2017.
  * [38] Yinbin Miao, Ziteng Liu, Hongwei Li, Kim-Kwang Raymond Choo, and Robert H Deng.  Privacy-preserving byzantine-robust federated learning via blockchain systems.  IEEE Transactions on Information Forensics and Security, 17:2848–2861, 2022.
  * [39] Yuval Nardi, Stephen E Fienberg, and Robert J Hall.  Achieving both valid and secure logistic regression analysis on aggregated data from different private sources.  Journal of Privacy and Confidentiality, 4(1), 2012.
  * [40] Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng.  Reading digits in natural images with unsupervised feature learning.  2011\.
  * [41] Dario Pasquini, Mathilde Raynal, and Carmela Troncoso.  On the (in) security of peer-to-peer decentralized machine learning.  In 2023 IEEE Symposium on Security and Privacy (SP), pages 418–436. IEEE Computer Society, 2023.
  * [42] Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al.  Pytorch: An imperative style, high-performance deep learning library.  Advances in neural information processing systems, 32, 2019.
  * [43] Jie Peng, Weiyu Li, and Qing Ling.  Byzantine-robust decentralized stochastic optimization over static and time-varying networks.  Signal Processing, 183:108020, 2021.
  * [44] Krishna Pillutla, Sham M Kakade, and Zaid Harchaoui.  Robust aggregation for federated learning.  IEEE Transactions on Signal Processing, 70:1142–1154, 2022.
  * [45] William H Press.  Numerical recipes 3rd edition: The art of scientific computing.  Cambridge university press, 2007.
  * [46] Jaak Randmets.  Programming languages for secure multi-party computation application development.  2017\.
  * [47] Mathilde Raynal, Dario Pasquini, and Carmela Troncoso.  Can decentralized learning be more robust than federated learning?  arXiv preprint arXiv:2303.03829, 2023.
  * [48] Jayanth Regatti, Hao Chen, and Abhishek Gupta.  Bygars: Byzantine sgd with arbitrary number of attackers.  arXiv preprint arXiv:2006.13421, 2020.
  * [49] Thijs Vogels, Lie He, Anastasiia Koloskova, Sai Praneeth Karimireddy, Tao Lin, Sebastian U Stich, and Martin Jaggi.  Relaysum for decentralized deep learning on heterogeneous data.  Advances in Neural Information Processing Systems, 34:28004–28015, 2021.
  * [50] Xiao Wang, Samuel Ranellucci, and Jonathan Katz.  Global-scale secure multiparty computation.  In Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security, pages 39–56, 2017.
  * [51] Han Xiao, Kashif Rasul, and Roland Vollgraf.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  arXiv preprint arXiv:1708.07747, 2017.
  * [52] Cong Xie, Oluwasanmi Koyejo, and Indranil Gupta.  Phocas: dimensional byzantine-resilient stochastic gradient descent.  arXiv preprint arXiv:1805.09682, 2018.
  * [53] Cong Xie, Sanmi Koyejo, and Indranil Gupta.  Zeno: Distributed stochastic gradient descent with suspicion-based fault-tolerance.  In International Conference on Machine Learning, pages 6893–6901. PMLR, 2019.
  * [54] Cong Xie, Sanmi Koyejo, and Indranil Gupta.  Zeno++: Robust fully asynchronous sgd.  In International Conference on Machine Learning, pages 10495–10503. PMLR, 2020.
  * [55] Zhixiong Yang and Waheed U Bajwa.  Byrdie: Byzantine-resilient distributed coordinate descent for decentralized learning.  IEEE Transactions on Signal and Information Processing over Networks, 5(4):611–627, 2019.
  * [56] Dong Yin, Yudong Chen, Ramchandran Kannan, and Peter Bartlett.  Byzantine-robust distributed learning: Towards optimal statistical rates.  In International Conference on Machine Learning, pages 5650–5659. PMLR, 2018.

##  Appendix A Privacy Analysis

###### Proof of Theorem 2.

The functionality of the protocol $\pi$, denoted as $f(x,y):=w$, is
deterministic and ensures correctness. This correctness is verified by
computing the sum of all outputs from $n$ parties and evaluating this sum
modulo $\mathbb{Z}_{2^{k}}$, specifically, $(w_{1}+w_{2}+\ldots+w_{n}$ mod
$\mathbb{Z}_{2^{k}}$). The protocol specifies for each party $P_{i}$ a
corresponding component of $f(x,y)$, $f_{i}(x,y):=w_{i}$, where $w_{i}$ is the
output computed by party $P_{i}$.

Define the view of party $P_{i}$ during the execution of protocol $\pi$ as:

$\operatorname{view}_{i}^{\pi}(x,y):=(x_{i},y_{i},r_{i},m_{1},m_{2},\ldots,m_{t})\in\mathbb{Z}_{2^{k}},$

where $r_{i}$ represents the outcome of the $P_{i}$ internal coin tosses and
$m_{1},m_{2},\ldots,m_{t}$ denote the received messages.
To prove that $\pi$ privately computes $f$, we must show that there exists a
probabilistic polynomial-time simulator $S$ for every $I$ such that:

$\\{S(x_{I},f_{I}(x,y))\\}_{x,y}\stackrel{{\scriptstyle\text{perf}}}{{\equiv}}\\{\operatorname{view}_{I}^{\pi}(x,y)\\}_{x,y}.$

The SecureDL algorithm involves three key operations on secret-shared data:
Cosine similarity computation, comparison over secret shared data and
L2normalization.

The actual view of $P_{I}$, for the computation is as follows:

$\displaystyle\operatorname{view}_{I}^{\pi}(\vec{x})=($
$\displaystyle\vec{x},m^{cosine}_{1},m^{cosine}_{2},\ldots,m^{cosine}_{I},m^{comp}_{1},$
$\displaystyle
m^{comp}_{2},\ldots,m^{comp}_{n},m^{l2norm}_{1},m^{l2norm}_{2},\ldots,$
$\displaystyle m^{l2norm}_{I})$

where $\vec{x}$ denotes the vectors of additive shares of the inputs held by
each honest parties, $m^{cosine}_{i}$ are the messages exchanged during the
cosine similarity computation, $m^{comp}_{i}$ are the messages exchanged for
the comparison operation and $m^{l2norm}_{i}$ are the messages exchanged for
the L2-Normalization computation.

Given the additive sharing scheme, all elements involved in
$\operatorname{view}_{I}^{\pi}(\vec{x}$ are independently and uniformly
distributed within $\mathbb{Z}_{2^{k}}$, ensuring that from $P_{I}$’s
perspective, all components are indistinguishable from random. This setup,
based on the privacy-preserving properties of cosine similarity, secure
comparison and L2Normalization operations, allows $S_{I}$ to simulate a
plausible set of interactions that $P_{I}$ (or any group of honest parties)
would observe, without revealing any private information. The simulator
$S_{I}$ thus constructs a simulated view that includes simulated messages for
each step of the norm computation, ensuring these simulated components are
indistinguishable from those in a real protocol execution.

We construct a simulator, denoted $S_{I}$, for simulating the collective view
of honest parties within the execution of SecureDL protocol. The role of
$S_{I}$ is to create a plausible simulation of the protocol execution as it
would appear to the honest parties, focusing on the data exchanges and
computations that occur without assuming control over the adversary’s direct
observations.

In the case of cosine similarity computation, $S_{I}$ simulates the messages
exchanged during this step, such as
$\tilde{m}^{cosine}_{1},\tilde{m}^{cosine}_{2},\ldots,\tilde{m}^{cosine}_{n}$.
This simulation is consistent with the privacy assurances specified in Theorem
7, making these simulated messages indistinguishable from random values in
$\mathbb{Z}_{2^{k}}$ to any observer, thereby maintaining the integrity of the
privacy guarantees.

During the comparison, $S_{I}$ constructs messages such as
$\tilde{m}^{comp}_{1},\tilde{m}^{comp}_{2},\ldots,\tilde{m}^{comp}_{n}$,
simulating the inter-party communications. SecureDL utilized Rabbit secure
comparison protocol [36], which has perfect security within
$\mathbb{Z}_{2^{k}}$. Therefore, to any observer, these simulated messages are
indistinguishable from random values within $\mathbb{Z}_{2^{k}}$, thereby
upholding the integrity of the privacy guarantees.

Finally, during the L2-normalization computation, $S_{I}$ constructs messages
such as
$\tilde{m}^{l2norm}_{1},\tilde{m}^{l2norm}_{2},\ldots,\tilde{m}^{l2norm}_{n}$,
simulating the messages exchanged during. These simulated messages are crafted
to be statistically indistinguishable from those in a genuine protocol run,
aligning with the privacy-preserving methodology of the square root function
described in Theorem 8.

The simulated view $S_{I}$ provides for the protocol includes the inputs of
all such parties, denoted as $x_{1},x_{2},\ldots,x_{m}$, where $m$ is the
number of honest parties. Thus, the complete simulator view is represented as:

$\displaystyle S_{I}(\bar{x},f_{I}(\bar{x}))=($
$\displaystyle\tilde{\vec{x}},\tilde{m}^{cosine}_{1},\tilde{m}^{cosine}_{2},\ldots,\tilde{m}^{cosine}_{n},\tilde{m}^{comp}_{1}$
$\displaystyle,\tilde{m}^{comp}_{2},\ldots,\tilde{m}^{comp}_{n}\,\tilde{m}^{l2norm}_{1},\tilde{m}^{l2norm}_{2},\ldots,$
$\displaystyle\tilde{m}^{l2norm}_{n})$

Every component of $S_{I}$ is independent and uniformly random within
$\mathbb{Z}_{2^{k}}$). As $S_{I}$ is designed to select values that are not
only independently and uniformly random but also drawn from the same
distribution as those in $\operatorname{view}_{I}^{\pi}$, these components
become indistinguishable. This indistinguishability, ensures that they
resemble random values, thus reinforcing the privacy aspect of the protocol.

∎

######  Theorem 3 (privacy w.r.t semi-honest behavior).

Consider a secure multi-party computation protocol $\pi$ designed to compute a
function $f(x,y)$ utilizing the Beaver multiplication approach (detailed in
Section 3.2.1). This protocol involves $n$ parties, denoted as
$P_{1},P_{2},\ldots,P_{n}$, with a subset $I\subset[n]$ consisting of semi-
honest parties where at least one party is honest, while the rest are semi-
honest. The protocol $\pi$ is considered to privately compute the Beaver
multiplication $f(x,y)$ if a probabilistic polynomial-time simulator $S_{i}$
can be constructed such that, given all potential inputs, the simulated view
of $P_{i}$ is statistically indistinguishable from $P_{i}$’s actual view
during the execution of the protocol.

###### Proof.

The functionality of the protocol $\pi$, denoted as $f(x,y):=w$, is
deterministic and ensures correctness. This correctness is verified by
computing the sum of all outputs from $n$ parties and evaluating this sum
modulo $\mathbb{Z}_{2^{k}}$, specifically, $(w_{1}+w_{2}+\ldots+w_{n}$ mod
$\mathbb{Z}_{2^{k}}$). The protocol specifies for each party $P_{i}$ a
corresponding component of $f(x,y)$, $f_{i}(x,y):=w_{i}$, where $w_{i}$ is the
output computed by party $P_{i}$.

Define the view of party $P_{i}$ during the execution of protocol $\pi$ as:

$\operatorname{view}_{i}^{\pi}(x,y):=(x_{i},y_{i},r_{i},m_{1},m_{2},\ldots,m_{t})\in\mathbb{Z}_{2^{k}},$

where $r_{i}$ represents the outcome of the $P_{i}$ internal coin tosses and
$m_{1},m_{2},\ldots,m_{t}$ denote the received messages.
To prove that $\pi$ privately computes $f$, we must show that there exists a
probabilistic polynomial-time simulator $S$ for every $I$ such that:

$\\{S(x_{I},f_{I}(x,y))\\}_{x,y}\stackrel{{\scriptstyle\text{perf}}}{{\equiv}}\\{\operatorname{view}_{I}^{\pi}(x,y)\\}_{x,y}.$

The actual view of $P$ in protocol $\pi$ for the multiplication function
$f(x,y)$ is :

$\displaystyle\operatorname{view}_{I}^{\pi}(x,y)=($ $\displaystyle
x_{I},y_{I},a_{I},b_{I},c_{I},\delta_{I},\epsilon_{I})$

where $y_{1},\delta_{I},$ and $\epsilon_{I}$ are messages received by $P_{I}$
from other parties. Also, $a_{I}$, $b_{I}$ and $c_{I}$ are the Beaver triples
received by $P_{I}$ for a multiplication.

It is important to note that all these elements are additively shared between
the parties or results of the addition of two additively shared values.
Therefore, based on the definition in Section 3.2.1, they are independent
uniformly random within the $\mathbb{Z}_{2^{k}}$ set.

Furthermore, from the $\operatorname{view}_{I}^{\pi}(x,y)$, $P_{I}$ can
compute all other relevant quantities and this view contains all of $P_{I}$’s
information.

Now, we construct a simulator, denoted $S$, for the view of party $P_{I}$ that
simulates the computation of $\delta$ and $\epsilon$, representing the
differences between simulated inputs $\tilde{x}_{I}$ and $\tilde{y}_{I}$, and
predetermined shares $\tilde{a}_{I}$ and $\tilde{b}_{I}$ from Beaver triples.
These simulated values are independent and chosen uniformly at random,
ensuring they mirror the actual protocol’s input and share distribution. The
simulator then calculates $\tilde{\delta}_{I}=\tilde{x}_{I}-\tilde{a}_{I}$ and
$\tilde{\epsilon}_{I}=\tilde{y}_{I}-\tilde{b}_{I}$, mirroring the protocol’s
approach to determining $\delta$ and $\epsilon$.

With ${\delta}$ and ${\epsilon}$ computed, $S$ proceeds to simulate the
computation of the share of the product, $\tilde{w}_{I}$, using the formula
$\tilde{w}_{I}=\tilde{c}_{I}+{\epsilon}\cdot\tilde{b}_{I}+{\delta}\cdot\tilde{a}_{I}+{\epsilon}\cdot{\delta}$.
This step effectively mimics the actual protocol’s computation, incorporating
the adjustment based on the computed differences ($\delta$ and $\epsilon$) and
the correction factor ($\tilde{\epsilon_{I}}\cdot\tilde{\delta_{I}}$),
utilizing the simulated shares of $a$, $b$, and $c$ from the Beaver triples.

We define simulator $S$ view for the multiplication as

$\displaystyle S(x_{I},f_{I}(x,y))=($ $\displaystyle
x,\tilde{x_{1}},\tilde{y_{1}},\tilde{a_{I}},\tilde{b_{I}},\tilde{c_{I}},\tilde{\delta_{I}}\tilde{\epsilon_{I}})$

where each component of $S$ is independent uniformly random in
$\mathbb{Z}_{2^{k}}$. Since $S$ selects and computes values that are
independently and uniformly random, and from the same distribution as those in
$\operatorname{view}^{\pi}$, they are indistinguishable. As a result, the
statistical distance between the simulated view $S(x_{I},f_{I}(x,y))$ and the
actual view $\operatorname{view}_{I}^{\pi}(x,y)$ is effectively zero for all
$x,y$. Consequently, all components, except for $x$, are indistinguishable
from random values, thereby affirming the protocol’s privacy.

∎

######  Theorem 4 (privacy w.r.t semi-honest behavior).

Consider a secure multi-party computation protocol $\pi$ designed to compute a
function $f(x)$ utilizing the inverse function (detailed in Section 3.2.3).
This protocol involves $n$ parties, denoted as $P_{1},P_{2},\ldots,P_{n}$,
with a subset $I\subset[n]$ consisting of semi-honest parties where at least
one party is honest, while the rest are semi-honest. The protocol $\pi$ is
considered to privately compute the inverse function $f(x)$ if a probabilistic
polynomial-time simulator $S_{i}$ can be constructed such that, given all
potential inputs, the simulated view of $P_{i}$ is statistically
indistinguishable from $P_{i}$’s actual view during the execution of the
protocol.

###### Proof.

The protocol $\pi$ ensures deterministic correctness by summing the outputs of
$n$ parties modulo $\mathbb{Z}_{2^{k}}$. Each party $P_{i}$ contributes a
specific output $w_{i}$ to the function $f(x,y)$. The privacy of $\pi$ is
shown by proving that for any inputs $x$ and $y$, a simulator can generate a
view for party $P$ that is indistinguishable from its actual view during the
protocol’s execution, encompassing inputs, internal randomness, and received
messages.

The inversion function consists of three main operations on secret-shared
inputs: addition, multiplication by a public constant, and Beaver
multiplication. In contrast to Beaver multiplication, both the addition and
the multiplication by a public constant operations are executed locally on the
secret-shared data.

The inverse function begins with a “for” loop, within which there are two
Beaver multiplications; the output of the first multiplication serves as the
input for the second Beaver multiplication. Therefore, we can define the
operations inside this loop as $f(x,y)$ and represent this function in the
following form:

$\displaystyle f^{\prime}(x,y)=x\times y=w$ $\displaystyle
f^{\prime\prime}(w,x)=w\times x$

Here, $w$ is the output of the first multiplication $f^{\prime}(x,y)$, and the
output of $f^{\prime\prime}(w,x)$ is equal to $f(x,y)$.

Based on Theorem 3, protocol $\pi$ can compute each of the multiplication
privately. As long as $w1$, $w2$, …and $w_{n}$, the shares of the Beaver
multiplications output, are not revealed, they remain uniformly random and
independent. However, since the output of the first multiplication is the
input of the second multiplication, we need to show that the first
multiplication $f^{\prime}(x,y)$ remains private when the second
multiplication $f^{\prime\prime}(w,x)$ is executed. In other words, the
information received by $P$ during the second multiplication should not reveal
any details about the inputs $x$ and $y$ of the first multiplication.

Therefore, we need to define the actual view of $P_{I}$ within protocol $\pi$
specifically for the second multiplication:

$\displaystyle\operatorname{view}_{I}^{\pi}(w,x)=$ $\displaystyle\
(x_{I},y_{I},w_{I},a_{I},b_{I},c_{I},a_{I}^{\prime},b_{I}^{\prime},c_{I}^{\prime},$
$\displaystyle\
\delta_{2},\delta_{3},\ldots,\delta_{n},\epsilon_{2},\epsilon_{3},\ldots,\epsilon_{n},$
$\displaystyle\
\delta_{2}^{\prime},\delta_{3}^{\prime},\ldots,\delta_{n}^{\prime},\epsilon_{2}^{\prime},\epsilon_{3}^{\prime},\ldots,\epsilon_{n}^{\prime})$

where $y_{1}$ is the share of initial guess,
$\delta_{2},\delta_{3},\ldots,\delta_{n},$ and
$\epsilon_{2},\epsilon_{3},\ldots,\epsilon_{n}$ are messages received by $P$
from other parties for the second multiplication, and
$\delta_{2}^{\prime},\delta_{3}^{\prime},\ldots,\delta_{n}^{\prime},\epsilon_{2}^{\prime},\epsilon_{3}^{\prime},\ldots,\epsilon_{n}^{\prime}$
are messages received by $P$ from other parties for the first multiplication.
Also, $a_{I}$, $b_{I}$ and $c_{I}$ and $a_{I}^{\prime}$, $b_{I}^{\prime}$ and
$c_{1}^{\prime}$ are the Beaver triples received by $P$ for the
multiplications and $w_{1}$ is the result of first multiplication.

All these elements, except for $x$, are additively shared between the parties
or results of the addition of two additively shared values. Therefore, based
on the definition in 3.2.1, they are independent uniformly random within the
$\mathbb{Z}_{2^{k}}$ set.

Furthermore, from the $\operatorname{view}_{I}^{\pi}(w,x)$, $P$ can compute
all other relevant quantities and this view contains all of $P$’s information.

Now, we construct a simulator, denoted $S$, for the view of party $P$ that
simulates the computation of $\delta$ and $\epsilon$, representing the
differences between simulated inputs $\tilde{x}_{I}$ and $\tilde{y}_{I}$, and
predetermined shares $\tilde{a}_{I}$ and $\tilde{b}_{I}$ from Beaver triples.
These simulated values are independent and chosen uniformly at random,
ensuring they mirror the actual protocol’s input and share distribution. The
simulator then calculates $\tilde{\delta}=\tilde{x}-\tilde{a}_{I}$ and
$\tilde{\epsilon}=\tilde{y}-\tilde{b}_{I}$, mirroring the protocol’s approach
to determining $\delta$ and $\epsilon$.

With ${\delta}$ and ${\epsilon}$ computed, $S$ proceeds to simulate the
computation of the share of the product, $\tilde{w}_{I}$, using the formula
$\tilde{w}_{I}=\tilde{c}_{I}+{\epsilon}\cdot\tilde{b}_{I}+{\delta}\cdot\tilde{a}_{I}+{\epsilon}\cdot{\delta}$.
This step effectively mimics the actual protocol’s computation, incorporating
the adjustment based on the computed differences ($\delta$ and $\epsilon$) and
the correction factor ($\tilde{\epsilon}\cdot\tilde{\delta}$), utilizing the
simulated shares of $c$, $a$, and $b$ from the Beaver triples.

Now, we define simulator $S$ as

$\displaystyle S(x_{I},f_{I}(w,x))=($
$\displaystyle\tilde{x}_{I},\tilde{y}_{I},\tilde{a}_{I},\tilde{b}_{I},\tilde{c}_{I},\tilde{a}_{I}^{\prime},\tilde{b}_{I}^{\prime},\tilde{c}_{I}^{\prime},\tilde{\delta}_{2}$
$\displaystyle,\tilde{\delta}_{3},\ldots,\tilde{\delta}_{n},\tilde{\delta}_{2}^{\prime},\tilde{\delta}_{3}^{\prime},\ldots,\tilde{\delta}_{n}^{\prime},\tilde{\epsilon}_{2},\tilde{\epsilon}_{3}$
$\displaystyle,\ldots,\tilde{\epsilon}_{n},\tilde{\epsilon}_{2}^{\prime},\tilde{\epsilon}_{3}^{\prime},\ldots,\tilde{\epsilon}_{n}^{\prime})$

Unlike the first beaver multiplication, the simulator view for the second
multiplication consists of all messages $P$ receives during the second
multiplication, plus what it could see from the first multiplication.

As shown, all components of $S$ are independent and uniformly random in
$\mathbb{Z}_{2^{k}}$, except for $x$, which is $P$’s private input. Since $S$
selects and computed values that are independently and uniformly random, and
from the same distribution as those in $\operatorname{view}^{\pi}$, they are
indistinguishable. As a result, the statistical distance between the simulated
view $S(x,f^{\prime\prime}_{I}(w,x))$ and the actual view
$\operatorname{view}_{I}^{\pi}(w,x)$ is effectively zero for all $w,x$.
Consequently, all components, except for $x$, are indistinguishable from
random values, thereby affirming the protocol’s privacy.

Moreover, since for each multiplication, only a new set of Beaver triples is
used, the values $\tilde{\gamma_{n}}$, $\tilde{\delta_{n}}$ are different from
$\tilde{\gamma_{n}^{\prime}}$, $\tilde{\delta_{n}^{\prime}}$ in the second
multiplication. Therefore, all these intermediate value remain
indistinguishable from random values.

Before discussing the actual and simulated views of the entire inversion
function, we first need to demonstrate that the local operations on share
values in inverse function do not reveal any information about the output
share of the second multiplication. As shown in this algorithm, each client
subtract its output share of the second multiplication (which we call
$w^{\prime}$) from twice of one of the input share of the multiplication, $x$.
Therefore, we need to demonstrate that simulator $S$ can mimic the actual
protocol’s computation:

$[\\![w^{\prime\prime}]\\!]=2\times[\\![x]\\!]-[\\![w^{\prime}]\\!]$

To ensure the indistinguishability of the simulated computation from the
actual protocol’s operation $2\times[\\![x]\\!]_{i}-[\\![w^{\prime}]\\!]_{i}$,
the simulator $S$ selects uniformly distributed and independent random
variables, $[\\![\tilde{x}]\\!]$ and $[\\![\tilde{w}^{\prime}]\\!]$. These
variables are crucial for mimicking the actual computation without revealing
any sensitive information about the output of the second multiplication,
$w^{\prime}$, or the input, $x$. By calculating
$[\\![\tilde{w}^{\prime\prime}]\\!]=2\times[\\![\tilde{x}]\\!]-[\\![\tilde{w}^{\prime}]\\!]$
with these selected variables, $S$ manages to simulate the operation in a way
that the outcome mirrors the distribution and independence characteristics of
the actual computation.

The above steps represent a single execution of the loop inside the inversion
function. To show the complete simulator view for this function, we need to
demonstrate the simulator view when these steps are repeated $k$ times:

$\displaystyle S(x_{I},f_{I}(x))=($
$\displaystyle\tilde{x}_{I},\tilde{y}_{I},\tilde{a}_{I}^{(1)},\tilde{b}_{I}^{(1)},\tilde{c}_{I}^{(1)},\tilde{a}_{I}^{\prime(1)},\tilde{b}_{I}^{\prime(1)},\tilde{c}_{I}^{\prime(1)},\tilde{\delta}_{2}^{(1)},$
$\displaystyle\tilde{\delta}_{3}^{(1)},\ldots,\tilde{\delta}_{n}^{(1)},\tilde{\delta}_{2}^{\prime(1)},\tilde{\delta}_{3}^{\prime(1)},\ldots,\tilde{\delta}_{n}^{\prime(1)},\tilde{\epsilon}_{2}^{(1)},\tilde{\epsilon}_{3}^{(1)},$
$\displaystyle\ldots,\tilde{\epsilon}_{n}^{(1)},\tilde{\epsilon}_{2}^{\prime(1)},\tilde{\epsilon}_{3}^{\prime(1)},\ldots,\tilde{\epsilon}_{n}^{\prime(1)},\ldots,\tilde{a}_{1}^{(k)},\tilde{b}_{1}^{(k)},$
$\displaystyle\tilde{c}_{1}^{(k)},\tilde{a}_{1}^{\prime(k)},\tilde{b}_{1}^{\prime(k)},\tilde{c}_{1}^{\prime(k)},\tilde{\delta}_{2}^{(k)},\tilde{\delta}_{3}^{(k)},\ldots,\tilde{\delta}_{n}^{(k)},$
$\displaystyle\tilde{\delta}_{2}^{\prime(k)},\tilde{\delta}_{3}^{\prime(k)},\ldots,\tilde{\delta}_{n}^{\prime(k)},\tilde{\epsilon}_{2}^{(k)},\tilde{\epsilon}_{3}^{(k)},\ldots,\tilde{\epsilon}_{n}^{(k)},\tilde{\epsilon}_{2}^{\prime(k)},$
$\displaystyle\tilde{\epsilon}_{3}^{\prime(k)},\ldots,\tilde{\epsilon}_{n}^{\prime(k)},\tilde{w}^{(1)},\tilde{w}^{\prime(1)},\tilde{w}^{\prime\prime(1)},\ldots,\tilde{w}^{(k)},$
$\displaystyle\tilde{w}^{\prime(k)},\tilde{w}^{\prime\prime(k)})$

Every component of $S$ is independent and uniformly random within
$\mathbb{Z}_{2^{k}}$, with the exception of $x$, which represents $P$’s
private input. As $S$ is designed to select values that are not only
independently and uniformly random but also drawn from the same distribution
as those in $\operatorname{view}_{I}^{\pi}$, these components become
indistinguishable. This indistinguishability, applicable to all components
other than $x$, ensures that they resemble random values, thus reinforcing the
privacy aspect of the protocol.

∎

######  Theorem 5 (privacy w.r.t semi-honest behavior).

Consider a secure multi-party computation protocol $\pi$ designed to compute a
function $f(x)$ utilizing the square root function (detailed in Section
3.2.4). This protocol involves $n$ parties, denoted as
$P_{1},P_{2},\ldots,P_{n}$, with a subset $I\subset[n]$ consisting of semi-
honest parties where at least one party is honest, while the rest are semi-
honest. The protocol $\pi$ is considered to privately compute the square root
function $f(x)$ if a probabilistic polynomial-time simulator $S_{i}$ can be
constructed such that, given all potential inputs, the simulated view of
$P_{i}$ is statistically indistinguishable from $P_{i}$’s actual view during
the execution of the protocol.

###### Proof.

The protocol $\pi$ ensures deterministic correctness by summing the outputs of
$n$ parties modulo $\mathbb{Z}_{2^{k}}$. Each party $P_{i}$ contributes a
specific output $w_{i}$ to the function $f(x)$. The privacy of $\pi$ is shown
by proving that for any input $x$, a simulator can generate a view for party
$P$ that is indistinguishable from its actual view during the protocol’s
execution, encompassing inputs, internal randomness, and received messages.

The square root function consists of four main operations on secret-shared
data: addition, multiplication by a public constant, Beaver multiplication and
inversion. The addition and the multiplication by a public constant operations
are executed locally on the secret-shared data.

The square root function begins with a ’for’ loop that iterates $k$ times,
with $k$ being fixed and known to all parties. Within this loop, the inverse
of the initial guess is computed. Subsequently, the output of the inversion
function is multiplied by the share of input of the square root function using
Beaver multiplication. Following this, the output of this multiplication is
locally added to the initial guess. Finally, the output from the previous
computation is multiplied by 1/2 to yield the final approved result for the
square root function.

We now define the actual view of $P$ within protocol $\pi$ for the square
function:

$\displaystyle\operatorname{view}_{I}^{\pi}(x)=($ $\displaystyle
x_{I},m^{inv(1)}_{2},m^{inv(1)}_{3},\ldots,m^{inv(1)}_{n},m^{mul(1)}_{2},$
$\displaystyle
m^{mul(1)}_{3},\ldots,m^{mul(1)}_{n},\ldots,m^{inv(k)}_{2},m^{inv(k)}_{3}$
$\displaystyle,\ldots,m^{inv(k)}_{n},m^{mul(k)}_{2},m^{mul(k)}_{3},\ldots,m^{mul(k)}_{n})$

where $x_{I}$ is a share of the input of square function,
$m^{inv}_{1},m^{inv}_{2},\ldots,m^{inv}_{n}$ are messages received by $P$ from
other parties for the inversion operation and
$m^{mul}_{2},m^{mul}_{3},\ldots,m^{mul}_{n})$ are messages received by $P$
from other parties for the Beaver multiplication operation in each of $k$
iterations.

All these elements, are additively shared between the parties or results of
the addition of two additively shared values. Therefore, based on the
definition in Algorithm 3.2, they are independent uniformly random within the
$\mathbb{Z}_{2^{k}}$ set.

Furthermore, from the $\operatorname{view}_{I}^{\pi}(x)$, $P$ can compute all
other relevant quantities and this view contains all of $P$’s information.

Now, we construct a simulator, denoted $S$, for the view of party $P$ that
simulates the computation of the square root function. The simulator $S$
begins by simulating the initial setup, including the distribution of the
secret-shared input $\tilde{Y_{1}}$ and the initial guess $\tilde{x_{0}}$ for
the square root computation. For the inversion operation, $S$ simulates the
messages received from other parties during the execution of the inverse
function $\tilde{m}^{inv}_{1},\tilde{m}^{inv}_{2},\ldots,\tilde{m}^{inv}_{n}$
and the outcome of the inversion function $\tilde{w}^{inv}$. According to
Theorem 4, the inverse function can be computed privately, and the simulator
can successfully simulate these exchanged messages, which are
indistinguishable from random values in $\mathbb{Z}_{2^{k}}$.

For the Beaver multiplication, $S$ simulates the Beaver triples and the
messages exchanged during the Beaver multiplication process
$\tilde{m}^{mul}_{1},\tilde{m}^{mul}_{2},\ldots,\tilde{m}^{mul}_{n}$. In
simulating the Beaver multiplication function, $S$ adheres to the privacy
guarantees provided by Theorem 3. Therefore, the simulator can successfully
simulate these exchanged messages, which are indistinguishable from random
values in $\mathbb{Z}_{2^{k}}$. Also, since in actual protocol, parties do not
reveal the shares of the output of Beaver multiplication function
$\tilde{w}^{mul}_{n}$, $S$ can simulate $\tilde{w}^{mul}_{1}$ as uniformly
random and independent values in $\mathbb{Z}_{2^{k}}$ that makes it
indistinguishable.

The final steps of the algorithm involve local computations by $P$, including
adding the result of Beaver multiplication (which is called here
$[\\![w^{\prime}]\\!]$) to the current estimate of square root (
$[\\![x_{n}]\\!]$) and then multiplying by $1/2$ to adjust for the next
iteration or final result. In this step, $S$ simulates these computations by
following the same steps, the simulator $S$ selects uniformly distributed and
independent random variables, $[\\![\tilde{w}^{\prime}]\\!]$ and
$[\\![\tilde{x_{n}}^{\prime}]\\!]$ from $\mathbb{Z}_{2^{k}}$ and compute the
final share value for the this round of approximation as follows:

$[\\![\tilde{x}_{n+1}]\\!]\leftarrow\frac{1}{2}\left([\\![\tilde{x}_{n}]\\!]+[\\!\tilde{[w^{\prime}]}\\!]\right)$

These steps effectively mimic the actual protocol’s computation, and since the
square root computation iterates this process $k$ times, $S$ repeats the
simulation for each iteration, updating the simulated values according to the
algorithm’s steps.

Now we show the complete simulator view for square function:

$\displaystyle S(x_{I},f_{I}(x))=($ $\displaystyle
x_{I},\tilde{m}^{inv(1)}_{2},\tilde{m}^{inv(1)}_{3},\ldots,\tilde{m}^{inv(1)}_{n},\tilde{m}^{inv}_{2},$
$\displaystyle\tilde{m}^{inv(2)}_{3},\ldots,\tilde{m}^{inv(2)}_{n},\ldots,\tilde{m}^{inv(k)}_{2},$
$\displaystyle\tilde{m}^{inv(k)}_{3},\ldots,\tilde{m}^{inv(k)}_{n},\tilde{m}^{mul(1)}_{2},$
$\displaystyle\tilde{m}^{mul(1)}_{3},\ldots,\tilde{m}^{mul(1)}_{n},\tilde{m}^{mul(2)}_{2},$
$\displaystyle\tilde{m}^{mul(2)}_{3},\ldots,\tilde{m}^{mul(2)}_{n},\ldots,\tilde{m}^{mul(k)}_{2},$
$\displaystyle\tilde{m}^{mul(k)}_{3},\ldots,\tilde{m}^{mul(k)}_{n},\tilde{w}^{mul(1)}_{1},$
$\displaystyle\tilde{w}^{mul(2)}_{1},\ldots,\tilde{w}^{mul(k)}_{1},\tilde{w}^{inv(1)}_{1},$
$\displaystyle\tilde{w}^{inv(2)}_{1},\ldots,\tilde{w}^{inv(k)}_{1})$

Every component of $S$ is independent and uniformly random within
$\mathbb{Z}_{2^{k}}$ which represents $P$’s private input. As $S$ is designed
to select values that are not only independently and uniformly random but also
drawn from the same distribution as those in $\operatorname{view}_{I}^{\pi}$,
these components become indistinguishable. This indistinguishability,
applicable to all components ensures that they resemble random values, thus
reinforcing the privacy aspect of the protocol.

∎

######  Theorem 6 (privacy w.r.t semi-honest behavior).

Consider a secure multi-party computation protocol $\pi$ designed to compute
the norm of a vector, as detailed in line 1-3 of Algorithm 3. This protocol
involves $n$ parties, denoted as $P_{1},P_{2},\ldots,P_{n}$, with a subset
$I\subset[n]$ consisting of semi-honest parties where at least one party is
honest, while the rest are semi-honest. Each party $P_{i}$ holds an additive
share of a set of private inputs $x$, where $x$ represents the collective
input vector shared among the parties. The protocol $\pi$ is said to privately
compute the norm function $f(x)$ if there exists a probabilistic polynomial-
time simulator $S$ that can simulate a view for any subset of parties that is
statistically indistinguishable from their actual views during the protocol’s
execution, given all potential inputs.

###### Proof.

The protocol $\pi$ guarantees deterministic correctness by computing the sum
of the outputs from $n$ parties modulo $\mathbb{Z}_{2^{k}}$, where each party
$P_{i}$ contributes an output $w_{i}$ corresponding to their share of the
computation of $f(x)$. To demonstrate the privacy of $\pi$, we show that for
any collective input $x$, a simulator $S$ can generate a simulated view for
any honest party or group of honest parties that mirrors their actual
experience during the protocol’s execution. This includes their inputs, the
internal randomness used, and the messages received from other parties.

The norm computation involves three key operations on secret-shared data:
Beaver multiplication for squaring the input vector, local summation of the
squared values, and finally, square root computation to derive the norm.

The actual view of $P_{I}$, for the computation is as follows:

$\operatorname{view}_{I}^{\pi}(x)=(x_{I},m^{mul}_{1},m^{mul}_{2},\ldots,m^{mul}_{n},m^{sqrt}_{1},m^{sqrt}_{2},\ldots,m^{sqrt}_{n}),$

where $x_{I}$ denotes the vector of additive shares of the input held by all
honest parties, $m^{mul}_{i}$ are the messages exchanged during the Beaver
multiplication, and $m^{sqrt}_{i}$ are the messages exchanged for the square
root computation.

Given the additive sharing scheme, all elements involved in
$\operatorname{view}_{I}^{\pi}(\vec{x})$ are independently and uniformly
distributed within $\mathbb{Z}_{2^{k}}$, ensuring that from $P$’s perspective,
all components are indistinguishable from random. This setup, based on the
privacy-preserving properties of Beaver multiplication and square root
operations, allows $S$ to simulate a plausible set of interactions that $P$
(or any group of honest parties) would observe, without revealing any private
information. The simulator $S$ thus constructs a simulated view that includes
simulated messages for each step of the norm computation, ensuring these
simulated components are indistinguishable from those in a real protocol
execution.

We construct a simulator, denoted $S$, for simulating the collective view of
honest parties in the vector norm computation within the SecureDL protocol.
The role of $S$ is to create a plausible simulation of the protocol execution
as it would appear to the honest parties, focusing on the data exchanges and
computations that occur without assuming control over the adversary’s direct
observations.

In the case of Beaver multiplication, $S$ simulates the Beaver triples and the
messages exchanged during this phase, such as
$\tilde{m}^{mul}_{1},\tilde{m}^{mul}_{2},\ldots,\tilde{m}^{mul}_{n}$. This
simulation is consistent with the privacy assurances specified in Theorem 3,
making these simulated messages indistinguishable from random values in
$\mathbb{Z}_{2^{k}}$ to any observer, thereby maintaining the integrity of the
privacy guarantees.

For local computations, including the summation of outputs, the simulator $S$
performs:

$[\\![\tilde{\text{sum}}]\\!]\leftarrow\sum_{i=1}^{n}[\\![\tilde{w}_{i}^{mul}]\\!],$

imitating the aggregation process faithfully without disclosing any
individual’s private data.

During the square root computation, $S$ constructs messages such as
$\tilde{m}^{sqrt}_{1},\tilde{m}^{sqrt}_{2},\ldots,\tilde{m}^{sqrt}_{n}$,
simulating the inter-party communications. These simulated messages are
crafted to be statistically indistinguishable from those in a genuine protocol
run, aligning with the privacy-preserving methodology of the square root
function described in Theorem 5.

Considering multiple honest parties, the simulated view $S$ provides for the
protocol includes the inputs of all such parties, denoted as
$x_{1},x_{2},\ldots,x_{m}$, where $m$ is the number of honest parties. Thus,
the complete simulator view is represented as:

$S(x_{I},f_{I}(x))=(x_{I},\tilde{m}^{mul}_{1},\tilde{m}^{mul}_{2},\ldots,\tilde{m}^{mul}_{n},\tilde{m}^{sqrt}_{1},\tilde{m}^{sqrt}_{2},\ldots,\tilde{m}^{sqrt}_{n}),$

Each component of $S$ is independently and uniformly random within
$\mathbb{Z}_{2^{k}}$, ensuring that the simulation reflects the private inputs
and the exchange of messages among honest parties, all while remaining
indistinguishable from a real execution to any external observer.

∎

######  Theorem 7 (privacy w.r.t semi-honest behavior).

Consider a secure multi-party computation protocol $\pi$ designed to compute a
function $f(x,y)$, utilizing the cosine similarity computation between two
vectors (as detailed in Section 2). This protocol involves $n$ parties,
denoted as $P_{1},P_{2},\ldots,P_{n}$, with a subset $I\subset[n]$ consisting
of semi-honest parties where at least one party is honest, while the rest may
be semi-honest. Each party $P_{i}$ possesses an additive share of the private
inputs $x$ and $y$. The protocol $\pi$ is considered to effectively compute
the cosine similarity function $f(x,y)$ in a private manner if a probabilistic
polynomial-time simulator $S$ can be constructed. For any given set of
potential inputs, the simulated view of $P_{i}$ should be statistically
indistinguishable from $P_{i}$’s actual view during the execution of the
protocol.

###### Proof.

The protocol $\pi$ ensures deterministic correctness by summing the outputs of
$n$ parties modulo $\mathbb{Z}_{2^{k}}$. Each party $P_{i}$ contributes a
specific output $w_{i}$ to the function $f(x,y)$. The privacy of $\pi$ is
shown by proving that for any inputs $x$ and $y$, a simulator can generate a
view for party $P$ that is indistinguishable from its actual view during the
protocol’s execution, encompassing inputs, internal randomness, and received
messages.

In the first step of the cosine similarity computation function, the dot
product of the inputs should be computed. In our work, a single Beaver
multiplication is utilized to perform this operation. Following this, the norm
of each vector is computed, and then these norm values are multiplied using
Beaver triple multiplication. Subsequently, the inverse of this multiplication
needs to be computed. Finally, the result of that last step is multiplied by
the dot product results computed in the first step to calculate the final
output of the cosine similarity function.

We now define the actual view of $P$ within protocol $\pi$ for the square
function:

$\displaystyle\operatorname{view}_{I}^{\pi}(x,y)=($ $\displaystyle
x_{I},y_{I}m^{mul_{1}}_{1},m^{mul_{1}}_{2},\ldots,m^{mul_{1}}_{n},m^{norm_{1}}_{1},$
$\displaystyle
m^{norm_{1}}_{2},\ldots,m^{norm_{1}}_{n},m^{norm_{2}}_{1},m^{norm_{2}}_{2},\ldots,$
$\displaystyle
m^{norm_{2}}_{n},m^{mul_{2}}_{1},m^{mul_{2}}_{2},\ldots,m^{mul_{2}}_{n},m^{inv}_{1},$
$\displaystyle
m^{inv}_{2},\ldots,m^{inv}_{n},m^{mul_{3}}_{1},m^{mul_{3}}_{2},\ldots,m^{mul_{3}}_{n})$

where $x_{I}$ and $y_{I}$ are the share of the inputs of norm computation
function, $m^{mul_{1}}_{1},m^{mul_{1}}_{2},\ldots,m^{mul_{1}}_{n}$,
$m^{mul_{2}}_{1},m^{mul_{2}}_{2},\ldots,m^{mul_{2}}_{n}$ and
$m^{mul_{3}}_{1},m^{mul_{3}}_{2},\ldots,m^{mul_{3}}_{n}$ are messages received
by $P$ from other parties for the Beaver multiplication operations and
$m^{norm_{1}}_{1},m^{norm_{1}}_{2},\ldots,m^{norm_{1}}_{n}$ and
$m^{norm_{2}}_{1},m^{norm_{2}}_{2},\ldots,m^{norm_{2}}_{n}$ are messages
received by $P$ from other parties for the norm computation operation and
finally $m^{inv}_{1},m^{inv}_{2},\ldots,m^{inv}_{n}$ are messages received by
$P$ from other parties for the inversion operation.

All these elements, are additively shared between the parties or results of
the addition of two additively shared values. Therefore, based on the
definition in Algorithm 3.2, they are independent uniformly random within the
$\mathbb{Z}_{2^{k}}$ set. Furthermore, from the
$\operatorname{view}_{I}^{\pi}(x,y)$, $P$ can compute all other relevant
quantities and this view contains all of $P$’s information.

Now, we construct a simulator, denoted $S$, for the view of party $P$ that
simulates the computation of the cosine similarity computation function. The
simulator $S$ begins by simulating the initial setup, including the of the
secret-shared inputs $\tilde{w_{a}}$ and $\tilde{w_{b}}$. For the Beaver
multiplications, $S$ simulates the Beaver triples and the messages exchanged
during the Beaver multiplication process
$\tilde{m}^{mul_{1}}_{1},\tilde{m}^{mul_{1}}_{2},\ldots,\tilde{m}^{mul_{1}}_{n}$,
$\tilde{m}^{mul_{2}}_{1},\tilde{m}^{mul_{2}}_{2},\ldots,\tilde{m}^{mul_{2}}_{n}$
. In simulating the Beaver multiplication function, $S$ adheres to the privacy
guarantees provided by Theorem 3. Therefore, the simulator can successfully
simulate these exchanged messages, which are indistinguishable from random
values in $\mathbb{Z}_{2^{k}}$. Also, since in actual protocol, parties do not
reveal the shares of the output of Beaver multiplication functions in any
steps $\tilde{w}^{mul_{1}}_{n}$,$\tilde{w}^{mul_{2}}_{n}$and
$\tilde{w}^{mul_{3}}_{n}$, $S$ can simulate them as uniformly random and
independent values in $\mathbb{Z}_{2^{k}}$ that makes it indistinguishable.

Next step involves vector norm computations, $S$ simulates the messages
exchanged during the computation process
$\tilde{m}^{norm_{1}}_{1},\tilde{m}^{norm_{1}}_{2},\ldots,\tilde{m}^{norm_{1}}_{n}$
and
$\tilde{m}^{norm_{2}}_{1},\tilde{m}^{norm_{2}}_{2},\ldots,\tilde{m}^{norm_{2}}_{n}$
. In simulating the norm computation function, $S$ adheres to the privacy
guarantees provided by Theorem 6. Therefore, the simulator can successfully
simulate these exchanged messages, which are indistinguishable from random
values in $\mathbb{Z}_{2^{k}}$. Also, since in actual protocol, parties do not
reveal the shares of the output of norm functions in any steps
$\tilde{w}^{norm_{1}}_{n}$ and $\tilde{w}^{norm_{2}}_{n}$, $S$ can simulate
them as uniformly random and independent values in $\mathbb{Z}_{2^{k}}$ that
makes it indistinguishable.

Finally, the inversion computation operation, $S$ simulates the messages
received from other parties during the execution of this function
$\tilde{m}^{inv}_{1},\tilde{m}^{inv}_{2},\ldots,\tilde{m}^{inv}_{n}$ and the
outcome of the inversion function $\tilde{w}^{inv}$. According to Theorem 4,
the inversion function can be computed privately, and the simulator can
successfully simulate these exchanged messages, which are indistinguishable
from random values in $\mathbb{Z}_{2^{k}}$. Also, since in actual protocol,
parties do not reveal the shares of the output of inversion function
$\tilde{w}^{inv}_{n}$, $S$ can simulate $\tilde{w}^{inv}_{1}$ as uniformly
random and independent values in $\mathbb{Z}_{2^{k}}$ that makes it
indistinguishable.

Now we show the complete simulator view for cosine similarity computation:

$\displaystyle S(x_{I},f_{I}(x,y))=($ $\displaystyle
x_{I},y_{I},\tilde{m}^{mul_{1}}_{1},\tilde{m}^{mul_{1}}_{2},\ldots,\tilde{m}^{mul_{1}}_{n},\tilde{m}^{mul_{2}}_{1}$
$\displaystyle,\tilde{m}^{mul_{2}}_{2},\ldots,\tilde{m}^{mul_{2}}_{n}\,\tilde{m}^{mul_{3}}_{1},\tilde{m}^{mul_{3}}_{2},\ldots,$
$\displaystyle\tilde{m}^{mul_{3}}_{n}\,\tilde{m}^{norm_{1}}_{1},\tilde{m}^{norm_{1}}_{2},\ldots,\tilde{m}^{norm_{1}}_{n},$
$\displaystyle\tilde{m}^{norm_{2}}_{1},\tilde{m}^{norm_{2}}_{2},\ldots,\tilde{m}^{norm_{2}}_{n},\tilde{m}^{inv}_{1},\tilde{m}^{inv}_{2}$
$\displaystyle,\ldots,\tilde{m}^{inv}_{n})$

Every component of $S$ is independent and uniformly random within
$\mathbb{Z}_{2^{k}}$ which represents $P$’s private input. As $S$ is designed
to select values that are not only independently and uniformly random but also
drawn from the same distribution as those in $\operatorname{view}_{I}^{\pi}$,
these components become indistinguishable. This indistinguishability,
applicable to all components ensures that they resemble random values, thus
reinforcing the privacy aspect of the protocol.

∎

######  Theorem 8 (privacy w.r.t semi-honest behavior).

Consider a secure multi-party computation protocol $\pi$ designed to compute a
function $f(x,y)$ utilizing the L2-Normalization computation between two
vectors (detailed in Section 3). This protocol involves $n$ parties, denoted
as $P_{1},P_{2},\ldots,P_{n}$, with a subset $I\subset[n]$ consisting of semi-
honest parties where at least one party is honest, while the rest are semi-
honest. The protocol $\pi$ is considered to privately compute the cosine
similarity function $f(x,y)$ if a probabilistic polynomial-time simulator
$S_{i}$ can be constructed such that, given all potential inputs, the
simulated view of $P_{i}$ is statistically indistinguishable from $P_{i}$’s
actual view during the execution of the protocol.

###### Proof.

The protocol $\pi$ ensures deterministic correctness by summing the outputs of
$n$ parties modulo $\mathbb{Z}_{2^{k}}$. Each party $P_{i}$ contributes a
specific output $w_{i}$ to the function $f(x,y)$. The privacy of $\pi$ is
shown by proving that for any inputs $x$ and $y$, a simulator can generate a
view for party $P$ that is indistinguishable from its actual view during the
protocol’s execution, encompassing inputs, internal randomness, and received
messages.

In the first step of the L2-Normalization function, the norm of each input
vector is computed. Then, the inverse of $[\\![\mathbf{w}_{a}]\\!]$, the
vector to be normalized, is computed. Following this, the inverse value is
multiplied by the norm of the reference vector $[\\![\mathbf{w}_{b}]\\!]$
using the Beaver multiplication function. Finally, the output of this
multiplication is multiplied by $[\\![\mathbf{w}_{a}]\\!]$ using the Beaver
multiplication function to produce the final output.

We now define the actual view of $P$ within protocol $\pi$ for the square
function:

$\displaystyle\operatorname{view}_{I}^{\pi}(x,y)=($ $\displaystyle
x_{I},y_{I}m^{mul_{1}}_{1},m^{mul_{1}}_{2},\ldots,m^{mul_{1}}_{n},m^{norm_{1}}_{1},$
$\displaystyle
m^{norm_{1}}_{2},\ldots,m^{norm_{1}}_{n},m^{norm_{2}}_{1},m^{norm_{2}}_{2},\ldots,$
$\displaystyle
m^{norm_{2}}_{n},m^{mul_{2}}_{1},m^{mul_{2}}_{2},\ldots,m^{mul_{2}}_{n},m^{inv}_{1},$
$\displaystyle m^{inv}_{2},\ldots,m^{inv}_{n})$

where $x_{I}$ is a share of the input of norm computation function,
$m^{mul_{1}}_{1},m^{mul_{1}}_{2},\ldots,m^{mul_{1}}_{n}$, and
$m^{mul_{2}}_{1},m^{mul_{2}}_{2},\ldots,m^{mul_{2}}_{n}$ are messages received
by $P$ from other parties for the Beaver multiplication operations and
$m^{norm_{1}}_{1},m^{norm_{1}}_{2},\ldots,m^{norm_{1}}_{n}$ and
$m^{norm_{2}}_{1},m^{norm_{2}}_{2},\ldots,m^{norm_{2}}_{n}$ are messages
received by $P$ from other parties for the norm computation operation and
finally $m^{inv}_{1},m^{inv}_{2},\ldots,m^{inv}_{n}$ are messages received by
$P$ from other parties for the inversion operation.

All these elements, are additively shared between the parties or results of
the addition of two additively shared values. Therefore, based on the
definition in Algorithm 3.2, they are independent uniformly random within the
$\mathbb{Z}_{2^{k}}$ set. Furthermore, from the