# Privacy-Preserving, Dropout-Resilient Aggregation in Decentralized Learning

Ali Reza Ghavamipour, Benjamin Zi Hao Zhao, Fatih Turkmen

###### Abstract.

Decentralized learning (DL) offers a novel paradigm in machine learning by
distributing training across clients without central aggregation, enhancing
scalability and efficiency. However, DL’s peer-to-peer model raises challenges
in protecting against inference attacks and privacy leaks. By forgoing central
bottlenecks, DL demands privacy-preserving aggregation methods to protect data
from ’honest but curious’ clients and adversaries, maintaining network-wide
privacy. Privacy-preserving DL faces the additional hurdle of client dropout,
clients not submitting updates due to connectivity problems or unavailability,
further complicating aggregation.

This work proposes three secret sharing-based dropout resilience approaches
for privacy-preserving DL. Our study evaluates the efficiency, performance,
and accuracy of these protocols through experiments on datasets such as MNIST,
Fashion-MNIST, SVHN, and CIFAR-10. We compare our protocols with traditional
secret-sharing solutions across scenarios, including those with up to 1000
clients. Evaluations show that our protocols significantly outperform
conventional methods, especially in scenarios with up to 30% of clients
dropout and model sizes of up to $10^{6}$ parameters. Our approaches
demonstrate markedly high efficiency with larger models, higher dropout rates,
and extensive client networks, highlighting their effectiveness in enhancing
decentralized learning systems’ privacy and dropout robustness.

##  1\. Introduction

Machine learning (ML) has become a pivotal component in numerous applications,
including pattern recognition, medical diagnosis, and credit risk assessment.
The effectiveness of a machine learning model is heavily dependent on the
availability of large volumes of data. The conventional method of training a
machine learning model involves collecting a dataset on a central server and
conducting the training process on this server. However, centralization poses
difficulties when the data is distributed over numerous devices or among a
workforce that are located in different geographical regions. This issue is
compounded by growing concerns over data privacy. To address these challenges,
researchers have suggested alternative approaches to centralized learning
under the umbrella term Collaborative Machine Learning (CML). CML enables the
training of machine learning models directly on local devices to enhance
privacy (by maintaining data locality) and offload compute demand (away from
the central server) (Li et al., 2020).

Federated Learning (FL) (McMahan et al., 2017), a key example of CML, has
garnered notable interest across academia and industry. It decentralizes the
training process across multiple clients, ranging from mobile devices to data
centers, under the coordination of a central server. Clients locally update
the model using their data, then share these updates with the server, which
aggregates them for distribution. While FL facilitates training in novel
contexts, it relies heavily on a central server, introducing risks like a
single point of failure and challenges in maintaining model integrity and data
privacy (Bonawitz et al., 2019).

Decentralized Learning (DL) (Lian et al., 2017; Beltrán et al., 2023;
Koloskova et al., 2019; Hegedűs et al., 2021) emerged as a popular, scalable,
and communication-efficient alternative to traditional CML algorithms. Unlike
FL methods, DL operates without a central aggregator, thereby mitigating
integrity and privacy risks associated with the central server in FL, and more
importantly avoiding a (potentially untrusted) single point of failure. DL
achieves global model training through on-device aggregation of model
parameters, facilitated by peer-to-peer exchanges among clients (Hegedűs et
al., 2019). This process, akin to gossip-based algorithms in random networks
eliminates the need for centralized aggregation. In DL, each client plays an
active role in updating its model using both local data and updates from its
peers, leading to improvements in model accuracy and faster convergence.

As we have established, the practice of sharing model updates instead of raw
datasets mitigates privacy concerns related to the centralization of data for
learning. Unfortunately, CML retain risks of private information leakage
(Boenisch et al., 2023; Wen et al., 2022), as a passive adversary can infer
sample membership (Shokri et al., 2017; Zhao et al., 2021) and reconstruct
training data (Luo et al., 2021) from the shared updates of honest users.
Moreover, DL systems are especially susceptible to said privacy risk, as the
architecture of DL requires all clients to share their updates with every
other client for aggregation, thereby providing any client the opportunity to
launch the aforementioned privacy attacks (Pasquini et al., 2023).

To mitigate these privacy concerns, secure aggregation is proposed to prevent
the aggregator(s) from inferring private data from local model updates
(Ghavamipour et al., 2023, 2022; Fereidooni et al., 2021; So et al., 2022).
However, implementing secure aggregation faces implementation challenges
because of client dropout (as depicted in Figure 1). The issue of Dropout
arises when a client fails to submit its model updates or cannot participate
in the secure aggregation procedure due to poor network connections, energy
constraints, or temporary unavailability. Such dropout can disrupt the secure
aggregation process, necessitating a restart of the round, potentially leading
to a Denial of Service (DoS) effect on model training.

In this work, we introduce three novel secret sharing-based protocols designed
for privacy-preserving aggregation within decentralized learning environments.
These protocols enable dropout-resilient aggregation, merging clients’ local
models into a global model while ensuring the privacy of individual data
contributions. Our approaches not only effectively mitigate privacy risks
posed by ’honest but curious’ clients but also uphold the integrity of the
learning process despite varying levels of client participation, thereby
enhancing dropout resilience. The underlying techniques are inspired by their
proven effectiveness in federated learning. However, our contribution lies in
adapting and refining these techniques to address the unique challenges of
secure decentralized learning. This adaptation extends their applicability and
enhances the privacy and security framework of the learning process,
especially by incorporating mechanisms for dropout resilience. To validate the
effectiveness of our proposed protocols, we conducted a comprehensive
evaluation across multiple datasets, demonstrating their robustness and
scalability in diverse learning scenarios.

##  2\. Related work

Research on privacy-preserving and dropout-resilient FL is extensive, yet
studies tackling similar issues in DL are notably fewer (Pasquini et al.,
2023). In this respect, PPDL stands out as the first to directly address
dropout challenges in the realm of privacy-enhanced DL.

In the context of FL, various strategies have been developed for performing
privacy-preserving aggregation with a limited outlook on resiliency to client
dropout. Most existing works focus on combining federated training with
Differential Privacy (DP) (Dwork, 2006), Homomorphic Encryption (HE) (Gentry,
2009), and secure Multi-Party Computation (MPC) (Canetti et al., 1996). Since
dropout has an impact on the privacy protection mechanism employed in the
aggregation method, highlighting the differences between these methodologies
in terms of privacy guarantees, efficiency, and the implementation challenges
is important.

Approaches employing homomorphic encryption result in significant performance
overheads (Truex et al., 2019). This technique requires all clients to either
share a common secret key or hold shares of a secret key (Aono et al., 2017;
Zhang et al., 2020). These shares must be generated through complex multi-
party protocols or distributed by a trusted third party (Truex et al., 2019),
which results in prohibitive overheads for large-scale CML systems (Zhang et
al., 2022). Moreover, supporting dropout resilience in conjunction with
homomorphic encryption poses an additional challenge, as it requires
sophisticated mechanisms to handle the potential discontinuity in
participation without compromising the security or the integrity of the
aggregated model updates (Tian et al., 2022).

As a more scalable and dropout-resistant alternative, MPC has been proposed
(Bonawitz et al., 2017). In this model, users’ data is masked, with the seeds
for generating these masks securely distributed among the users through a
threshold secret-sharing scheme to manage client dropouts. An improvement on
this approach, (Bell et al., 2020) replaces the complete communication graph
with a $k$-regular graph (i.e., every vertex having a degree of $k$), reducing
communication overhead. A DP-based FL method has been introduced where noise
is added to each client’s locally trained model before aggregation (Geyer et
al., 2017), effectively masking the data distribution of the clients. However,
this method requires careful balancing between the level of privacy maintained
and the impact on the model’s performance due to perturbation.

Guo et al. (Guo et al., 2021) pioneered the application of differential
privacy in decentralized learning through the introduction of LEASGD, which
enhances a stochastic gradient descent algorithm with privacy protection and
noise reduction strategies. While this method effectively maintains privacy at
the model level, there is a competing trade-off in the utility of the model.
Further advancing the field, Bellet et al. (Bellet et al., 2018) devised a
fully decentralized algorithm for training personalized ML models, embedding
differential privacy to safeguard individual data privacy. Further, Xu et al.
(Xu et al., 2022) presents $D^{2}$-MHE, a secure and efficient framework for
decentralized deep learning that employs advanced homomorphic encryption
techniques for the private updating of gradients. This method notably
decreases communication complexity and provides robust data privacy
safeguards. It emphasizes training models in an encrypted format, leveraging
sophisticated cryptographic schemes such as Brakerski-Fan-Vercauteren (BFV)
and Cheon-Kim-Kim-Song (CKKS). Despite its advantages in guaranteed
protections of client updates, (Xu et al., 2022) remains burdened by
inefficient computation and does not address functional implications of client
dropout in deployment as we do with PPDL.

##  3\. Preliminaries

In this section, we provide the necessary background on decentralized
learning, and introduce the building blocks used to provide privacy of updates
and resilience against dropouts in PPDL.

Figure 1. Collaborative learning system in a federated (left) and
decentralized fashion when Client 4 has dropped out.

###  3.1. Learning in a Decentralized Setting

In a decentralized learning framework, each participant, denoted as $c$ within
the user subgroup $C$, establishes communication links directly with a
designated subset referred to as their neighbors $\mathbf{N}(c)$. These links
can be either static, established at the outset, or dynamic, subject to change
over time. The ensemble of users forms an undirected graph represented by
$G=(C,\cup_{c\in C,~{}c^{\prime}\in\mathbf{N}(c)}(c,c^{\prime}))$ , where the
vertices represent the users and the edges denote the connections among them
(Lian et al., 2017).

In this environment, each participant $c$ possesses a unique dataset
$D_{i}=\left\\{\left(x_{i},y_{i}\right)\right\\}_{i}$ that is sampled from an
undisclosed distribution $\xi_{i}$. When these individual datasets are
amalgamated, they form a comprehensive global dataset $D$ characterized by the
distribution $\xi$. Initially, every participant is equipped with a common set
of initial model parameters, labeled as $w^{0}$.

The objective of the training endeavor is to discover the optimal set of
parameters, represented by $\mathbf{w}^{*}$, for the machine learning model.
$\mathbf{w}^{*}$ aims to minimize the expected loss function over the 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}}$

For every client $n_{i}$ within the network, $\mathbb{E}_{s_{i}\sim
D_{i}}\left[\mathcal{L}\left(\theta;s_{i}\right)\right]$ determines the
expected loss associated with the dataset $D_{i}$ of that specific client,
with $s_{i}$ representing a sample drawn from $D_{i}$. Consequently, the goal
of this formulation is to identify the model parameters $\theta$ that lead to
the minimization of the average expected loss across all clients in the
network.

1

2

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

User local training data: $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

We summarize the decentralized training of ML models in Algorithm 1. The
process unfolds through a sequence of stages until a specified termination
point (e.g., convergence). Initially, each client $c$ performs gradient
descent on their unique model parameters, leading to the generation of an
interim model update, denoted as $w_{c}^{t+1/2}$. Subsequently, these clients
exchange their interim model updates $w_{c}^{t+1/2}$ with their network
neighbors ($\mathbf{N}(c)$), while also receiving updates from these
neighbors.

Following the exchange, clients aggregate the updates received from their
neighbors with their own. This aggregation typically involves averaging the
updates to modify their local state, expressed mathematically as
$w^{t+1}=\frac{1}{|\mathbf{N}(c)|}\sum_{c\in\mathbf{N}(c)}w_{c}^{t+1/2}$ that
signifies the collective adjustment based on the aggregated updates.

In this study, we assume that the clients exhibit full connectivity, which
implies that every client is directly connected to all other clients within
each subgroup. This full connectivity framework ensures that every client can
directly exchange information with every other client in its subgroup,
facilitating a comprehensive and synchronous training process across the
network.

###  3.2. Shamir’s Secret Sharing

Shamir’s Secret Sharing (SSS) Scheme (Shamir, 1979) allows a secret $s$ to be
divided into $n$ pieces, known as shares, using a $t$-out-of-$n$ scheme. Any
group of $t$ or more shares can be used to reconstruct the secret $s$. The
process is as follows:

  * •

To generate shares from a secret $s$, by using the function
$Ss.Share(s,t,n)$, $t-1$ random positive integers $a_{1},\ldots,a_{t-1}$ are
selected from a finite field $\mathbb{Z}_{P}$, with $a_{0}=s$ representing the
secret. Let $f(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots+a_{t-1}x^{t-1}\mod P$ be a
polynomial with coefficients from $\mathbb{Z}_{P}$, where
$\mathcal{U}=\\{u_{i}|u_{i}\in[1,P]\\}$ is a set of $n$ random numbers and
$0<t\leq n<P$. The shares are then
$\\{(u_{i},s_{i})\\}_{u_{i}\in\mathcal{U}}=\\{(u_{i},f(u_{i}))\\}_{u_{i}\in\mathcal{U}}$.

  * •

To reconstruct the secret $s$ from shares using $Ss.Recon\\\
(\\{(u_{i},s_{i})\\}_{u_{i}\in\mathcal{U}},t)$, any subset of $t$ shares can
be used for the recovery of $s$ through Lagrange interpolation. Since
$a_{0}=s$, the secret is efficiently found as
$s=a_{0}=f(0)=\sum_{j=0}^{t}f(u_{j})\\\ \prod_{i=0,i\neq
j}^{t}\frac{u_{i}}{u_{i}-u_{j}}\mod P$.

Moreover, SSS method inherently supports operations that resemble additive
homomorphism, allowing for the direct combination of secrets. If the index $i$
and the corresponding element $u_{i}$ of any share in the set
$\\{(u_{i},s_{i})\\}_{u_{i}\in\mathcal{U}}$ for a given secret $s$ match the
index and element $v_{i}$ in another set
$\\{(v_{i},s^{\prime}_{i})\\}_{v_{i}\in\mathcal{V}}$ for a different secret
$s^{\prime}$, the secrets can be seamlessly combined. The combined secret
$s+s^{\prime}$ can be efficiently reconstructed by applying the reconstruction
function $Ss.Recon$ on these merged shares.

The security of Shamir’s $t$-out-of-$n$ secret sharing ensures that for any
two sets of shares $U,V$ both less than threshold $t$, the output of
$Ss.Recon(V)$ is indistinguishable from $Ss.Recon(U)$, thereby maintaining the
confidentiality of the secret $s$.

###  3.3. Diffie-Hellman Key Agreement Protocol

The Diffie-Hellman (DH) key agreement protocol (Hellman, 1976) is structured
around probabilistic polynomial-time (PPT) algorithms, as outlined below:

Parameter Generation:
$(\mathbb{G}^{\prime},g,q,H)\leftarrow\text{DH}\text{Param}(\kappa)$: Given a
security parameter $\kappa$, this algorithm generates a cyclic group
$\mathbb{G}^{\prime}$ of prime order $q$ and a generator $g$ of the group, and
specifies a hash function $H$, such as SHA-256, for hashing purposes.

Key Generation: $(s,g^{s})\leftarrow\text{DHGen}(\mathbb{G}^{\prime},g,q)$:
This algorithm selects a secret key $s$ from the integer group
$\mathbb{Z}_{q}$ and computes $g^{s}$ as its corresponding public key.

Key Agreement: $s_{a,b}\leftarrow\text{DHAgree}(s_{a},g^{s_{b}})$: For a
secret key $s_{a}$ and a public key $g^{s_{b}}$, generated by another party’s
secret key $s_{b}$, this algorithm produces the shared secret key
$s_{a,b}=H((g^{s_{b}})^{s_{a}})$, leveraging the hash function $H$ for the
final key derivation.

The security of the DH key agreement protocol, when deployed to protect
against honest-but-curious adversaries, relies on a fundamental cryptographic
principle known as the Decisional Diffie-Hellman (DDH) assumption (Boneh,
1998). This assumption secures the protocol by rendering it computationally
difficult to differentiate between instances of the DH exchange and random
group elements.

##  4\. Problem Definition

Recall that in a collaborative learning setting, an honest client aims to
obtain an aggregated model update that integrates local models trained on
other clients’ private datasets. The hidden aggregation of these updates helps
mitigate privacy risks to client datasets in two main ways. First, it protects
individual local models from malicious scrutiny by obscuring specific details,
preventing adversaries from identifying and exploiting exact data sources.
Second, it reduces the impact of any single client’s input by merging
contributions from multiple clients into the aggregated model.

In FL, a central server collects model updates from clients before
distributing the aggregated results back to them. This centralized approach
ensures that only the server can access each client’s individual updates.
However, in DL, the absence of a central server elevates privacy risks, as
updates must be shared directly between clients for aggregation (Pasquini et
al., 2023). These risks can be mitigated by implementing secure aggregation
schemes.

Moreover, when secure aggregation is implemented in a collaborative learning
setting, client dropout poses a significant challenge (Bonawitz et al., 2017).
Clients may exit the aggregation process before sharing their model updates
due to latency, network connectivity issues, or unexpected shutdowns. This can
occur before they share their updates with any other clients or after having
distributed them to everyone. Since dropout is a prevalent concern in deployed
systems, designing systems resilient to client dropouts up to a certain
threshold is vital.

This work presents privacy-preserving DL algorithms that are resilient to
dropout, ensuring the model remains accurate and operationally efficient.

###  4.1. Threat model

The threat model considered in this paper encompasses a landscape dominated by
non-malicious yet curious clients operating under the assumption of an honest
majority. While adhering to the established protocols of the system, these
’honest-but-curious’ clients want to obtain or infer additional information
about their peers through the interactions of DL. Their approach does not
involve transmitting incorrect or manipulated data; instead, they aim to
derive as much insight as possible from the communication flows inherent in
the learning process. Adding to this complexity, we consider the scenario
where a semi-honest client may collude with others. This collusion aims to
pool resources and shared insights to enhance their collective ability to
infer private information beyond what is intended through the system’s
interactions.

Therefore, the threat model underscores the need for advanced mechanisms to
manage individual curiosity-driven inference attacks and collaborative efforts
among semi-honest clients. These mechanisms are vital for providing robust
privacy assurances when deployed in realistic environments, protecting private
local data against these enhanced potential privacy risks.

##  5\. Approaches

In this section, we introduce three distinct approaches for implementing
secure aggregation in DL environments, emphasizing the incorporation of
dropout resilience.

###  5.1. SA using Shamir’s secret sharing

This method allows clients to work together to build a shared model vector,
$W$, enhancing resilience against dropout by enabling the model’s
reconstruction even if some clients do not contribute. Each client
participates in the aggregation process by supplying vectors made up of field
elements from a field of size $q$. This arrangement aligns with the objectives
of the decentralized model. The approach not only addresses the complexities
of distributed computation but also introduces an effective mechanism for
managing client dropout. It ensures the confidentiality and integrity of the
model aggregation process, eliminating the need for a centralized server.

1

2

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

Number of global iterations $R_{g}$

Shamir’s threshold $t$ (e.g., $t=(n/2)+1$)

Output : A globally trained model $\mathbf{w}$ for each client

3 for  _$r=1$ to $R_{g}$_ do

// Initialization step

4 All clients start with the same initial model $\mathbf{w}^{0}$.

5 for  _$i=0$ to $n$_ do

6 Train local model:
$\mathbf{w}_{i}\leftarrow\text{LocalUpdate}(\mathbf{w}^{r-1},D_{i})$

7

8 Generate and distribute $n$ shares of $\mathbf{w}_{i}$, denoted as
$\llbracket\mathbf{w}_{i}\rrbracket_{j}$ for $j=0,1,\ldots,n$, to all clients,
including itself

9

10 Receive shares $\llbracket\mathbf{w}_{j}\rrbracket_{i}$ from all other
clients

11

12 Aggregate own share with received shares from other clients:
$\llbracket\mathbf{\bar{w}}\rrbracket_{i}=\sum_{\begin{subarray}{c}j=0\\\
j\neq
i\end{subarray}}^{n}\llbracket\mathbf{w}_{j}\rrbracket_{i}+\llbracket\mathbf{w}_{i}\rrbracket_{i}$

13

14 Transmit $\llbracket\mathbf{\bar{w}}\rrbracket_{i}$ to all other clients
and receive $\llbracket\mathbf{\bar{w}}\rrbracket_{j}$ from them

15

16 if  _total shares received $\geq t$_ then

17 Perform Shamir Reconstruction to obtain $\mathbf{\bar{w}}$ and update
global model: $\hat{\mathbf{w}}^{r}=\frac{1}{n}\mathbf{\bar{w}}$

18

19

20

Algorithm 2 PPDL-NV: Secure Aggregation via Shamir’s Secret Sharing for PPDL

In this approach summarized in Algorithm 2, each client $P_{i}$ generates $n$
shares for each element of their input vector $w_{i}$, adhering to a
predetermined threshold $t$. The threshold $t$ should exceed the number of
semi-honest clients to protect the integrity and confidentiality of the
aggregation process. Next, each client distributes one share to the other
clients while retaining a share for itself. Subsequently, clients aggregate
the shares of the secret value received from others with their own and
broadcast the cumulative value to all participants. Once sufficient shares of
these combined values are collected, every client can reconstruct the
aggregated value.

Although this approach inherently tolerates dropouts, the inefficiency of
traditional Shamir’s Secret Sharing in a decentralized setting primarily stems
from the extensive number of secret values that need to be shared. These
secret values correlate directly with the number of model weights, resulting
in excessive communication and computation overheads.

Improvements to this inefficiency can be achieved by utilizing Packed Shamir
Secret Sharing (Franklin and Yung, 1992), a drop-in adaptation of Shamir’s
Secret Sharing in all three of our proposed approaches. Packed Shamir Secret
Sharing significantly improves communication and computation efficiency by
including multiple values within a single share. The packed secret sharing
method has the capacity to split $k$ secret values into $n$ shares while
requiring at least $t+k$ shares to recover the secret. Despite these
improvements, this proposed scheme’s naive application, still observes the
vector size for secret sharing still correlating with the model’s parameter
size. The packing only lowers the per-client communication burden,
particularly with large-scale models.

####  5.1.1. Security Analysis

In this part, we explore the security features of the PPDL-NV algorithm in
detail:

###### Theorem 1.

The $PPDL-NV$ protocol, which utilizes SSS to distribute model updates as $n$
shares within a finite field $\mathbb{F}_{q}$ among clients, ensures security
against semi-honest adversaries and exhibits resilience to client dropout in
the honest majority setting.

###### Proof.

In PPDL-NV protocol, Shamir’s Secret Sharing (SSS) ensures the confidentiality
of model updates. Each element of a model update $s$ is divided into $n$
shares within a finite field $\mathbb{F}_{q}$ (assuming $n<q$), according to
$A(x)=\sum_{i=0}^{t-1}a_{i}x^{i}$, where $a_{0}=s$ and the coefficients
$a_{i}$ are randomly and uniformly chosen from $\mathbb{F}_{q}$. This approach
utilizes unique, non-zero points $x_{i}$ in $\mathbb{F}_{q}$, ensuring each
share $v_{i}=A(x_{i})$ contains part of the secret without fully disclosing
it.

The security of SSS stems from the fact that a polynomial of degree $t-1$ can
only be uniquely determined by any $t$ distinct evaluations ($v_{i}$), making
it mathematically infeasible to reconstruct $s$ from fewer than $t$ shares.
This is due to there being $q^{t-1}$ potential polynomials that could
correspond to any given set of $t-1$ shares, preserving the secrecy of $s$.

This mechanism also underpins the protocol’s resilience to client dropout, as
the threshold $t$ can be adjusted to maintain confidentiality despite partial
participation. In essence, for any subset of $t-1$ shares, the distribution of
potential secrets remains uniform, ensuring no leakage of information about
$s$.

For reconstruction, the protocol employs Lagrange polynomials $L_{i}$ for each
share $i$, calculated as $L_{i}=\frac{\prod_{j\neq i}(X-x_{j})}{\prod_{j\neq
i}(x_{i}-x_{j})}$, where $L_{i}(x_{i})=1$ and $L_{i}(x_{j})=0$ for all $j\neq
i$. This enables the secure computation of
$A(0)=s=\sum_{i=1}^{t}v_{i}L_{i}(0)$ from precisely $t$ shares.

∎

###  5.2. SA using LWE-Based Masking

As we mentioned previously, packed secret sharing significantly improves the
communication efficiency of PPDL-NV, however, the quantity of values that need
to be secret shared still directly correlates to the size of the model update
vector. To address this limitation in our second proposal, we draw inspiration
from the work of Stevens et al. (Stevens et al., 2022) and propose the use of
a dropout-resilient Differentially Private (DP) secure protocol grounded with
the Learning With Errors (LWE) assumption for a decentralized learning
setting. This second approach which we call PPDL-LWE, each client generates a
one-time pad of equal length to their model parameters and broadcast it to all
other clients. Utilizing SSS, clients collaboratively sum their masks and then
subtract each client’s mask from the aggregated model updates value, thereby
enhancing both the efficiency and security of the process.

1

2

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

Number of global iterations $R_{g}$

Public $m\times n$ matrix $A$ over finite field $\mathbb{F}_{q}$

Output : A globally trained model $\mathbf{w}$ for each client

3 for  _$r=1$ to $R_{g}$_ do

// Initialization step

4 All clients start with the same initial model $\mathbf{w}^{0}$.

5 for  _$i=0$ to $n$_ do

6 Train local model:
$\mathbf{w}_{i}\leftarrow\text{LocalUpdate}(\mathbf{w}^{r-1},D_{i})$

7

8 Generate secret vector $\mathbf{s}_{i}$ of size $n$

9 Generate random noise vector $\mathbf{e}_{i}$ of size $m$

10 Compute masking vector $\mathbf{b}_{i}\leftarrow
A\cdot\mathbf{s}_{i}+\mathbf{e}_{i}$

11 Mask model parameters:
$\mathbf{h}_{i}\leftarrow\mathbf{w}_{i}+\mathbf{b}_{i}$

12 Transmit $\mathbf{h}_{i}$ to all clients

13 Receive $\mathbf{h}_{j}$ from all other clients

14

15 Distribute $\llbracket\mathbf{s}_{i}\rrbracket$ to all clients

16 Collect $\llbracket\mathbf{s}_{j}\rrbracket$ from all clients

17

// Using Secret Sharing for aggregation

18 Compute $\mathbf{s}_{\text{sum}}\leftarrow\sum_{j}\mathbf{s}_{j}$

19

20 Aggregate masked model parameters:
$\mathbf{H}_{\text{sum}}\leftarrow\sum_{j}\mathbf{h}_{j}$

21 Compute aggregated model update:
$\mathbf{W}_{\text{sum}}\leftarrow\mathbf{H}_{\text{sum}}-A\cdot\mathbf{s}_{\text{sum}}$

22

23 Update global model:
$\hat{\mathbf{w}}^{r}\leftarrow\frac{1}{n}\mathbf{W}_{\text{sum}}$

24

25

Algorithm 3 PPDL-LWE: Secure Aggregation via LWE-Based Masking for PPDL

As illustrated in Algorithm 3, clients share a public $m\times n$ matrix $A$,
where each element of the matrix is from the finite field $\mathbb{F}_{q}$.
Each client $i$ independently generates a secret vector $s_{i}$ of size $n$
and an error vector $e_{i}$ of size $m$, both derived from the same
distribution. The client then computes a vector $b_{i}=A\cdot s_{i}+e_{i}$,
where $A$ is the public $m\times n$ matrix. This forms an LWE sample with the
pair $(A,b_{i})$, where $b_{i}$ effectively serves as a one-time pad to mask
the client’s model update $w_{i}$, resulting in a masked vector
$h_{i}=w_{i}+b_{i}$.

Next, clients transmit $h_{i}$ to other clients and subsequently compute the
aggregation of the received vectors, $h_{\text{sum}}$, through vector
addition. The $h_{\text{sum}}$ is composed of
$w_{\text{sum}}+As_{\text{sum}}+e_{\text{sum}}$, where $e_{\text{sum}}$ is the
added noise that satisfies the $(\varepsilon,\delta)$-DP criterion, and
$w_{\text{sum}}+e_{\text{sum}}$ forms the noisy aggregated value of the model
updates from other clients. Therefore, to eliminate $As_{\text{sum}}$ from
$h_{\text{sum}}$, clients only need to compute $s_{\text{sum}}$. To determine
$s_{\text{sum}}$ without disclosing the individual $s_{i}$ values, clients
collaboratively use the SSS protocol, as introduced in Section 5.1. Finally,
each client, using the shared matrix $A$ and $s_{\text{sum}}$, computes
$h_{\text{sum}}$ as the aggregated value.

To ensure this protocol’s effectiveness, two key points are crucial for
balancing privacy and performance. First, protecting the confidentiality of
individual error vectors $e_{i}$ is essential, leveraging the LWE assumption
for privacy. By aggregating these vectors into a cumulative noise
$e_{\text{sum}}$ via discrete Gaussians, the protocol achieves differential
privacy, offering a precise yet privacy-aware estimation of $w_{\text{sum}}$.
Second, the dimension of the secret vector $S$ plays a vital role in enhancing
security. Stevens et al. (Stevens et al., 2022) emphasize the importance of
keeping $S_{i}$’s length at a minimum of 710 for robust security, regardless
of the secret input vector $w_{i}$’s dimensionality. These elements are
critical in creating a strong decentralized learning framework that
effectively addresses privacy and efficiency challenges. Beyond the specific
focus of adversarial robustness, adversarial training has been shown to
increase the generalization, and thus the model performance on regular
binaries too.

####  5.2.1. Security Analysis

In this subsection, we discuss the security provided by PPDL-LWE algorithm in
detail:

###### Theorem 2.

In settings with an honest majority, the $PPDL-LWE$ protocol is secure against
semi-honest adversaries by leveraging the LWE assumption for the encryption of
model updates and utilizing SSS for the secure aggregation of clients’ secret
vectors. This protocol exhibits resilience to client dropout, ensuring the
confidentiality and integrity of the DL process.

###### Proof.

The cornerstone of the $PPDL-LWE$ protocol’s security lies in its employment
of the LWE assumption, a principle positing that distinguishing between
genuine LWE samples $(A,A\cdot s_{i}+e_{i})$ and random pairs from the same
distribution is computationally infeasible for any polynomial-time adversary.
Here, $A$ represents a publicly known matrix, $s_{i}$ is a secret vector
selected by the client, and $e_{i}$ is an error vector with elements drawn
from a discretized Gaussian distribution. The distribution’s parameters are
chosen to maintain the encryption’s integrity while enabling efficient
decryption by legitimate entities.

The intractability of the LWE problem, rooted in the computational complexity
of solving certain lattice problems deemed hard for quantum computers,
underpins the protocol’s resistance to quantum attacks. Without exact
knowledge of $s_{i}$ and $e_{i}$, decryption of the encrypted model update
$h_{i}=w_{i}+A\cdot s_{i}+e_{i}$ by adversaries is rendered impractical. This
encryption model ensures that data confidentiality is upheld, even in the face
of semi-honest clients who follow the protocol yet attempt to extract
additional information.

Further enhancing the protocol’s security is the application of SSS for
aggregating the secret vectors $s_{i}$ into a collective sum $s_{\text{sum}}$.
The SSS mechanism necessitates a predetermined number of shares to reconstruct
any individual secret vector, thereby precluding semi-honest clients from
independently accessing or inferring another’s secret vector. The
collaborative computation of $s_{\text{sum}}$, essential for decrypting the
combined encrypted vectors $h_{\text{sum}}$, intrinsically protects against
the potential disclosure of sensitive data to semi-honest participants during
the aggregation phase.

∎

###  5.3. SA with pairwise masking

Building on the principles of the previous approach, the third proposed
protocol emphasizes masking clients’ model parameters before transmission to
other clients. This method introduces a novel aspect where clients engage in
pairwise sharing of a seed for a pseudo-random number generator (PRNG) (Blum
and Micali, 2019; Narayanan and Shmatikov, 2008), allowing each client to
produce a shared vector tailored to the desired size locally. This technique
addresses the unique challenges of secure aggregation by incorporating
principles akin to those explored by Bonawitz et al. (Bonawitz et al., 2017)
in their work on Federated Learning. It offers a refined solution for
enhancing privacy and security in decentralized learning environments.

In this protocol, each client $C_{i}$ generates a unique pairwise mask for
their vector relative to every other neighbouring client $C_{j}$. The
collective result of combining these masked vectors $\mathbf{y}_{i}$ is the
aggregation of the original inputs, effectively concealing the individual
vectors $\mathbf{w}_{i}$. The generation of these masks is facilitated by a
PRNG, which uses a result derived from each client’s public keys, exchanged
during the initial steps of the protocol. This mechanism guarantees a secure
and agreed-upon method for mask generation, ensuring the confidentiality of
the data during the aggregation process.

$y_{i}=w_{i}+\sum_{j:i<j}\text{PRNG}(s_{i,j})-\sum_{j:i>j}\text{PRNG}(s_{j,i})$

The Diffie-Hellman key exchange protocol provides a robust method for
generating a common seed for a PRNG, essential for creating pairwise masks in
secure communications. After generating and exchanging public keys
$g^{a_{i}}\mod q$, each client uses their private key $a_{i}$ in conjunction
with the received public keys from other clients to generate a shared secret
seed $s_{i,j}$. This seed initializes the PRNG, allowing each pair of clients
to agree on a complementary sequence of random numbers for mask generation,
facilitating secure and pairwise synchronized communications across the
network.

1

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

Number of global iterations $R_{g}$

Common base $g$ and prime $q$ for DH key exchange

Output : A globally trained model $\mathbf{w}$ for each client

2 for  _$r=1$ to $R_{g}$_ do

// Initialization step

3 All clients start with the same initial model $\mathbf{w}^{0}$.

4 for  _$i=0$ to $n$_ do

5 Train local model:
$\mathbf{w}_{i}\leftarrow\text{LocalUpdate}(\mathbf{w}^{0},D_{i})$

6

7 Generate private key $a_{i}$ and compute public key $g^{a_{i}}$

8 Exchange public keys $g^{a_{i}}$ with other clients

9

10 Distribute shares of $a_{i}$ using SSS to each client

11

12 for  _each client $C_{j}$ where $j\neq i$_ do

13 Receive public key $g^{a_{j}}$ from client $C_{j}$

14 Compute shared secret $s_{i,j}=(g^{a_{j}})^{a_{i}}$

15 Generate pairwise masks PRNG($s_{i,j}$)

16

17 Generate personal mask $b_{i}$ using PRNG

18 $\mathbf{y}_{i}\leftarrow\mathbf{w}_{i}+b_{i}$

19

20 for  _each client $C_{j}$ where $j\neq i$_ do

21 if  _$i <j$_ then

22 $\mathbf{y}_{i}\leftarrow\mathbf{y}_{i}+\text{PRNG}(s_{i,j})$

23

24 else

25 $\mathbf{y}_{i}\leftarrow\mathbf{y}_{i}-\text{PRNG}(s_{j,i})$

26

27

28 Broadcast $\mathbf{y}_{i}$ to all other clients

29

30

31 Initialize an empty vector $\mathbf{V}$ for aggregation

32 for  _each received masked vector $\mathbf{y}_{j}$ from clients_ do

33 $\mathbf{V}\leftarrow\mathbf{V}+\mathbf{y}_{j}$

34

35

36 if  _a client $C_{k}$ drops out_ then

37 Collect shares of $a_{k}$ from remaining clients to reconstruct $a_{k}$

38 for  _each client $C_{j}$ where $j\neq k$_ do

39 Compute shared secret $s_{j,k}$ and $s_{k,j}$ using $a_{k}$

40 Adjust $\mathbf{V}$ by removing the mask contributions;

41

42

43 $\hat{\mathbf{w}}^{r}\leftarrow\frac{1}{n}\mathbf{V}$;

Algorithm 4 PPDL-PW: Secure Aggregation with Pairwise Masking and Diffie-
Hellman (DH) Key Exchange

Similar to earlier approaches, we tackle the issue of clients dropping out
after broadcasting their mask vector. A straightforward approach is having the
remaining clients remove the dropout mask and resend the updated vector.
However, this brings us a new challenge: more clients may drop out during this
recovery phase before sharing their seeds, requiring additional recovery
phases for these new dropouts. As a result, this approach could trigger a
cascade of recoveries, possibly equaling the total number of clients and
complicating the process.

To circumvent this issue, we employ the threshold secret sharing protocol
introduced in Section 5.1, where users distribute a share of their private key
to all other clients. In the case of a client dropping out after sending its
masked model update vector, remaining client utilizes the SSS to reconstruct
the dropout’s private key. This enables the recalculation and removal of the
dropout’s mask from the aggregated value. While this solution necessitates
additional steps for seed recovery and mask recalibration, it ensures the
integrity of the aggregation process is maintained, even in the event of
client dropouts.

# of users | Dataset | DL | PPDL-NV | PPDL-LWE | PPDL-PW | DLDP
---|---|---|---|---|---|---
50 | MNIST | $96.56\%$ | $96.52\%$ | $89.12\%(\epsilon=9.25)$ | $96.22\%$ | $89.85\%(\epsilon=9.25)$
CIFAR-10 | $74.46\%$ | $73.98\%$ | $62.12\%(\epsilon=11.31)$ | $73.9\%$ | $62.74\%(\epsilon=11.31)$
SVHN | $92.92\%$ | $92.61\%$ | $83.03\%(\epsilon=11.00)$ | $91.82\%$ | $83.07\%(\epsilon=11.00)$
Fashion-MNIST | $87.48\%$ | $87.22\%$ | $83.01\%(\epsilon=11.00)$ | $86.92\%$ | $83.19\%(\epsilon=11.00)$
100 | MNIST | $96.24\%$ | $96.11\%$ | $88.60\%(\epsilon=9.33)$ | $96.11\%$ | $89.12\%(\epsilon=9.33)$
CIFAR-10 | $71.24\%$ | $71.02\%$ | $62.21\%(\epsilon=11.58)$ | $71.20\%$ | $62.56\%(\epsilon=11.31)$
SVHN | $92.12\%$ | $92.03\%$ | $82.47\%(\epsilon=11.00)$ | $91.23\%$ | $82.97\%(\epsilon=11.00)$
Fashion-MNIST | $87.13\%$ | $87.02\%$ | $82.21\%(\epsilon=10.610)$ | $87.12\%$ | $82.91\%(\epsilon=10.61)$

Table 1. Accuracy comparison of different aggregation method in Decentralized
learning

####  5.3.1. Security Analysis

In this subsection, we detail the security measures implemented by the PPDL-PW
algorithm:

###### Theorem 3.

PPDL-PW protocol, under the Decisional Diffie-Hellman (DDH) assumption,
establishes a secure protocol for exchanging keys and masking model updates.
This protocol ensures the confidentiality and integrity of decentralized
learning processes, bolstered by the indistinguishability of shared secrets
and enhanced with Shamir’s Secret Sharing (SSS) for dropout resilience.

###### Proof.

Given a cyclic group $\mathbb{G}$ of order $q$ with generator $g$, the DDH
assumption (as described in 3.3) states that for any polynomial-time
adversary, distinguishing between tuples $(g^{a},g^{b},g^{ab})$ and
$(g^{a},g^{b},g^{c})$, where $c$ is chosen uniformly at random from
$\mathbb{Z}_{q}$, is computationally hard. This assumption is crucial for
securing the key exchange phase, ensuring shared secrets $g^{ab}$ are
indistinguishable from random and protected against eavesdropping.

Following key exchange, the protocol uses a PRNG seeded with Diffie-Hellman
derived shared secrets $s_{ij}=g^{a_{i}a_{j}}$ to generate cryptographic masks
for obfuscating model parameters $w$. The security of this masking relies on
the assumption that the hash function $H$, applied to $s_{ij}$ for randomness
extraction, produces a uniformly random string that serves as a secure PRNG
seed. These masks ensure confidentiality through computational secrecy,
predicated on the DDH problem’s hardness.

In the aggregation phase, clients compile masked model updates without
exposing individual contributions, preserving privacy and integrity. This is
achieved by each client $C_{n}$ aggregating the received masked updates $\sum
y_{i}^{(w)}$, where $y_{i}^{(w)}=w_{i}+\sum m_{ij}$, leveraging the
computational indistinguishability of the masks from random due to the secure
PRNG process.

Moreover, integrating Shamir’s Secret Sharing (SSS) with a defined threshold
enhances the protocol’s security against dropout. It leverages the uniform
randomness and indistinguishability of shares to preserve confidentiality and
integrity, even amid client dropouts. This strategic addition ensures the
aggregation process remains secure despite network variability, reinforcing
the protocol’s robust security framework and its efficiency in decentralized
settings.

∎

##  6\. Evaluation

In this section, we conduct a set of experiments to demonstrate the robustness
and efficiency of our proposed protocols.

###  6.1. Experimental Setup

We implemented the protocols in Python, utilizing the Pytorch framework for
model training (Paszke et al., 2019)111The implementation will be made
publicly available upon acceptance.. All experiments were conducted on a
compute cluster with an Intel Xeon Gold 6150, Nvidia V100 GPU, and 128GB RAM
in the local network.

####  6.1.1. Datasets

For our assessment, we utilized four widely recognized datasets in deep
learning: MNIST (LeCun, 1998), Fashion-MNIST (Xiao et al., 2017), SVHN (Netzer
et al., 2011), and CIFAR-10 (Krizhevsky et al., 2009), all partitioned into
subsets that are independent and identically distributed (IID). We divided the
training data into smaller subsets (generally in equal sizes) and distributed
these among the clients at random. The MNIST dataset is comprised of 60,000
training images and 10,000 testing images of handwritten digits in grayscale,
with each image measuring $28\times 28$ pixels. Fashion-MNIST offers a dataset
for a 10-class fashion item classification challenge, including 60,000
training images and 10,000 testing images of fashion items. Derived from
Google Street View images of house numbers, the SVHN dataset contains 99,289
color images in ten categories, with a training set of 73,257 images and a
testing set of 26,032 images, each standardized to $28\times 28$ pixels.
CIFAR-10 presents a varied set of 50,000 training and 10,000 testing color
images distributed over ten unique categories, with each image depicting one
category.

####  6.1.2. Model

We implemented tailored model architectures to address the unique
characteristics of our datasets: a CNN for CIFAR-10 and SVHN and a two-layer
MLP for MNIST and Fashion-MNIST. The CNN architecture features two
convolutional layers with a kernel size of $3\times 1$ per layer, followed by
three fully connected layers, with 384 neurons in each hidden layer and 10
neurons in the output layer. This structure is designed to effectively process
and learn from the complex image data presented by CIFAR-10. The model is
optimized with a learning rate of 0.002 and a batch size of 128, incorporating
Group Normalization (GN) alongside max pooling and dropout rates between 0.2
to 0.5, culminating in a fully connected output layer. The MLP model is
comprised of two fully connected layers with 100 and 10 neurons, respectively.
This model is optimized with a learning rate of 0.01 and a batch size of 128.

###  6.2. Classification Accuracy

A comprehensive accuracy comparison of different aggregation methods we
presented in Section 5 is provided in Table 1. The experiments involve four
datasets (MNIST, CIFAR-10, SVHN, and Fashion-MNIST) and the number of users
set at 50 and 100. The aggregation methods compared include baseline DL
without privacy-preserving aggregation, PPDL-NV, PPDL-LWE, PPDL-PW, and DLDP
(Differentially Private Decentralized Learning (Cheng et al., 2019)).

For both groups of 50 and 100 users, DL consistently achieves the highest
accuracy across all datasets, serving as a benchmark for the effectiveness of
decentralized learning without privacy-preserving constraints. PPDL-NV and
PPDL-PW closely match the DL’s accuracy with minimal losses, indicating their
capability to maintain high accuracy while offering privacy-preserving
benefits. Specifically, PPDL-NV demonstrates accuracies of $96.52\%$ and
$96.11\%$ for MNIST, closely following DL’s $96.56\%$ and $96.24\%$ for groups
of 50 and 100 users, respectively. This pattern of minimal accuracy reduction
persists across other datasets, underscoring the efficiency of these methods
in balancing privacy with performance.

PPDL-LWE and DLDP, however, exhibit a noticeable decrease in accuracy due to
their rigorous privacy constraints, as evidenced by their accuracy figures and
$\epsilon$ values. In the CIFAR-10 dataset, PPDL-LWE’s accuracy dips to
$62.12\%$ for 50 users and $62.21\%$ for 100 users, a significant reduction
from DL’s $74.46\%$ and $71.24\%$. This decline in performance is echoed
across the board, with PPDL-LWE and DLDP consistently posting lower accuracies
in exchange for stronger privacy guarantees denoted by their respective
$\epsilon$ values. For instance, in the SVHN dataset, DLDP’s accuracy is
$83.07\%$ for 50 users and $82.97\%$ for 100 users, compared to DL’s more
robust $92.92\%$ and $92.12\%$.

In conclusion, PPDL-NV and PPDL-PW strike a good balance between privacy
preservation and accuracy, closely matching the benchmarks set by the baseline
DL. Meanwhile, PPDL-LWE offers strong privacy guarantees by combining
differential privacy and masking techniques for DL, achieving a level of
accuracy comparable to that of DLDP.

Figure 2. Implications of increasing the number of clients on the efficiency
of protocols.

Figure 3. Implications of increasing the number of model parameters on the
efficiency of protocols.

###  6.3. Impact of Client Number and Dropout on Computational Overhead

Figure 2 presents a comparative analysis of the three privacy-preserving
aggregation methods for DL in terms of computation time when the number of
clients and dropout ratio change. This examination is based on a single
iteration of the learning process, with the model parameter count set at
50,000. Additionally, we note that 20% of the network clients are considered
semi-honest, adding another layer of complexity to the privacy-preserving
mechanisms employed.

As the number of clients increases from 10 to 1000, we observe a notable
increase in computation times for all evaluated methods. PPDL-NV, despite
leveraging packed Shamir secret sharing, experiences a significant rise in
computation time, which varies from 12.22 seconds to 694.79 seconds. This
increase underscores both the method’s computational demand and its robustness
in handling complex calculations. On the other hand, PPDL-LWE stands out for
its exceptional efficiency, with computation times only ranging from 0.16 to
16.43 seconds as the number of clients grows. This efficiency highlights PPDL-
LWE’s potential for scalability in large-scale applications where
computational resources are a critical consideration.”

PPDL-PW stands out for its unique response to network conditions. At a 0%
dropout rate, it maintains constant computation times of 0.71 seconds
irrespective of the number of clients, showcasing unparalleled efficiency in
stable conditions. However, its computation times increase linearly with the
number of clients and dropout rates as network instability grows, peaking at
49.50 seconds for 1000 clients at a 30% dropout rate. This behavior points to
a direct sensitivity to dropout rates, a characteristic not as pronounced in
the other methods, where increases in computation time remain relatively
unaffected by variations in dropout.

###  6.4. Impact of Model Size on Computational Efficiency

The scalability of PPDL-NV, PPDL-LWE, and PPDL-PW in response to increasing
model sizes and varying dropout rates is illuminated through a closer
examination of their computational performance, as depicted in Figure 3. PPDL-
NV ’s computational times escalate significantly with model size, increasing
from 0.11 seconds for 10 secret values to 760.58 seconds for 1,000,000 secret
values at a 0% dropout rate. This trend intensifies under a 30% dropout rate,
where computational times further surge to 983.88 seconds for 1,000,000 secret
values, indicating a profound sensitivity to both increased model size and
higher dropout rates. In contrast, PPDL-LWE exhibits extraordinary resilience
to these factors, with computation times only slightly increasing from 0.66
seconds for 10 secret values to 0.73 seconds for 1,000,000 secret values, even
at a 30% dropout rate. This negligible variation suggests unparalleled
stability across model size and network reliability dimensions.

PPDL-PW, on the other hand, while demonstrating a modest increase in
computation time with model size, reveals a more nuanced sensitivity to
dropout rates. For example, at a 0% dropout rate, computation times increase
slightly from 0.76 seconds for 10 secret values to 0.77 seconds for 1,000,000
secret values. However, as the dropout rate reaches 30%, computation times for
PPDL-PW rise more noticeably, from 0.76 seconds for 10 secret values to 11.25
seconds for 1,000,000 secret values. This pattern suggests that while PPDL-PW
is somewhat resilient to model size increases, its efficiency is more
significantly impacted by higher dropout rates, especially as the model size
grows.

These numerical comparisons reveal the critical interplay between model size
and dropout rates in decentralized learning environments. PPDL-NV, though
scalable to a degree, faces substantial challenges in maintaining
computational efficiency with larger model sizes and higher dropout rates.
PPDL-LWE stands out for its robustness, showing minimal impact from either
increasing model sizes or varying dropout rates, making it a highly reliable
choice for large-scale applications. PPDL-PW occupies a middle ground,
offering reasonable scalability and efficiency but with a noticeable decrease
in performance under higher dropout rates and larger model sizes.

| PPDL-NV | PPDL-LWE | PPDL-PW |  $\mathrm{D}^{2}$-MHE | Paillier-HE
---|---|---|---|---|---
MNIST | 20.93 | 0.24 | 0.21 | 26.2 (Xu et al., 2023) | 59.54 (Xu et al., 2023)
CIFAR10 | 513.18 | 0.24 | 0.21 | 62.19 (Xu et al., 2023) | 106.42 (Xu et al., 2023)

Table 2. Computational overhead of one iteration of various privacy-preserving
approaches (Seconds)

###  6.5. Computation overhead comparison

In addition to evaluating our proposed approaches, we also compare our
protocols with two homomorphic encryption-based DL aggregation protocols,
namely $\mathrm{D}^{2}$-MHE (Xu et al., 2023) and Paillier-HE (Xu et al.,
2023), to provide a comprehensive analysis of computational overhead across
different privacy-preserving mechanisms when applied to the MNIST and CIFAR-10
datasets. Table 2 illustrates the comparative computational demand for one
iteration among various approaches, including PPDL-NV, PPDL-LWE, PPDL-PW,
along with the aforementioned homomorphic encryption-based schemes.

The $\mathrm{D}^{2}$-MHE scheme capitalizes on recent advancements in
homomorphic encryption, explicitly employing the Brakerski-Fan-Vercauteren
(BFV) framework, aiming to minimize computational costs while securely
updating gradients in a decentralized training context. On the other hand,
Paillier-HE represents a classical approach to homomorphic encryption, adapted
here for decentralized settings. The performance data for both
$\mathrm{D}^{2}$-MHE and Paillier-HE were adopted from the study (Xu et al.,
2023), eschewing direct implementation for these comparisons. We maintained
identical model architectures and configurations across all evaluated
protocols to ensure a fair and accurate comparison.

For the MNIST dataset, PPDL-NV’s method exhibits a relatively high
computational overhead at 20.93 seconds, which dramatically increases to
513.18 seconds for the more complex CIFAR-10 dataset, indicating its less
favorable scaling with data complexity. In stark contrast, PPDL-LWE and PPDL-
PW methods demonstrate exceptional efficiency, with negligible overheads of
0.24 and 0.21 seconds, respectively, for both datasets. This stark efficiency
highlights their suitability for decentralized scenarios where minimizing
computational burden is crucial. However, the $\mathrm{D}^{2}$-MHE and
Paillier-HE approaches present significantly higher computational times. For
MNIST, $\mathrm{D}^{2}$-MHE stands at 26.2 seconds, escalating to 62.19
seconds for CIFAR-10, while Paillier-HE jumps from 59.54 to 106.42 seconds,
respectively. These results reflect the inherent computational overhead
associated with HE techniques, particularly Paillier-HE’s intensive modular
exponential operations and the collaborative decryption process among multiple
users, which, despite its privacy advantages, results in considerable
computational overhead.

###  6.6. Computational and communication complexity

In this section, we derive the computational and communication complexities
associated with each of the proposed PPDL protocols.

####  6.6.1. PPDL-NV

Computational complexity: PPDL-NV protocol, employing Packed Shamir’s Secret
Sharing, has a computational complexity that unfolds across a few key steps.
Initially, clients generate packed shares of their local model update $w_{i}$
with a complexity of $O(nT/K)$, leveraging the efficiency of packing multiple
elements per share for $n$ clients, $T$ as the threshold, and $K$ as the
packing factor. The aggregation of shares from $n-1$ peers follows a linear
complexity of $O(n)$, thanks to the simple addition of packed shares. The
final, most complex phase is the reconstruction of the aggregated value from
shares, at $O(nT^{2}/K)$, due to polynomial interpolation for unpacking. The
protocol’s overall complexity is thus primarily determined by this
reconstruction phase, leading to an $O(nT^{2}/K)$ complexity.

Communication complexity: This protocol’s communication complexity arises from
two key operations: share distribution and aggregated share broadcasting. Each
client sends their packed shares to $n-1$ others and receives an equivalent
number from every other client, resulting in a communication complexity of
$O(n^{2})$. This stems from the need for each of the $n$ clients to interact
with all others. The aggregation step, involving each client broadcasting
their aggregated share to all, also reflects an $O(n^{2})$ complexity due to
the peer-to-peer exchange among $n$ participants. Thus, the protocol’s overall
communication complexity remains $O(n^{2})$, underscored by the extensive
interactions necessary for decentralized aggregation.

####  6.6.2. PPDL-LWE

Computational complexity: The computational complexity for each client is
primarily shaped by generating random vectors ($O(m)$), matrix-vector
multiplication ($O(mn)$), and leveraging packed Shamir’s Secret Sharing
($O(nmT/K)$ for sharing and $O(nT^{2}/K)$ for reconstruction). Given $m$
exceeds the length of the secret vector $s$, the initial vector generation
simplifies to $O(m)$. The subsequent operations, particularly the
reconstruction of packed secret shares, culminate in a dominant $O(nT^{2}/K)$
complexity. Thus, the overall client-side complexity is effectively summarized
by $O(nmT/K+nT^{2}/K)$.

Communication complexity: In PPDL-LWE protocol, the communication complexity
for each participant is derived from a series of direct, peer-to-peer
exchanges. Specifically, every client sends their encrypted gradient vector of
size $m$ to $k-1$ peers and receives an equivalent number of encrypted vectors
from others, leading to a communication load of $O(km(k-1))$. Additionally,
the aggregate mask, also of size $m$, is computed using multi-party
computation and subsequently distributed among $k-1$ peers, adding
$O(mk(k-1))$ to the communication cost. Secure aggregation, facilitated
through SSS, requires each client to distribute secret shares of their vector
$s$ to all $k-1$ other clients, contributing $O(k^{2}n)$ to the overall
complexity. Therefore, when accounting for both sending and receiving
operations in this decentralized scenario, the communication complexity for
each client effectively scales as $O(k^{2}m+k^{2}n)$.

####  6.6.3. PPDL-PW

Computational complexity: It is defined by two primary operations: $O(n^{2})$
for generating $t$-out-of-$n$ Shamir secret shares for the privacy key across
$n$ participants, reflecting the quadratic nature of polynomial computations
required for secure share distribution, and $O(mn)$ for the linear complexity
associated with generating pseudorandom values for each participant, where $m$
denotes the size of the input vector. Furthermore, secret reconstruction,
particularly exigent during participant dropouts, demands a computational
complexity of $O(n^{3})$ due to the intricacies of polynomial interpolation.
To enhance computational efficiency, our work incorporates packed Shamir’s
Secret Sharing, effectively reducing the complexity to $O(nmT/K)$ for share
generation and $O(nT^{2}/K)$ for reconstruction, with $T$ representing the
threshold for reconstruction and $K$ the number of secrets integrated into
each polynomial.

Communication complexity: Initially, each participant exchanges a single
public key with every other participant, resulting in $n(n-1)$ total public
key exchanges across the network. Concurrently, secret shares of the privacy
key are distributed similarly, with each participant sending and receiving a
secret share to and from each of the $n-1$ other participants, doubling the
count of exchanges and reinforcing the quadratic component of the
communication complexity. Additionally, each participant broadcasts a masked
data vector of size $m$ to all $n-1$ other participants, further contributing
to the communication load with $m(n-1)$ units of data sent by each
participant. The overall communication complexity per participant is
$O(n^{2}+mn)$, reflecting the quadratic growth from pairwise key and secret
share exchanges ($n^{2}$ for large $n$) and the linear growth from
broadcasting masked data vectors ($mn$).

##  7\. Conclusion

This study delves into the challenges and necessities of privacy preservation
and efficiency in decentralized learning environments. We introduce three
novel protocols designed for secure aggregation that directly address DL’s
unique challenges, such as heightened risks of information leakage and data
integrity issues in the face of variable client participation. Additionally,
exploring mechanisms for dropout resilience strengthens the learning process
against disruptions caused by client dropouts, enhancing the system’s overall
reliability and effectiveness. Through rigorous experimental evaluation across
various datasets and scenarios, we have empirically validated the
effectiveness of our proposed methods. Our experiments, testing our protocols
over diverse datasets to ensure robustness and generalizability, demonstrate
their computational efficiency and resilience to network fluctuations while
preserving privacy. The results of the experiments reaffirm the feasibility of
implementing privacy-preserving decentralized learning at scale. It provides
valuable insights into optimizing aggregation protocols to balance the trade-
offs between privacy, accuracy, and efficiency. This work lays the groundwork
for future progress in developing more efficient decentralized learning
architectures.

## References

  * (1)
  * Aono et al. (2017) Yoshinori Aono, Takuya Hayashi, Lihua Wang, Shiho Moriai, et al. 2017\.  Privacy-preserving deep learning via additively homomorphic encryption.  _IEEE transactions on information forensics and security_ 13, 5 (2017), 1333–1345.
  * Bell et al. (2020) James Henry Bell, Kallista A Bonawitz, Adrià Gascón, Tancrède Lepoint, and Mariana Raykova. 2020.  Secure single-server aggregation with (poly) logarithmic overhead. In _Proceedings of the 2020 ACM SIGSAC Conference on Computer and Communications Security_. 1253–1269.
  * Bellet et al. (2018) Aurélien Bellet, Rachid Guerraoui, Mahsa Taziki, and Marc Tommasi. 2018.  Personalized and private peer-to-peer machine learning. In _International Conference on Artificial Intelligence and Statistics_. PMLR, 473–481.
  * Beltrán et al. (2023) Enrique Tomás Martínez Beltrán, Mario Quiles Pérez, Pedro Miguel Sánchez Sánchez, Sergio López Bernal, Gérôme Bovet, Manuel Gil Pérez, Gregorio Martínez Pérez, and Alberto Huertas Celdrán. 2023.  Decentralized federated learning: Fundamentals, state of the art, frameworks, trends, and challenges.  _IEEE Communications Surveys & Tutorials_ (2023).
  * Blum and Micali (2019) Manuel Blum and Silvio Micali. 2019.  How to generate cryptographically strong sequences of pseudo random bits.  In _Providing Sound Foundations for Cryptography: On the Work of Shafi Goldwasser and Silvio Micali_. 227–240.
  * Boenisch et al. (2023) Franziska Boenisch, Adam Dziedzic, Roei Schuster, Ali Shahin Shamsabadi, Ilia Shumailov, and Nicolas Papernot. 2023.  When the curious abandon honesty: Federated learning is not private. In _2023 IEEE 8th European Symposium on Security and Privacy (EuroS &P)_. IEEE, 175–199.
  * Bonawitz et al. (2019) Keith Bonawitz, Hubert Eichner, Wolfgang Grieskamp, Dzmitry Huba, Alex Ingerman, Vladimir Ivanov, Chloe Kiddon, Jakub Konečnỳ, Stefano Mazzocchi, Brendan McMahan, et al. 2019\.  Towards federated learning at scale: System design.  _Proceedings of machine learning and systems_ 1 (2019), 374–388.
  * Bonawitz et al. (2017) Keith Bonawitz, Vladimir Ivanov, Ben Kreuter, Antonio Marcedone, H Brendan McMahan, Sarvar Patel, Daniel Ramage, Aaron Segal, and Karn Seth. 2017.  Practical secure aggregation for privacy-preserving machine learning. In _proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_. 1175–1191.
  * Boneh (1998) Dan Boneh. 1998.  The decision diffie-hellman problem. In _International algorithmic number theory symposium_. Springer, 48–63.
  * Canetti et al. (1996) Ran Canetti, Uri Feige, Oded Goldreich, and Moni Naor. 1996.  Adaptively secure multi-party computation. In _Proceedings of the twenty-eighth annual ACM symposium on Theory of computing_. 639–648.
  * Cheng et al. (2019) Hsin-Pai Cheng, Patrick Yu, Haojing Hu, Syed Zawad, Feng Yan, Shiyu Li, Hai Li, and Yiran Chen. 2019.  Towards decentralized deep learning with differential privacy. In _International Conference on Cloud Computing_. Springer, 130–145.
  * Dwork (2006) Cynthia Dwork. 2006.  Differential privacy. In _International colloquium on automata, languages, and programming_. Springer, 1–12.
  * Fereidooni et al. (2021) Hossein Fereidooni, Samuel Marchal, Markus Miettinen, Azalia Mirhoseini, Helen Möllering, Thien Duc Nguyen, Phillip Rieger, Ahmad-Reza Sadeghi, Thomas Schneider, Hossein Yalame, et al. 2021\.  SAFELearn: Secure aggregation for private federated learning. In _2021 IEEE Security and Privacy Workshops (SPW)_. IEEE, 56–62.
  * Franklin and Yung (1992) Matthew Franklin and Moti Yung. 1992.  Communication complexity of secure computation. In _Proceedings of the twenty-fourth annual ACM symposium on Theory of computing_. 699–710.
  * Gentry (2009) Craig Gentry. 2009.  _A fully homomorphic encryption scheme_.  Stanford university.
  * Geyer et al. (2017) Robin C Geyer, Tassilo Klein, and Moin Nabi. 2017.  Differentially private federated learning: A client level perspective.  _arXiv preprint arXiv:1712.07557_ (2017).
  * Ghavamipour et al. (2022) Ali Reza Ghavamipour, Fatih Turkmen, and Xiaoqian Jiang. 2022.  Privacy-preserving logistic regression with secret sharing.  _BMC Medical Informatics and Decision Making_ 22, 1 (2022), 1–11.
  * Ghavamipour et al. (2023) Ali Reza Ghavamipour, Fatih Turkmen, Rui Wang, and Kaitai Liang. 2023.  Federated Synthetic Data Generation with Stronger Security Guarantees. In _Proceedings of the 28th ACM Symposium on Access Control Models and Technologies_. 31–42.
  * Guo et al. (2021) Shangwei Guo, Tianwei Zhang, Guowen Xu, Han Yu, Tao Xiang, and Yang Liu. 2021.  Topology-aware differential privacy for decentralized image classification.  _IEEE Transactions on Circuits and Systems for Video Technology_ 32, 6 (2021), 4016–4027.
  * Hegedűs et al. (2019) István Hegedűs, Gábor Danner, and Márk Jelasity. 2019.  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_. Springer, 74–90.
  * Hegedűs et al. (2021) István Hegedűs, Gábor Danner, and Márk Jelasity. 2021.  Decentralized learning works: An empirical comparison of gossip learning and federated learning.  _J. Parallel and Distrib. Comput._ 148 (2021), 109–124.
  * Hellman (1976) Martin Hellman. 1976.  New directions in cryptography.  _IEEE transactions on Information Theory_ 22, 6 (1976), 644–654.
  * Koloskova et al. (2019) Anastasia Koloskova, Sebastian Stich, and Martin Jaggi. 2019.  Decentralized stochastic optimization and gossip algorithms with compressed communication. In _International Conference on Machine Learning_. PMLR, 3478–3487.
  * Krizhevsky et al. (2009) Alex Krizhevsky, Geoffrey Hinton, et al. 2009\.  Learning multiple layers of features from tiny images.  (2009).
  * LeCun (1998) Yann LeCun. 1998.  The MNIST database of handwritten digits.  _http://yann. lecun. com/exdb/mnist/_ (1998).
  * Li et al. (2020) Tian Li, Anit Kumar Sahu, Ameet Talwalkar, and Virginia Smith. 2020.  Federated learning: Challenges, methods, and future directions.  _IEEE signal processing magazine_ 37, 3 (2020), 50–60.
  * Lian et al. (2017) Xiangru Lian, Ce Zhang, Huan Zhang, Cho-Jui Hsieh, Wei Zhang, and Ji Liu. 2017.  Can decentralized algorithms outperform centralized algorithms? a case study for decentralized parallel stochastic gradient descent.  _Advances in neural information processing systems_ 30 (2017).
  * Luo et al. (2021) Xinjian Luo, Yuncheng Wu, Xiaokui Xiao, and Beng Chin Ooi. 2021.  Feature inference attack on model predictions in vertical federated learning. In _2021 IEEE 37th International Conference on Data Engineering (ICDE)_. IEEE, 181–192.
  * McMahan et al. (2017) Brendan McMahan, Eider Moore, Daniel Ramage, Seth Hampson, and Blaise Aguera y Arcas. 2017.  Communication-efficient learning of deep networks from decentralized data. In _AISTATS_. 1273–1282.
  * Narayanan and Shmatikov (2008) Arvind Narayanan and Vitaly Shmatikov. 2008.  Robust de-anonymization of large sparse datasets. In _2008 IEEE Symposium on Security and Privacy (sp 2008)_. IEEE, 111–125.
  * Netzer et al. (2011) Yuval Netzer, Tao Wang, Adam Coates, Alessandro Bissacco, Bo Wu, and Andrew Y Ng. 2011.  Reading digits in natural images with unsupervised feature learning.  (2011).
  * Pasquini et al. (2023) Dario Pasquini, Mathilde Raynal, and Carmela Troncoso. 2023.  On the (In) security of Peer-to-Peer Decentralized Machine Learning. In _2023 IEEE Symposium on Security and Privacy (SP)_. IEEE Computer Society, 418–436.
  * Paszke et al. (2019) Adam Paszke, Sam Gross, Francisco Massa, Adam Lerer, James Bradbury, Gregory Chanan, Trevor Killeen, Zeming Lin, Natalia Gimelshein, Luca Antiga, et al. 2019\.  Pytorch: An imperative style, high-performance deep learning library.  _Advances in neural information processing systems_ 32 (2019).
  * Shamir (1979) Adi Shamir. 1979.  How to share a secret.  _Commun. ACM_ 22, 11 (1979), 612–613.
  * Shokri et al. (2017) Reza Shokri, Marco Stronati, Congzheng Song, and Vitaly Shmatikov. 2017.  Membership inference attacks against machine learning models. In _2017 IEEE symposium on security and privacy (SP)_. IEEE, 3–18.
  * So et al. (2022) Jinhyun So, Chaoyang He, Chien-Sheng Yang, Songze Li, Qian Yu, Ramy E Ali, Basak Guler, and Salman Avestimehr. 2022.  Lightsecagg: a lightweight and versatile design for secure aggregation in federated learning.  _Proceedings of Machine Learning and Systems_ 4 (2022), 694–720.
  * Stevens et al. (2022) Timothy Stevens, Christian Skalka, Christelle Vincent, John Ring, Samuel Clark, and Joseph Near. 2022.  Efficient differentially private secure aggregation for federated learning via hardness of learning with errors. In _31st USENIX Security Symposium (USENIX Security 22)_. 1379–1395.
  * Tian et al. (2022) Haibo Tian, Yanchuan Wen, Fangguo Zhang, Yunfeng Shao, and Bingshuai Li. 2022.  A distributed threshold additive homomorphic encryption for federated learning with dropout resiliency based on lattice. In _International Symposium on Cyberspace Safety and Security_. Springer, 277–292.
  * Truex et al. (2019) Stacey Truex, Nathalie Baracaldo, Ali Anwar, Thomas Steinke, Heiko Ludwig, Rui Zhang, and Yi Zhou. 2019.  A hybrid approach to privacy-preserving federated learning. In _Proceedings of the 12th ACM workshop on artificial intelligence and security_. 1–11.
  * Wen et al. (2022) Yuxin Wen, Jonas Geiping, Liam Fowl, Micah Goldblum, and Tom Goldstein. 2022.  Fishing for user data in large-batch federated learning via gradient magnification.  _arXiv preprint arXiv:2202.00580_ (2022).
  * Xiao et al. (2017) Han Xiao, Kashif Rasul, and Roland Vollgraf. 2017.  Fashion-mnist: a novel image dataset for benchmarking machine learning algorithms.  _arXiv preprint arXiv:1708.07747_ (2017).
  * Xu et al. (2022) Guowen Xu, Guanlin Li, Shangwei Guo, Tianwei Zhang, and Hongwei Li. 2022.  Privacy-preserving decentralized deep learning with multiparty homomorphic encryption.  _arXiv preprint arXiv:2207.04604_ (2022).
  * Xu et al. (2023) Guowen Xu, Guanlin Li, Shangwei Guo, Tianwei Zhang, and Hongwei Li. 2023.  Secure decentralized image classification with multiparty homomorphic encryption.  _IEEE Transactions on Circuits and Systems for Video Technology_ (2023).
  * Zhang et al. (2020) Chengliang Zhang, Suyi Li, Junzhe Xia, Wei Wang, Feng Yan, and Yang Liu. 2020.  $\\{$BatchCrypt$\\}$: Efficient homomorphic encryption for $\\{$Cross-Silo$\\}$ federated learning. In _2020 USENIX annual technical conference (USENIX ATC 20)_. 493–506.
  * Zhang et al. (2022) Li Zhang, Jianbo Xu, Pandi Vijayakumar, Pradip Kumar Sharma, and Uttam Ghosh. 2022.  Homomorphic encryption-based privacy-preserving federated learning in iot-enabled healthcare system.  _IEEE Transactions on Network Science and Engineering_ (2022).
  * Zhao et al. (2021) Benjamin Zi Hao Zhao, Aviral Agrawal, Catisha Coburn, Hassan Jameel Asghar, Raghav Bhaskar, Mohamed Ali Kaafar, Darren Webb, and Peter Dickinson. 2021.  On the (in) feasibility of attribute inference attacks on machine learning models. In _2021 IEEE European Symposium on Security and Privacy (EuroS &P)_. IEEE.


free action of an involution on $M_{x}(\mathcal{B})$ corresponding to the
vector $\Lambda_{i}$.

######  Remark 4.27.

In the case of small covers over $3$-polytope the incompressibility of facet
submanifolds follows from [WY17, Theorem 3.3]. Another approach to this result
is represented in [DO01, DJS98, D08] and is based on the fact that
$M_{x}(F_{i})$ is a totally geodesic hypersurface in $M(P,\Lambda)$ with the
structure of a cubical complex, which is nonpositively curved in the sense of
Alexandrov and Gromov [G87].

###### Proof of Proposition 4.26.

In $M(P,\Lambda)$ the copies of $F_{i}$ are glued in a disjoint union of
$2^{r-r(F_{i})}$ manifolds $M_{x}(F)$. Each manifold is glued of copies of
$F_{i}$ corresponding to polytopes $P\times b$ with $b$ lying in the coset
$x+\pi_{F_{i}}\in\mathbb{Z}_{2}^{r}/\pi_{F_{i}}$. There is a piecewise-linear
homeomorphism between the part of the polytope $P$ between
$P_{k}(\mathcal{B})$ and $F_{i}$ and $F_{i}\times I$. This homeomorphism gives
an isotopy between $P_{k}(\mathcal{B})$ and $F_{i}$.

There are two possibilities: either $\Lambda_{i}\not\in\pi_{\mathcal{B}}$, or
$\Lambda_{i}\in\pi_{\mathcal{B}}$. In the first case $M_{x}(F_{i})$ has a
product tubular neighbourhood with the boundary consisting of two manifolds
$M_{x}(\mathcal{B})$ and $M_{x+\Lambda_{i}}(\mathcal{B})$. In particular, all
the three manifolds are isotopic and homeomorphic to
$M(F_{i},\Lambda_{\mathcal{B}})$, and $M_{x}(F_{i})$ is incompressible by
Proposition 4.22.

In the second case $M_{x}(F_{i})$ has a nontrivial tubular neighbourhood with
the boundary $M_{x}(\mathcal{B})$. $M_{x}(F_{i})$ is homeomorphic to a factor
space of $M(F_{i},\Lambda_{\mathcal{B}})$ by the action of the involution
given by
$\Lambda_{i}\in\pi_{\mathcal{B}}\simeq\mathbb{Z}_{2}^{r(\mathcal{B})}$. The
action if free, since $\Lambda_{i}\notin\langle\Lambda_{p},\Lambda_{q}\rangle$
for any vertex $F_{i}\cap F_{p}\cap F_{q}$ of $F_{i}$. Then $M_{x}(F_{i})$ is
homeomorphic to the manifold $M(F_{i},\Lambda_{F_{i}})$, where
$\Lambda_{F_{i}}$ is a vector-colouring given by the composition
$\\{F_{j}\colon
F_{j}\in\mathcal{B}\\}\to\pi_{\mathcal{B}}\to\pi_{\mathcal{B}}/\langle\Lambda_{i}\rangle$.
The structure of $I$-bundle of the tubular neighbourhood of $M_{x}(F_{i})$
gives a homeomorphism of this neighbourhood and the mapping cylinder of the
quotient mapping $M(F_{i},\Lambda_{\mathcal{B}})\to M(F_{i},\Lambda_{F_{i}})$
described above. It corresponds to the mapping from the boundary
$M_{x}(\mathcal{B})$ to the zero section $M_{x}(F_{i})$ of the tubular
neighbourhood. This mapping is homotopic to the identical mapping and is a
$2$-sheeted covering.

Thus, the inclusion $i\colon M_{x}(\mathcal{B})\to M(P,\Lambda)$ up to a
homotopy can be decomposed as a composition of the $2$-sheeted covering
$c\colon M_{x}(\mathcal{B})\to M_{x}(F_{i})$ and the inclusion $j\colon
M_{x}(F_{i})\to M(P,\Lambda)$. We have the composition of the homomorphisms

$\pi_{1}(M_{x}(\mathcal{B}))\xrightarrow{c_{*}}\pi_{1}(M_{x}(F_{i}))\xrightarrow{j_{*}}\pi_{1}(M(P,\Lambda)).$

The first mapping is injective due to the covering space property, and the
composition is injective by Proposition 4.22. Also $\pi_{1}(M_{x}(F_{i}))/{\rm
Im}\,c_{*}\simeq\mathbb{Z}_{2}$. Thus, as in the case of belts, we obtain that
${\rm Ker}\,j_{*}\cap{\rm Im}\,c_{*}=\\{1\\}$. In particular, there is an
embedding ${\rm Ker}\,j_{*}\to\pi_{1}(M_{x}(F_{i}))/{\rm
Im}\,c_{*}\simeq\mathbb{Z}_{2}$. As discussed in the proof of Proposition
4.22, this implies that ${\rm Ker}\,j_{*}$ is trivial, if
$\chi(M_{x}(F_{i}))\leqslant 0$. The last condition is satisfied, since
$M_{x}(F_{i})$ is covered by $M_{x}(\mathcal{B})$, which has a nonpositive
Euler characteristic for $k\geqslant 4$. ∎

######  Example 4.28.

If $F_{i}$ is a quadrangle, then taking into account Example 4.24 we have the
following possibilities:

  1. (1)

$\Lambda_{i}\not\in\pi_{\mathcal{B}}$. Then $M_{x}(F_{i})\simeq
M_{x}(\mathcal{B})\simeq M_{x+\Lambda_{i}}(F_{i})$ is either $T^{2}$, or
$K_{2}$. If $M(P,\Lambda)$ is orientable, then only the case $T^{2}$ is
possible.

  2. (2)

$\Lambda_{i}\not\in\pi_{\mathcal{B}}$. Then $M_{x}(F_{i})$ has a tubular
neighbourhood with the boundary $M_{x}(\mathcal{B})$, and there is a
$2$-sheeted covering $M_{x}(\mathcal{B})\to M_{x}(F_{i})$. There are the
following possibilities:
$(M_{x}(\mathcal{B}),M_{x}(F_{i}))\in\\{(T^{2},T^{2}),(T^{2},K^{2}),(K^{2},K^{2})\\}$.
If $M(P,\Lambda)$ is orientable, then $M_{x}(\mathcal{B})\simeq T^{2}$, since
it has a product neighbourhood. The vector $\Lambda_{i}$ is a linear
combination of an odd number of vectors from the base of the set
$\\{\Lambda_{j}\colon F_{j}\in\mathcal{B}\\}$. Therefore, the corresponding
involution on $M_{x}(\mathcal{B})$ changes the orientation, and
$M_{x}(F_{i})\simeq K^{2}$.

####  4.3.3. The $JSJ$-decomposition and an explicit geometrization.

To pass to the $JSJ$-decomposition of the orientable manifold $M(P,\Lambda)$
we first realize geometrically the combinatorial decomposition of item (1) of
Theorem 4.11 using Corollary 2.34. Each planar section
$\widehat{P}_{4}(\mathcal{B})$ of $P$ corresponding to a belt $\mathcal{B}$ is
isotopic to the piecewise linear polygon $P_{4}(\mathcal{B})$. Hence, the
corresponding submanifolds $\widehat{M}_{x}(\mathcal{B})$ and
$M_{x}(\mathcal{B})$ are isotopic in $M(P,\Lambda)$. Thus, in $M(P,\Lambda)$
we obtain a disjoint family of incompressible tori
$\widehat{M}_{x}(\mathcal{B})$ corresponding to $4$-belts $\mathcal{B}$ from
the nested family, incompressible tori $M_{x}(F_{i})$ corresponding to ”free”
quadrangles $F_{i}$ of almost Pogorelov polytopes with
$r(F_{i})>r(\mathcal{B}(F_{i}))$, and incompressible tori
$\widehat{M}_{x}(\mathcal{B})$, which are boundaries of the tubular
neighbourhoods of the incompressible submanifolds $M_{x}(F_{i})\simeq K^{2}$
corresponding to ”free” quadrangles $F_{i}$ of almost Pogorelov polytopes with
$r(F_{i})=r(\mathcal{B}(F_{i}))$. For a $4$-belt around a quadrangle the
section $\widehat{P}_{4}(\mathcal{B})$ may be easily chosen as a slight shift
of the facet.

Now we delete from the flag polytope $P\neq I^{3}$ all the sections
$\widehat{P}_{4}(\mathcal{B})$ corresponding to the belts from the
decomposition (1) and delete all the ”free quadrangles” of almost Pogorelov
polytopes from the decomposition. Then each part $Q_{i}$ corresponding to an
almost Pogorelov polytope $R_{i}$ without adjacent quadrangles is homeomorphic
to this polytope with all the quadrangles deleted and to a right-angled
polytope of finite volume in $\mathbb{H}^{3}$ with ideal points deleted. The
realization of a right-angled polytope of finite volume in $\mathbb{H}^{3}$ is
unique up to isometries of $\mathbb{H}^{3}$. Each part $Q_{j}$ corresponding
to a $k$-prism $R_{j}$, $k\geqslant 5$, is homeomorphic to this prism with
some disjoint set of quadrangles deleted, and also to a direct product of a
polygon with some set of vertices deleted and the segment. The polygon may be
realized as a right-angled polygon with deleted points lying on the absolute.
The realization is not unique. In the orientable manifold $M(P,\Lambda)$ this
partition of the polytope corresponds to a partition of the manifold into
pieces defined by the deletion of the incompressible tori corresponding to the
belts from (1) and incompressible tori and Klein bottles corresponding to
”free quadrangles” of almost Pogorelov polytopes. Each piece is glued from
right-angled polytopes of finite volume in $\mathbb{H}^{2}\times\mathbb{R}$
and $\mathbb{H}^{3}$.

The vector-colouring $\Lambda$ of rank $r$ induces a vector-colouring
$\Lambda_{Q_{i}}$ of each piece $Q_{i}$, which we consider as a right-angled
polytope of finite volume in $\mathbb{H}^{3}$ or
$\mathbb{H}^{2}\times\mathbb{R}$.

######  Definition 4.29.

Denote by $\pi_{Q_{i}}\subset\mathbb{Z}_{2}^{r}$ a linear span of vectors
$\Lambda_{j}$ corresponding to facets of $Q_{i}$, and $r_{i}=\dim\pi_{Q_{i}}$.

In the orientable manifold $M(P,\Lambda)$ each peace $M_{x}(Q_{i})$
corresponding to $Q_{i}$ is homeomorphic to $N(Q_{i},\Lambda_{Q_{i}})$ and is
glued of the polytopes $Q_{i}\times b$ with $b$ lying in the coset
$x+\pi_{Q_{i}}\in\mathbb{Z}_{2}^{r}/\pi_{Q_{i}}$. There are $2^{r-r_{i}}$ such
pieces. The manifold $M_{x}(Q_{i})$ contains the torus
$\widehat{M}_{y}(\mathcal{B})$ from the above collection in its boundary if
and only if $\widehat{P}_{4}(\mathcal{B})$ lies in the boundary of $Q_{i}$,
and $y+\pi_{\mathcal{B}}\subset x+\pi_{Q_{i}}$. It contains the torus or the
Klein bottle $M_{y}(F_{j})$ from the above collection in its closure in
$M(P,\Lambda)$ if and only $F_{j}$ is a free quadrangle of the almost
Pogorelov polytope $R_{i}$, and $y+\pi_{\mathcal{B}}\subset x+\pi_{Q_{i}}$.
This gives an explicit geometrization of the pieces of the manifold
$M(P,\Lambda)$.

Now our goal is to prove that this is actually the minimal geometric
decomposition from Theorem 0.2. For this we will use Proposition 4.8. First
using Proposition 4.6 we will prove that the collection of incompressible tori
from Theorem 4.11 gives the $JSJ$-decomposition, and then we will prove that
$M(P,\Lambda)$ is not a $Sol$-manifold.

######  Proposition 4.30.

For an orientable manifold $M(P,\Lambda)$ over a flag polytope $P$ different
from $k$-prisms, the closure of each piece $M_{x}(Q_{i})$ corresponding to a
$k$-prism, $k\geqslant 5$, is a Seifert fibered manifold with toric boundary,
and it is not homeomorphic to $D^{2}\times S^{1}$, $T^{2}\times I$ and
$K^{2}\widetilde{\times}I$. Moreover, for any two pieces $M_{x}(Q_{i})$ and
$M_{y}(Q_{j})$ with a common boundary torus $T$ we have
$f(T,\overline{M_{x}(Q_{i})})\neq f(T,\overline{M_{y}(Q_{j})})$.

######  Remark 4.31.

If $P$ is a $k$-prism, $k\geqslant 4$, then the same argument as in the proof
of Proposition 4.30 gives a structure of a closed Seifert fibered manifold on
an orientable manifold $M(P,\Lambda)$.

###### Proof of Proposition 4.30.

First consider the case $\Lambda=E$, and $M(P,E)=\mathbb{R}\mathcal{Z}_{P}$.

Consider the $k$-gon $L$, which is the base of the prism $S=L\times I$. There
are $l$ of its edges corresponding to the canonical $4$-belts of $P$ (we will
call these edges ”singular”). Then copies of each base $L$ of $S$ in
$\mathbb{R}\mathcal{Z}_{P}$ are glued into several copies of an oriented
$2$-dimensional submanifold $N$, which is homeomorphic to a sphere
$S^{2}_{g,s}$ with $g$ handles and $s$ holes. Denote by $L^{\prime}$ the
polygon obtained by contraction of $l$ singular edges of $L$, and
$k^{\prime}=k-l$. It is easy to see that $k^{\prime}\geqslant 3$. Denote by
$\widehat{N}\simeq S^{2}_{g}$ the corresponding manifold without holes. Then
$\widehat{N}\simeq\mathbb{R}\mathcal{Z}_{L^{\prime}}$. In particular,
$g=1+(k^{\prime}-4)2^{k^{\prime}-3}$ according to Example 1.2. Each singular
edge of $L$ corresponds to a disjoint set of $2^{k^{\prime}-2}$ holes with the
boundary of each hole consisting of $4$ edges. Thus, there are
$s=l2^{k^{\prime}-2}$ holes. Then in $\mathbb{R}\mathcal{Z}_{P}$ the $k$-prism
corresponds to a disjoint union of submanifolds homeomorphic to
$S^{2}_{g,s}\times S^{1}$. We have $l\geqslant 2$ for $k^{\prime}=3$, and
$l\geqslant 1$ for $k^{\prime}\geqslant 4$. Therefore, $s\geqslant 4$.

######  Lemma 4.32.

The manifold $S^{2}_{g,s}\times S^{1}$ with $g\geqslant 0$ and $s\geqslant 3$
can not cover a manifold homotopy equivalent to $D^{2}\times S^{1}$,
$T^{2}\times I$ and $K^{2}\widetilde{\times}I$.

###### Proof.

Set $X=S^{2}_{g,s}\times S^{1}$. The manifold $S^{2}_{g,s}$ is homotopy
equivalent to a wedge of $p=2g+s-1\geqslant 2$ circles. In particular,
$\pi_{1}(X)=F_{p}\times\mathbb{Z}$, where $F_{p}$ is a free group on $p$
generators, and there is a subgroup in $\pi_{1}(X)$ isomorphic to $F_{2}$. If
$\varphi\colon X\to Y$ is a covering, then $\varphi_{*}$ is an injection, and
$\pi_{1}(Y)$ contains a subgroup $G$ isomorphic to $F_{2}$. Then $Y$ is not
homotopy equivalent to $D^{2}\times S^{1}$ and $T^{2}\times I$, since their
fundamental groups are abelian. If $Y$ is homotopy equivalent to
$K^{2}\widetilde{\times}I$, then $\pi_{1}(Y)\simeq\pi_{1}(K^{2})$ and we will
identify these groups. Consider the $2$-sheeted covering $\psi\colon T^{2}\to
K^{2}$. This corresponds to the short exact sequence
$1\to\pi_{1}(T^{2})\to\pi_{1}(K^{2})\to\mathbb{Z}_{2}\to 1$. Since $G$ is not
abelian, it is not contained in $\psi_{*}(\pi_{1}(T^{2}))$, and there is a
short exact sequence $1\to{\rm Im}\,\psi_{*}\cap G\to G\to\mathbb{Z}_{2}\to
1$, which shows that the subgroup ${\rm Im}\,\psi_{*}\cap G$ has index $2$ in
$G$. Then it corresponds to a $2$-sheeted covering $\zeta\colon Z\to S^{1}\vee
S^{1}$, where $Z$ is connected. In this case $Z$ is homotopy equivalent to a
wedge of $3$ circles, and ${\rm Im}\,\psi_{*}\cap G\simeq F_{3}$. But the
group ${\rm Im}\,\psi_{*}\cap G$ is abelian. A contradiction. This finishes
the proof. ∎

Thus, each piece of $\mathbb{R}\mathcal{Z}_{P}$ corresponding to a $k$-prism,
is not homeomorphic to $D^{2}\times S^{1}$, $T^{2}\times I$ and
$K^{2}\widetilde{\times}I$, and has a unique Seifert fibered structure by
Theorem 4.4. If two pieces $M_{1}$ and $M_{2}$ have a common boundary torus
$T$, they correspond to different prisms. Since the prisms are twisted, the
elements $f(T,M_{1})$ and $f(T,M_{2})$ in $PH_{1}(T^{2})$ correspond to the
classes of $(1,0)$ and $(0,1)$, and are different.

Now consider the case of any vector-colouring $\Lambda$. Each manifold
$\overline{M_{x}(Q_{i})}$ corresponding to a $k$-prism is homeomorphic to a
quotient space of $S^{2}_{g,s}\times S^{1}$ by a freely acting subgroup
isomorphic to $H(\Lambda)\cap\mathbb{Z}_{2}^{Q_{i}}$, where
$\mathbb{Z}_{2}^{Q_{i}}$ is a linear span of basis vectors
$e_{j}\in\mathbb{Z}_{2}^{m}$ corresponding to facets of $Q_{i}$ (remind that
$Q_{i}$ is obtained from the prism $L\times I$ by the deletion of the
quadrangles corresponding to canonical belts). The action moves fibers to
fibers and induces the following Seifert fibered structure on
$\overline{M_{x}(Q_{i})}$. Fibers are again formed by the copies of $z\times
I\subset L\times I$. Denote by $F_{p}$ and $F_{q}$ facets of $P$ containing
bases of the prism. Then in $\overline{M_{x}(Q_{i})}$ the copies of $z\times
I\subset L\times I$ form circles $C(z)$.

  1. (1)

If the point $z$ lies in the interior of $L$, or in the interior of a singular
edge, then there is a neighbourhood $U(z)$ such that the copies of $U(z)\times
I$ are glued to a direct product $U(z)\times S^{1}$, where $S^{1}$ is glued of
$2^{\dim\langle\Lambda_{p},\Lambda_{q}\rangle}$ copies of $I$. Hence, the
fiber $C(z)$ is regular.

  2. (2)

If $z$ lies in the interior of a regular edge of $L$, or it is a common vertex
of a regular edge and a singular edge, then the regular edge corresponds to
some facet $F_{a}$ of $P$ with
$\Lambda_{a}\notin\\{\Lambda_{p},\Lambda_{q}\\}$. Since $M(P,\Lambda)$ is
orientable, either $\Lambda_{p}=\Lambda_{q}$, or $\Lambda_{p}\neq\Lambda_{q}$
and $\Lambda_{a}\notin\langle\Lambda_{p},\Lambda_{q}\rangle$. In both cases
there is a neighbourhood $U(z)$ such that the copies of $U(z)\times I$ are
glued to a direct product $U(z)\times S^{1}$, where $S^{1}$ is glued of
$2^{\dim\langle\Lambda_{p},\Lambda_{q}\rangle}$ copies of $I$. Hence, the
fiber $C(z)$ is regular.

  3. (3)

If $z$ is a common vertex of two regular edges of $L$, then these edges
correspond to facets $F_{a}$ and $F_{b}$ of $P$, with
$\Lambda_{p},\Lambda_{q}\notin\langle\Lambda_{a},\Lambda_{b}\rangle$. If
$\Lambda_{p}=\Lambda_{q}$, then again $C(z)$ has a trivial tubular
neighbourhood. If $\Lambda_{p}\neq\Lambda_{q}$, then
$\Lambda_{q}=\Lambda_{a}+\Lambda_{b}+\Lambda_{p}$, since $M(P,\Lambda)$ is
orientable. In this case $C(z)$ has a tubular neighbourhood that forms a
standard fibered torus corresponding to the rotation by angle $\pi$.

Lemma 4.32 implies that $\overline{M_{x}(Q_{i})}$ is not not homeomorphic to
$D^{2}\times S^{1}$, $T^{2}\times I$ and $K^{2}\widetilde{\times}I$, and has a
unique Seifert fibered structure by Theorem 4.4. If two pieces $M_{x}(Q_{i})$
and $M_{y}(Q_{j})$ have a common boundary torus $T$, they correspond to
different prisms. Since the prisms are twisted, Example 4.24 shows that the
elements $f(T,M_{1})$ and $f(T,M_{2})$ in $PH_{1}(T^{2})$ are different. ∎

Now we are ready to finish the proof of Theorem 4.11.

By Theorem 4.7 pieces corresponding to almost Pogorelov polytopes without
adjacent quadrangles do not have a structure of a Seifert fibered manifold,
and all the Seifert fibered pieces of $M(P,\Lambda)$ correspond to $k$-prisms
and to Klein bottles arising from some free quadrangles of almost Pogorelov
polytopes. The latter pieces have a common boundary only with hyperbolic
pieces. Thus, Propositions 4.30 and Proposition 4.6 imply that we indeed have
a $JSJ$-decomposition.

To use Proposition 4.8 we need to prove that orientable $M(P,\Lambda)$ can not
be a $Sol$-manifold. As it is mentioned in this Proposition, a $Sol$-manifold
has one $JSJ$-torus, moreover, either both components of the complement of
this torus are $K^{2}\widetilde{\times}I$, or the complement to the torus is
homeomorphic to $T^{2}\times I$. For $M(P,\Lambda)$ the hyperbolic pieces are
not homeomorphic to $K^{2}\widetilde{\times}I$ and $T^{2}\times I$, since they
do not admit a Seifert fibered structure. Also we have proved that pieces
corresponding to $k$-prisms are not homeomorphic to $K^{2}\widetilde{\times}I$
and $T^{2}\times I$. Only a piece corresponding to a Klein bottle arising from
a free quadrangle can be homeomorphic to $K^{2}\widetilde{\times}I$, but not
to $T^{2}\times I$. Then the adjacent piece with the same boundary component
is hyperbolic, which is a contradiction. This finishes the proof of Theorem
4.11.

######  Corollary 4.33.

For orientable manifolds $M(P,\Lambda)$ defined by vector-colourings of simple
$3$-polytopes the following five of eight Thurston’s geometries arise:

  * •

$S^{3}$ for the simplex $\Delta^{3}$;

  * •

$S^{2}\times\mathbb{R}$ for the $3$-prism $\Delta^{2}\times I$;

  * •

$\mathbb{R}^{3}$ for the cube $I^{3}$;

  * •

$\mathbb{H}^{2}\times\mathbb{R}$ for $k$-prisms, $k\geqslant 5$, and pieces
corresponding to them;

  * •

$\mathbb{H}^{3}$ for Pogorelov polytopes and pieces corresponding to almost
Pogorelov polytopes.

##  5\. Acknowledgements

This work is supported by the Russian Science Foundation under grant
20-11-19998. The author is grateful to Victor Buchstaber for his encouraging
support and attention to this work, to Taras Panov for his advises, and to
Vladimir Shastin and Dmitry Gugnin for fruitful discussions.

## References

  * [A70a] E.M. Andreev, _On convex polyhedra in Lobachevskii spaces_ , Math. USSR-Sb, 10:3 (1970), 413–440.
  * [A70b] E.M. Andreev, _On convex polyhedra of finite volume in Lobachevskii space_ , Math. USSR-Sb. 12:2 (1970), 255–259.
  * [AFW15] M. Aschenbrenner, S. Friedl, H. Wilton, _$3$ -manifold groups_, EMS Series of Lectures in Mathematics, 2015.
  * [A10] Anton Ayzenberg, _The problem of Buchstaber number and its combinatorial aspects_ , preprint, arXiv:1003.0637 (2010), 1–14.
  * [A16] Anton Ayzenberg, _Buchstaber invariant, minimal non-simplices and related_ , Osaka J. Math. 53 (2016), no. 2, 377–395.
  * [B1913] G.D. Birkhoff. _The Reducibility of Maps_. Am. J. Math. 35 (1913), 115–128.
  * [B02] F. Bonahon, _Geometric structures on $3$-manifolds_, in: Handbook of Geometric Topology, pp. 93–164, North-Holland, Amsterdam, 2002.
  * [BE17S] V.M. Buchstaber, N.Yu. Erokhovets, _Fullerenes, Polytopes and Toric Topology_ , In Volume 35 Combinatorial and Toric Homotopy: Introductory Lectures of Lect. Notes Ser. Inst. Math. Sci. Natl. Univ. Singap.; World Sci. Publ.: River Edge, NJ, USA, 2017; P. 67–178, arXiv: math.CO/160902949.
  * [BE17I] V.M. Buchstaber, N.Yu. Erokhovets, _Construction of families of three-dimensional polytopes, characteristic patches of fullerenes and Pogorelov polytopes_ , Izvestiya: Mathematics, 81:5 (2017), P. 901–972.
  * [BEMPP17] V.M. Buchstaber, N.Yu. Erokhovets, M. Masuda, T.E. Panov, S. Park, _Cohomological rigidity of manifolds defined by right-angled $3$-dimensional polytopes_, Russian Math. Surveys. 2017. V. 72, N. 2. P. 199–256. arXiv:1610.07575v3.
  * [BP15] V.M. Buchstaber, T. E. Panov, _Toric topology_ , Math. Surveys Monogr. V. 204, Amer. Math. Soc.: Providence, RI, USA, 2015.
  * [BP16] V.M. Buchstaber, T. E. Panov, _On manifolds defined by $4$-colourings of simple $3$-polytopes_, Uspekhi Mat. Nauk 71 (2016), no. 6, 157–158 (Russian). Russian Math. Surveys 71 (2016), no. 6 (English translation).
  * [D08] M. Davis, _The geometry and topology of Coxeter groups_ , London Mathematical Society Monographs Series, vol. 32, Princeton University Press, 2008.
  * [DJ91] M.W. Davis and T. Januszkiewicz, _Convex polytopes, Coxeter orbifolds and torus actions_ , Duke Math. J. 62 (1991), no. 2, 417–451.
  * [DJS98] M. Davis, T. Januszkiewicz and R. Scott, _Nonpositive curvature of blow-ups_ , Selecta Math. 4 (1998), no. 4, 491–547.
  * [DO01] M.W. Davis, B. Okun, _Vanishing theorems and conjectures for the $2$-homology of right-angled Coxeter groups_, Geometry and Topology. 5 (2001), 7–74.
  * [EV20b] A.A. Egorov, A.Yu. Vesnin, _On correlation of hyperbolic volumes of fullerenes with their properties_ , Comput. Math. Biophys., 8 (2020), 150–167
  * [EV20c] A. Egorov, A. Vesnin, _Volume estimates for right-angled hyperbolic polyhedra_ , arXiv:2010.11147
  * [E08] N. Yu. Erokhovets, _Buchstaber invariant of simple polytopes_ , Russian Math. Surveys, 63:5 (2008), 962–964
  * [E14] N.Yu. Erokhovets _Buchstaber invariant theory of simplicial complexes and convex polytopes_ , Proc. Steklov Inst. Math., 286 (2014), 128–187.
  * [E19] N.Yu. Erokhovets, _Three-dimensional right-angled polytopes of finite volume in the Lobachevsky space: combinatorics and constructions_ , Proc. Steklov Inst. Math., 305 (2019), 78–134.
  * [G87] M. Gromov, _Hyperbolic groups_ , in Essays in group theory, Springer, New York (1987), 75–263.
  * [H02] A. Hatcher. _Algebraic Topology_. https://pi.math.cornell.edu/ hatcher/AT/AT.pdf
  * [H07] A. Hatcher. _Notes on Basic $3$-Manifold Topology_. https://pi.math.cornell.edu/ hatcher/3M/3Mfds.pdf
  * [I01] I.V. Izmest’ev _Free torus action on the manifold $Z_{P}$ and the group of projectivities of a polytope $P$_, Russian Math. Surveys, 56:3 (2001), 582–583.
  * [LW20] Zhi Lü, Lisu Wu, _Combinatorial characterization of right-angled hyperbolicity of $3$-orbifolds_, arXiv: 2009.11034.
  * [MV86] A.D. Mednykh, A.Yu. Vesnin, _On three-dimensional hyperbolic manifolds of Lobell type_ , Complex Analysis and Applications’85, eds.: L. Iliev and I. Ramadanov, Sofia, Publ. House of Bulgarian Acad. Sci. (1986), 440–446.
  * [L09] Wolfgang Lück, _Survey on aspherical manifolds_ , arXiv:0902.2480v3. Published in Proceedings of the 5-th ECM, Amsterdam (2008).
  * [M90] A.D. Mednykh, _Three-dimensional hyperelliptic manifolds_ , Ann. Global. Anal. Geom., 8:1 (1990), 13–19.
  * [MT14] J.W. Morgan, G. Tian, _The Geometrization Conjecture_ , Clay Mathematics Monographs, 5, AMS, 2014.
  * [NN05] H. Nakayama, Y. Nishimura, _The orientability of small covers and colouring simple polytopes_ , Osaka J. Math. 42:1 (2005), 243–256.
  * [PV16] T.E. Panov, Ya.A. Veryovkin, _Polyhedral products and commutator subgroups of right-angled Artin and Coxeter groups_ , Sb. Math., 207:11 (2016), 1582–1600.
  * [P67] A.V. Pogorelov, _A regular partition of Lobachevskian space_ , Math. Notes. 1:1 (1967), 3–5.
  * [S09] T.A. Schroeder _Geometrization of $3$-dimensional Coxeter orbifolds and Singer’s conjecture_, Geom. Dedicata. 140 (2009), 163–174.
  * [S83] P. Scott, _The geometries of $3$-manifolds_, Bull. London Math. Soc. 15 (1983), no. 5, 401–487.
  * [T02] W.P. Thurston, _The geometry and topology of three-manifolds_ , electronic version 1.1 of 2002. A version is currently available from the Mathematical Sciences Research Institute at the URL http://www.msri.org/publications/books/gt3m/.
  * [V87] A.Yu. Vesnin, _Three-dimensional hyperbolic manifolds of Löbell type_ , Siberian Mathematical Journal, 28:5 (1987), 731–734.
  * [V17] A.Yu. Vesnin, _Right-angled polyhedra and hyperbolic $3$-manifolds_, Russian Math. Surveys, 72:2 (2017), 335–374.
  * [VE20] A.Yu. Vesnin, A.A. Egorov, _Ideal right-angled polyhedra in Lobachevsky space_ , Chebyshevskii sbornik, 21:2 (2020), 65–83.
  * [VM99] A.Yu. Vesnin, A.D. Mednykh _Spherical coxeter groups and hyperelliptic 3-manifolds_ , Mathematical Notes, 66 (1999), 135–138.
  * [VS88] E.B. Vinberg, O.V. Shvartsman, _Discrete groups of motions of spaces of constant curvature (English. Russian original)_ , Geometry. II: Spaces of constant curvature, Encycl. Math. Sci. 1993. V. 29, P. 139–248; translation from Itogi Nauki Tekh., Ser. Sovrem. Probl. Mat., Fundam. Napravleniya. 1988. V. 29, P. 147–259.
  * [W19] Lisu Wu, _Atoroidal manifolds in small covers_ , arXiv:1812.09896.
  * [WY17] Lisu Wu, Li Yu, _Fundamental groups of small covers revisited_ , IMRN, rnz034 (2019), arXiv:1712.00698
  * [Z95] G.M. Ziegler, _Lectures on polytopes_ , Grad. Texts in Math., V. 152, New York: Springer-Verlag, 1995.