#  Adaptive Differentially Quantized Subspace Perturbation (ADQSP): A Unified
Framework for Privacy-Preserving Distributed Average Consensus

Qiongxiu Li, Jaron Skovsted Gundersen, Milan Lopuhaä-Zwakenberg and Richard
Heusdens Q. Li is with Tsinghua University, China (email:
qiongxiuli@mail.tsinghua.edu.cn). J. S. Gundersen is with the Department of
Electronic Systems, Aalborg University, Denmark, (email:jaron@es.aau.dk).M.
Lopuhaä-Zwakenberg is with University of Twente, the Netherlands,
(email:m.a.lopuhaa@utwente.nl).R. Heusdens is with the Netherlands Defence
Academy (NLDA), the Netherlands, and with the Faculty of Electrical
Engineering, Mathematics and Computer Science, Delft University of Technology,
Delft, the Netherlands (email: r.heusdens@{mindef.nl,tudelft.nl}).

###### Abstract

Privacy-preserving distributed average consensus has received significant
attention recently due to its wide applicability. Based on the achieved
performances, existing approaches can be broadly classified into perfect
accuracy-prioritized approaches such as secure multiparty computation (SMPC),
and worst-case privacy-prioritized approaches such as differential privacy
(DP). Methods of the first class achieve perfect output accuracy but reveal
some private information, while methods from the second class provide privacy
against the strongest adversary at the cost of a loss of accuracy. In this
paper, we propose a general approach named adaptive differentially quantized
subspace perturbation (ADQSP) which combines quantization schemes with so-
called subspace perturbation. Although not relying on cryptographic
primitives, the proposed approach enjoys the benefits of both accuracy-
prioritized and privacy-prioritized methods and is able to unify them. More
specifically, we show that by varying a single quantization parameter the
proposed method can vary between SMPC-type performances and DP-type
performances. Our results show the potential of exploiting traditional
distributed signal processing tools for providing cryptographic guarantees. In
addition to a comprehensive theoretical analysis, numerical validations are
conducted to substantiate our results.

###### Index Terms:

Secure multiparty computation, differential privacy, decentralized networks,
subspace perturbation, data aggregation, consensus, quantization.

##  I Introduction

As the world is becoming increasingly interconnected and digitized, data are
often collected and stored in personal devices such as tablets and phones [1].
To process such massive amounts of data over different devices poses many
challenges including: (1) the requirement for distributed processing tools
that can process data in a network of devices without any centralized
coordination; (2) the need for lightweight solutions as these devices are
often limited in computational resources, and (3) the demand for privacy-
preserving algorithms, as these devices often contain sensitive personal data
captured by sensors such as images and GPS data [1]. Combined, these
challenges call for interdisciplinary research across different fields such as
cryptography, information theory and distributed signal processing for
developing efficient and privacy-preserving distributed computation methods.

The average consensus problem has been intensively investigated and widely
applied in many applications, e.g., optimization [2], group coordination [3],
and federated learning [4]. Recently, privacy-preserving distributed average
consensus, which aims to guarantee all participants in a network to output an
accurate average consensus without violating privacy concerns, has received a
lot of attention [5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20,
21, 22, 23, 24]. There are at least five aspects to be considered when
designing privacy-preserving distributed average consensus algorithms:
centralized vs. decentralized coordination, computational complexity,
communication costs, and most importantly, the achieved privacy level and
output accuracy. With respect to the first concern, in this paper we only
consider fully distributed/decentralized solutions which do not require any
centralized coordination such as a trusted third party. Secondly, the
computational complexity depends heavily on the so-called security model,
i.e., whether we demand computational or information-theoretical security. In
this work, we will restrict ourselves to information-theoretical security
based algorithms since they are generally computationally less complex
compared to computational security based approaches as the former does not
involve complex encryption operations.

With respect to communication cost, privacy, and accuracy, most existing work
focuses on privacy and accuracy, while the aspect of communication cost is
rarely addressed. Ideally, one would like perfect accuracy while guaranteeing
privacy even against the strongest adversary, which is all participants except
one collude. This, however, has been shown to be impossible [25]. The main
reason is that having knowledge of the average result will reveal the private
data held by the only non-colluding participant. As a result, existing work
falls into two categories. The first category contains algorithms that
guarantee privacy against the worst-case adversary using differential privacy
(DP) techniques [26, 27] by inserting noise into the calculations [10, 11, 12,
13]. This guarantees one individual’s privacy even when all other participants
are compromised, at the cost of output accuracy. The second category contains
secure multiparty computation (SMPC) based approaches like secret sharing [14,
15, 16, 17] and correlated noise insertion [20, 21, 22], which offer perfect
accuracy but only guarantee privacy under additional assumptions on the set of
compromised participants.

###  I-A Paper contribution

In this paper, we present a communication efficient algorithm that links the
performances of SMPC and DP approaches in a unified framework. Our key results
are summarized as follows:

  1. 1.

We analyze the problem of privacy-preserving distributed average consensus
over networks and prove two impossibility results about the performances of
privacy and accuracy given the network topology. In particular, we prove that
the so-called ideal world defined in SMPC is impossible to achieve if the
adversary disconnects the network.

  2. 2.

We propose a novel approach, referred to as _adaptive differentially quantized
subspace perturbation (ADQSP)_ , by combining the potential of quantization
schemes and the subspace perturbation technique. It enjoys superior
performance compared to existing approaches in terms of accuracy, privacy and
communication efficiency.

  3. 3.

We show that our proposed approach can achieve SMPC and (relaxed) DP
performances by appropriate parameter settings. To the best of our knowledge,
the proposed approach is the first information-theoretical approach that
unifies both SMPC and DP in this context.

Both theoretical investigations and numerical validations are presented to
consolidate our claims. We published preliminary results in [28] where only
the connection of quantized subspace perturbation and DP is shown. In this
paper we show that the proposed ADQSP approach can achieve both SMPC and DP
related performances. In addition, we give a complete information-theoretical
analysis of privacy via mutual information.

###  I-B Outline and Notation

The paper is organized as follows. In Section II, we introduce the problem
setup and define the adversary model and privacy metrics. In Section III, we
analyze the problem at hand and prove two impossibility results regarding the
performances. In Section IV, we introduce the proposed approach. In Section V,
we analyze the performance of existing SMPC and DP approaches, while in
Section VI, we analyze the performance of the proposed approach and show that
by tuning a single parameter the performance can vary between that of SMPC and
(relaxed) DP. Numerical validations are demonstrated in Section VII and
conclusions are drawn in Section VIII.

We use bold letters for vectors ($\boldsymbol{x}$) and matrices
($\boldsymbol{X}$), where capital letters are used for matrices. Sets are
denoted by calligraphic letters ($\mathcal{X}$). $\boldsymbol{I}$ denotes the
identity matrix. We refer to the $i$-th entry of a vector $\boldsymbol{x}$ as
$x_{i}$.111For simplicity we assume that the entries $x_{i}$ are scalar
variables but the results can easily be generalized to arbitrary dimensions.
With a slight abuse of notation, we denote a random variable by a capital
letter $X$ no matter if the outcome is a scalar $x$, a vector
$\boldsymbol{x}$, or a matrix $\boldsymbol{X}$.

##  II Preliminaries

In this section we review some necessary fundamentals for the remainder of the
paper.

###  II-A Privacy-preserving distributed average consensus

A network is modelled as a graph $\mathcal{G}=({\cal V},\mathcal{E})$, where
${\cal V}=\\{1,\ldots,n\\}$ is the set of vertices representing the
nodes/agents/participants in the network, and $\mathcal{E}\subseteq{\cal
V}\times{\cal V}$ is the set of $m:=|\mathcal{E}|$ (undirected) edges,
representing the communication links in the network. The set of neighbors of
node $i$ is denoted as ${\cal N}_{i}=\\{j\,|\,(i,j)\in\mathcal{E}\\}$ and its
degree is $d_{i}=|{\cal N}_{i}|$. A graph is connected if for every pair of
nodes there is a path between them. In this paper, for the feasibility of the
average output, we assume the graph $\mathcal{G}$ is connected.

Assume each node $i\in{\cal V}$ in the network holds private data $s_{i}$. The
goal of privacy-preserving distributed average consensus is to allow each node
to obtain the average of all private data over the network, i.e.,

$\displaystyle
s_{\scriptscriptstyle\mathrm{ave}}=\frac{1}{n}\sum_{\scriptscriptstyle
i\in{\cal V}}s_{i},$ (1)

without revealing each node’s private data and without any centralized
coordination.

###  II-B Adversary model

In this paper we consider both the well-known eavesdropping adversary and the
so-called passive (i.e., honest-but-curious) adversary. Throughout the paper,
we assume these two adversaries can cooperate by sharing information to
increase the chance of inferring private data. The eavesdropping adversary
works by eavesdropping all communication channels (edges) between nodes in the
network. The passive adversary is assumed to be able to corrupt a subset of
the nodes, referred to as corrupt nodes. The nodes that are not corrupt, on
the other hand, are referred to as honest nodes. The corrupt nodes are assumed
to not deviate from the protocol, but collect all information they see
throughout the protocol. The collected information includes for example the
inputs of the corrupt nodes and the messages they receive during the
computation from neighboring nodes. Denote the set of honest nodes as ${\cal
V}_{h}$ and the corrupt nodes as ${\cal V}_{c}$. We let
$\mathcal{E}_{h}=\\{(i,j)\in\mathcal{E}\mid i,j\in{\cal V}_{h}\\}$ be the set
of edges between two honest nodes and
$\mathcal{E}_{c}=\mathcal{E}\setminus\mathcal{E}_{h}$ be the set of edges
containing at least one corrupt node. Furthermore, the set of honest neighbors
of node $i$ is denoted by ${\cal N}_{\scriptscriptstyle
i,h}=\\{j\,|\,(i,j)\in\mathcal{E}_{h}\\}$.

###  II-C Performance evaluation and corresponding metrics

To evaluate the performance of a privacy-preserving algorithm, there are at
least two key requirements.

####  II-C1 Output accuracy

The output accuracy measures how good the functionality of the algorithm is. A
typical way to quantify the output accuracy is to adopt some distance measures
to evaluate “how far” the output of the privacy-preserving algorithm is,
denoted as $\tilde{\boldsymbol{y}}\in\mathbb{R}^{n}$, to the desired output
$\boldsymbol{y}\in\mathbb{R}^{n}$. In this paper we use the mean squared error
(MSE) to quantify the output accuracy as it is widely used for iterative
processes. It is defined as:

$\displaystyle
e=\frac{1}{n}\left|\left|\tilde{\boldsymbol{y}}-\boldsymbol{y}\right|\right|^{2}.$
(2)

####  II-C2 Individual privacy

Individual privacy measures how well the private data of an honest node is
being protected against the considered adversaries. Since the approaches
considered here are information-theoretical ones, privacy should also be
quantified using an information-theoretical measure. Widely used information-
theoretical metrics for assessing privacy loss include for example
$\epsilon$-differential privacy and mutual information [29]. In this paper we
adopt mutual information as our primary privacy metric for two main reasons.
Firstly, its efficacy has been demonstrated in the realm of privacy-preserving
distributed processing and in various applications [25, 30]. Secondly, it has
been shown in [31, 32] that mutual information is a relaxed version of
$\epsilon$-differential privacy (thus in Section V we refer that our proposed
approach can achieve performances of relaxed DP approaches). And it is easier
to implement mutual information in practice [33]. Considering two (continuous)
random variables $X$ and $Y$, the mutual information is defined by

$\displaystyle{\rm I}(X;Y)=h(X)-h(X|Y),$ (3)

where $h(X)$ denotes the differential entropy of $X$ and $h(X|Y)$ is the
conditional differential entropy, assuming they exist.222In the case of
discrete random variables we replace both differential entropies by the
Shannon entropy so that $I(X;Y)=H(X)-H(Y|X)$. We have that ${\rm I}(X;Y)=0$
when $X$ and $Y$ are independent, meaning that $Y$ does not carry any
information about $X$ and ${\rm I}(X;Y)$ is maximal when there is a one-to-one
relation between $Y$ and $X$.

##  III Problem analysis and impossibility results

In this section we prove two impossibility results, showing that in
distributed average consensus 1) the twin goals of perfect accuracy and worse-
case privacy guarantee cannot be achieved simultaneously; 2) if the subgraph
of honest nodes is disconnected, then no protocol can achieve the performances
of the case where a trusted third party (TTP) is assumed to be available.
These two results are related to the performances of two well-established
privacy-preserving techniques: DP and SMPC, respectively. Without loss of
generality, throughout the paper, we assume the following (recall the private
data $s_{i}$ is a realization of random variable $S_{i}$).

######  Assumption 1.

All private data are statistically independent, i.e., $\forall i,j\in{\cal
V},i\neq j:{\rm I}(S_{i};S_{j})=0$.

######  Assumption 2.

The size of the network $n=|{\cal V}|$ is known to all nodes. Hence, knowing
the average of the data implies knowing the total sum and vice versa.

We have the following results.

###  III-A Impossibility result I: Perfect accuracy and worst-case privacy
cannot be achieved simultaneously

######  Lemma 1.

By assuming perfect accuracy and worst-case privacy, i.e., ${\cal V}_{c}={\cal
V}\setminus\\{i\\}$, the individual privacy leakage becomes

$\displaystyle{\rm I}(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal V}}S_{j},\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal V}_{c}})={\rm
I}(S_{i};S_{i}),$ (4)

which is maximal.

The proof follows trivially from the fact that
$\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
V}}S_{j}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
V}_{c}}S_{j}=S_{i}$ [25]. Similar results have also been proved via different
metrics such as differential privacy [10]. Thus, if there are $n-1$ corrupt
nodes, it is impossible to achieve any privacy for the only remaining honest
node without compromising accuracy. Hence, there is an inherent trade-off
between privacy and accuracy for differential privacy related approaches.

###  III-B Impossibility result II: An SMPC-like ideal world cannot be
achieved unless all honest nodes are connected

In SMPC, the _ideal world_ describes the setting in which a TTP is assumed to
be available. The TTP will (securely) collect all private data from each node
and then compute the output of the function and send back the output to the
nodes. However, in practice a TTP might not exist. The goal of SMPC is to
design a protocol to replace a TTP. In the context of average consensus, as
the corrupt nodes have available both their own private data and the average
result, the information observed by the adversary in an ideal world setting is
given by:

$\displaystyle{\cal O}_{\scriptscriptstyle\mathrm{ideal},{\cal V}_{c}}$
$\displaystyle=\\{S_{i}\\}_{\scriptscriptstyle i\in{\cal
V}_{c}}\cup\\{\operatorname*{\textstyle\sum}_{\scriptscriptstyle i\in{\cal
V}}S_{i}\\}.$ (5)

Hence, for an arbitrary honest node $i\in{\cal V}_{h}$ we have

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\mathrm{ideal},{\cal
V}_{c}})={\rm I}(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle
i\in{\cal V}_{h}}S_{i}).$ (6)

Hence, a perfect SMPC protocol for privacy-preserving distributed average
consensus outputs the correct average value and guarantees that the adversary
obtains no more information about the honest nodes’ private data than (6). The
following result shows that such a protocol cannot exist when the honest nodes
do not form a connected subgraph.

######  Proposition 1.

Let $\mathcal{G}_{h}=({\cal V}_{h},\mathcal{E}_{h})$ be the subgraph of
$\mathcal{G}$ obtained by removing all corrupt nodes. Let
$\mathcal{G}_{\scriptscriptstyle h,1},\ldots,\mathcal{G}_{\scriptscriptstyle
h,k_{h}}$ be the components (connected subgraphs that are not part of any
larger connected subgraph) of $\mathcal{G}_{h}$ and let ${\cal
V}_{\scriptscriptstyle h,k}$ denote the vertex set of
$\mathcal{G}_{\scriptscriptstyle h,k}$.

Then for any protocol outputting
$f(s_{1},s_{2},\ldots,s_{n})=\operatorname*{\textstyle\sum}_{\scriptscriptstyle
i=1}^{n}s_{i}$ to all nodes, after the protocol the adversary will always have
learned $\\{\operatorname*{\textstyle\sum}_{\scriptscriptstyle i\in{\cal
V}_{\scriptscriptstyle h,k}}S_{i}\\}_{\scriptscriptstyle k=1,2,\ldots,k_{h}}$.

###### Proof.

See Appendix C. ∎

In other words, any algorithm with perfect accuracy will always leak the
partial sums of the components of $\mathcal{G}_{h}$ to the adversary. Note
that $\mathcal{G}_{h}$ is very likely to be disconnected in incomplete
networks, especially in the presence of a lot of corrupt nodes. Hence, a
perfect SMPC protocol for privacy-preserving distributed average consensus
does not exist if the adversary disconnects the honest nodes [34].

###  III-C Redefined ideal world for incomplete networks

Using Proposition 1, we can derive a tighter bound on the information view of
the adversary by taking the network topology into account, which we refer to
as the redefined ideal world. The information observed by the adversary in
this redefined ideal world setting, referred to as ${\cal
O}_{\scriptscriptstyle\mathrm{reideal}}$, is

$\displaystyle{\cal O}_{\scriptscriptstyle\mathrm{reideal},{\cal
V}_{c}}=\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}_{c}}\cup\\{\operatorname*{\textstyle\sum}_{\scriptscriptstyle i\in{\cal
V}_{\scriptscriptstyle h,k}}S_{i}\\}_{\scriptscriptstyle k=1,2,\ldots,k_{h}}.$
(7)

Hence, since ${\cal V}_{\scriptscriptstyle h,k}\subseteq{\cal V}_{h}$ we have
${\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\mathrm{reideal},{\cal
V}_{c}})\geq{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\mathrm{ideal},{\cal
V}_{c}})$ and equality holds if and only if the subgraph $\mathcal{G}_{h}$ is
connected, i.e., if $k_{h}=1$.

For the simplicity of notation, assume that the honest node $i$ belongs to the
first honest component, i.e., $i\in{\cal V}_{\scriptscriptstyle h,1}$. We
conclude that a perfect SMPC protocol should reveal no more information about
$s_{i}$ than

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\mathrm{reideal},{\cal
V}_{c}})={\rm I}(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal V}_{\scriptscriptstyle h,1}}S_{j}).$ (8)

##  IV Proposed ADQSP protocol

The proposed ADQSP is constructed from two building blocks in distributed
optimization, namely _adaptive differential quantization_ [35, 28] and
_subspace perturbation_ [18, 19]. In what follows, we first briefly introduce
the fundamentals of distributed optimization and these two building blocks,
and afterwards we explain the details of the proposed approach.

###  IV-A Distributed optimization

To solve (1) in a distributed manner, we first formulate it as a constrained
optimization problem:

$\begin{array}[]{ll}{\displaystyle\min_{\\{\scriptscriptstyle
x_{1},\ldots,x_{n}\\}}}&{{\displaystyle\operatorname*{\textstyle\sum}_{\scriptscriptstyle
i\in{\cal V}}\frac{1}{2}\|x_{i}-s_{i}\|^{2}}}\\\ {\text{ s.t.
}}&{\forall}(i,j)\in\mathcal{E}:~{}{x_{i}=x_{j}},\end{array}$ (9)

where $x_{i}$ is a local optimization variable at node $i$ with optimal value
$x_{i}^{*}=s_{\scriptscriptstyle\rm ave}$. A typical way to solve the above
problem is to apply a solver like ADMM [36] or PDMM [37, 38]. As shown in [38]
these distributed optimization algorithms can be described in a general
framework using monotone operator theory [39] and operator splitting
techniques.

For average consensus, the local updating functions are given by

$\displaystyle x_{\scriptscriptstyle
i}^{(t+1)}=\frac{s_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{i}}B_{\scriptscriptstyle i|j}z_{\scriptscriptstyle
i|j}^{(t)}}{1+cd_{i}}$ (10) $\displaystyle z_{\scriptscriptstyle
j|i}^{(t+1)}=\theta z_{\scriptscriptstyle
j|i}^{(t)}+(1-\theta)\left(z_{\scriptscriptstyle
i|j}^{(t)}+2cB_{\scriptscriptstyle i|j}x_{i}^{(t+1)}\right).$ (11)

Here $\boldsymbol{z}\in\mathbb{R}^{2m}$ is an auxiliary variable having
entries indicated by $z_{\scriptscriptstyle i|j}$ and $z_{\scriptscriptstyle
j|i}$, held by node $i$ and $j$, respectively, related to edge
$(i,j)\in\mathcal{E}$. The matrix $\boldsymbol{B}\in\mathbb{R}^{m\times n}$ is
the graph incidence matrix and $B_{\scriptscriptstyle i|j}$ and
$B_{\scriptscriptstyle j|i}$ are edge-related (scalar) weights, which are
related to entries of $\boldsymbol{B}$ as $B_{\scriptscriptstyle
k,i}=B_{\scriptscriptstyle i|j}$ and $B_{\scriptscriptstyle
k,j}=B_{\scriptscriptstyle j|i}$ for $e_{k}=(i,j)$, i.e., the $k$-th edge in
the graph. We will use the convention that $B_{\scriptscriptstyle i|j}=1$ and
$B_{\scriptscriptstyle j|i}=-1$ if $i<j$. In addition, $c>0$ and
$\theta\in[0,1)$ are constants, with $c$ controlling the convergence rate and
$\theta$ controlling the averaging of the (non-expansive) operators (recall
that $d_{i}=|\mathcal{N}_{i}|$ is the degree of node $i$). The case $\theta=0$
corresponds to PDMM and $\theta=0.5$ corresponds to ADMM.

The protocol is summarized in Algorithm 1 where $t_{\max}$ denotes the maximum
number of iterations. Note that there is also an alternative broadcast
algorithm that requires only broadcasting of $x_{i}^{(t+1)}$’s to all
neighbors, instead of exchanging the $z_{j|i}^{(t+1)}$’s one by one; the
reception of $x_{i}^{(t+1)}$ is all that is needed for node $j\in{\cal N}_{i}$
to compute $z_{j|i}^{(t+1)}$ (see Appendix B for details).

Algorithm 1 Distributed optimization for average consensus

At each $i\in{\cal V}$:

  1. 1.

Initialize $z_{i|j}^{(0)}=0$;

  2. 2.

For $t=0,1,\ldots,t_{\max}-1$ do

    1. (a)

Compute $x_{i}^{(t+1)}$ and $\\{z_{j|i}^{(t+1)}\\}_{j\in{\cal N}_{i}}$ using
(10) and (11), respectively;

    2. (b)

Send $z_{j|i}^{(t+1)}$ to neighbor $j\in{\cal N}_{i}$;

  3. 3.

Output $x_{i}^{(t_{\max})}$

###  IV-B Subspace perturbation

By inspection of (10), we can see that there can be two noise-insertion
options to protect the private data $s_{i}$: adding noise to the optimization
variable $\boldsymbol{x}\in\mathbb{R}^{n}$ directly or adding noise to the
auxiliary variable $\boldsymbol{z}\in\mathbb{R}^{2m}$. The subspace
perturbation approach adds noise to the auxiliary variable $\boldsymbol{z}$,
as it often has more degrees of freedom [18, 19]. We have shown in previous
work [19, 35] that only a part of $\boldsymbol{z}$ is predictable (like
$\boldsymbol{x}$ converges to a value known by the adversary), while the other
part is not. To explain this in more detail, we first write the local
functions (10) and (11) in a compact form as follows:

$\displaystyle\boldsymbol{x}^{(t+1)}$
$\displaystyle=(\boldsymbol{I}+c\boldsymbol{C}^{\top}\boldsymbol{C})^{-1}(\boldsymbol{s}-\boldsymbol{C}^{\top}\boldsymbol{z}^{(t)})$
(12) $\displaystyle\boldsymbol{z}^{(t+1)}$
$\displaystyle=\theta\boldsymbol{z}^{(t)}+(1-\theta)\left(\boldsymbol{P}\boldsymbol{z}^{(t)}+2c\boldsymbol{P}\boldsymbol{C}\boldsymbol{x}^{(t+1)}\right),$
(13)

where
$\boldsymbol{C}=[\boldsymbol{B}_{\scriptscriptstyle+}^{\top},\boldsymbol{B}_{\scriptscriptstyle-}^{\top}]^{\top}\in\mathbb{R}^{2m\times
n}$ and $\boldsymbol{B}_{\scriptscriptstyle+}$ and
$\boldsymbol{B}_{\scriptscriptstyle-}$ contains the positive and negative
entries of $\boldsymbol{B}$, respectively. Furthermore,
$\boldsymbol{P}\in\mathbb{R}^{2m\times 2m}$ is a permutation matrix switching
the upper $m$ rows and lower $m$ rows of the matrix it operates on, i.e.,
$\boldsymbol{P}\boldsymbol{C}=[\boldsymbol{B}_{\scriptscriptstyle-}^{\top},\boldsymbol{B}_{\scriptscriptstyle+}^{\top}]^{\top}$.

Let
$\Psi=\mathrm{ran}(\boldsymbol{C})+\mathrm{ran}(\boldsymbol{P}\boldsymbol{C})$,
whose orthogonal complement is equal to
$\Psi^{\perp}=\ker(\boldsymbol{C}^{\top})\cap\ker((\boldsymbol{P}\boldsymbol{C})^{\top})$.
Moreover, let $\boldsymbol{\Pi}_{\Psi}$ be the orthogonal projection onto
$\Psi$ and let
$\boldsymbol{z}_{\scriptscriptstyle\Psi}^{(t)}=\boldsymbol{\Pi}_{\Psi}\boldsymbol{z}^{(t)}$
and
$\boldsymbol{z}_{\scriptscriptstyle\Psi^{\perp}}^{(t)}=(\boldsymbol{I}-\boldsymbol{\Pi}_{\Psi})\boldsymbol{z}^{(t)}$.
We then have the following decomposition

$\boldsymbol{z}^{(t)}=\boldsymbol{z}_{\scriptscriptstyle\Psi}^{(t)}+\boldsymbol{z}_{\scriptscriptstyle\Psi^{\perp}}^{(t)}.$
(14)

It has been proven in [35] that

$\displaystyle\boldsymbol{z}_{\scriptscriptstyle\Psi^{\perp}}^{(t)}=\frac{1}{2}\left(\boldsymbol{z}_{\scriptscriptstyle\Psi^{\perp}}^{(0)}+\boldsymbol{P}\boldsymbol{z}_{\scriptscriptstyle\Psi^{\perp}}^{(0)}\right)+\frac{1}{2}(2\theta-1)^{t}\left(\boldsymbol{z}_{\scriptscriptstyle\Psi^{\perp}}^{(0)}-\boldsymbol{P}\boldsymbol{z}_{\scriptscriptstyle\Psi^{\perp}}^{(0)}\right).$

Thus, for a given graph and $\theta$,
$\boldsymbol{z}_{\scriptscriptstyle\Psi^{\perp}}^{(t)}$ only depends on the
initialization of the auxiliary variable $\boldsymbol{z}^{(0)}$. The main idea
of subspace perturbation is to initialize $\boldsymbol{z}^{(0)}$ with a
certain distribution having a sufficiently large variance, such that it can
help to protect the private data from being revealed to others (see
Proposition 3 for details of the privacy proof). Moreover, by inspecting (12),
we conclude that the $\boldsymbol{x}$-update is not affected by
$\boldsymbol{z}_{\scriptscriptstyle\Psi^{\perp}}^{(t)}$ as
$(\boldsymbol{z}_{\scriptscriptstyle\Psi^{\perp}}^{(t)})^{\top}\boldsymbol{C}=\boldsymbol{0}$.
Hence, the output accuracy is not affected.

###  IV-C Adaptive differential quantization

Adaptive differential quantization schemes in distributed optimization were
first introduced in [40, 41]. They exploit the fact that when the algorithm
converges, the difference between successive updates will converge to zero.

Let
$Q^{(t)}\colon\mathbb{R}\rightarrow\\{\Delta^{(t)}(a+1/2)\\}_{a\in\mathcal{A}}$
denote an $l$-bit uniform (mid-rise) quantization function where
$a\in\mathcal{A}=\\{-2^{l-1},-2^{l-1}+1,\ldots,2^{l-1}-1\\}$. Here
$\Delta^{(t)}$ is the quantization cell-width which we define as

$\displaystyle\Delta^{(t)}=\max\\{\gamma^{t}\Delta^{(0)},\Delta_{\scriptscriptstyle\mathrm{min}}\\},$
(15)

where $\gamma\in(0,1)$ is a constant for controlling the decreasing rate,
$\Delta^{(0)}$ denotes the initial cell-width and
$\Delta_{\scriptscriptstyle\mathrm{min}}$ denotes the minimum cell-width.
Given cell-width $\Delta^{(t)}$ at iteration $t$, $Q^{(t)}$ maps each input
into its nearest representation value (midpoint of the quantization cells) in
$\\{\Delta^{(t)}(a+1/2)\\}_{\scriptscriptstyle a\in\mathcal{A}}$.

Adaptive differential quantization does not operate on the auxiliary variable
$\boldsymbol{z}$ directly but on the difference of successive variables. That
is, let $\hat{\boldsymbol{z}}$ denote the quantized version of
$\boldsymbol{z}$ and define $\Delta z_{\scriptscriptstyle j|i}^{(t+1)}$ as

$\displaystyle\Delta z_{\scriptscriptstyle
j|i}^{(t+1)}=\left\\{\begin{array}[]{ll}z_{\scriptscriptstyle
j|i}^{(1)}-z_{\scriptscriptstyle j|i}^{(0)}&\textrm{ if $t=0$}\\\
z_{\scriptscriptstyle j|i}^{(t+1)}-\hat{z}_{\scriptscriptstyle
j|i}^{(t)}&\textrm{ if $t\geq 1$}.\end{array}\right.$ (18)

and

$\displaystyle\Delta\hat{z}_{\scriptscriptstyle
j|i}^{(t+1)}=Q^{(t+1)}\left(\Delta z_{\scriptscriptstyle j|i}^{(t+1)}\right).$
(19)

Upon receiving the quantized $\Delta\hat{z}_{\scriptscriptstyle j|i}$, each
node then calculates $\hat{z}_{\scriptscriptstyle j|i}$ as

$\displaystyle\hat{z}_{\scriptscriptstyle
j|i}^{(t+1)}=\left\\{\begin{array}[]{ll}z_{\scriptscriptstyle
j|i}^{(0)}+\Delta\hat{z}_{\scriptscriptstyle j|i}^{(1)}&\textrm{ if $t=0$}\\\
\hat{z}_{\scriptscriptstyle j|i}^{(t)}+\Delta\hat{z}_{\scriptscriptstyle
j|i}^{(t+1)}&\textrm{ if $t\geq 1$}.\end{array}\right.$ (22)

Thus, the quantized $\hat{\boldsymbol{z}}$ can then be constructed as

$\displaystyle\hat{\boldsymbol{z}}^{(t)}=\boldsymbol{z}^{(0)}+\sum_{\tau=1}^{(t)}\Delta\hat{{\boldsymbol{z}}}^{(\tau)}.$
(23)

Às such, the quantized auxiliary variable $\hat{\boldsymbol{z}}^{(t+1)}$
cannot be reconstructed by the adversary until $\boldsymbol{z}^{(0)}$ is
known.

The process of quantization will inevitably introduce distortion in the
computations. Let $n_{\scriptscriptstyle j|i}^{(t+1)}$ denote the introduced
error when quantizing $\Delta z_{\scriptscriptstyle j|i}^{(t+1)}$. We then
have, by combining (18) and (22), that

$\displaystyle n_{\scriptscriptstyle j|i}^{(t+1)}$
$\displaystyle=\Delta\hat{z}_{\scriptscriptstyle j|i}^{(t+1)}-\Delta
z_{\scriptscriptstyle j|i}^{(t+1)}$ $\displaystyle=\hat{z}_{\scriptscriptstyle
j|i}^{(t+1)}-z_{\scriptscriptstyle j|i}^{(t+1)}.$ (24)

When implementing quantization, i.e., $\Delta z\rightarrow\Delta\hat{z}$, we
apply a popular technique in quantization called dithering [42] when
implementing the quantization function $Q^{(t)}$, this ensure that the
quantization error is uniformly distributed over
$[-\frac{\Delta^{(t)}}{2},\frac{\Delta^{(t)}}{2}]$, and is independent of
$\Delta z_{\scriptscriptstyle j|i}^{(t+1)}$, thus of $z_{\scriptscriptstyle
j|i}^{(t+1)}$. In the coming Section VI-C we will show how this property
benefits the privacy analysis.

###  IV-D Details of the proposed approach

Putting things together, the proposed approach first applies subspace
perturbation and then adopts adaptive differential quantization to quantize
the difference variable before updating. More specifically, at $t=0$, subspace
perturbation is applied by initializing $z_{\scriptscriptstyle i|j}^{(0)}$ at
every node $i$ with noise drawn from a distribution having large variance and
sending it to neighbors $j\in{\cal N}_{i}$ via a securely encrypted channel.
Each node $i$ then updates its local variable $x_{\scriptscriptstyle i}^{(1)}$
and auxiliary variables $z_{\scriptscriptstyle j|i}^{(1)}$ according to (10)
and (11), respectively, after which $\Delta z_{\scriptscriptstyle j|i}^{(1)}$
and $\Delta\hat{z}_{\scriptscriptstyle j|i}^{(1)}$ are computed using (18) and
(19), respectively. After exchanging these quantities between neighboring
nodes, $\Delta\hat{\boldsymbol{z}}$ is computed as (22).

For $t\geq 1$, after achieving the quantized $\hat{z}_{\scriptscriptstyle
i|j}^{(t)}$, each node $i$ then repeats the following updating steps:

$\displaystyle x_{\scriptscriptstyle
i}^{(t+1)}=\frac{s_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{i}}B_{\scriptscriptstyle i|j}\hat{z}_{\scriptscriptstyle
i|j}^{(t)}}{1+cd_{i}}$ (25) $\displaystyle\forall j\in{\cal
N}_{\scriptscriptstyle i}:z_{\scriptscriptstyle
j|i}^{(t+1)}=\theta\hat{z}_{\scriptscriptstyle
j|i}^{(t)}+(1-\theta)\left(\hat{z}_{\scriptscriptstyle
i|j}^{(t)}+2cB_{\scriptscriptstyle i|j}x_{i}^{(t+1)}\right).$ (26)

Note that except transmitting the initialized $\boldsymbol{z}^{(0)}$ all the
communication channels do not require secure channel encryption when
transmitting the quantized $\Delta\hat{\boldsymbol{z}}$, since from (23) we
can see that the quantized $\hat{\boldsymbol{z}}^{(t)}$ cannot be
reconstructed unless the initialized $\boldsymbol{z}^{(0)}$ is revealed (see
Theorem 2 for detailed privacy proofs).

Algorithm 2 summarizes the details of the proposed approach. In the coming
sections we will analyze the performance of the proposed approach and show its
relation to both SMPC and DP.

Algorithm 2 Proposed ADQSP: privacy-preserving distributed average consensus
via adaptive differentially quantized subspace perturbation

Initialization :

Each node $i$ randomly initializes $z_{\scriptscriptstyle i|j}^{(0)}$’s from
independent Gaussian distributions333Note that except for being independent,
each node can choose its own noise distributions and variances, as long as
they are sufficiently large for privacy guarantee. ${\cal
N}(0;\sigma_{z}^{2})$ for all $j\in\mathcal{N}_{i}$.

Input :

Initialized auxiliary variables $\boldsymbol{z}^{(0)}$, quantization
parameters $\Delta^{(0)}$, $\gamma,\Delta_{\scriptscriptstyle\mathrm{min}},l$,
and $t_{\max}$.

Output :

Optimization solution: $x_{\scriptscriptstyle i}^{(t_{\max})}$

for  _$t=0,1,\ldots,t_{\max}-1$_ do

if  _$t=0$_ then

Receive $z_{\scriptscriptstyle j|i}^{(0)}$ from $j\in{\cal
N}_{\scriptscriptstyle i}$ via secure channels [43].
$x_{\scriptscriptstyle i}^{(1)}\leftarrow$ (10), $\\{z_{\scriptscriptstyle
j|i}^{(1)}\\}_{\scriptscriptstyle j\in{\cal N}_{\scriptscriptstyle
i}}\leftarrow$ (11).

end if

else

Send $\Delta\hat{z}_{\scriptscriptstyle j|i}^{(t)}$ to $j\in{\cal
N}_{\scriptscriptstyle i}$ via non-secure channels.
$\\{\hat{z}_{\scriptscriptstyle i|j}^{(t)}\\}_{\scriptscriptstyle j\in{\cal
N}_{\scriptscriptstyle i}}\leftarrow$ $\eqref{eq:zhatupquant}$,
$x_{\scriptscriptstyle i}^{(t)}\leftarrow$ (25),
$\\{z_{\scriptscriptstyle j|i}^{(t+1)}\\}_{\scriptscriptstyle j\in{\cal
N}_{\scriptscriptstyle i}}\leftarrow$ (26).

end if

$\\{\Delta\hat{z}_{\scriptscriptstyle j|i}^{(t+1)}\\}_{\scriptscriptstyle
j\in{\cal N}_{\scriptscriptstyle i}}\leftarrow$ (19)$,\\{\Delta
z_{\scriptscriptstyle j|i}^{(t+1)}\\}_{\scriptscriptstyle j\in{\cal
N}_{\scriptscriptstyle i}}\leftarrow$ (18)

end for

##  V Information-theoretical analysis of existing SMPC and DP approaches

Before showing that the proposed ADQSP approach can obtain both SMPC and
(relaxed) DP performances, we first introduce and analyze two example
approaches of SMPC and DP. In particular, we will give an information
theoretical analysis of individual privacy.

###  V-A Performance analysis of SMPC-based distributed average consensus

####  V-A1 Application of additive secret sharing in distributed average
consensus

Additive secret sharing is a popular SMPC technique. As an example, we now
briefly explain how to apply additive secret sharing to distributed average
consensus to achieve privacy-preservation [14, 16]. The basic idea is to
encrypt the private data before performing averaging using a traditional
average consensus algorithm such as Algorithm 1 or its broadcast alternative.
Let $\mathbb{Z}_{p}$ be the cyclic group of $p$ elements, represented by the
integers $\\{0,\ldots,p-1\\}$. In order to apply additive secret sharing, we
first need to transform all private data $s_{i}$ to integers in
$\mathbb{Z}_{p}$, where negative numbers are represented by their modular
additive inverse and floating point numbers are scaled up into integers. In
addition, $p$ should be sufficiently large such that
$p\geq\operatorname*{\textstyle\sum}_{\scriptscriptstyle i\in{\cal V}}s_{i}$.
Hence, discrete random variables are considered here. To apply additive secret
sharing [44], each node $i$ first chooses $d_{i}$ elements
$\\{r_{i}^{j}\in\mathbb{Z}_{p}\\}_{\scriptscriptstyle j\in{\cal N}_{i}}$
uniformly at random. It then sends $r_{i}^{j}$ to node $j\in{\cal N}_{i}$
(which requires secure channel encryption) and computes its own share as

$\displaystyle
r_{i}^{i}=s_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
N}_{i}}r_{i}^{j}~{}\mathrm{mod}~{}p,$ (27)

where $r_{i}^{i}$ is a noisy version of the private data $s_{i}$. Two key
properties of additive secret sharing, which we will prove using mutual
information in Proposition 2, are: 1) the secret can only be reconstructed
when all shares are known; 2) no information about the hidden secret can be
inferred as long as one share is missing. We have the following result.

######  Proposition 2.

(Properties of additive secret sharing) Let $R_{i}^{j}$ be uniformly
distributed in $\mathbb{Z}_{p}$ and let $r_{i}^{i}$ be as in (27).
Furthermore, let $k$ be an element in ${\cal N}_{i}^{\prime}={\cal
N}_{i}\cup\\{i\\}$. Then

$\displaystyle{\rm I}(S_{i};\\{R_{i}^{j}\\}_{\scriptscriptstyle j\in{\cal
N}_{i}^{\prime}})={\rm I}(S_{i};S_{i}).$ (28) $\displaystyle{\rm
I}(S_{i};\\{R_{i}^{j}\\}_{\scriptscriptstyle j\in{\cal
N}_{i}^{\prime}\setminus\\{k\\}})=0$ (29)

###### Proof.

See Appendix D. ∎

In order to guarantee that adding noise to the original private data has no
effect on the average result, each node $i$ adds all received shares
$r_{j}^{i}$ from neighboring nodes to the share $r_{i}^{i}$. That is, node $i$
constructs data $s^{\prime}_{i}$ as

$\displaystyle s_{i}^{\prime}$
$\displaystyle=r_{i}^{i}+\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{i}}r_{j}^{i}~{}\mathrm{mod}~{}p$
$\displaystyle=s_{i}+\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{i}}(r_{j}^{i}-r_{i}^{j})~{}\mathrm{mod}~{}p$ (30)

and uses $s^{\prime}_{i}$ as input to Algorithm 1 (broadcast type). After
obtaining the average of $s^{\prime}_{i}$, each node then constructs the final
average output, denoted by $s_{\rm smpc}$, as $s_{\rm smpc}=(n\times
s^{\prime}_{\rm ave}~{}\mathrm{mod}~{}p)/n$.

####  V-A2 Output accuracy

Since $\operatorname*{\textstyle\sum}_{\scriptscriptstyle i\in{\cal
V}}\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
N}_{i}}(r_{j}^{i}-r_{i}^{j})~{}\mathrm{mod}~{}p=0$, the sum of
$s^{\prime}_{i}$ is the same as the sum of $s_{i}$, i.e.,

$\displaystyle\operatorname*{\textstyle\sum}_{\scriptscriptstyle i\in{\cal
V}}s_{i}^{\prime}~{}\mathrm{mod}~{}p$
$\displaystyle=\operatorname*{\textstyle\sum}_{\scriptscriptstyle i\in{\cal
V}}\big{(}s_{i}+\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
N}_{i}}(r_{j}^{i}-r_{i}^{j})\big{)}~{}\mathrm{mod}~{}p$
$\displaystyle=\operatorname*{\textstyle\sum}_{\scriptscriptstyle i\in{\cal
V}}s_{i}$

Thus, the MSE is then given by

$\displaystyle e_{\rm smpc}$ $\displaystyle=(s_{\rm smpc}-s_{\rm ave})^{2}$
$\displaystyle=(\frac{\operatorname*{\textstyle\sum}_{\scriptscriptstyle
i\in{\cal
V}}s_{i}^{\prime}~{}\mathrm{mod}~{}p}{n}-\frac{\operatorname*{\textstyle\sum}_{\scriptscriptstyle
i\in{\cal V}}s_{i}}{n})^{2}=0.$

Hence, output accuracy is not affected by applying additive secret sharing.

####  V-A3 Individual privacy

To analyze privacy, we need to first specify the view of the adversaries. In
this analysis, we consider a scenario where each honest node has at least one
corrupt neighbor. In that case, the view of the adversaries is given by

$\displaystyle{\cal O}_{\scriptscriptstyle\rm SMPC,{\cal V}_{c}}=$
$\displaystyle\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}_{c}}\cup\\{R_{\scriptscriptstyle
j}^{k},R_{k}^{j}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}}\cup\\{X^{(t)}\\}_{t\geq
1}.$

With (10) and (11) we have that

$\displaystyle x_{i}^{(t+3)}-2\theta x_{i}^{(t+2)}+(2\theta-1)x_{i}^{(t+1)}$
$\displaystyle=\frac{-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{i}}B_{\scriptscriptstyle i|j}(z_{\scriptscriptstyle
i|j}^{(t+3)}-2\theta z_{\scriptscriptstyle
i|j}^{(t+2)}+(2\theta-1)z_{\scriptscriptstyle i|j}^{(t+1)})}{1+cd_{i}}$
$\displaystyle=\frac{-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{i}}2c(1-\theta)((1-\theta)x_{i}^{(t+1)}+\theta
x_{j}^{(t+1)}-x_{j}^{(t+2)})}{1+cd_{i}}.$ (31)

Hence, the adversary can compute $\boldsymbol{x}^{(t)}$ for $t\geq 3$ using
the first two iterations ($t=1,2$). We have the following result.

######  Theorem 1.

(Information loss of SMPC protocol) Assume that each honest node has at least
one corrupt neighbor. Then computing averaging using inputs $s_{i}^{\prime}$
given by (30), the adversaries can infer the following information about an
arbitrary honest node $i\in{\cal V}_{h}$:

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\rm SMPC,{\cal
V}_{c}})={\rm I}(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal V}_{\scriptscriptstyle h,1}}S_{j}).$

###### Proof.

See Appendix E and F. ∎

Hence, we conclude that the above SMPC approach achieves perfect output
accuracy and the individual privacy reaches the bound (8) in the redefined
ideal world, i.e.,

$\displaystyle\left(e_{\scriptscriptstyle\rm SMPC}=0,{\rm I}(S_{i};{\cal
O}_{\scriptscriptstyle\rm SMPC,{\cal V}_{c}})={\rm
I}(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
V}_{\scriptscriptstyle h,1}}S_{j})\right).$ (32)

###  V-B Performance analysis of DP-based distributed average consensus

In this section, we describe how DP-like methods [11, 12, 10] can be applied
in average consensus. Specifically, this approach falls under _local
differential privacy_ (LDP) [45], in which there is no centralized server
available and each node considers all other nodes to be corrupt. The most
straightforward way to incorporate LDP in distributed average consensus is via
_local perturbation_ : every node $i$ draws a random noise $r_{i}$ from some
predetermined distribution, and adds it to its private data to obtain
perturbed data, denoted as

$\displaystyle\forall i\in{\cal V}:~{}\tilde{s}_{i}=s_{i}+r_{i}$ (33)

An average consensus protocol is then run on the perturbed data
$\tilde{s}_{i}$ instead of the private data $s_{i}$.

####  V-B1 Output accuracy

Since distributed average consensus protocol is performed on $\tilde{s}_{i}$,
its output is then given by $\frac{1}{n}\sum_{i}\tilde{s}_{i}$, so the MSE (2)
is given by

$\displaystyle{e_{\scriptscriptstyle\rm
DP}}=\frac{1}{n}\sum_{i=1}^{n}(\tilde{s}_{i}-s_{i})^{2}=\frac{1}{n}\sum_{i=1}^{n}r_{i}^{2}.$
(34)

####  V-B2 Individual privacy

As explained before, mutual information is a relaxed version of
$\epsilon$-differential privacy [31, 32]. For consistency with the rest of
this paper, here we also measure privacy leakages of DP approaches via mutual
information. Therefore, we refer that our approach achieves performances of
relaxed DP approaches. DP assumes that all nodes other than the considered
node $i$ are corrupt. In particular, the DP adversary knows $\tilde{s}_{j}$
for $j\neq i$ and, from the output of the average consensus protocol, also
$\tfrac{1}{n}\sum_{j}\tilde{s}_{j}$. It follows that the DP adversary can
always deduce $\tilde{s}_{i}$, and so individual privacy is given by

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\rm DP,{\cal
V}\setminus\\{i\\}})={\rm I}(S_{i};S_{i}+R_{i}).$ (35)

Existing mechanisms give bounds to this, under assumptions of the distribution
of the $S_{i}$. For instance, if it is known that $s_{i}\in[\alpha,\alpha+M]$
for $\alpha,M\in\mathbb{R}$, then taking $r_{i}$ to follow the Laplace
distribution with parameter $M/\varepsilon$ ensures that (35) is bounded by
$\varepsilon$ [26]. Note that all noises $R_{i}$ are independent of each other
and their variances, denoted $\sigma^{2}_{r_{i}}$, is given by
$\sigma^{2}_{r_{i}}=2M^{2}/\varepsilon^{2}$. Given (34), the variance of
$E_{\scriptscriptstyle\rm DP}$ is thus

$\displaystyle\frac{1}{n^{2}}\sum_{i=1}^{n}\sigma^{2}_{r_{i}}=\frac{2M^{2}}{n\varepsilon^{2}}.$
(36)

This shows that the more privacy we demand, i.e., the lower $\varepsilon$ is,
the less accurate the output average will be. Hence, there is a _privacy-
accuracy trade-off_ in DP approaches.

Overall, we conclude the output accuracy and individual privacy of a DP based
approach is given by

$\displaystyle\left({e_{\scriptscriptstyle\rm
DP}}=\frac{1}{n}\sum_{i=1}^{n}r_{i}^{2};\quad{\rm I}(S_{i};{\cal
O}_{\scriptscriptstyle\rm DP,{\cal V}\setminus\\{i\\}})={\rm
I}(S_{i};S_{i}+R_{i})\right)$ (37)

##  VI Connection of Proposed approach and existing SMPC and DP approaches

We first analyze the output accuracy and individual privacy of the proposed
approach and then explain how it connects to existing SMPC and DP approaches.

###  VI-A Output accuracy

As proved in [40, 41, 35], the output accuracy is dependent on the parameter
of $\Delta_{\scriptscriptstyle\mathrm{min}}$, i.e., minimum quantization cell-
width. Let $r_{i,\scriptscriptstyle\mathrm{min}}$ denote the residual error in
the output of node $i$ compared to the true average
$s_{\scriptscriptstyle\mathrm{ave}}$, so that the MSE of the proposed approach
is given by

$\displaystyle e_{\scriptscriptstyle\rm ADQSP}=\frac{1}{n}\sum_{i\in{\cal
V}}r^{2}_{i,\scriptscriptstyle\mathrm{min}}.$ (38)

We have that

$\displaystyle r_{i,\scriptscriptstyle\mathrm{min}}$
$\displaystyle=x_{\scriptscriptstyle
i}^{(t)}-s_{\scriptscriptstyle\mathrm{ave}}$
$\displaystyle\stackrel{{\scriptstyle(a)}}{{=}}\frac{s_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{i}}B_{\scriptscriptstyle i|j}\hat{z}_{\scriptscriptstyle
i|j}^{(t-1)}}{1+cd_{i}}-s_{\scriptscriptstyle\mathrm{ave}}$
$\displaystyle\stackrel{{\scriptstyle(b)}}{{=}}\frac{s_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{i}}B_{\scriptscriptstyle i|j}z_{\scriptscriptstyle
i|j}^{(t-1)}}{1+cd_{i}}-\frac{\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{i}}B_{\scriptscriptstyle i|j}n_{\scriptscriptstyle
i|j}^{(t-1)}}{1+cd_{i}}-s_{\scriptscriptstyle\mathrm{ave}},$ (39)

where (a) uses (25) and (b) uses (24). Since the first term in the right-hand
side of (39) equals $s_{\scriptscriptstyle\mathrm{ave}}$ as
$t\rightarrow\infty$, we conclude that

$r_{i,\scriptscriptstyle\mathrm{min}}\rightarrow-\frac{\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{i}}B_{\scriptscriptstyle i|j}n_{\scriptscriptstyle
i|j}^{(t-1)}}{1+cd_{i}}\quad\text{as }t\to\infty.$

Note that for the special case where
$\Delta_{\scriptscriptstyle\mathrm{min}}=0$, we have that
$n_{\scriptscriptstyle i|j}^{(t)}\to 0$ as $t\rightarrow\infty$ and thus
$r^{2}_{i,\scriptscriptstyle\mathrm{min}}\to 0$, hence perfect output accuracy
is guaranteed.

###  VI-B Individual privacy

With the adopted quantization scheme, the total collection of information
transmitted over the network is $\\{z_{\scriptscriptstyle
i|j}^{(0)}\\}_{\scriptscriptstyle(i,j)\in\mathcal{E}},\\{\Delta\hat{z}_{\scriptscriptstyle
i|j}^{(t)}\\}_{\scriptscriptstyle(i,j)\in\mathcal{E},t\geq 1}$. Of these, only
the initialized $\\{z_{\scriptscriptstyle
i|j}^{(0)}\\}_{\scriptscriptstyle(i,j)\in\mathcal{E}}$ are transmitted over a
secure channel. Thus, the eavesdropping adversary has the knowledge of
$\\{\Delta\hat{z}_{\scriptscriptstyle
j|k}^{(t)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E},t\geq 1}$ The passive
adversary has the knowledge of $\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}_{c}}\cup\\{Z_{\scriptscriptstyle
j|k}^{(0)},\Delta\hat{Z}_{\scriptscriptstyle
j|k}^{(t)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c},t\geq 1}$ and hence
combining the knowledge of these gives that the view of an adversary in our
proposed algorithm is

$\displaystyle{\cal O}_{\scriptscriptstyle\rm ADQSP,{\cal
V}_{c}}=\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}_{c}}\cup\\{Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}}\cup\\{\Delta\hat{Z}_{\scriptscriptstyle
j|k}^{(t)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E},t\geq 1}).$

In what follows we will show that the proposed approach can achieve both SPMC
and DP performances under different parameter settings.

###  VI-C Proposed approach achieves SMPC performances by setting
$\Delta_{\mathrm{min}}=0$

We will prove our claim via two main results: 1) the proposed approach obtains
similar properties as the SMPC technique, i.e., additive secret sharing; 2)
The proposed approach achieves the same performances as the SMPC approach.

We remark that the initialized $z_{\scriptscriptstyle i|j}^{(0)}$’s together
with $x_{i}^{(1)}$ can be considered as shares of $s_{i}$, similar to the
additive secret sharing scheme. In the following, we prove that it also
satisfies two key properties of additive secret sharing scheme, similar to
Proposition 2.

######  Proposition 3.

(The proposed ADQSP satisfies two properties required for additive secret
sharing.) Let $Z_{\scriptscriptstyle i|j}^{(0)}\sim{\cal N}(0,\sigma_{z}^{2})$
and let
$x_{i}^{(1)}=\frac{s_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{i}}B_{\scriptscriptstyle i|j}z_{\scriptscriptstyle
i|j}^{(0)}}{1+cd_{i}}$. Furthermore, let $k$ be an element in ${\cal N}_{i}$
and denote the variance of $S_{i}$ by $\sigma^{2}_{s}$. Then

$\displaystyle{\rm I}(S_{i};\\{Z_{\scriptscriptstyle
i|j}^{(0)}\\}_{\scriptscriptstyle j\in{\cal
N}_{i}\setminus\\{k\\}},X_{i}^{(1)})$
$\displaystyle\leq\frac{1}{2}\log(1+\frac{\sigma_{s}^{2}}{\sigma_{z}^{2}})$
(40) $\displaystyle{\rm I}(S_{i};\\{Z_{\scriptscriptstyle
i|j}^{(0)}\\}_{\scriptscriptstyle j\in{\cal N}_{i}},X_{i}^{(1)})$
$\displaystyle={\rm I}(S_{i};S_{i}).$ (41)

For $\sigma_{z}^{2}\rightarrow\infty$ we obtain

$\displaystyle\lim_{\sigma_{z}^{2}\rightarrow\infty}{\rm
I}(S_{i};\\{Z_{\scriptscriptstyle i|j}^{(0)}\\}_{\scriptscriptstyle j\in{\cal
N}_{i}\setminus\\{k\\}},X_{i}^{(1)})=0.$ (42)

###### Proof.

See Appendix G. ∎

We now proceed to the main results of individual privacy.

######  Theorem 2.

(Upper and lower bound of the information loss of the proposed ADQSP approach
when $\Delta_{\scriptscriptstyle\mathrm{min}}=0$.) Assume that all nodes has
at least one corrupt neighbor, the information that the adversaries can infer
about an arbitrary honest node $i\in{\cal V}_{h}$ is upper bounded by:

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\rm ADQSP,{\cal
V}_{c}})\leq$ $\displaystyle{\rm
I}(S_{i};\\{S_{j}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle j,h}}B_{\scriptscriptstyle j|k}Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle j\in{\cal V}_{\scriptscriptstyle
h,1}},\\{Z_{\scriptscriptstyle j|k}^{(0)}-Z_{\scriptscriptstyle
k|j}^{(0)}\\}_{\scriptscriptstyle j,k\in{\cal V}_{\scriptscriptstyle h,1}}),$
(43)

assuming $\sigma_{z}^{2}\rightarrow\infty$, the above becomes

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\rm ADQSP,{\cal
V}_{c}})\leq{\rm I}(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal V}_{\scriptscriptstyle h,1}}S_{j}).$ (44)

Assuming $t_{\max}\rightarrow\infty$, the information loss is also lower
bounded by:

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\rm ADQSP,{\cal
V}_{c}})$ $\displaystyle\geq
I(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
V}_{h,1}}S_{j}).$ (45)

###### Proof.

See Appendix I for proof of (2) and (44), Appendix J for proof of (45). ∎

Overall, we conclude that when $\Delta_{\mathrm{min}}=0$ the output accuracy
and individual privacy of the proposed ADQSP protocol is given by

$\displaystyle\left(e_{\scriptscriptstyle\rm ADQSP}=0;{\rm I}(S_{i};{\cal
O}_{\scriptscriptstyle\rm ADQSP,{\cal V}_{c}})={\rm
I}(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
V}_{\scriptscriptstyle h,1}}S_{j}).\right)$ (46)

which is identical to the performance of SMPC approach (32).

(a) $\theta=0$

(b) $\theta=0.2$

(c) $\theta=0.5$

Figure 1: Convergence of the optimization variable in terms of three different
variances of the auxiliary variable, i.e., $\sigma_{z}=10^{3}$,
$\sigma_{z}=10^{2}$ and $\sigma_{z}=10^{1}$ given three different distributed
optimizers: (a) $\theta=0$ (PDMM), (b) $\theta=0.2$ and (c) $\theta=0.5$
(ADMM), wherein $\Delta_{\scriptscriptstyle\mathrm{min}}=0$.

(a) $\theta=0$

(b) $\theta=0.2$

(c) $\theta=0.5$

Figure 2: Convergence of the optimization variable in terms of three different
quantization parameter setting, i.e.,
$\Delta_{\scriptscriptstyle\mathrm{min}}=10^{-3}$,
$\Delta_{\scriptscriptstyle\mathrm{min}}=10^{-2}$ and
$\Delta_{\scriptscriptstyle\mathrm{min}}=10^{-1}$ given three different
distributed optimizers: (a) $\theta=0$ (PDMM), (b) $\theta=0.2$ and (c)
$\theta=0.5$ (ADMM), wherein $\sigma_{z}=10^{3}$.

###  VI-D Proposed approach achieves performances of (relaxed) DP approaches
by setting $\Delta_{\mathrm{min}}>0$

DP approach is the worst-case scenario where there are $n-1$ corrupt nodes,
i.e., ${\cal V}_{c}={\cal V}\setminus\\{i\\}$, which implies ${\cal
N}_{\scriptscriptstyle i,h}=\emptyset$ and $\mathcal{G}_{i}=\\{i\\}$. We have
the following result

######  Theorem 3.

(Information loss of the proposed approach when ${\cal V}_{c}={\cal
V}\setminus\\{i\\}$ and $\Delta_{\mathrm{min}}>0$) The information loss is
given by

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\rm ADQSP,{\cal
V}\setminus\\{i\\}})={\rm I}(S_{i};\\{S_{i}+c_{\scriptscriptstyle
i,k}N_{\scriptscriptstyle k|i}^{(t+1)}\\}_{t\geq 0})$ (47)

where $c_{\scriptscriptstyle
i,k}=\frac{1+cd_{i}}{(1-\theta)2cB_{\scriptscriptstyle i|k}}$.

###### Proof.

See Appendix K. ∎

Note that in this case if $\Delta_{\mathrm{min}}=0$, we have
$N_{\scriptscriptstyle k|i}^{(t)}\rightarrow 0$ thus the above ${\rm
I}(S_{i};{\cal O}_{\scriptscriptstyle\rm ADQSP,{\cal V}\setminus\\{i\\}})={\rm
I}(S_{i};\\{S_{i}+c_{\scriptscriptstyle i,k}N_{\scriptscriptstyle
k|i}^{(t+1)}\\}_{t\geq 0})={\rm I}(S_{i};S_{i})$ which is maximal, i.e., all
the private information is revealed.

Therefore, we should set $\Delta_{\mathrm{min}}>0$ and the corresponding
quantization noise $N_{\scriptscriptstyle k|i}^{(t+1)}$ will help to guarantee
privacy. By inspecting the output accuracy (38) and individual privacy (47) we
can see that increasing $\Delta_{\mathrm{min}}$ will result less accurate
output and more privacy guarantee as the quantization noise $n_{i|j}^{(t)}$s
at convergence becomes larger. This complies to the privacy-accuracy trade-off
of DP discussed in Section V-B. Overall, we conclude that by setting
$\Delta_{\mathrm{min}}>0$, the proposed ADQSP gives privacy guarantees in the
presence of $n-1$ corrupt nodes, analogous to DP. Its output accuracy and
individual privacy are given by

$\displaystyle\left(e_{\scriptscriptstyle\rm ADQSP}=\frac{1}{n}\sum_{i\in{\cal
V}}r^{2}_{i,\scriptscriptstyle\mathrm{min}};\right.$ $\displaystyle\left.{\rm
I}(S_{i};{\cal O}_{\scriptscriptstyle\rm ADQSP,{\cal V}\setminus\\{i\\}})={\rm
I}(S_{i};\\{S_{i}+c_{\scriptscriptstyle i,k}N_{\scriptscriptstyle
k|i}^{(t+1)}\\}_{t\geq 0}).\right)$ (48)

##  VII Numerical results

Figure 3: Individual privacy: normalized mutual information (RHS of (2)) as a
function of $\sigma_{z}$ using the proposed approach; NMI of ${\rm
I}(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
V}_{\scriptscriptstyle h,1}}S_{j})$ using the existing SMPC approach.  Figure
4: Output accuracy: MSE of the optimization variable in terms of iteration
numbers using the proposed approach and DP approach under two different sets
of parameter. Figure 5: Individual privacy: NMI as a function of iteration
numbers using the proposed approach and DP approach under two different set of
parameters.

In this section, simulation results will be presented to demonstrate the
performance of the proposed approach and its connections to both SMPC and DP.

###  VII-A Convergence behavior of the proposed approach

To simulate a distributed network, we simulate a geometric graph with $n=30$
nodes in a room of size $1\times 1\times 1$ meter and the coordinates of each
node are randomly generated from uniform distribution within the range of
$[0,1]$. Every two nodes are neighbors if and only if their distance is within
the radius $\sqrt{\frac{2\log(n)}{n}}$, this guarantees that the generated
graph will be connected with a high probability [46]. Without loss of
generality, all private data $\\{s_{i}\\}_{i\in{\cal V}}$ are randomly drawn
from a Gaussian distribution with unit variance and zero mean. The constant
$c$ for controlling the convergence rate is set as $1$. The bitrate $l$ is set
as $2$.

To demonstrate the flexibility and general applicability of the proposed
approach, in Fig. 1 and 2 we show its convergence behavior under different
parameter settings. Each experiment is averaged over $10^{4}$ times. The
mutual information is estimated using the npeet toolbox [47].

  1. 1.

First, we demonstrate that the proposed approach is applicable to different
types of distributed optimizers, i.e., to different choices of
$\theta\in[0,1)$. We take $\theta=0,~{}0.2,~{}0.5$; note that $\theta=0$
corresponds to PDMM and $\theta=0.5$ corresponds to ADMM. As can be seen from
Fig. 1 and 2, the convergence behavior is independent of the choice of
$\theta$, and our approach can be applied to different distributed optimizers.

  2. 2.

In Fig. 1 we demonstrate the convergence behavior of the optimization variable
by varying the variance of the initialized auxiliary variable, which controls
the achieved privacy level (see details below in Fig. 3). Clearly, we can see
that the convergence rate is independent of the variance magnitude, as a
higher variance only incurs a higher initial error, thus a larger offset.

  3. 3.

In Fig. 2 we demonstrate the convergence behaviors by varying the quantization
cell-width $\Delta_{\scriptscriptstyle\mathrm{min}}$. We can see that, as
expected, the output accuracy is degraded by increasing
$\Delta_{\scriptscriptstyle\mathrm{min}}$ (in Fig. 5 we will show the privacy
leakage becomes less by increasing $\Delta_{\scriptscriptstyle\mathrm{min}}$).
Hence, the trade-off between privacy and accuracy is controlled by the
parameter $\Delta_{\scriptscriptstyle\mathrm{min}}$.

###  VII-B Connection to existing SMPC and DP approaches

We now proceed to consolidate our claims that the proposed approaches can
reduce to both SMPC and DP by choosing appropriate parameter settings.

####  VII-B1 SMPC

In Fig. 1 we show that by setting $\Delta_{\scriptscriptstyle\mathrm{min}}=0$
the proposed approach is able to converge to accurate output average result,
similar to the results reported in SMPC approach [16, 14]. As for individual
privacy, we consider the case where there are only two honest nodes in the
network and they are connected to each other. In Fig. 3 we show the achieved
privacy level for one honest node of the proposed approach, by taking the
normalized mutual information (NMI) on RHS of (2) as a function of the
variance $\sigma_{z}$. In addition, we also depict the achieved privacy of the
existing SMPC approach, i.e., the normalized mutual information ${\rm
I}(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
V}_{\scriptscriptstyle h,1}}S_{j})$ in the redefined ideal world (8). We see
that by increasing the variance $\sigma_{z}$, the proposed approach gets
closer to the bound given in SMPC approach. Hence, with Fig. 1 and 3, we
validate the claim that the proposed approach can achieve the same
performances as SMPC approach when
$\Delta_{\scriptscriptstyle\mathrm{min}}=0$.

####  VII-B2 DP

In order to demonstrate that the proposed approach achieves similar privacy to
a DP approach by setting $\Delta_{\scriptscriptstyle\mathrm{min}}>0$, we
assume that the noise added in DP approach is uniformly distributed over the
range $[\frac{-u_{r}}{2},\frac{u_{r}}{2}]$. By inspecting Fig. 4 we can see
that by setting $u_{r}=\Delta_{\scriptscriptstyle\mathrm{min}}$, the proposed
approach achieves similar output accuracy as the DP approach. Note that by
tuning parameters $c$ the constant for controlling the convergence rate and
$\gamma$ the decreasing rate of quantization cell-width, it is possible to
achieve a good combination which even has a faster convergence rat compared to
the non-quantized case (see [40, 41] for more details). As for individual
privacy, let node $i$ be the only honest node and for simplicity we let
$c=d_{i}=1$ and $\theta=0$ such that $c_{\scriptscriptstyle
i,k}=\frac{1+cd_{i}}{(1-\theta)2cB_{\scriptscriptstyle i|k}}=1$ in (47). In
Fig. 5 we plot the NMI of ${\rm I}(S_{i};\\{S_{i}+c_{\scriptscriptstyle
i,j}N_{\scriptscriptstyle j|i}^{(t+1)}\\}_{\scriptscriptstyle j\in{\cal
N}_{i}})$ as a function of the iteration number $t$ using the proposed
approach. For the DP type approach, the NMI is given by ${\rm
I}(S_{i};S_{i}+R_{i})$. From the figure we conclude that as the iteration
grows, ${\rm I}(S_{i};\\{S_{i}+c_{\scriptscriptstyle i,j}N_{\scriptscriptstyle
j|i}^{(t+1)}\\}_{\scriptscriptstyle j\in{\cal N}_{i}})$ of the proposed
approach can attach to the ${\rm I}(S_{i};S_{i}+R_{i})$ of DP type approach,
which substantiates our theoretical results.

##  VIII Conclusion

In this paper, we proposed a novel privacy-preserving distributed average
consensus approach called ADQSP. Through a comprehensive information-
theoretical privacy analysis, we demonstrate the flexibility and optimality of
the proposed approach. Though not directly derived from existing cryptographic
tools, it enjoys both the benefits of SMPC and DP techniques and can achieve
their performances by controlling the quantization parameter. Experimental
results are presented to validate our theoretical analysis.

##  Appendix A List of Abbreviations

Abbreviation | Full description
---|---
SMPC | Secure multiparty computation
DP | Differential privacy
ADQSP | Adaptive differentially quantized subspace perturbation
MSE | Mean squared error
TTP | Trusted third party
LDP | Local differential privacy
TABLE I: Abbreviations

##  Appendix B Broadcast alternative of Algorithm 1

Algorithm 3 Distributed optimization for average consensus (broadcast)

At each $i\in{\cal V}$:

  1. 1.

Initialize $\\{z_{\scriptscriptstyle i|j}^{(0)}=0\\}_{\scriptscriptstyle
j\in{\cal N}_{i}}$;

  2. 2.

For $t=0,1,\ldots,t_{\max}-1$ do

    1. (a)

Compute $x_{\scriptscriptstyle i}^{(t+1)}$ using (10);

    2. (b)

Broadcast $x_{i}^{(t+1)}$ to all $j\in{\cal N}_{i}$;

    3. (c)

Compute $\forall j\in{\cal N}_{\scriptscriptstyle i}:z_{\scriptscriptstyle
i|j}^{(t+1)},z_{\scriptscriptstyle j|i}^{(t+1)}$ using (11);

  3. 3.

Output $x_{i}^{(t_{\max})}$

##  Appendix C Proof of Proposition 1

To explain the main idea we use the case that $k_{h}=2$, i.e., the adversary
disconnects the honest nodes into two components denoted as a “left” component
$\mathcal{L}$ and a “right” component $\mathcal{R}$. Let
$\boldsymbol{s}_{\mathcal{L}}$, $\boldsymbol{s}_{\mathcal{R}}$ and
$\boldsymbol{s}_{{\cal V}_{c}}$ be vectors consisting of the inputs for the
left component, the right component, and the corrupt nodes, respectively.

###### Proof.

Let $\operatorname{F}$ be the protocol outputting $\sum_{i=1}^{n}s_{i}$. The
view of the adversary is

$\displaystyle{\cal O}_{\scriptscriptstyle\operatorname{F},{\cal
V}_{c}}=\\{\boldsymbol{s}_{{\cal V}_{c}},\boldsymbol{r}_{{\cal
V}_{c}},\boldsymbol{m}_{\mathcal{L}},\boldsymbol{m}_{\mathcal{R}},f(\boldsymbol{s}_{\mathcal{L}},\boldsymbol{s}_{{\cal
V}_{c}},\boldsymbol{s}_{\mathcal{R}})\\},$ (49)

where $\boldsymbol{r}_{{\cal V}_{c}}$ is a vector containing the so-called
randomness from the corrupt nodes, $\boldsymbol{m}_{\mathcal{L}}$ is a vector
containing all messages received from nodes in $\mathcal{L}$ and similarly for
$\boldsymbol{m}_{\mathcal{R}}$ in $\mathcal{R}$.

The adversary can simulate a run of the protocol where it takes the actions
for the nodes in $\mathcal{R}$. It means that it chooses some inputs and
randomness and follow the steps in $\operatorname{F}$, where it uses the
messages $\boldsymbol{m}_{\mathcal{L}}$ when needed in $\operatorname{F}$. If
at some point an entry in $\boldsymbol{m}_{\mathcal{R}}$ differs from the view
it will abort the protocol and start over. Since
$\boldsymbol{s}_{\mathcal{R}}$ and $\boldsymbol{r}_{\mathcal{R}}$ is a valid
choice (there might of course be several others) the adversary will succeed at
some point meaning that it will find an $\tilde{\boldsymbol{s}}_{\mathcal{R}}$
and $\tilde{\boldsymbol{r}}_{\mathcal{R}}$ giving the exact same view as in
(49). Since the adversary uses the exact same messages from the nodes in
$\mathcal{L}$ as in the real execution of $\operatorname{F}$ and the correct
output is included in the view we must have
$f(\boldsymbol{s}_{\mathcal{L}},\boldsymbol{s}_{{\cal
V}_{c}},\boldsymbol{s}_{\mathcal{R}})=f(\boldsymbol{s}_{\mathcal{L}},\boldsymbol{s}_{{\cal
V}_{c}},\tilde{\boldsymbol{s}}_{\mathcal{R}})$. Hence, the adversary can
determine

$\displaystyle\operatorname*{\textstyle\sum}_{\scriptscriptstyle
i\in\mathcal{L}}s_{i}=f(\boldsymbol{s}_{\mathcal{L}},\boldsymbol{s}_{{\cal
V}_{c}},\boldsymbol{s}_{\mathcal{R}})-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
i\in{\cal V}_{c}}s_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle i\in
R}\tilde{s}_{i}$

When the adversary knows $\operatorname*{\textstyle\sum}_{\scriptscriptstyle
i\in\mathcal{L}}s_{i}$ it can of course also determine
$\operatorname*{\textstyle\sum}_{\scriptscriptstyle
i\in\mathcal{R}}s_{i}=\operatorname*{\textstyle\sum}_{\scriptscriptstyle
i=1}^{n}s_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle i\in{\cal
V}_{c}}s_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
i\in\mathcal{L}}s_{i}$. The above proof can easily be generalized to the case
where $k_{h}>2$ and that in this case the adversary will learn all the sums of
the private data in each component. Hence, the proof is now complete. ∎

##  Appendix D Proof of Proposition 2

###### Proof.

The first equality holds since

$\displaystyle(r_{i}^{i}+\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{i}}r_{i}^{j})~{}\mathrm{mod}~{}p=s_{i}.$ (50)

For the last equality we consider two cases. First assume $k=i$, then clearly
${\rm I}(S_{i};\\{R_{i}^{j}\\}_{\scriptscriptstyle j\in{\cal
N}_{i}^{\prime}\setminus\\{k\\}})=0$ since all the $R_{i}^{j}$ are independent
of $S_{i}$. The last case considers $k\neq i$, and in this case we have that

$\displaystyle{\rm I}(S_{i};\\{R_{i}^{j}\\}_{\scriptscriptstyle j\in{\cal
N}_{i}^{\prime}\setminus\\{k\\}})$
$\displaystyle\stackrel{{\scriptstyle\text{$(a)$}}}{{=}}{\rm
I}(S_{i};\\{R_{i}^{j}\\}_{\scriptscriptstyle j\in{\cal
N}_{i}\setminus\\{k\\}},S_{i}-R_{i}^{k})$
$\displaystyle\stackrel{{\scriptstyle\text{$(b)$}}}{{=}}{\rm
I}(S_{i};S_{i}-R_{i}^{k}),$

where $(a)$ uses (50) and the fact that ${\rm I}(X;Y,Z)={\rm I}(X;f(Y,Z))$ if
$f$ is a bijective function; $(b)$ follows from independence between
$\\{S_{i},S_{i}-R_{i}^{k}\\}$ and $\\{R_{i}^{j}\\}_{\scriptscriptstyle
j\in{\cal N}_{i}\setminus\\{k\\}}$. Due to the fact that $R_{i}^{k}$ is
uniformly distributed in $\mathbb{Z}_{p}$, the random variable
$S_{i}-R_{i}^{k}$ is also uniformly distributed in $\mathbb{Z}_{p}$ and hence
independent of $S_{i}$ which completes the proof of (29). ∎

##  Appendix E Necessary result for proving Theorem 1

######  Lemma 2.

Let $X_{1},\ldots X_{n}$ and $R_{1},\ldots R_{n}$ be independent random
variables satisfying $\forall i\colon{\rm I}(X_{i};X_{i}+R_{i})=0$. Then

$\displaystyle\forall i:$ $\displaystyle{\rm
I}(X_{i};X_{1}+R_{1},\ldots,X_{n}+R_{n},\operatorname*{\textstyle\sum}_{j=1}^{n}R_{j})=I(X_{i};\operatorname*{\textstyle\sum}_{j=1}^{n}X_{j}).$

###### Proof.

We first present the following equality:

$\displaystyle\begin{bmatrix}1&1&\cdots&1&1\\\ 0&1&\cdots&1&1\\\
\vdots&\ddots&\ddots&\vdots&\vdots\\\ 0&\cdots&0&1&1\\\
0&\cdots&\cdots&0&1\end{bmatrix}\begin{bmatrix}X_{1}+R_{1}\\\ X_{2}+R_{2}\\\
\vdots\\\ X_{n}+R_{n}\\\
-\sum_{i=1}^{n}R_{i}\end{bmatrix}=\begin{bmatrix}\sum_{i=1}^{n}X_{i}\\\
\sum_{i=2}^{n}X_{i}-R_{i}\\\ \vdots\\\ X_{n}-\sum_{i=1}^{n-1}R_{i}\\\
-\sum_{i=1}^{n}R_{i}\end{bmatrix}$ (51)

With the above result we have

$\displaystyle{\rm
I}(X_{i};X_{1}+R_{1},\ldots,X_{n}+R_{n},\operatorname*{\textstyle\sum}_{j=1}^{n}R_{j})$
$\displaystyle={\rm
I}(X_{i};\operatorname*{\textstyle\sum}_{j=1}^{n}X_{j},\operatorname*{\textstyle\sum}_{j=2}^{n}X_{j}-R_{1},\ldots,X_{n}-\operatorname*{\textstyle\sum}_{j=1}^{n-1}R_{j},\operatorname*{\textstyle\sum}_{j=1}^{n}R_{j})$
$\displaystyle=I(X_{i};\operatorname*{\textstyle\sum}_{j=1}^{n}X_{j}).$

where the first equality holds as the linear map in (51) is bijective; by
inspecting the linear map we can see that the difference of the $k$’th and
$(k+1)$’th rows in RHS of (51) is $X_{k}+R_{k}$, which is independent of all
$X_{i}$s and the $k$’th row of (51), thus
$X_{i}\rightarrow\operatorname*{\textstyle\sum}_{j=1}^{n}X_{j}\rightarrow\operatorname*{\textstyle\sum}_{j=2}^{n}X_{j}-R_{1}\rightarrow\ldots\rightarrow
X_{n}-\operatorname*{\textstyle\sum}_{j=1}^{n-1}R_{i}\rightarrow\operatorname*{\textstyle\sum}_{j=1}^{n}R_{j}$
forms a Markov chain. Thus, the second equality holds. ∎

##  Appendix F Proof of Theorem 1

###### Proof.

We have that

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\rm SMPC,{\cal
V}_{c}})$ $\displaystyle={\rm I}(S_{i};\\{S_{j}\\}_{\scriptscriptstyle
j\in{\cal V}_{c}}\cup\\{R_{\scriptscriptstyle
j}^{k},R_{k}^{j}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}}\cup\\{X^{(1)},X^{(2)}\\})$

as from (31) all $\\{X^{(t)}\\}_{t\geq 2}$ can be determined using
$\\{X^{(1)},X^{(2)}\\}$. Furthermore, note that since we initialize
$z_{\scriptscriptstyle i|j}^{(0)}=0$ and with the inputs from (30) we have
that

$\displaystyle x_{j}^{(1)}$ $\displaystyle=\frac{s_{j}^{\prime}}{1+cd_{j}}$
$\displaystyle x_{j}^{(2)}$
$\displaystyle=\frac{s_{j}^{\prime}+2c(1-\theta)\operatorname*{\textstyle\sum}_{\scriptscriptstyle
k\in{\cal V}_{j}}x_{k}^{(1)}}{1+cd_{j}}$

from (10) and (11).

Thus, there is a bijection between $\\{s_{j}^{\prime}\\}_{\scriptscriptstyle
j\in{\cal V}}$ and $\boldsymbol{x}^{(1)}$ and furthermore,
$\\{s_{j}^{\prime}\\}_{\scriptscriptstyle j\in{\cal V}}$ is enough for
computing $\boldsymbol{x}^{(2)}$. In addition, the corrupt
$\\{s_{j}^{\prime}\\}_{\scriptscriptstyle j\in{\cal V}_{c}}$ can be computed
using $\\{s_{j}\\}_{\scriptscriptstyle j\in{\cal V}_{c}}$ and
$\\{r_{\scriptscriptstyle
j}^{k},r_{k}^{j}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}}$ based on
(30). Thus we have

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\rm SMPC,{\cal
V}_{c}})$ $\displaystyle={\rm I}(S_{i};\\{S_{j}\\}_{\scriptscriptstyle
j\in{\cal V}_{c}},\\{R_{\scriptscriptstyle
j}^{k},R_{k}^{j}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}},\\{S_{j}^{\prime}\\}_{\scriptscriptstyle
j\in{\cal V}_{h}})$
$\displaystyle\stackrel{{\scriptstyle\text{$(a)$}}}{{=}}{\rm
I}(S_{i};\\{R_{\scriptscriptstyle
j}^{k},R_{k}^{j}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}},\\{S_{j}^{\prime}\\}_{\scriptscriptstyle
j\in{\cal V}_{h}})$
$\displaystyle\stackrel{{\scriptstyle\text{$(b)$}}}{{=}}{\rm
I}(S_{i};\\{R_{\scriptscriptstyle
j}^{k},R_{k}^{j}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}},\\{S_{j}+\operatorname*{\textstyle\sum}_{\scriptscriptstyle
k\in{\cal N}_{\scriptscriptstyle
j,h}}R_{k}^{j}-R_{j}^{k}\\}_{\scriptscriptstyle j\in{\cal V}_{h}})$
$\displaystyle\stackrel{{\scriptstyle\text{$(c)$}}}{{=}}{\rm
I}(S_{i};\\{S_{j}+\operatorname*{\textstyle\sum}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle j,h}}R_{k}^{j}-R_{j}^{k}\\}_{\scriptscriptstyle
j\in{\cal V}_{h}})$
$\displaystyle\stackrel{{\scriptstyle\text{$(d)$}}}{{=}}{\rm
I}(S_{i};\\{S_{j}+\operatorname*{\textstyle\sum}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle j,h}}R_{k}^{j}-R_{j}^{k}\\}_{\scriptscriptstyle
j\in{\cal V}_{\scriptscriptstyle h,1}})$
$\displaystyle\stackrel{{\scriptstyle\text{$(e)$}}}{{=}}{\rm
I}(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
V}_{\scriptscriptstyle h,1}}S_{j})$

where (a) holds as the term $\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}_{c}}$ is independent of all other terms; $(b)$ uses the fact that ${\rm
I}(X;Y,Z)={\rm I}(X;f(Y,Z))$ if $f$ is a bijective function, $(c)$ holds as
all terms in $\\{R_{\scriptscriptstyle
j}^{k},R_{k}^{j}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}}$ are
independent of $\\{S_{j}+\operatorname*{\textstyle\sum}_{\scriptscriptstyle
k\in{\cal N}_{\scriptscriptstyle
j,h}}R_{k}^{j}-R_{j}^{k}\\}_{\scriptscriptstyle j\in{\cal V}_{h}}$, and $(d)$
follows from the independence of the different components, and (e) holds as
(d) is a special case of Lemma 2 wherein
$\operatorname*{\textstyle\sum}_{i=1}^{n}R_{i}=0$. ∎

##  Appendix G Proof of Proposition 3

###### Proof.

The equality comes immediately as $s_{i}$ can be determined by
$\\{z_{\scriptscriptstyle i|j}^{(0)}\\}_{\scriptscriptstyle j\in{\cal N}_{i}}$
and $x_{i}^{(1)}$ using (10). Now consider the inequality. We have that

$\displaystyle{\rm I}(S_{i};\\{Z_{\scriptscriptstyle
i|j}^{(0)}\\}_{\scriptscriptstyle j\in{\cal
N}_{i}\setminus\\{k\\}},X_{i}^{(1)})$
$\displaystyle\stackrel{{\scriptstyle\text{$(a)$}}}{{=}}{\rm
I}(S_{i};\\{Z_{\scriptscriptstyle i|j}^{(0)}\\}_{\scriptscriptstyle j\in{\cal
N}_{i}\setminus\\{k\\}},S_{i}-B_{\scriptscriptstyle i|k}Z_{\scriptscriptstyle
i|k}^{(0)})$ $\displaystyle\stackrel{{\scriptstyle\text{$(b)$}}}{{=}}{\rm
I}(S_{i};S_{i}-Z_{\scriptscriptstyle i|k}^{(0)})$
$\displaystyle=h(S_{i}-Z_{\scriptscriptstyle
i|k}^{(0)})-h(Z_{\scriptscriptstyle i|k}^{(0)})$
$\displaystyle\stackrel{{\scriptstyle\text{$(c)$}}}{{=}}h(S_{i}-Z_{\scriptscriptstyle
i|k}^{(0)})-\frac{1}{2}\log(2\pi e\sigma_{z}^{2})$
$\displaystyle\stackrel{{\scriptstyle\text{$(d)$}}}{{\leq}}\log\left(1+\frac{\sigma_{\scriptscriptstyle
s}^{2}}{\sigma_{z}^{2}}\right)$

where (a) uses $\eqref{eq:xup}$ and the fact that ${\rm I}(X;Y,Z)={\rm
I}(X;f(Y,Z))$ if $f$ is a bijective function. (b) follows as
$Z_{\scriptscriptstyle i|j}^{(0)}$ is independent of $S_{i}$ and
$Z_{\scriptscriptstyle i|k}^{(0)}$ and assuming the constant
$B_{\scriptscriptstyle i|k}=1$ (for the case of $B_{\scriptscriptstyle
i|k}=-1$ the proof is the same.). (c) holds as the entropy of a normal
distribution with variance $\sigma^{2}$ is given by $\frac{1}{2}\log(2\pi
e\sigma^{2})$. (d) follows from the fact that the maximum entropy of a
distribution with fixed variance is given by the normal distribution, thus we
obtain the above upper bound.

When $\sigma_{z}^{2}\rightarrow\infty$, $\frac{\sigma_{\scriptscriptstyle
s}^{2}}{\sigma_{z}^{2}}\rightarrow 0$ we thus have

$\displaystyle\lim_{\scriptscriptstyle\sigma_{z}^{2}\rightarrow\infty}{\rm
I}(S_{i};\\{Z_{\scriptscriptstyle i|j}^{(0)}\\}_{\scriptscriptstyle j\in{\cal
N}_{i}\setminus\\{k\\}},X_{i}^{(1)})=0,$

as mutual information is non-negative. ∎

##  Appendix H Necessary results for proving Theorem 2

######  Lemma 3.

Let $X,R$ be independent random variables with variance
$\sigma^{2}_{x},\sigma^{2}_{r}<\infty$, we have

$\displaystyle\lim_{\sigma^{2}_{r}\rightarrow\infty}{\rm I}(X;X+R)=0,$ (52)

i.e., $X$ is asymptotically independent of $X+R$ if
$\sigma^{2}_{r}\rightarrow\infty$.

###### Proof.

Let $\gamma=1/\sigma_{r}$ and define $R^{\prime}=\gamma R$. Hence,
$R^{\prime}$ has unit variance. Since mutual information is invariant under
scaling, we have $I(X;X+R)=I\left(\gamma X;\gamma X+R^{\prime}\right).$ As a
consequence, we have

$\displaystyle\lim_{\sigma^{2}_{r}\rightarrow\infty}I(X;X+R)$
$\displaystyle=\lim_{\gamma\rightarrow 0}I\left(\gamma X;\gamma
X+R^{\prime}\right)$ $\displaystyle=I\left(0;R^{\prime}\right)=0.$

∎

##  Appendix I Proof of (2) and (44) in Theorem 2

###### Proof.

Consider the difference of two successive $\boldsymbol{x}$-updates (12):

$\displaystyle\boldsymbol{x}^{(t+1)}-\boldsymbol{x}^{(t)}=-(I+c\boldsymbol{C}^{T}\boldsymbol{C})^{-1}(\boldsymbol{C}^{T}\Delta{\boldsymbol{z}}^{(t)}).$

Similarly, the difference of two successive $\boldsymbol{z}$ updates in (13)
is given by

$\displaystyle\Delta{\boldsymbol{z}}^{(t+1)}$
$\displaystyle=\theta\Delta{\boldsymbol{z}}^{(t)}+(1-\theta)\boldsymbol{P}\Delta{\boldsymbol{z}}^{(t)}$
$\displaystyle+2c(1-\theta)(\boldsymbol{P}\boldsymbol{C}(\boldsymbol{x}^{(t+1)}-\boldsymbol{x}^{(t)})).$
$\displaystyle=\theta\Delta{\boldsymbol{z}}^{(t)}+(1-\theta)\boldsymbol{P}\Delta{\boldsymbol{z}}^{(t)}$
$\displaystyle-2c(1-\theta)(I+c\boldsymbol{C}^{T}\boldsymbol{C})^{-1}(\boldsymbol{P}\boldsymbol{C}\boldsymbol{C}^{T}\Delta{\boldsymbol{z}}^{(t)}).$
(53)

Hence, $\Delta{\boldsymbol{z}}^{(t+1)}$ can be determined by
$\Delta{\boldsymbol{z}}^{(t)}$.

For an honest node $i$ we have

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\rm ADQSP,{\cal
V}_{c}})$ $\displaystyle={\rm I}(S_{i};\\{S_{j}\\}_{\scriptscriptstyle
j\in{\cal V}_{c}},\\{Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}},\\{\Delta\hat{Z}_{\scriptscriptstyle
j|k}^{(t)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E},t\geq 1})$
$\displaystyle\stackrel{{\scriptstyle\text{$(a)$}}}{{\leq}}{\rm
I}(S_{i};\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}_{c}},\\{Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}},\\{\Delta
Z_{\scriptscriptstyle
j|k}^{(t)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E},t\geq 1})$
$\displaystyle\stackrel{{\scriptstyle\text{$(b)$}}}{{=}}{\rm
I}(S_{i};\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}_{c}},\\{Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}},\\{\Delta
Z_{\scriptscriptstyle j|k}^{(1)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}})$
$\displaystyle\stackrel{{\scriptstyle\text{$(c)$}}}{{=}}{\rm
I}(S_{i};\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}_{c}},\\{Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}},X^{(1)},\\{\Delta
Z_{\scriptscriptstyle
j|k}^{(1)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{h}})$
$\displaystyle\stackrel{{\scriptstyle\text{$(d)$}}}{{=}}{\rm
I}(S_{i};\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}_{c}},\\{Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}},X^{(1)},\\{Z_{\scriptscriptstyle
j|k}^{(0)}-Z_{\scriptscriptstyle
k|j}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{\scriptscriptstyle h}})$
$\displaystyle\stackrel{{\scriptstyle\text{$(e)$}}}{{=}}{\rm
I}(S_{i};\\{S_{j}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle j,h}}B_{\scriptscriptstyle j|k}Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle j\in{\cal V}_{h}},\\{Z_{\scriptscriptstyle
j|k}^{(0)}-Z_{\scriptscriptstyle
k|j}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{\scriptscriptstyle h}})$
$\displaystyle\stackrel{{\scriptstyle\text{$(f)$}}}{{=}}{\rm
I}(S_{i};\\{S_{j}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle j,h}}B_{\scriptscriptstyle j|k}Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle j\in{\cal V}_{\scriptscriptstyle
h,1}},\\{Z_{\scriptscriptstyle j|k}^{(0)}-Z_{\scriptscriptstyle
k|j}^{(0)}\\}_{\scriptscriptstyle j,k\in{\cal V}_{\scriptscriptstyle h,1}})$

where (a) follows from the fact that $\Delta\hat{z}_{\scriptscriptstyle
j|k}^{(t)}$ is a random function of $\Delta z_{\scriptscriptstyle j|k}^{(t)}$
due to quantization, and hence we upper bound the information leakage by
replacing $\Delta\hat{z}_{\scriptscriptstyle j|k}^{(t)}$ by $\Delta
z_{\scriptscriptstyle j|k}^{(t)}$. (b) uses the result of (I). Since each node
has at least one corrupt neighbor thus $\boldsymbol{x}^{(1)}$ can be
determined using $\\{z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}},\\{\Delta
z_{\scriptscriptstyle j|k}^{(1)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}}$
through (11). In addition, using $\boldsymbol{x}^{(1)}$ and
$\\{z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}}$ one can further
determine $\\{z_{\scriptscriptstyle
j|k}^{(1)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}}$, thus also
$\\{\Delta z_{\scriptscriptstyle
j|k}^{(1)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}}$. Hence, (c) holds.
Since $\Delta z_{\scriptscriptstyle i|j}^{(1)}=z_{\scriptscriptstyle
i|j}^{(1)}-z_{\scriptscriptstyle i|j}^{(0)}$, replace $z_{\scriptscriptstyle
i|j}^{(1)}$ using (11) we thus have

$\displaystyle\frac{\Delta z_{\scriptscriptstyle
i|j}^{(1)}}{1-\theta}-2cB_{\scriptscriptstyle
j|i}x_{j}^{(1)}=z_{\scriptscriptstyle j|i}^{(0)}-z_{\scriptscriptstyle
i|j}^{(0)}.$ (54)

Hence, $\\{z_{\scriptscriptstyle j|i}^{(0)}-z_{\scriptscriptstyle
i|j}^{(0)}\\}_{\scriptscriptstyle(i,j)\in\mathcal{E}_{\scriptscriptstyle h}}$
and $\\{x_{j}^{(1)}\\}_{\scriptscriptstyle j\in{\cal V}_{h}}$ can determine
$\\{\Delta z_{\scriptscriptstyle
i|j}^{(1)}\\}_{\scriptscriptstyle(i,j)\in\mathcal{E}_{\scriptscriptstyle h}}$,
thus (d) holds. In addition, from (10) we have

$\displaystyle(1+cd_{i})x_{\scriptscriptstyle
i}^{(1)}+\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
N}_{\scriptscriptstyle i,c}}B_{\scriptscriptstyle i|j}z_{\scriptscriptstyle
i|j}^{(0)}=s_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
N}_{\scriptscriptstyle i,h}}B_{\scriptscriptstyle i|j}z_{\scriptscriptstyle
i|j}^{(0)},$

which again all term in the LHS is known to the adversaries, and hence we
obtain (e). For (e) we also remove $x^{(1)}_{j}$ for corrupt $j$’s since they
can be computed from $\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}_{c}},\\{Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}}$ and after removal
of this $\\{Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}}$ is independent of
the rest and can be removed. (f) follows by the independence of the different
components. Hence, the proof of (2) is complete.

If $\sigma_{z}^{2}\rightarrow\infty$, based on Lemma 3 we have $i\in{\cal
V}_{\scriptscriptstyle h,1}:~{}\lim_{\sigma_{z}^{2}\rightarrow\infty}{\rm
I}(S_{i};S_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle i,h}}B_{\scriptscriptstyle i|k}Z_{\scriptscriptstyle
i|k}^{(0)})=0$, i.e., the private data $S_{i}$ is asymptotically independent
of $S_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle i,h}}B_{\scriptscriptstyle i|k}Z_{\scriptscriptstyle
i|k}^{(0)}$. Thus, the independence condition required in Lemma 2 is
satisfied, the proof follows similarly, we thus have,

$\displaystyle{\rm
I}(S_{i};\\{S_{j}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle j,h}}B_{\scriptscriptstyle j|k}Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle j\in{\cal V}_{\scriptscriptstyle
h,1}},\\{Z_{\scriptscriptstyle j|k}^{(0)}-Z_{\scriptscriptstyle
k|j}^{(0)}\\}_{\scriptscriptstyle j,k\in{\cal V}_{\scriptscriptstyle h,1}})$
$\displaystyle={\rm
I}(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
V}_{\scriptscriptstyle h,1}}S_{j}).$

Hence, proof of (44) is complete.

∎

##  Appendix J Proof of (45) in Theorem 2

###### Proof.

We first derive some equalities which will be used in the proof later. Since
$\Delta z_{\scriptscriptstyle j|i}^{(t+1)}=z_{\scriptscriptstyle
j|i}^{(t+1)}-\hat{z}_{\scriptscriptstyle
j|i}^{(t)}=\Delta\hat{z}_{\scriptscriptstyle
j|i}^{(t+1)}-n_{\scriptscriptstyle j|i}^{(t+1)}$, replace
$z_{\scriptscriptstyle j|i}^{(t+1)}$ using (26) we thus have $\forall t\geq 1$

$\displaystyle\frac{\Delta\hat{z}_{\scriptscriptstyle
j|i}^{(t+1)}-n_{\scriptscriptstyle
j|i}^{(t+1)}}{1-\theta}-2cB_{\scriptscriptstyle
i|j}x_{i}^{(t+1)}=\hat{z}_{\scriptscriptstyle
i|j}^{(t)}-\hat{z}_{\scriptscriptstyle j|i}^{(t)}.$ (55)

Thus, for the corrupt neighbor $k\in{\cal N}_{\scriptscriptstyle i,c}$ the
above becomes

$\displaystyle x_{i}^{(t+1)}+\frac{n_{\scriptscriptstyle
k|i}^{(t+1)}}{2cB_{\scriptscriptstyle
i|k}(1-\theta)}=\frac{-\hat{z}_{\scriptscriptstyle
i|k}^{(t)}+\hat{z}_{\scriptscriptstyle k|i}^{(t)}}{2cB_{\scriptscriptstyle
i|k}}+\frac{\Delta\hat{z}_{\scriptscriptstyle
k|i}^{(t+1)}}{2cB_{\scriptscriptstyle i|k}(1-\theta)}.$ (56)

For the honest neighbor $j\in{\cal N}_{\scriptscriptstyle i,h}$, using (23)
the above (55) becomes

$\displaystyle x_{i}^{(t+1)}+\frac{n_{\scriptscriptstyle
j|i}^{(t+1)}}{2cB_{\scriptscriptstyle
i|j}(1-\theta)}+\frac{z_{\scriptscriptstyle i|j}^{(0)}-z_{\scriptscriptstyle
j|i}^{(0)}}{2cB_{\scriptscriptstyle i|j}}$
$\displaystyle=\frac{-\operatorname*{\textstyle\sum}_{\tau=1}^{(t)}\Delta\hat{z}_{\scriptscriptstyle
i|j}^{(\tau)}+\operatorname*{\textstyle\sum}_{\tau=1}^{(t)}\Delta\hat{z}_{\scriptscriptstyle
j|i}^{(\tau)}}{2cB_{\scriptscriptstyle
i|j}}+\frac{\Delta\hat{z}_{\scriptscriptstyle
j|i}^{(t+1)}}{2cB_{\scriptscriptstyle i|j}(1-\theta)}.$ (57)

Using (23), (25) can be written as

$\displaystyle s_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{\scriptscriptstyle i,h}}B_{\scriptscriptstyle
i|j}z_{\scriptscriptstyle i|j}^{(0)}-(1+cd_{i})x_{i}^{(t+1)}$
$\displaystyle=\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
N}_{\scriptscriptstyle i,h}}B_{\scriptscriptstyle
i|j}(\operatorname*{\textstyle\sum}_{\tau=1}^{t}\Delta\hat{z}_{\scriptscriptstyle
i|j}^{(\tau)})+\operatorname*{\textstyle\sum}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle i,c}}B_{\scriptscriptstyle
i|k}\hat{z}_{\scriptscriptstyle i|k}^{(t)},$ (58)

Note that, all terms in the RHS of the above equations are known by the
adversary, i.e., included in ${\cal O}_{\scriptscriptstyle\rm ADQSP,{\cal
V}_{c}}$.

As a consequence, take the difference of the LHS of (J) and (56) and scale up
by $2c$ we have

$\displaystyle\frac{n_{\scriptscriptstyle j|i}^{(t+1)}}{B_{\scriptscriptstyle
i|j}(1-\theta)}+\frac{z_{\scriptscriptstyle i|j}^{(0)}-z_{\scriptscriptstyle
j|i}^{(0)}}{B_{\scriptscriptstyle i|j}}-\frac{n_{\scriptscriptstyle
k|i}^{(t+1)}}{B_{\scriptscriptstyle i|k}(1-\theta)}$ (59)

In addition, first multiple $(1+cd_{i})$ with the LHS of (56) and add to LHS
of (J) we have

$\displaystyle s_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{\scriptscriptstyle i,h}}B_{\scriptscriptstyle
i|j}z_{\scriptscriptstyle i|j}^{(0)}+c_{\scriptscriptstyle
i,k}N_{\scriptscriptstyle k|i}^{(t+1)},$ (60)

recall $c_{\scriptscriptstyle i,k}=\frac{(1+cd_{i})}{2cB_{\scriptscriptstyle
i|k}(1-\theta)}$.

With the above results we thus have

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\rm ADQSP,{\cal
V}_{c}})$ $\displaystyle\stackrel{{\scriptstyle\text{$(a)$}}}{{=}}{\rm
I}\left(S_{i};\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}_{c}},\\{Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}_{c}},\\{\Delta\hat{Z}_{\scriptscriptstyle
j|k}^{(t)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E},t\geq 1},\right.$
$\displaystyle\left.\\{\frac{N_{\scriptscriptstyle
j|i}^{(t+1)}}{B_{\scriptscriptstyle
i|j}(1-\theta)}+\frac{Z_{\scriptscriptstyle i|j}^{(0)}-Z_{\scriptscriptstyle
j|i}^{(0)}}{B_{\scriptscriptstyle i|j}}\right.$
$\displaystyle\left.-\frac{N_{\scriptscriptstyle
k|i}^{(t+1)}}{B_{\scriptscriptstyle i|k}(1-\theta)}\\}_{\scriptscriptstyle
i\in{\cal V}_{h},j\in{\cal N}_{\scriptscriptstyle i,h},k\in{\cal
N}_{\scriptscriptstyle i,c},t\geq 0},\right.$
$\displaystyle\left.\\{S_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{\scriptscriptstyle i,h}}B_{\scriptscriptstyle
i|j}Z_{\scriptscriptstyle i|j}^{(0)}+c_{\scriptscriptstyle
i,k}N_{\scriptscriptstyle k|i}^{(t+1)}\\}_{\scriptscriptstyle i\in{\cal
V}_{h},k\in{\cal N}_{\scriptscriptstyle i,c},t\geq 0}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{$(b)$}}}{{\geq}}{\rm
I}\left(S_{i};\\{\frac{N_{\scriptscriptstyle
j|i}^{(t+1)}}{B_{\scriptscriptstyle
i|j}(1-\theta)}+\frac{Z_{\scriptscriptstyle i|j}^{(0)}-Z_{\scriptscriptstyle
j|i}^{(0)}}{B_{\scriptscriptstyle i|j}}\right.$
$\displaystyle\left.-\frac{N_{\scriptscriptstyle
k|i}^{(t+1)}}{B_{\scriptscriptstyle i|k}(1-\theta)}\\}_{\scriptscriptstyle
i\in{\cal V}_{h,1},j\in{\cal N}_{\scriptscriptstyle i,h},k\in{\cal
N}_{\scriptscriptstyle i,c},t\geq 0},\right.$
$\displaystyle\left.\\{S_{i}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal N}_{\scriptscriptstyle i,h}}B_{\scriptscriptstyle
i|j}Z_{\scriptscriptstyle i|j}^{(0)}+c_{\scriptscriptstyle
i,k}N_{\scriptscriptstyle k|i}^{(t+1)}\\}_{\scriptscriptstyle i\in{\cal
V}_{h,1},k\in{\cal N}_{\scriptscriptstyle i,c},t\geq 0}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{$(c)$}}}{{\geq}}{\rm
I}\left(S_{i};\\{\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
V}_{h,1}}S_{j}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle j,l\in{\cal
V}_{h,1}}B_{\scriptscriptstyle i|j}(N_{\scriptscriptstyle
l|j}^{(t+1)}-N_{\scriptscriptstyle j|l}^{(t+1)})\right.$
$\displaystyle\left.+\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal V}_{h,1},k\in{\cal N}_{\scriptscriptstyle j,c}}c_{\scriptscriptstyle
j,k}N_{\scriptscriptstyle k|j}^{(t+1)}\\}_{t\geq 0}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{$(d)$}}}{{\geq}}{\rm
I}\left(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
V}_{h,1}}S_{j}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle j,l\in{\cal
V}_{h,1}}B_{\scriptscriptstyle i|j}(N_{\scriptscriptstyle
l|j}^{(t_{\max})}-N_{\scriptscriptstyle j|l}^{(t_{\max})})\right.$
$\displaystyle\left.+\operatorname*{\textstyle\sum}_{\scriptscriptstyle
j\in{\cal V}_{h,1},k\in{\cal N}_{\scriptscriptstyle j,c}}c_{\scriptscriptstyle
j,k}N_{\scriptscriptstyle k|j}^{(t_{\max})}\right),$

where (a) uses the fact that (59) and (60) can be computed by the knowledge of
the adversary. (b) holds by removing the first three terms and consider only
the honest component ${\cal V}_{h,1}$. (c) holds by making a linear
combination of the terms in (b) where the coefficients are
$\frac{1}{2|\mathcal{N}_{\scriptscriptstyle i,c}|}$ for the first terms and
$\frac{1}{|\mathcal{N}_{\scriptscriptstyle i,c}|}$ for the remaining terms.
(d) holds because we consider only the last iteration $t_{\max}$.

Remark that if $\Delta_{\scriptscriptstyle\mathrm{min}}=0$ then
$N_{\scriptscriptstyle i|j}^{(t_{\max})}$ will converge almost surely to $0$
when $t_{\max}\rightarrow\infty$. Hence in the limit we have

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\rm ADQSP,{\cal
V}_{c}})$ $\displaystyle\geq{\rm
I}(S_{i};\operatorname*{\textstyle\sum}_{\scriptscriptstyle j\in{\cal
V}_{h,1}}S_{j}).$

Hence, the proof of (45) is complete. ∎

##  Appendix K Proof of Theorem 3

###### Proof.

We first present the following equality result: similar to (13), consider the
difference of two successive $\boldsymbol{z}$ updates in (26):

$\displaystyle\Delta{\hat{z}_{\scriptscriptstyle
j|i}}^{(t+1)}+n_{\scriptscriptstyle j|i}^{(t+1)}-n_{\scriptscriptstyle
j|i}^{(t)}$ $\displaystyle=\theta\Delta{\hat{z}_{\scriptscriptstyle
j|i}}^{(t)}+(1-\theta)\Delta\hat{z}_{\scriptscriptstyle
i|j}^{(t)}-\frac{2c(1-\theta)B_{\scriptscriptstyle
i|j}}{1+cd_{i}}\sum_{\scriptscriptstyle
k\in\mathcal{N}_{i}}B_{\scriptscriptstyle
i|k}\Delta\hat{z}_{\scriptscriptstyle i|k}^{(t)}.$ (61)

Hence, $\Delta{\hat{z}_{\scriptscriptstyle j|i}}^{(t+1)}$ can be determined by
the difference of quantization noise over successive iterations
$n_{\scriptscriptstyle j|i}^{(t+1)}-n_{\scriptscriptstyle j|i}^{(t)}$ and
$\Delta{\hat{z}_{\scriptscriptstyle j|i}}^{(t)}$ and
$\Delta{\hat{z}_{\scriptscriptstyle i|j}}^{(t)}$ in the previous iteration.

As for $\Delta{\hat{z}_{\scriptscriptstyle j|i}}^{(1)}$ in the first iteration
we have

$\displaystyle\Delta{\hat{z}_{\scriptscriptstyle
j|i}}^{(1)}\stackrel{{\scriptstyle\text{$(a)$}}}{{=}}z_{\scriptscriptstyle
j|i}^{(1)}-z_{\scriptscriptstyle j|i}^{(0)}+n_{\scriptscriptstyle j|i}^{(1)}$
$\displaystyle\stackrel{{\scriptstyle\text{$(b)$}}}{{=}}(1-\theta)(z_{\scriptscriptstyle
i|j}^{(0)}-z_{\scriptscriptstyle j|i}^{(0)})+\frac{1}{c_{\scriptscriptstyle
i,j}}(s_{i}+c_{\scriptscriptstyle i,j}n_{\scriptscriptstyle
j|i}^{(1)}-\operatorname*{\textstyle\sum}_{\scriptscriptstyle
k\in\mathcal{N}_{i}}B_{\scriptscriptstyle i|k}z_{\scriptscriptstyle
i|k}^{(0)}),$ (62)

where (a) uses (22) and (24); (b) replaces $z_{\scriptscriptstyle j|i}^{(1)}$
using (10) and (11).

We start our proof similar to the proof in Appendix J. However, since ${\cal
V}_{c}={\cal V}\setminus\\{i\\}$, ${\cal V}_{h}=\\{i\\}$ and ${\cal
N}_{\scriptscriptstyle i,h}=\emptyset$ we do not have any honest neighbors and
hence we are not adding (59). Thus the equality (a) in the proof of Appendix J
becomes the first equality below:

$\displaystyle{\rm I}(S_{i};{\cal O}_{\scriptscriptstyle\rm ADQSP,{\cal
V}\setminus\\{i\\}})$ $\displaystyle={\rm
I}\left(S_{i};\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}\setminus\\{i\\}},\\{Z_{\scriptscriptstyle
j|k}^{(0)},\Delta\hat{Z}_{\scriptscriptstyle
j|k}^{(t)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E},t\geq 1}\right.,$
$\displaystyle\left.\\{S_{i}+c_{\scriptscriptstyle i,k}N_{\scriptscriptstyle
k|i}^{(t+1)}\\}_{\scriptscriptstyle k\in{\cal N}_{\scriptscriptstyle i},t\geq
0}\right)$ $\displaystyle\stackrel{{\scriptstyle\text{$(a)$}}}{{=}}{\rm
I}\left(S_{i};\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}\setminus\\{i\\}},\\{Z_{\scriptscriptstyle
j|k}^{(0)},\Delta\hat{Z}_{\scriptscriptstyle
j|k}^{(t)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E},t\geq 1}\right.,$
$\displaystyle\left.\\{N_{\scriptscriptstyle
k|i}^{(t+1)}-N_{\scriptscriptstyle k|i}^{(t)}\\}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle i},t\geq 1},\\{S_{i}+c_{\scriptscriptstyle
i,k}N_{\scriptscriptstyle k|i}^{(t+1)}\\}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle i},t\geq 0}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{$(b)$}}}{{=}}{\rm
I}\left(S_{i};\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}\setminus\\{i\\}},\\{Z_{\scriptscriptstyle
j|k}^{(0)},\Delta\hat{Z}_{\scriptscriptstyle
j|k}^{(1)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}}\right.,$
$\displaystyle\left.\\{N_{\scriptscriptstyle
k|i}^{(t+1)}-N_{\scriptscriptstyle k|i}^{(t)}\\}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle i},t\geq 1},\\{S_{i}+c_{\scriptscriptstyle
i,k}N_{\scriptscriptstyle k|i}^{(t+1)}\\}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle i},t\geq 0}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{$(c)$}}}{{=}}{\rm
I}\left(S_{i};\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}\setminus\\{i\\}},\\{Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}}\right.,$
$\displaystyle\left.\\{N_{\scriptscriptstyle
k|i}^{(t+1)}-N_{\scriptscriptstyle k|i}^{(t)}\\}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle i},t\geq 1},\\{S_{i}+c_{\scriptscriptstyle
i,k}N_{\scriptscriptstyle k|i}^{(t+1)}\\}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle i},t\geq 0}\right)$
$\displaystyle\stackrel{{\scriptstyle\text{$(d)$}}}{{=}}{\rm
I}\left(S_{i};\\{N_{\scriptscriptstyle k|i}^{(t+1)}-N_{\scriptscriptstyle
k|i}^{(t)}\\}_{\scriptscriptstyle k\in{\cal N}_{\scriptscriptstyle i},t\geq
1},\\{S_{i}+c_{\scriptscriptstyle i,k}N_{\scriptscriptstyle
k|i}^{(t+1)}\\}_{\scriptscriptstyle k\in{\cal N}_{\scriptscriptstyle i},t\geq
1}\right)$ $\displaystyle\stackrel{{\scriptstyle\text{$(e)$}}}{{=}}{\rm
I}\left(S_{i};\\{S_{i}+c_{\scriptscriptstyle i,k}N_{\scriptscriptstyle
k|i}^{(t+1)}\\}_{\scriptscriptstyle k\in{\cal N}_{\scriptscriptstyle i},t\geq
1}\right)$

where (a) follows as $\\{N_{\scriptscriptstyle
k|i}^{(t+1)}-N_{\scriptscriptstyle k|i}^{(t)}\\}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle i},t\geq 1}$ can be computed by taking the difference
of the last term over successive iterations. (b) holds as based on (K), all
$\\{\Delta\hat{Z}_{\scriptscriptstyle
j|k}^{(t)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E},t\geq 2}$ can be computed
using $\\{N_{\scriptscriptstyle k|i}^{(t+1)}-N_{\scriptscriptstyle
k|i}^{(t)}\\}_{\scriptscriptstyle k\in{\cal N}_{\scriptscriptstyle i},t\geq
1}$ and $\\{S_{j}\\}_{\scriptscriptstyle j\in{\cal
V}\setminus\\{i\\}},\\{Z_{\scriptscriptstyle
j|k}^{(0)},\Delta\hat{Z}_{\scriptscriptstyle
j|k}^{(1)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E},t\geq 1}$. (c) holds as
$\\{\Delta\hat{Z}_{\scriptscriptstyle
j|k}^{(1)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}}$ can be computed using
the other terms based on (K). (d) holds as $\\{S_{j}\\}_{\scriptscriptstyle
j\in{\cal V}\setminus\\{i\\}},\\{Z_{\scriptscriptstyle
j|k}^{(0)}\\}_{\scriptscriptstyle(j,k)\in\mathcal{E}}$ are independent of the
rest two terms. (e) holds as $\\{N_{\scriptscriptstyle
k|i}^{(t+1)}-N_{\scriptscriptstyle k|i}^{(t)}\\}_{\scriptscriptstyle k\in{\cal
N}_{\scriptscriptstyle i},t\geq 1}$ can be determined by
$\\{S_{i}+c_{\scriptscriptstyle i,k}N_{\scriptscriptstyle
k|i}^{(t+1)}\\}_{\scriptscriptstyle k\in{\cal N}_{\scriptscriptstyle i},t\geq
1}$. Hence, the proof is complete. ∎

## References

  * [1] J. Poushter and others,  “Smartphone ownership and internet usage continues to climb in emerging economies,”  Pew Research Center, vol. 22, pp. 1–44, 2016.
  * [2] R. Olfati-Saber, J. A. Fax, and R. M. Murray,  “Consensus and cooperation in networked multi-agent systems,”  IEEEE Proc., vol. 95, no. 1, pp. 215-233, 2007.
  * [3] J. N. Tsitsiklis,  “Problems in decentralized decision making and computation.,”  Tech. Rep., Tech. Rep., Ph.D. dissertation, Massachusetts Institute of Technology, Cambridge, 1984.
  * [4] T. Li, A. K. Sahu, A. Talwalkar and V. Smith,  “Federated learning: Challenges, methods, and future directions,”  IEEE Signal Process. Magazine, vol. 37, no. 3, pp. 50-60,, 2020.
  * [5] R. C. Hendriks, Z. Erkin, and T. Gerkmann,  “Privacy-preserving distributed speech enhancement for wireless sensor networks by processing in the encrypted domain,”  in Proc. Int. Conf. Acoust., Speech, Signal Process., pp. 7005–7009, 2013.
  * [6] M. H. Ruan, M. Ahmad, Y. Q. Wang,  “Secure and privacy-preserving average consensus,”  in Proc. Workshop Cyber-Phys. Syst. Secur. Privacy, pp. 123-129, 2017.
  * [7] P. Braca, R. Lazzeretti, S. Marano, and V. Matta,  “Learning with privacy in consensus $+$ obfuscation,”  IEEE signal process. Lett., vol. 23, no. 9, pp. 1174–1178, 2016.
  * [8] M. T. Hale, M. Egerstedt,  “Differentially private cloud-based multi-agent optimization with constraints,”  in Proc. American Control Conf., pp. 1235-1240, 2015.
  * [9] M. T. Hale, M. Egerstedt,  “Cloud-enabled differentially private multiagent optimization with constraints,”  IEEE Trans. Control Netw. Syst., vol. 5, no. 4, pp. 1693–1706, 2018.
  * [10] E. Nozari, P. Tallapragada, and J. Cortés,  “Differentially private average consensus: Obstructions, trade-offs, and optimal algorithm design,”  Automatica, vol. 81, pp. 221–231, 2017.
  * [11] M. Kefayati, M. S. Talebi, B. H. Khalajand H. R. Rabiee ,  “Secure consensus averaging in sensor networks using random offsets,”  in Proc. of the IEEE Int. Conf. on Telec., and Malaysia Int. Conf. on Commun., pp. 556–560, 2007.
  * [12] Z. Huang, S. Mitra, and G. Dullerud,  “Differentially private iterative synchronous consensus,”  in ACM workshop Privacy electron. Soc., pp. 81–90, 2012.
  * [13] Y. Guo and Y. Gong,  “Practical collaborative learning for crowdsensing in the internet of things with differential privacy,”  in in Proc. IEEE Conf. Commun. Netw. Secur. (CNS), pp.1–9, 2018.
  * [14] N. Gupta, J. Katz, N. Chopra,  “Privacy in distributed average consensus,”  IFAC-PapersOnLine, vol. 50, no. 1, pp. 9515-9520, 2017.
  * [15] N. Gupta, J. Kat and N. Chopra,  “Statistical privacy in distributed average consensus on bounded real inputs,”  in ACC, pp 1836-1841, 2019.
  * [16] Q. Li, I. Cascudo, and M. G. Christensen,  “Privacy-preserving distributed average consensus based on additive secret sharing,”  in Proc. Eur. Signal Process. Conf., pp. 1-5, 2019.
  * [17] Q. Li and M. G. Christensen,  “A privacy-preserving asynchronous averaging algorithm based on shamir’s secret sharing,”  in Proc. Eur. Signal Process. Conf., pp. 1-5, 2019.
  * [18] Q. Li, R. Heusdens and M. G. Christensen,  “Convex optimisation-based privacy-preserving distributed average consensus in wireless sensor networks,”  in Proc. Int. Conf. Acoust., Speech, Signal Process., pp. 5895-5899, 2020.
  * [19] Q. Li, R. Heusdens and M. G. Christensen,  “Privacy-preserving distributed optimization via subspace perturbation: A general framework,”  in IEEE Trans. Signal Process., vol. 68, pp. 5983 - 5996, 2020.
  * [20] N. E. Manitara and C. N. Hadjicostis,  “Privacy-preserving asymptotic average consensus,”  in ECC, pp. 760–765, 2013.
  * [21] Y. Mo and R. M. Murray,  “Privacy preserving average consensus,”  IEEE Trans. Automat Contr., vol. 62, no. 2, pp. 753–765, 2017.
  * [22] J. He, L. Cai, C. Zhao, P. Cheng, X. Guan,  “Privacy-preserving average consensus: privacy analysis and algorithm design,”  IEEE Trans. Signal Inf. Process. Netw., vol. 5, no. 1, pp. 127–138, 2019.
  * [23] Y. Xiong and Z. Li,  “Privacy-preserved average consensus algorithms with edge-based additive perturbations,”  Automatica, vol. 140, pp. 110223, 2022.
  * [24] Y. Zhou and S. Pu,  “Private and accurate decentralized optimization via encrypted and structured functional perturbation,”  IEEE Control Syst. Lett., vol. 7, pp. 1339–1344, 2022.
  * [25] Q. Li, J. S. Gundersen, R. Heusdens and M. G. Christensen,  “Privacy-preserving distributed processing: Metrics, bounds, and algorithms,”  in IEEE Trans. Inf. Forensics Security. vol. 16, pp. 2090–2103, 2021.
  * [26] C. Dwork,  “Differential privacy,”  in ICALP, pp. 1–12, 2006.
  * [27] C. Dwork, F. McSherry, K. Nissim, A. Smith,  “Calibrating noise to sensitivity in private data analysis,”  in Proc. Theory of Cryptography Conf. , pp. 265-284, 2006.
  * [28] Q. Li, M. Lopuhaä-Zwakenberg, R. Heusdens and M. G. Christensen,  “Two for the price of one: communication efficient and privacy-preserving distributed average consensus using quantization,”  in Proc. Eur. Signal Process. Conf., 2022.
  * [29] T. M. Cover and J. A. Tomas,  Elements of information theory,  John Wiley & Sons, 2012.
  * [30] Y. Bu, S. Zou, and V. V. Veeravalli,  “Tightening mutual information-based bounds on generalization error,”  IEEE J. Sel. Areas Info. Theory. vol. 1, no. 1, pp. 121–130, 2020.
  * [31] P. Cuff and L. Yu,  “Differential privacy as a mutual information constraint,”  in Proc. 23rd ACM SIGSAC Conf. Comput. Commun. Secur., pp 43–54, 2016.
  * [32] G. Barthe and B. Kopf,  “Information-theoretic bounds for differentially private mechanisms,”  in IEEE 24th Computer Security Foundations Symposium, 2011, pp. 191–204.
  * [33] M. Gtz, A. Machanavajjhala, G. Wang, X. Xiao, J. Gehrke,  “Publishing search logs—a comparative study of privacy guarantees,”  IEEE Trans. Knowl. Data. Eng. vol. 24, pp. 520 - 532, 2011.
  * [34] Amos Beimel,  “On private computation in incomplete networks,”  in Structural Information and Communication Complexity. 2005, pp. 18–33, Springer Berlin Heidelberg.
  * [35] Q. Li, R. Heusdens and M. G. Christensen,  “Communication efficient privacy-preserving distributed optimization using adaptive differential quantization,”  Signal Process., 2022.
  * [36] S. Boyd, N. Parikh, E. Chu, B. Peleato, J. Eckstein, et al.,  “Distributed optimization and statistical learning via the alternating direction method of multipliers,”  Foundations and Trends in Machine learning, vol. 3, no. 1, pp. 1–122, 2011.
  * [37] G. Zhang and R. Heusdens,  “Distributed optimization using the primal-dual method of multipliers,”  IEEE Trans. Signal Process., vol. 4, no. 1, pp. 173–187, 2018.
  * [38] T. Sherson, R. Heusdens, W. B. Kleijn,  “Derivation and analysis of the primal-dual method of multipliers based on monotone operator theory,”  IEEE Trans. Signal Inf. Process. Netw., vol. 5, no. 2, pp 334-347, 2018.
  * [39] E. Ryu, S. P. Boyd,  “Primer on monotone operator methods,”  Appl. Comput. Math., vol. 15, no. 1, pp. 3-43,, 2016.
  * [40] D. H. M. Schellekens, T. Sherson, and R. Heusdens,  “Quantisation effects in PDMM: A first study for synchronous distributed averaging,”  in Proc. Int. Conf. Acoust., Speech, Signal Process., pp. 4237–4241, 2017.
  * [41] J. A. G. Jonkman, T. Sherson, and R. Heusdens,  “Quantisation effects in distributed optimisation,”  in Proc. Int. Conf. Acoust., Speech, Signal Process., pp. 3649–3653, 2018.
  * [42] L. Schuchman,  “Dither signals and their effect on quantization noise,”  IEEE Transactions on Communication Technology, vol. 12, no. 4, pp. 162–165, 1964.
  * [43] D. Dolev, C. Dwork, O. Waarts, M. Yung,  “Perfectly secure message transmission,”  J. Assoc. Comput. Mach., vol. 40, no. 1, pp. 17-47,, 1993.
  * [44] R. Cramer, I. B. Damgård, and J. B. Nielsen,  “Secure multiparty computation and secret sharing,”  2015\.
  * [45] Shiva Prasad Kasiviswanathan, Homin K Lee, Kobbi Nissim, Sofya Raskhodnikova, and Adam Smith,  “What can we learn privately?,”  SIAM Journal on Computing, vol. 40, no. 3, pp. 793–826, 2011.
  * [46] J. Dall and M. Christensen,  “Random geometric graphs,”  Physical review E, vol. 66, no. 1, pp. 016121, 2002.
  * [47] G. Ver Steeg,  “Non-parametric entropy estimation toolbox (npeet),”  https://github.com/gregversteeg/NPEET, 2000.