∎

11institutetext: S. Zhang 22institutetext: Laboratory for Information and
Decision Systems (LIDS), MIT, MA 02139, USA
22email<EMAIL_ADDRESS>33institutetext: T. Ohlson Timoudas44institutetext:
KTH Royal Institute of Technology 100 44 Stockholm, Sweden
44email<EMAIL_ADDRESS>55institutetext: M. Dahleh 66institutetext:
Laboratory for Information and Decision Systems (LIDS), MIT, MA 02139, USA
66email<EMAIL_ADDRESS>
# Consensus with Preserved Privacy against Neighbor Collusion††thanks: This
work was supported by Knut and Alice Wallenberg Foundation.

Silun Zhang  Thomas Ohlson Timoudas  Munther A. Dahleh

(Received: date / Accepted: date)

###### Abstract

This paper proposes a privacy-preserving algorithm to solve the average
consensus problem based on Shamir’s secret sharing scheme, in which a network
of agents reach an agreement on their states without exposing their individual
state until an agreement is reached. Unlike other methods, the proposed
algorithm renders the network resistant to the collusion of any given number
of neighbors (even with all neighbors’ colluding). Another virtue of this work
is that such a method can protect the network consensus procedure from
eavesdropping.

###### Keywords:

privacy-preserving consensuscyber security network control secret sharing
scheme

##  1 Introduction

As a successful conceptual abstraction of many emerging phenomena in nature,
the multi-agent model (MAM) has been extensively studied in the last decades.
These studies initiated from the fundamental but also inspiring problem,
namely multi-agent consensus, which aims at driving the states of agents to a
global agreement. The formal study of the consensus problem was first
introduced by Degroot degroot1974reaching  in the 1970s, which sparked many
further extensions and developments (see, e.g., olfati2007consensus ;
ren2005survey ; jadbabaie2003coordination  and the references therein). The
methods and results, that were conceived in the study of the consensus
problem, were later adapted to network coordination problems in control
theory, such as formation control song2017intrinsic ; zhang2020intrinsic ;
fax2004information ; zhang2018intrinsic ; zhang2016spherical , distributed
optimization nedic2014distributed ; nedic2009distributed ;
nedic2010constrained ; qu2017harnessing , and also network games
cenedese2020asynchronous ; zhang2019strategy . In the control setting, the
situation is further complicated, as the the agents are governed by nonlinear
dynamics thunberg2014distributed ; zhang2020modeling .

In distributed algorithms, each agent typically requires access to the states
of its neighbors in order to compute a local update. This may leave the agents
in the network vulnerable, as some of them may not wish to disclose this local
information to their neighbors, especially if some of it is highly private or
sensitive. For many applications, it is therefore essential to achieve network
consensus, while preserving the privacy of each agent. For example, in opinion
dynamics albi2014boltzmann , opinions may relate to a sensitive topic, and the
participating individuals expect these to remain secret, especially from their
acquaintances, i.e., each of their neighbors.

The fundamental idea of many existing approaches to privacy-preserving
consensus algorithms, is to conceal the individual state by adding a
deterministic or stochastic disturbance to the real state before communicating
it. This idea was first mentioned by Kefayati et al. in kefayati2007secure ,
where a zero-mean normal noise was added to the agents’ state. Based on this
work, huang2012differentially  proposed a synchronization algorithm that
blends the true state with a random noise drawn from a Laplace distribution
with a time-decaying magnitude. These methods guarantee that the agents reach
consensus, but the value agreed upon may not necessarily be the average of the
initial states. To achieve average consensus, Mo and Murray mo2016privacy
shifted the real state by a particular linear combination of Gaussian
processes, tailored specifically to ensure that at any time the sum of all the
noise injected previously vanishes exactly (also cf. liu2017secure ;
he2018privacy ; katewa2015protecting ). The true states can also be masked by
using a deterministic state mapping altafini2019dynamical , or by simply
adding a deterministic disturbance, such as an offset manitara2013privacy ;
gupta2017privacy , and a perturbation function whose integral corresponding to
the historical effects equals to zero rezazadeh2018privacy .

Another approach to privacy-preserving consensus takes advantage of
homomorphic encryption schemes, which allows algebraic computations to be
performed directly on the encrypted data without the need of deciphering it
first gentry2009fully . Indeed, many prevalent encryption methods are
naturally partially homomorphic, meaning that one, but not the other, of the
addition and multiplication operations can be performed directly on the
ciphertexts. For example, the RSA and ElGamal cryptosystems allow
multiplications on the ciphered data, and the Benaloh and Paillier systems
allow additions without deciphering acar2018survey . In the classical
consensus algorithm, only addition is involved, which is why the Paillier
cryptosystems were used in alexandru2019encrypted  and ruan2019secure  to
achieve privacy-preserving consensus.

In cryptography, the secret sharing scheme is a multi-party encryption method
to share a confidential message with multiple parties, that ensures that even
with the collusion of a certain number of parties, it is still not possible to
uncover the secret message. Shamir shamir1979share  presented the first
algorithm to solve the secret sharing problem, and the good survey paper
beimel2011secret  provides more insights on the historical evolution of this
problem.

In this work, we employ a secret sharing scheme for the communication between
agents, to address the problem of privacy-preserving consensus on undirected
graphs. As in network coordination, each agent is required to send its state
to all its neighbors, which indeed injects into the network the duplicates of
same piece of information. In order to preserve its privacy, each agent can
partition its local information into several so-called secret shares. Then,
rather than sending the full information to all of its neighbors, each agent
only sends one share to each neighbor. As the information can be reconstructed
entirely from a certain specified number of shares, the information injected
into the network for each agent is still intact but in a confidential way. In
addition, the secret sharing scheme makes the communication naturally
resistant to eavesdropping.

Unlike methods based on differential privacy techniques
huang2012differentially ; mo2016privacy ; liu2017secure ; he2018privacy ;
katewa2015protecting , the proposed method can reach average consensus with no
errors, and also protect the network from eavesdropping. In addition, the
privacy security adopted in this paper renders the network immune to the
collusion of any given number of neighbors. This is in contrast to
manitara2013privacy ; mo2016privacy , where at least one neighbor of each
agent must be honest.

In the rest of the paper, we use $\mathbb{Z}+$ to denote the set of all
positive integers, and for any $N\in\mathbb{Z}+$, we define the set
$[N]=\\{1,2,\dots,N\\}$. In addition, we denote by $|S|$ the cardinality of a
given set $S$. For any event $A$, the indicator function $\mathbbm{1}(A)=1$
when $A$ happens, otherwise $\mathbbm{1}(A)=0$. Moreover, we denote
$\mathbf{1}\in\mathbb{R}^{n}$ is the vector consisting of all one entries.

##  2 Preliminaries

In this section, we will introduce the notions used in the paper, and revisit
some fundamental results on graph theory and secret sharing schemes.

###  2.1 Network graph and consensus algorithm with switching topology

For a networked system, the topology of inter-agent connectivity can be
modeled by a graph $\mathcal{G}=(\mathcal{V},\mathcal{E})$, where the set of
nodes is $\mathcal{V}=\big{\\{}1,\ldots,N\big{\\}}$, and
$\mathcal{E}\subset\mathcal{V}\times\mathcal{V}$ is the edge set. A graph
$\mathcal{G}$ is undirected if $(i,j)\in\mathcal{E}$, for any
$(j,i)\in\mathcal{E}$. In this paper, without further indication, we assume
that all the graphs are undirected. We also define the neighbor set of a node
$i$ as $\mathcal{N}_{i}=\big{\\{}j:(j,i)\in\mathcal{E}\big{\\}}$, and we say
that $j$ is a neighbor of $i$, if $j\in\mathcal{N}_{i}$. Moreover, we say that
two edges are adjacent if they are incident to a same endpoint.

The union of any two graphs $\mathcal{G}_{1}$ and $\mathcal{G}_{2}$ is defined
by
$\mathcal{G}_{1}\bigcup\mathcal{G}_{2}=\big{(}\mathcal{V}_{1}\bigcup\mathcal{V}_{2},\mathcal{E}_{1}\bigcup\mathcal{E}_{2}\big{)}$.
Given a finite set of graphs
$\bar{\mathcal{G}}=\\{\mathcal{G}_{1},\mathcal{G}_{2},\dots,\mathcal{G}_{M}\\}$
all having the same set of nodes $\mathcal{V}$, we say that a function
$\mathcal{H}:\mathbb{Z}+\to\bar{\mathcal{G}}$ is a dynamical graph. Moreover,
a dynamical graph $\mathcal{H}(t)$ is jointly connected across any time
interval $I\subset\mathbb{Z}+$ if the graph $\bigcup_{t\in I}\mathcal{H}(t)$
is connected.

Without loss of generality, we denote by $x_{i}(t)\in\mathbb{R}$ the state of
node $i$ at time $t\in\mathbb{Z}+$. We say that the agents in such a network
have reached consensus, if for any initial condition $x_{i}(0)$,
$i\in\mathcal{V}$, it holds that at some time $t\in\mathbb{Z}+$,
$x_{i}(t)=x_{j}(t)$ for all $i,j\in\mathcal{V}$. To tackle this problem, one
can cast to the discrete-time consensus algorithm

$x_{i}(t+1)=x_{i}(t)+\alpha_{i}(t)\sum_{j\in\mathcal{N}_{i}}(x_{j}(t)-x_{i}(t)),$
(1)

for $i\in[N]$, where $\alpha_{i}(t)\in\mathbb{R}$ is a step size. It has been
shown that if a communication graph $\mathcal{G}$ is connected, and the step
size $\alpha_{i}$ in (1) satisfies $\alpha_{i}<\frac{1}{|\mathcal{N}_{i}|}$,
then the iterative algorithm given in (1) ensures that the states of all
agents converge to the average value $\bar{x}_{0}$, where
$\bar{x}_{0}=\frac{1}{N}\sum_{i=1}^{N}x_{i}(0)$, (see olfati2007consensus ;
jadbabaie2003coordination ; ren2005consensus  and the references therein).

Moreover, when the communication topology is a dynamical graph
$\mathcal{H}(t)$, $t\in\mathbb{Z}+$, the following lemma gives a sufficient
condition for asymptotic convergence of the consensus algorithm in (1).

######  Lemma 1 (Proposition 2, moreau2005stability )

Given a dynamical undirected graph $\mathcal{H}(t)$, let
$\alpha_{i}(t)=\frac{1}{1+|\mathcal{N}_{i}(t)|}$ for each time $t$. If for any
time $T$ the graph
$\bar{\mathcal{H}}_{T}=\bigcup_{t=T}^{\infty}\mathcal{H}(t)$ is connected,
then consensus is globally asymptotically reached using the iterative
algorithm in (1).

Note that Lemma 1 only guarantees consensus but not average consensus for the
agents’ states.

###  2.2 Secret sharing schemes

The secret sharing scheme is an encryption method for sharing a confidential
message with multiple parties, such that even with the collusion of a certain
number of parties, the message should still not be disclosed.

Specifically, an $(n,p)$ secret sharing scheme consists of two algorithms
(Share, Reconstruct) with the forms that

  * •

Share takes as input a secret $M$ and outputs $n$ shares
$(M_{1},\dots,M_{n})$;

  * •

Reconstruct takes as input $p$ different shares $(M_{i})_{i\in\mathcal{I}}$
for any index set $\mathcal{I}\subset[n]$ with $|\mathcal{I}|=p$, and outputs
$M$.

The generated secret share $M_{i}$ is then distributed to the party $i$ for
each $i\in[n]$. The security of such a scheme requires that any collusion of
less than $p$ parties should reveal no information about the message $M$. More
precisely, this means that for any index set $\mathcal{I}\subset[n]$ with
$|\mathcal{I}|<p$, the distribution of $(M_{i})_{i\in\mathcal{I}}$ should be
independent of the true message $M$. Secret sharing schemes are used in many
applications, e.g., encryption keys, distributed storage, missile launch
codes, and numbered bank accounts. In these applications, each of the
generated pieces of information must keep the original message confidential,
as their exposure is undesirable, however, it is also critical that the
message should not be lost.

One celebrated secret sharing scheme is the Shamir’s scheme proposed by Adi
Shamir in 1979 shamir1979share . In this scheme, the Share algorithm samples
the values of a secret $(p-1)$-order polynomial at $n$ different points, and
the Reconstruct algorithm can recover the secret polynomial from any $p$ of
these samples. In addition, as the $(p-1)$-order polynomial contains the true
message $M$ as its constant term, $M$ can be reconstructed (see Appendix for
more details).

##  3 Problem formulation

In this paper, we want to achieve network consensus subject to communication
safety, and also anti-collusion of neighbors.

Define the security degree by an integer tuple

$p=(p_{1},p_{2},\dots,p_{N})\in\mathbb{Z}+^{N},$

with $(p_{i}-1)$ indicating the maximum number of neighbors of agent $i$ that
are allowed to collude without a privacy leak. Next, we give the detailed
definition of the security adopted in the paper.

######  Definition 1 ($p$-degree security)

We say that an algorithm in a network is of $p$-degree security if for each
agent $i\in[N]$, at any time $t\in\mathbb{Z}+$,

  1. (1)

the state $x_{i}(t)$ is safe even with the collusion of less than $p_{i}$
neighbors in $\mathcal{N}_{i}$, and

  2. (2)

it is not possible to disclose the state $x_{i}(t)$ by eavesdropping the
communication on less than $p_{i}$ edges in
$\\{(i,j)\in\mathcal{E}:j\in\mathcal{N}_{i}\\}$.

In this definition, we set the security degree $p_{i}$ for each agent $i$ is
to assure that even a certain number of $i$’s neighbors betray or get
attacked, the state $x_{i}(k)$ is still not leaked.

###### Remark 1

For an algorithm of $p$-degree security, (i) if $p_{i}\geq 2$, the state
$x_{i}(t)$ is kept secret from every neighbor $j\in\mathcal{N}_{i}$. (ii) If
$p_{i}=|\mathcal{N}_{i}|$, then $x_{i}(t)$ is disclosed only when all
neighbors of a node are colluding. (iii) If $p_{i}>|\mathcal{N}_{i}|$, then
the state $x_{i}(t)$ is completely confidential in the network.

Now we are ready to state the problem of privacy-preserving consensus that
will be solved in this paper.

###### Problem 1

In a network consisting of $N$ agents, the problem of privacy-preserving
consensus with security degree $p$ is to achieve for every agent $i$ that

  1. (a)

average consensus is reached, i.e.,

$\lim_{t\to\infty}x_{i}(t)=\frac{1}{N}\sum_{j\in[N]}x_{j}(0),\qquad\forall
i\in[N],\text{ and }$

  2. (b)

the consensus algorithm is of $p$-degree security.

We note that the privacy-preserving requirement of $(2)$ in Problem 1 is only
valid before consensus has been reached. After that, although the information
transmitted between agents is still encrypted, or more precisely the
communication satisfies $p$-degree security, the agent state $x_{i}(k)$ is
nevertheless already known to all the other agents, due to the state
consensus.

##  4 Privacy-preserving consensus based on secret sharing

Two algorithms are proposed in this section. The first one solves the privacy-
preserving consensus problem by using a secret sharing scheme in
communication. The second one is a key distribution algorithm which
synchronizes a secret key across the network within finite steps.

###  4.1 Privacy-preserving consensus algorithm

In this subsection, we propose an algorithm inspired by the Shamir’s secret
sharing scheme to solve Problem 1.

As a private key, each agent $i$ will randomly initialize111In this paper, any
random variables are drawn from the uniform distribution on their supported
sets. a coefficient vector
$a^{(i)}=(a_{1}^{(i)},\dots,a^{(i)}_{p_{i}-1})\in\mathbb{[}-1,1]^{p_{i}-1}$,
and keep this vector $a^{(i)}$ secret from all other agents. Then for each
$i\in[N]$, we define an encryption polynomial of order $(p_{i}-1)$ by

$f_{i}(\theta,t)=\sum_{j=1}^{p_{i}-1}a_{j}^{(i)}\theta^{j}+x_{i}(t),$

for $\theta\in\mathbb{R}$, $t\in\mathbb{Z}+$. This polynomial is only known to
agent $i$, since the coefficients $a^{(i)}$ and state $x_{i}(t)$ are both
hidden from the others. Note that the state $x_{i}(t)$ is equal to
$f_{i}(0,t)$.

Let a security degree $p\in\mathbb{Z}+^{N}$, and we say that $p$ has maximal
order $\bar{p}$, if it holds that

$\bar{p}=\max_{i\in[N]}p_{i}.$

Note that such an upper bound $\bar{p}$ of secret degrees indicates the
maximal capacity of the tolerance for attacks on the neighbors, and can be
preassigned for a privacy-preserving algorithm.

Then we define the key sequence for $\bar{p}$ communication channels by an
integer vector

$S=(S_{1},\dots,S_{\bar{p}})\in[1,\kappa]^{\bar{p}}\subset\mathbb{Z}^{\bar{p}},$

where $\kappa\in\mathbb{Z}+$ is the maximal possible key and in general
$\kappa\gg\bar{p}$.

In order to ensure that the agents communicate using the same key sequence,
they first need to agree on a common key sequence $S$. To this end, one method
is to preassign a random, or a default key sequence for all the agents. For
example, we can set a default key $S=(1,2,3,\dots,\bar{p})$, which is actually
widely used in many secret sharing applications. An alternative method to
establishing a common key sequence $S$ is to use a consensus algorithm, which
can synchronize the key sequences of all the agents starting from any random
initial keys. The latter will be further detailed in Section 4.2.

Next, we present Algorithm 1 to reach asymptotic consensus with $p$-degree
security for a group of agents $\mathcal{V}$. To store the information
transmitted through each channel, every node $i\in\mathcal{V}$ sets a local
buffer $r_{i}(k)\in\mathbb{R}$, for every $k\in S$.

Algorithm 1 starts with a Handshake procedure (Step 1 in Algorithm 1), in
which a communication channel $c_{ij}\in S$ is assigned for each edge $(i,j)$.
Particularly, at the beginning of each iteration, the agent $i$,
$i\in\mathcal{V}$, randomly selects a Handshake Pair
$(b_{j}^{(i)},c^{(i)}_{j})$ for each edge $(i,j)\in\mathcal{E}$, with
$b_{j}^{(i)}\in[-1,1]$ being a random bid value, and $c^{(i)}_{j}\in S$ being
the preferred channel for edge $(i,j)$ according to agent $i$. Then the edge
$(i,j)$ will be assigned the preferred channel with the larger bid value from
the nodes $i$ and $j$.

After each edge has been assigned a channel, a channel-wise consensus
iteration (Step 2 in Algorithm 1) is performed amongst the agents. In
particular, for a given channel $k\in S$, each agent $i$ updates the buffer
$r_{i}(k)$ by using the information only from the neighbors in
$\\{j\in\mathcal{N}_{i}:c_{ij}=k\\}$, i.e., only performs a consensus
iteration on the edges whose communication channels have been selected to be
$k$.

Moreover, the Handshake procedure selects a channel for each edge randomly and
repeatedly at each time $t\in\mathbb{Z}+$. This guarantees that, over any long
enough time period, the dynamical graph corresponding to each channel will be
jointly connected. As a result, the buffers on each channel will reach
consensus asymptotically, and then so does the reconstructed state $x_{i}(t)$.
Proposition 1 shows that Algorithm 1 achieves average consensus asymptotically
for all the agents.

Algorithm 1 Privacy-preserving consensus with security degree $p$.

0: Security degree $p=(p_{1},p_{2},\dots,p_{N})$; Initial $x_{i}(0)$, $\forall
i\in[N]$; Graph $\mathcal{G}=(\mathcal{E},\mathcal{V})$; Secret key
$S\in[1,\kappa]^{\bar{p}}$, which has been successfully distributed to all
nodes; Step size $\alpha$.

1: Initialization: For each node $i$, randomly choose222The random selection
is drawn from the uniform distribution, in particular $a^{(i)}\sim
U([-1,1]^{p_{i}-1})$, $b^{(i)}_{j}\sim U([-1,1])$, and $c_{j}^{(i)}\sim U(S)$,
where $U(\cdot)$ is the uniform distribution. a coefficient vector
$a^{(i)}\in\mathbb{[}-1,1]^{p_{i}-1}$, and Handshake Pairs
$(b^{(i)}_{j},c^{(i)}_{j})$, $\forall j\in\mathcal{N}_{i}$, where
$b^{(i)}_{j}\in[-1,1]$ and $c^{(i)}_{j}\in S$. Initialize the buffers as
$r_{i}(k)=f_{i}(k,0)$, for any $i\in[N]$, and $k\in S$.

2: for $t=1,2,\dots$ do

3: for $i=1$ to $N$ do

4: %Step 1 (Handshake): decide a channel $c_{ij}$ for each edge
$(i,j)\in\mathcal{E}$.

5: for $j\in\mathcal{N}_{i}$ do

6: if $b^{(i)}_{j}\geq b^{(j)}_{i}$ then

7: $c_{ij}\leftarrow c^{(i)}_{j}$;

8: else

9: $c_{ij}\leftarrow c^{(j)}_{i}$;

10: end if

11: end for

12: %Step 2 (Chanel-wise consensus): update $i$’s buffer using the information
over channel $c_{ij}$ for each neighbor $j$. Note that $r_{j}(c_{ij})$ is the
only information needed by $i$.

13: for $k$ in $S$ do

14:
$r_{i}(k)\\!\leftarrow\\!r_{i}(k)\\!+\\!\alpha\sum_{j\in\mathcal{N}_{i}}\mathbbm{1}(c_{ij}\\!=\\!k)\big{[}r_{j}(k)\\!-\\!r_{i}(k)\big{]};$
(2)

15: end for

16: %Step 3: Reconstruct the state $x_{i}(t)$ from buffers.

17: Update $x_{i}(t)$:  $x_{i}(t)\leftarrow\sum_{k\in
S}r_{i}(k)\frac{\prod_{\ell\in S\setminus\\{k\\}}(-\ell)}{\prod_{\ell\in
S\setminus\\{k\\}}(k-\ell)};$

18: end for

19: %Reset Handshake pairs.

20: For each node $i$, randomly choose Handshake Pairs
$(b^{(i)}_{j},c^{(i)}_{j})$, $\forall j\in\mathcal{N}_{i}$.

21: end for

###### Proposition 1

If the communication graph $\mathcal{G}$ is connected, and the step size
$\alpha$ satisfies

$\alpha<\frac{1}{\max_{i\in\mathcal{V}}|\mathcal{N}_{i}|},$

then Algorithm 1 solves Problem 1.

###### Proof

For any time $t\in\mathbb{Z}+$, through the Handshake procedure, we denote by
$c_{ij}(t)\in S$ the assigned communication channel on the edge $(i,j)$.

Then given a key sequence $S\in\mathbb{Z}^{\bar{p}}$, for each channel $k\in
S$, we define a channel vector

$\xi_{k}(t)=\big{(}\,r_{1}(k),r_{2}(k),\dots,r_{N}(k)\,\big{)}\bigg{|}_{t}\in\mathbb{R}^{N},$

where $r_{i}(k)\big{|}_{t}$ is agent $i$’s buffer corresponding to the channel
$k$ at time $t$. Then this channel vector satisfies

$\xi_{k}(t+1)=\xi_{k}(t)-\alpha L_{k}(t)\xi_{k}(t),$ (3)

where the matrix $L_{k}(t)$ is the Laplacian matrix of channel $k$ at time
$t$. In particular, the matrix
$L_{k}(t)=[l_{k,t}(i,j)]_{i,j}\in\mathbb{R}^{N\times N}$ satisfies

$l_{k,t}(i,j)\\!=\\!\begin{cases}-1&\text{ if }i\\!\neq\\!j,\text{ and
}c_{ij}(t)=k,\\\
\sum_{\ell\in\mathcal{N}_{i}}\\!\\!\mathbbm{1}(c_{i\ell}(t)=k)&\text{ if
}i\\!=\\!j,\\\ 0&\text{ otherwise}.\\\ \end{cases}$

Denote the set of all the subgraphs of $\mathcal{G}$ by $\bar{\mathcal{G}}$.
Then, for each channel $k$, define the dynamical graph
$\mathcal{H}_{k}:\mathbb{Z}+\to\bar{\mathcal{G}}$, such that the Laplacian
matrix of $\mathcal{H}_{k}(t)$ is $L_{k}(t)$. Then for all $k\in S$, dynamical
graph $\mathcal{H}_{k}(t)$ satisfies that for any time $t_{0}$, there exists
an infinite subset of time instants, denoted by
$\bar{T}_{t_{0}}\subset\\{t\in\mathbb{Z}+:t\geq t_{0}\\}$, such that
$\mathcal{H}_{k}(t)$ is connected for any $t\in\bar{T}_{t_{0}}$. The existence
of $\bar{T}_{t_{0}}$ is because, in the Handshake procedure, the channels
$c_{ij}(t)$ are randomly selected at each time $t$.

Then, for each channel $k$, we define the average buffer vector
$\bar{\xi}_{k}(t)=\frac{1}{N}\mathbf{1}^{T}\xi_{k}(t)$, which can be shown to
be invariant along the trajectory of system (3). This is due to the fact that
$\mathbf{1}^{T}(I-\alpha L_{k}(t))=\mathbf{1}^{T}$, for any $t\in\mathbb{Z}+$.
This implies

$\bar{\xi}_{k}(t)=\frac{1}{N}\mathbf{1}^{T}\xi_{k}(0),\quad\forall t.$ (4)

Then the consensus error is given by
$\delta_{k}(t)=\xi_{k}(t)-\mathbf{1}\bar{\xi}_{k}(0)$. Note that
$\delta_{k}(t)^{T}\mathbf{1}=0$ for any $t$. Furthermore, for any $t_{p}$ such
that $L_{k}(t_{p})$ corresponds to a connected graph, we know that the matrix
$L_{k}(t_{p})$ has a simple smallest eigenvalue $0$ with the eigenvector
$\mathbf{1}$. This implies that

$\displaystyle\max_{x\in\\{x^{T}\mathbf{1}=0\\}}\frac{x^{T}(I-\alpha
L_{k}(t_{p}))x}{x^{T}x}$ (5) $\displaystyle=$ $\displaystyle
1-\alpha\min_{x\in\\{x^{T}\mathbf{1}=0\\}}\frac{x^{T}L_{k}(t_{p})x}{x^{T}x}$
$\displaystyle=$ $\displaystyle 1-\alpha\lambda_{2}^{k}(t_{p}),$ (6)

where $\lambda_{2}^{k}(t_{p})$ is the second smallest eigenvalue of the
Laplacian $L_{k}(t_{p})$.

Then we consider a discrete Lyapunov function
$\Phi_{k}(t)=\delta_{k}(t)^{T}\delta_{k}(t)$, for each $k\in S$. Let
$t_{0}=1$. Then for any time instant $t_{p}\in\bar{T}_{t_{0}}$, we have

$\displaystyle\Phi_{k}(t_{p}+1)$ $\displaystyle=\|\big{[}I-\alpha
L_{k}(t_{p})\big{]}\xi_{k}(t_{p})-\mathbf{1}\bar{\xi}_{k}(0)\|^{2}_{2}$
$\displaystyle=\|\big{[}I-\alpha
L_{k}(t_{p})\big{]}\delta_{k}(t_{p})\|^{2}_{2}$
$\displaystyle\leq(1-\alpha\lambda_{2}(t_{p}))^{2}\|\delta_{k}(t_{p})\|^{2}_{2},$

where we use $L_{k}(t_{p})\mathbf{1}=0$ in the second equality, and equation
(6) in the last inequality. By Gershgorin theorem, all eigenvalues of
$L_{k}(t_{p})$ are located in the interval $[0,2\max_{i}|d_{i}^{k}(t_{p})|]$,
where $d_{i}^{k}(t_{p})$ is the $i$-th diagonal element of Laplacian
$L_{k}(t_{p})$. Thus if
$\alpha<\frac{1}{\max_{i\in\mathcal{V}}|\mathcal{N}_{i}|}<\frac{1}{\max_{i\in\mathcal{V}}|d_{i}^{k}(t_{p})|}$,
then $|1-\alpha\lambda_{2}(t_{p})|<1$. Therefore, the Lyapunov function
$\Phi_{k}(t)$ is strictly decreasing at any time $t\in\bar{T}_{t_{0}}$.
Combine the argument (4), average consensus follows for all channel $k\in S$.

Then we have for any $k\in S$ and $i\in\mathcal{V}$ ,

$\displaystyle\lim_{t\to\infty}r_{i}(k)\big{|}_{t}$
$\displaystyle=\frac{1}{N}\sum_{i\in\mathcal{V}}r_{i}(k)\big{|}_{t=0}=\frac{1}{N}\sum_{i\in\mathcal{V}}f_{i}(k,0)$
$\displaystyle=\frac{1}{N}\sum_{i\in\mathcal{V}}\sum_{j=1}^{p_{i}-1}\big{(}a_{j}^{(i)}\big{)}k^{j}+\frac{1}{N}\sum_{i\in\mathcal{V}}x_{i}(0)$
$\displaystyle=\sum_{j=1}^{\bar{p}-1}\Bigg{(}\frac{1}{N}\sum_{i\in\mathcal{V}}a_{j}^{(i)}\Bigg{)}k^{j}+\frac{1}{N}\sum_{i\in\mathcal{V}}x_{i}(0),$

in which we use $\bar{p}\geq\max_{i\in[N]}p_{i}$, and we set $a^{(i)}_{j}=0$
for any $j\geq p_{i}$. Then we see that after consensus is reached, i.e., when
$t$ is large enough, every node obtains $\bar{p}$ observations
$\\{(k,F(k)):k\in S\\}$ of the average polynomial $F(\theta)$, where
$F(\theta)$ is

$F(\theta)=\sum_{j=1}^{\bar{p}-1}\Bigg{(}\frac{1}{N}\sum_{i\in\mathcal{V}}a_{j}^{(i)}\Bigg{)}\theta^{j}+\frac{1}{N}\sum_{i\in\mathcal{V}}x_{i}(0).$

According to the Shamir’s algorithm, the constant term
$\frac{1}{N}\sum_{i\in\mathcal{V}}x_{i}(0)$ can be reconstructed by each agent
$i$ as

$\frac{1}{N}\sum_{i\in\mathcal{V}}x_{i}(0)=\sum_{k\in
S}r_{i}(k)\big{|}_{t=\infty}\frac{\prod_{\ell\in
S\setminus\\{k\\}}(-\ell)}{\prod_{\ell\in
S\setminus\\{k\\}}(k-\ell)}=x_{i}(\infty).$

Thus the assertion holds.

The $p$-degree security of Algorithm 1 follows that for any agent
$i\in\mathcal{V}$. Moreover, any collusion of less than its $p_{i}$ neighbors
cannot reconstruct $x_{i}(t)$.

For any adversary, since the key sequence $S$ is unknown, the interception on
the communication link does not give any useful information to reconstruct
$x_{i}(t)$. $\blacksquare$

Note that in Algorithm 1, we can use an alternative update law for each
$r_{i}(k)$ in (2), which is

$r_{i}(k)\leftarrow\alpha_{i}r_{i}(k)+\alpha_{i}\sum_{j\in\mathcal{N}_{i}}\mathbbm{1}(c_{ij}=k)r_{j}(k),$

where
$\alpha_{i}=\frac{1}{1+\sum_{j\in\mathcal{N}_{i}}\mathbbm{1}(c_{ij}=k)}$. But
by Lemma 1, this update law can only achieve consensus, but the reached state
does not necessarily equal to $\frac{1}{N}\sum_{i\in\mathcal{V}}x_{i}(0)$.

###  4.2 Key distribution

To protect the privacy-preserving algorithm from eavesdropping, a the secret
key sequence $S$ must first be distributed to each individual in the network.
By using such a key sequence, the information exchanged between the agents
afterwards becomes resistant to the wiretapping on communication links.

Indeed, the key sequence can be set to some default value, e.g.,
$S=(1,2,\dots,\bar{p})$. Even with such kinds of default keys being public,
any eavesdropper would still need at least $p_{i}$ pieces of information
transmitted to/from agent $i$ to reconstruct the state $x_{i}(t)$. However, we
still provide here a key distribution algorithm for the scenario in which the
key $S$ must be kept secret.

We note that consensus algorithms typically only provide asymptotic
convergence to a synchronized state. This means that, within finite time, one
agent’s key updated by the algorithm can only approach, but not equal, the
keys of the others. To reach an exact synchronization for the key sequence,
finite-time consensus algorithms are needed, such as, e.g., kibangou2014step ;
sundaram2007finite ; wang2010finite ; wei2018finite . These finite-time
consensus algorithms, however, often depend on particular communication graphs
kingston2006discrete , or require first computing a matrix factorization
kibangou2014step  or minimal polynomial sundaram2007finite  of the weight
matrix. For our purpose, with the elements of the key sequence being integers,
we can adopt the following finite-step consensus algorithm that can be
computed much more easily.

Define the communication weight matrix $W=[w_{ij}]\in\mathbb{R}^{N\times N}$,
satisfying the following conditions:

  1. (a)

$w_{ij}>0$ if $(i,j)\in\mathcal{E}$, and $w_{ij}=0$ if
$(i,j)\notin\mathcal{E}$. Moreover, $w_{ii}>0$ for $i\in\mathcal{N}$.

  2. (b)

The matrix $W$ is doubly stochastic, i.e., $\sum_{k}w_{ki}=1$, and
$\sum_{k}w_{ik}=1$ for any $i\in\mathcal{N}$.

Note that for any connected graph $\mathcal{G}$, the nonnegative matrix $W$ is
irreducible, and moreover, $W$ is primitive, i.e., $W$ has only one eigenvalue
with maximum modulus. In particular, we have the largest eigenvalue of $W$,
which is $1$, is simple with eigenvector $\mathbf{1}$.

Denote the spectral norm 333Spectral norm of a matrix $A\in\mathbb{C}^{n\times
n}$ is defined by  $\max_{\|x\|_{2}\neq 0}\frac{\|Ax\|_{2}}{\|x\|_{2}},$ which
is equal to the square root of the maximum eigenvalue of $A^{*}A$. of
$W-\frac{1}{n}\mathbf{1}\mathbf{1}^{T}$ by $\gamma$. Then we have
$\gamma\in(0,1)$. This is because the positive semidefinite matrix $W^{T}W$
has a unique largest eigenvalue $1$ with eigenvector $\mathbf{1}$.
Consequently,, all the eigenvalues of
$(W-\frac{1}{n}\mathbf{1}\mathbf{1}^{T})^{T}(W-\frac{1}{n}\mathbf{1}\mathbf{1}^{T})=W^{T}W-\frac{1}{n}\mathbf{1}\mathbf{1}^{T}$
belong to $(0,1)$.

We employ the classical consensus algorithm

$S_{i}(t+1)=\sum_{j=1}^{N}w_{ij}S_{j}(t),$ (7)

for $S_{i}(t)\in\mathbb{R}^{\bar{p}}$ and $i\in[N]$. Then the following lemma
gives the convergence rate for the consensus dynamics (7).

###### Lemma 2

Let $\kappa\in\mathbb{R}+$, and let a threshold $\delta\in\mathbb{R}+$ be
given. Then, for any initial condition $S_{i}(0)\in[0,\kappa]^{\bar{p}}$,
$i\in[N]$, the trajectory of the consensus algorithm (7) satisfies

$\|S_{i}(T)-\frac{1}{N}\sum_{j=1}^{N}S_{j}(0)\|_{\infty}\leq\delta,\qquad\forall
i\in[N],$

where $T=\left\lceil\log_{\lambda}\frac{\delta}{\kappa\sqrt{N}}\right\rceil$.

###### Proof

See Appendix B.

Next, we give the algorithm to distribute an integer key sequence to all the
agents. Note that in the algorithm we denote by $S_{i\ell}$ the $\ell$-th
element of agent $i$’s key sequence $S_{i}$.

Algorithm 2 Finite-step key sequence distribution.

0: $\bar{p}$: the number of channels; $\bar{N}$: the upper bound for the
number of nodes; $\lambda$: the spectral norm of
$W-\frac{1}{n}\mathbf{1}\mathbf{1}^{T}$.

1: Initialization: For each node $i$, randomly choose a real vector
$S_{i}(0)\sim U([1,\kappa]^{\bar{p}})$, where $\kappa$ is a default constant
such that $\bar{p}\ll\kappa$. $T=0.$

2: flag $\leftarrow\textbf{true}{}$ % Indicator that the key distribution is
incomplete.

3: while flag $=\textbf{true}{}$ do

4: %Consensus for
$\left\lceil\log_{\lambda}\frac{0.1}{\kappa\sqrt{\bar{N}}}\right\rceil$ steps.

5: for
$t=T+1,\dots,T+\left\lceil\log_{\lambda}\frac{0.1}{\kappa\sqrt{\bar{N}}}\right\rceil$
do

6: for $i=1$ to $N$ do

7: $S_{i}(t+1)=\sum_{j=1}^{N}w_{ij}S_{j}(t).$

8: end for

9: end for

10: flag $\leftarrow\textbf{false}{}$

11: % Check if the key distribution is done.

12: for $i=1$ to $N$ do

13: for $\ell=1$ to $\bar{p}$ do

14: $\Delta_{1}\leftarrow S_{i\ell}(t)-\left\lfloor S_{i\ell}(t)\right\rfloor$
% decimal part.

15: $\Delta_{2}\leftarrow\min_{j\in[1,\ell)}\big{|}\left\lfloor
S_{i\ell}(t)\right\rfloor-\left\lfloor S_{ij}(t)\right\rfloor\big{|}$ %
minimal discrepancy of element $S_{i\ell}$ away from the elements before it.

16: if $\Delta_{1}\leq 0.1$ or $\Delta_{1}\geq 0.9$ or $\Delta_{2}<0.5$ then

17: $S_{i\ell}(t)\leftarrow y$, for a random integer $y\in[1,\kappa]$.

18: flag $\leftarrow\textbf{true}{}$

19: end if

20: $S_{i\ell}(t)=\left\lfloor S_{i\ell}(t)\right\rfloor.$

21: end for

22: end for

23: end while

By Lemma 2, Algorithm 2 first guarantees that after a number
$\left\lceil\log_{\lambda}\frac{0.1}{\kappa\sqrt{\bar{N}}}\right\rceil$ of
consensus iterations, the consensus error from the average is smaller than the
threshold $\delta=0.1$. Then if each element in agent $i$’s state keeps some
distance away from the closest integer, and if there are no two identical
elements in agent $i$’s key sequence $S_{i}$, we take the integer part of the
key sequence $S_{i}$ as $i$’s key sequence.

Although, using Algorithm 2, we do not need to compute a matrix factorization,
or the minimal polynomial of the weight matrix kibangou2014step ;
sundaram2007finite , the algorithm requires some global information, i.e., the
spectral norm $\gamma$ of the graph. To avoid this, we can employ the
Metropolis matrix as the weight matrix, which is defined by

$w_{ij}=\begin{cases}\frac{1}{2\max(d_{i},d_{j})},\quad&\text{if
}(i,j)\in\mathcal{E}\text{ for }i\neq j,\\\
1-\sum_{\ell\in\mathcal{N}_{i}}\frac{1}{2\max(d_{i},d_{\ell})},\quad&\text{if
}i=j,\\\ 0,\quad&\text{otherwise},\end{cases}$

where $d_{i}$ is the degree of node $i$, i.e., $d_{i}=|\mathcal{N}_{i}|$. By
using this weight matrix, each node is only required to know the set of its
neighbors. Moreover, in this case, the spectral norm of the matrix
$W-\frac{1}{n}\mathbf{1}\mathbf{1}^{T}$ satisfies $\gamma\leq
1-\frac{1}{71N^{2}}$ (olshevsky2014linear, , Lemma 2.2).

Actually, when the number of nodes is large, the convergence rate of the
consensus algorithm, or the computation complexity for finite-step consensus
algorithms becomes enormous. Therefore, one solution to this is using a
default (or even public) key. By the results in section 4.1, we see that even
if an adversary is aware of the secret key, the privacy of agent $i$ is not
disclosed if the number of $i$’s communication channels eavesdropped by the
adversary is less than $p_{i}$.

##  5 Simulation

In this section, we will illustrate the algorithm using a numerical example,
in which a network consisting of $5$ nodes with a connection topology of
cyclic graph achieves average consensus using the proposed privacy-preserving
method. As reported in olfati2007consensus , if the step size in the
synchronization algorithm is not carefully chosen the system under a cyclic
connection graph will only reach consensus but not average consensus.

Specifically, we consider a cyclic graph $\mathcal{G}_{c}(5)$ consisting of
$5$ nodes as shown in Figure 2. Let the upper bound of the security degree
$\bar{p}=4$, and set the security degree $p=(2,3,4,2,3)$.

Figure 1: A cyclic graph $\mathcal{G}_{c}(5)$ with $5$ nodes.

Firstly a secret key $S\in[1,20]^{4}$ is distributed using Algorithm 2, after
$28$ iterations all agent share a common secret key

$S=(4,7,15,3).$

Then Algorithm 1 is used to achieve average consensus with the common secret
key $S$. In Figure 2, we show the trajectories of the buffer $r_{i}(4)$ for
all five agents. Figure 3 presents the states $x_{i}(t)$ reconstructed from
each channel’s buffer. We can see that consensus is reached, and moreover,
that consensus state is equal to the average of the initial states.

Figure 2: The buffer trajectories of the five agents, corresponding to the
first channel $k=4$. Figure 3: The trajectories of the reconstructed states of
all nodes using Algorithm 1. The average of the initial states is $37.731$,
and the consensus state is $31.731$.

##  6 Conclusion

This paper proposes a privacy-preserving mechanism for the average-consensus
problem based on the secret sharing scheme. The proposed algorithm renders the
network resistant to the collusion of any given number of neighbors, and
protects the consensus procedure from eavesdropping. In future work, we will
extend this idea to formation control and distributed optimization, and also
exploit it in the relevant applications, such as opinion agreement, sensor
network averaging, survey mechanism, and distributed decision making.

## Appendix A: Shamir’s scheme

The Shamir’s secret sharing scheme shamir1979share  allows a user to “share” a
secret $M$ among a group of $n$ participants, such that (a) any $p$ or more of
the participants can reconstruct $M$, and (b)any set of less than $p$
participants learn nothing about $M$.

For a secret $M\in\mathcal{F}$, where $\mathcal{F}$ is a field, the algorithm
Share($S$) is

  1. (1)

Let $a_{0}=M$;

  2. (2)

Choose at random $a_{1},\dots,a_{p-1}\in\mathcal{F}$;

  3. (3)

Let $f(x)=\sum_{i=0}^{p-1}a_{i}x^{i}$;

  4. (4)

The secret share $M_{i}=(x_{i},y_{i})$ for any $i\in[n]$, where
$y_{i}=f(x_{i})$.

To reconstruct $M$, we need at least $p$ shares of secret
$\\{M_{j}=(x_{j},y_{j})\\}_{j=1}^{p}$. Then one can use the Lagrange
interpolation formula,

$f(x)=\sum_{j=1}^{p}y_{j}L_{j}(x),$

where the Lagrange basis polynomial $L_{j}(x)$ is defined by

$L_{j}(x)=\frac{\prod_{k\in[p]\setminus\\{j\\}}(x-x_{k})}{\prod_{k\in[p]\setminus\\{j\\}}(x_{j}-x_{k})},$

for each $j\in[p]$. Once the polynomial $f(x)$ has been reconstructed, the
secret message can be recovered as $M=f(0)$, due to the definition of $f(x)$.
Equivalently, the true message $M$ can be reconstructed by

$M=f(0)=\sum_{i=1}^{M}y_{i}L_{i}(0)=\sum_{j=1}^{M}y_{j}\frac{\prod_{k\in[p]\setminus\\{j\\}}(-x_{k})}{\prod_{k\in[p]\setminus\\{j\\}}(x_{j}-x_{k})}.$

## Appendix B: Proof of Lemma 2

For each $\ell\in[\bar{p}]$, we denote the $\ell$-component vector by

$S^{(\ell)}(t)=\big{(}S_{1\ell}(t),S_{2\ell}(t),\dots,S_{N\ell}(t)\big{)}\in\mathbb{R}^{N},$

where $S_{ij}(t)$ is the $j$-th element of the key $S_{i}(t)$. Then for each
$\ell$, the consensus iteration reads $S^{(\ell)}(t+1)=WS^{(\ell)}(t)$.

Next, the average for element $\ell$ is
$\alpha_{\ell}(t)=\frac{1}{N}\mathbf{1}^{T}S^{(\ell)}(t)$. Moreover, for any
$t$, $\alpha_{\ell}(t+1)=\alpha_{\ell}(t)$, due to the fact that
$\mathbf{1}^{T}W=\mathbf{1}^{T}$. Thus we can denote the invariant average for
component $\ell$ by $\alpha_{\ell}=\alpha_{\ell}(0)$. Then we have for each
$\ell\in[\bar{p}]$,

$\displaystyle\|S^{(\ell)}(t+1)-\alpha_{\ell}\mathbf{1}\|_{\infty}$
$\displaystyle\leq\|S^{(\ell)}(t+1)-\alpha_{\ell}\mathbf{1}\|_{2}$
$\displaystyle=\|WS^{(\ell)}(t)-\alpha_{\ell}\mathbf{1}\|_{2}$
$\displaystyle=\|(W-\frac{1}{n}\mathbf{1}\mathbf{1}^{T})(S^{(\ell)}(t)-\alpha_{\ell}\mathbf{1})\|_{2}$
$\displaystyle\leq\lambda\|S^{(\ell)}(t)-\alpha_{\ell}\mathbf{1}\|_{2}$

Then for any time $t$,
$\|S^{(\ell)}(t)-\alpha_{\ell}\mathbf{1}\|_{\infty}\leq\lambda^{t}\|S^{(\ell)}(0)-\alpha_{\ell}\mathbf{1}\|_{2}\leq\lambda^{t}\sqrt{N}\|S^{(\ell)}(0)-\alpha_{\ell}\mathbf{1}\|_{\infty}$.
According to the initial condition,
$\|S^{(\ell)}(0)-\alpha_{\ell}\mathbf{1}\|_{\infty}\leq\kappa$. Then the
assertion follows. $\blacksquare$

## References

  * (1) M. DeGroot, “Reaching a consensus,” Journal of the American Statistical Association, vol. 69, no. 345, pp. 118–121, 1974.
  * (2) R. Olfati-Saber, A. Fax, and R. Murray, “Consensus and cooperation in networked multi-agent systems,” Proceedings of the IEEE, vol. 95, no. 1, pp. 215–233, 2007.
  * (3) W. Ren, R. Beard, and E. Atkins, “A survey of consensus problems in multi-agent coordination,” in Proceedings of the 2005, American Control Conference, 2005., pp. 1859–1864, IEEE, 2005.
  * (4) A. Jadbabaie, J. Lin, and S. Morse, “Coordination of groups of mobile autonomous agents using nearest neighbor rules,” IEEE Transactions on automatic control, vol. 48, no. 6, pp. 988–1001, 2003.
  * (5) W. Song, J. Markdahl, S. Zhang, X. Hu, and Y. Hong, “Intrinsic reduced attitude formation with ring inter-agent graph,” Automatica, vol. 85, pp. 193–201, 2017.
  * (6) S. Zhang, F. He, Y. Hong, and X. Hu, “An intrinsic approach to formation control of regular polyhedra for reduced attitudes,” Automatica, vol. 111, p. 108619, 2020.
  * (7) A. Fax and R. Murray, “Information flow and cooperative control of vehicle formations,” IEEE transactions on automatic control, vol. 49, no. 9, pp. 1465–1476, 2004.
  * (8) S. Zhang, W. Song, F. He, Y. Hong, and X. Hu, “Intrinsic tetrahedron formation of reduced attitude,” Automatica, vol. 87, pp. 375–382, 2018.
  * (9) S. Zhang, W. Song, F. He, Y. Yao, and X. Hu, “Spherical cyclic formation control,” in 2016 35th Chinese Control Conference (CCC), pp. 8207–8212, IEEE, 2016.
  * (10) A. Nedić and A. Olshevsky, “Distributed optimization over time-varying directed graphs,” IEEE Transactions on Automatic Control, vol. 60, no. 3, pp. 601–615, 2014.
  * (11) A. Nedic and A. Ozdaglar, “Distributed subgradient methods for multi-agent optimization,” IEEE Transactions on Automatic Control, vol. 54, no. 1, pp. 48–61, 2009.
  * (12) A. Nedic, A. Ozdaglar, and P. Parrilo, “Constrained consensus and optimization in multi-agent networks,” IEEE Transactions on Automatic Control, vol. 55, no. 4, pp. 922–938, 2010.
  * (13) G. Qu and N. Li, “Harnessing smoothness to accelerate distributed optimization,” IEEE Transactions on Control of Network Systems, vol. 5, no. 3, pp. 1245–1260, 2017.
  * (14) C. Cenedese, G. Belgioioso, Y. Kawano, S. Grammatico, and M. Cao, “Asynchronous and time-varying proximal type dynamics in multi-agent network games,” IEEE Transactions on Automatic Control, 2020.
  * (15) J. Zhang and M. Cao, “Strategy competition dynamics of multi-agent systems in the framework of evolutionary game theory,” IEEE Transactions on Circuits and Systems II: Express Briefs, vol. 67, no. 1, pp. 152–156, 2019.
  * (16) J. Thunberg, W. Song, E. Montijano, Y. Hong, and X. Hu, “Distributed attitude synchronization control of multi-agent systems with switching topologies,” Automatica, vol. 50, no. 3, pp. 832–840, 2014.
  * (17) S. Zhang, A. Ringh, X. Hu, and J. Karlsson, “Modeling collective behaviors: A moment-based approach,” IEEE Transactions on Automatic Control, 2020.
  * (18) G. Albi, L. Pareschi, and M. Zanella, “Boltzmann-type control of opinion consensus through leaders,” Philosophical Transactions of the Royal Society A: Mathematical, Physical and Engineering Sciences, vol. 372, no. 2028, p. 20140138, 2014.
  * (19) M. Kefayati, M. Talebi, B. Khalaj, and H. Rabiee, “Secure consensus averaging in sensor networks using random offsets,” in 2007 IEEE International Conference on Telecommunications and Malaysia International Conference on Communications, pp. 556–560, IEEE, 2007.
  * (20) Z. Huang, S. Mitra, and G. Dullerud, “Differentially private iterative synchronous consensus,” in Proceedings of the 2012 ACM workshop on Privacy in the electronic society, pp. 81–90, 2012.
  * (21) Y. Mo and R. Murray, “Privacy preserving average consensus,” IEEE Transactions on Automatic Control, vol. 62, no. 2, pp. 753–765, 2016.
  * (22) Q. Liu, X. Ren, and Y. Mo, “Secure and privacy preserving average consensus,” in 2017 11th Asian Control Conference (ASCC), pp. 274–279, IEEE, 2017.
  * (23) J. He, L. Cai, C. Zhao, P. Cheng, and X. Guan, “Privacy-preserving average consensus: privacy analysis and algorithm design,” IEEE Transactions on Signal and Information Processing over Networks, vol. 5, no. 1, pp. 127–138, 2018.
  * (24) V. Katewa, A. Chakrabortty, and V. Gupta, “Protecting privacy of topology in consensus networks,” in 2015 American Control Conference (ACC), pp. 2476–2481, IEEE, 2015.
  * (25) C. Altafini, “A dynamical approach to privacy preserving average consensus,” in 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 4501–4506, IEEE, 2019.
  * (26) N. Manitara and C. Hadjicostis, “Privacy-preserving asymptotic average consensus,” in 2013 European Control Conference (ECC), pp. 760–765, IEEE, 2013.
  * (27) N. Gupta, J. Katz, and N. Chopra, “Privacy in distributed average consensus,” IFAC-PapersOnLine, vol. 50, no. 1, pp. 9515–9520, 2017.
  * (28) N. Rezazadeh and S. Kia, “Privacy preservation in a continuous-time static average consensus algorithm over directed graphs,” in 2018 Annual American Control Conference (ACC), pp. 5890–5895, IEEE, 2018.
  * (29) C. Gentry and D. Boneh, A fully homomorphic encryption scheme, vol. 20.  Stanford university Stanford, 2009.
  * (30) A. Acar, H. Aksu, S. Uluagac, and M. Conti, “A survey on homomorphic encryption schemes: Theory and implementation,” ACM Computing Surveys (CSUR), vol. 51, no. 4, pp. 1–35, 2018.
  * (31) A. Alexandru, M. Darup, and G. Pappas, “Encrypted cooperative control revisited,” in 2019 IEEE 58th Conference on Decision and Control (CDC), pp. 7196–7202, IEEE, 2019.
  * (32) M. Ruan, H. Gao, and Y. Wang, “Secure and privacy-preserving consensus,” IEEE Transactions on Automatic Control, vol. 64, no. 10, pp. 4035–4049, 2019\.
  * (33) A. Shamir, “How to share a secret,” Communications of the ACM, vol. 22, no. 11, pp. 612–613, 1979.
  * (34) A. Beimel, “Secret-sharing schemes: a survey,” in International Conference on Coding and Cryptology, pp. 11–46, Springer, 2011.
  * (35) W. Ren and R. Beard, “Consensus seeking in multiagent systems under dynamically changing interaction topologies,” IEEE Transactions on automatic control, vol. 50, no. 5, pp. 655–661, 2005.
  * (36) L. Moreau, “Stability of multiagent systems with time-dependent communication links,” IEEE Transactions on automatic control, vol. 50, no. 2, pp. 169–182, 2005.
  * (37) A. Kibangou, “Step-size sequence design for finite-time average consensus in secure wireless sensor networks,” Systems & Control Letters, vol. 67, pp. 19–23, 2014.
  * (38) S. Sundaram and S. Hadjicostis, “Finite-time distributed consensus in graphs with time-invariant topologies,” in 2007 American Control Conference, pp. 711–716, IEEE, 2007.
  * (39) L. Wang and F. Xiao, “Finite-time consensus problems for networks of dynamic agents,” IEEE Transactions on Automatic Control, vol. 55, no. 4, pp. 950–955, 2010.
  * (40) J. Wei, S. Zhang, A. Adaldo, J. Thunberg, X. Hu, and K. Johansson, “Finite-time attitude synchronization with distributed discontinuous protocols,” IEEE Transactions on Automatic Control, vol. 63, no. 10, pp. 3608–3615, 2018.
  * (41) D. Kingston and R. Beard, “Discrete-time average-consensus under switching network topologies,” in 2006 American Control Conference, pp. 6–pp, IEEE, 2006.
  * (42) A. Olshevsky, “Linear time average consensus on fixed graphs and implications for decentralized optimization and multi-agent control,” arXiv preprint arXiv:1411.4186, 2014.

Silun Zhang received his B.Eng. and M.Sc. degrees in Automation from Harbin
Institute of Technology, China, in 2011 and 2013 respectively, and the PhD
degree in Optimization and Systems Theory from Department of Mathematics, KTH
Royal Institute of Technology, Sweden, in 2019.

He is currently a Wallenberg postdoctoral fellow with the Laboratory for
Information and Decision Systems (LIDS), MIT, USA. His main research interests
include nonlinear control, networked systems, rigidbody attitude control, and
modeling large-scale systems.

Thomas Ohlson Timoudas received his PhD degree in Mathematics in October 2018
from KTH Royal Institute of Technology, Sweden, and his MSc (2013) and BSc
(2012) degrees in Mathematics from Stockholm university, Sweden.

He is currently a postdoctoral researcher with the Department of Network and
Systems Engineering at KTH Royal Institute of Technology, Sweden. His main
research interests include dynamical systems, networked systems, internet of
things, and distributed algorithms.

Munther A. Dahleh received his Ph.D. degree from Rice University, Houston, TX,
in 1987 in Electrical and Computer Engineering. Since then, he has been with
the Department of Electrical Engineering and Computer Science (EECS), MIT,
Cambridge, MA, where he is now the William A. Coolidge Professor of EECS. He
is also a faculty affiliate of the Sloan School of Management. He is the
founding director of the newly formed MIT Institute for Data, Systems, and
Society (IDSS). Previously, he held the positions of Associate Department Head
of EECS, Acting Director of the Engineering Systems Division, and Acting
Director of the Laboratory for Information and Decision Systems. He was a
visiting Professor at the Department of Electrical Engineering, California
Institute of Technology, Pasadena, CA, for the Spring of 1993. He has
consulted for various national research laboratories and companies.

Dr. Dahleh is interested in Networked Systems with applications to Social and
Economic Networks, financial networks, Transportation Networks, Neural
Networks, and the Power Grid. Specifically, he focuses on the development of
foundational theory necessary to understand, monitor, and control systemic
risk in interconnected systems. He is four-time recipient of the George Axelby
outstanding paper award for best paper in IEEE Transactions on Automatic
Control. He is also the recipient of the Donald P. Eckman award from the
American Control Council in 1993 for the best control engineer under 35. He is
a fellow of IEEE and IFAC.