#  The Generations of Classical Correlations via Quantum Schemes

Zhenyu Chen, Lijinzhi Lin, Xiaodie Lin, Zhaohui Wei, Penghui Yao Institute for
Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084,
P. R. China. Email<EMAIL_ADDRESS>for
Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084,
P. R. China. Email<EMAIL_ADDRESS>for
Interdisciplinary Information Sciences, Tsinghua University, Beijing 100084,
P. R. China. Email<EMAIL_ADDRESS>Mathematical Sciences
Center, Tsinghua University, Beijing 100084, and Yanqi Lake Beijing Institute
of Mathematical Sciences and Applications, 101407, P. R. China. Email:
<EMAIL_ADDRESS>Key Laboratory for Novel Software Technology,
Nanjing University, Nanjing, Jiangsu Province 210023, P. R. China, and Hefei
National Laboratory, Hefei 230088, P. R. China. Email<EMAIL_ADDRESS>
###### Abstract

Suppose two separated parties, Alice and Bob, share a bipartite quantum state
or a classical correlation called a _seed_ , and they try to generate a target
classical correlation by performing local quantum or classical operations on
the seed, i.e., any communications are not allowed. We consider the following
fundamental problem about this setting: whether Alice and Bob can use a given
seed to generate a target classical correlation. We show that this problem has
rich mathematical structures. Firstly, we prove that even if the seed is a
pure bipartite state, the above decision problem is already NP-hard and a
similar conclusion can also be drawn when the seed is also a classical
correlation, implying that this problem is hard to solve generally.
Furthermore, we prove that when the seed is a pure quantum state, solving the
problem is equivalent to finding out whether the target classical correlation
has some canonical form of positive semi-definite factorizations that matches
the seed pure state, revealing an interesting connection between the current
problem and optimization theory. Based on this observation and other insights,
we give several necessary conditions where the seed pure state has to satisfy
to generate the target classical correlation, and it turns out that these
conditions can also be generalized to the case that the seed is a mixed
quantum state. Lastly, since canonical forms of positive semi-definite
factorizations play a crucial role in solving the problem, we develop an
algorithm that can compute them for an arbitrary classical correlation, which
has decent performance on the cases we test.

##  1 Introduction

Local state transformation is a fundamental problem in quantum information
theory, which has wide applications in communication complexity, resource
theory, quantum distributed computing, quantum interactive proof systems, etc.
In the setting of local state transformation, given two bipartite states
$\rho$ and $\sigma$, two separated parties, Alice and Bob, share $\rho$, and
their goal is to generate $\sigma$. In this paper, we concern ourselves about
the case that the target state $\sigma$ is a classical correlation $(X,Y)$,
which is a pair of random variables distributed according to a joint
probability distribution $P$, for convenience, we call the half of the total
number of bits needed to record the labels of $(X,Y)$ the _size_ of $P$.
Suppose $P$ is not a product probability distribution, then Alice and Bob have
to share some resource beforehand, such as another classical correlation
$P^{\prime}$ called a _seed_ correlation or a shared quantum state $\rho$
called a _seed_ state. In the former case, all their operations are supposed
to be classical and local (each operation involves only one party), while in
the latter case, they could perform local quantum operations, i.e., each party
can make proper quantum measurements on the quantum subsystem and output the
outcomes as $X$ or $Y$. Similar to the classical case, we define the size of
$\rho$ to be half of the total number of qubits in $\rho$, denoted
$\mbox{\sf{size}}(\rho)$. Here we stress that when Alice and Bob generate a
target classical correlation $P$ based on shared resources, any communication
between them is not allowed. In the current paper, we will focus on this kind
of setting.

In such settings, the minimum size of such seed correlation (state) that can
generate $P$ has been defined as the _classical (quantum) correlation
complexity_ of $P$, denoted $\mbox{\sf{R}}(P)$ ($\mbox{\sf{Q}}(P)$). In fact,
it has been proved that [Zha12, JSWZ13]

(1.1) $\mbox{\sf{R}}(P)=\lceil\log_{2}\mbox{\tt{rank}}_{+}(P)\rceil,$

and

(1.2) $\mbox{\sf{Q}}(P)=\lceil\log_{2}\mbox{\tt{rank}${}_{\tt
psd}$}(P)\rceil.$

For any nonnegative matrix $P\in\mbox{$\mathbb{R}$}_{+}^{n\times m}$,
$\mbox{\tt{rank}}_{+}(P)$ is the nonnegative rank defined as the minimum
number $r$ such that $P$ can be decomposed as the summation of $r$ nonnegative
matrices of rank $1$, and $\mbox{\tt{rank}${}_{\tt psd}$}(P)$ is the positive
semi-definite rank (PSD-rank), which is the minimum $r$ such that there are
$r\times r$ positive semi-definite matrices $C_{x}$,
$D_{y}\in\mbox{$\mathbb{C}$}^{r\times r}$ satisfying that
$P(x,y)=\mbox{\tt{tr}}(C_{x}D_{y})$ for all $x$ and $y$, and this is called a
_PSD decomposition_ [FMP+12, FGP+15].

In such a situation, a natural further question arises: given a specific
quantum state $\rho_{0}$ and $\mbox{\sf{size}}(\rho_{0})\geq\mbox{\sf{Q}}(P)$,
can we generate $P$ by measuring $\rho_{0}$ locally? Similarly, if we have a
classical correlation $P_{0}$ such that
$\mbox{\sf{size}}(P_{0})\geq\mbox{\sf{R}}(P)$, can we generate $P$ based on
$P_{0}$ using local operations only? Note that the work in [JSWZ13] cannot
answer these questions. In the current manuscript, we will show that these
problems have very rich mathematical structures.

## Contributions

Our main contributions are as follows.

  * •

We show that even for the special cases that the seed is a bipartite pure
state $|\psi\rangle$ or another classical correlation $P^{\prime}$,
determining whether or not $P$ can be produced from $|\psi\rangle$ or
$P^{\prime}$ is NP-hard, implying that one-shot local state transformation is
generally hard to solve.

  * •

We prove that if the seed is a bipartite pure state $|\psi\rangle$,
determining whether or not $P$ can be produced from $|\psi\rangle$ is
equivalent to finding out whether $P$ as a nonnegative matrix has a certain
canonical form of PSD factorizations that matches $|\psi\rangle$, revealing an
interesting connection between the current problem and optimization theory.

  * •

We prove several necessary conditions that $|\psi\rangle$ has to satisfy to
generate $P$. Furthermore, these conditions can also be generalized to the
case that the seed is a mixed quantum state.

  * •

We develop an algorithm that can compute the canonical form of PSD
factorizations for an arbitrary $P$, which has decent performance on the cases
we test, and thus can be directly utilized to determine whether a given seed
state $|\psi\rangle$ can produce $P$.

## Related work

Non-interactive simulations of joint distributions, the classical counterpart
of local state transformation, is a fundamental task in information theory. In
this setting, two separated parties are provided with sequences $X^{n}$ and
$Y^{n}$, respectively, where $\\{(X_{i},Y_{i})\\}_{1\leq i\leq n}$ are
identically distributed draws from a probability distribution $P(x,y)$. The
goal is to determine whether they can generate a pair of random variables
$(U,V)_{u,v}$ possessing a joint distribution that closely approximates a
target distribution $Q(u,v)$ without any communication between them. The
history of research on non-interactive simulations of joint probability
distributions dates back to the pioneering works by Gács and Körner [GK73] and
Wyner [Wyn75]. Interested readers may refer to subsequent work such as [GKS16,
KA16] and the references therein for more information. Local state
transformations, first investigated by Beigi [Bei13], have gained increasing
attention recently. However, characterizing the possibility of local state
transformations has proved challenging, leading to various studies on
necessary and sufficient conditions, as well as algorithm designs for this
problem [MBG+19, CFL+12, QY21, QY23].

Most research on non-interactive simulations of joint distributions and local
state transformations focuses on the asymptotic setting, where the parties
share infinite copies of the source states [DB14, Bei13]. However, to the best
of our knowledge, research on one-shot non-interactive simulations of joint
probability distributions and one-shot local state transformations is much
less. Jain, Shi, Wei, and Zhang proved that the minimum sizes of seed
classical states or quantum states required to generate a given joint
distribution are tightly captured by nonnegative ranks and positive
semidefinite ranks respectively. However, both of them are NP-hard to compute
[Vav10, Shi17].

## Preliminaries

Let $[n]=\\{1,2,\ldots,n\\}$. Let $A=[A(i,j)]_{i,j}$ be an arbitrary
$m$-by-$n$ matrix with the $(i,j)$-th entry being $A(i,j)$, and we write
$A^{T}$ as the transpose of A. We define
$\text{diag}(x_{1},x_{2},\ldots,x_{n})$ as the $n$-by-$n$ diagonal matrix with
the diagonal entries $x_{1},x_{2},\ldots,x_{n}$. If A is a square matrix, let
$A=\sum_{a}a|a\rangle\langle a|$ be its spectral decomposition. Given a
function $f$ from complex numbers to complex numbers, we define
$f(A)=\sum_{a}f(a)|a\rangle\langle a|$. A matrix $A$ is said to be positive
semi-definite if all its eigenvalues are nonnegative, and we write $A\geq 0$
to indicate matrix $A$ is a PSD matrix. If $A,B\geq 0$ such that
$\mathrm{tr}(AB)=0$, then $AB=0$ [FGP+15].

If $P$ is an $m$-by-$n$ classical correlation, let $P(x)$ denote the marginal
probability of getting $x$, i.e., $P(x)\equiv\sum_{y}P(x,y)$, and similarly,
$P(y)\equiv\sum_{x}P(x,y)$. $P(x|y)\equiv\frac{P(x,y)}{{P(y)}}$ denotes the
conditional probability of getting $x$ given $y$. Define the classical
fidelity for two nonnegative vectors $p(x)$ and $q(x)$ as
$F(p,q)=\sum_{x}\sqrt{p(x)}\cdot\sqrt{q(x)}$.

A quantum state $\rho$ in Hilbert space $\mathcal{H}$ is a trace-one positive
semi-definite operator acting on $\mathcal{H}$. A quantum state $\rho$ is
called pure if it is rank-one as a matrix, namely
$\rho=|\psi\rangle\langle\psi|$ for some unit vector $|\psi\rangle$. In this
special case, we also write $\rho$ as $|\psi\rangle$. For a pure state
$|\psi\rangle\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}$, its Schmidt
decomposition is defined as
$|\psi\rangle=\sum_{i}\sqrt{\lambda_{i}}|\alpha_{i}\rangle\otimes|\beta_{i}\rangle$,
where $|\alpha_{i}\rangle$ and $|\beta_{i}\rangle$ are orthonormal bases for
$\mathcal{H}_{A}$ and $\mathcal{H}_{B}$ respectively, nonnegative real numbers
${\lambda_{i}}$’s are called the Schmidt coeﬀicients of $|\psi\rangle$, and
$\sum_{i}\lambda_{i}=1$. For quantum states $\rho$ and $\sigma$, the fidelity
between them is defined as
$\mathrm{F}(\rho,\sigma)=\operatorname{tr}\left(\sqrt{\sigma^{1/2}\rho\sigma^{1/2}}\right)$.

##  2 The quantum case that $\rho$ is pure

We first consider the following special case: If the seed is a bipartite pure
state $|\psi\rangle$, can a target classical correlation $P$ be produced from
it by local operations only? We now show that this special case already has
very rich mathematical structures.

###  2.1 On the computational complexity

We first prove that solving this special case generally is already NP-hard,
implying that it is hard to solve the original problem efficiently.

As mentioned in the introduction, for a given classical correlation $P$, its
quantum correlation complexity, the minimum size of a quantum seed state
$|\psi_{0}\rangle$ that can generate $P$, has been characterized completely.

######  Lemma 2.1 ([JSWZ13])

Let $P=[P(x,y)]_{x,y}$ be a classical correlation, and
$\rho=\sum_{x,y}P(x,y)\cdot|x\rangle\langle x|\otimes|y\rangle\langle y|$ be a
quantum state in $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. Then it holds that

$\displaystyle\mbox{\sf{Q}}(\rho)=\lceil\log_{2}\mbox{\tt{rank}${}_{\tt
psd}$}(P)\rceil=\min_{\mathcal{H}_{A_{1}},\mathcal{H}_{B_{1}}}\\{\big{\lceil}\log_{2}\mbox{\tt{S-rank}}(|\psi\rangle)\big{\rceil}:|\psi\rangle\text{
is a pure state}$ $\displaystyle\text{ in
}\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{B_{1}},\rho=\mbox{\tt{tr}}_{\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{B_{1}}}|\psi\rangle\langle\psi|\\},$

where $\mbox{\tt{S-rank}}(|\psi\rangle)$ is the Schmidt rank of $|\psi\rangle$
with respect to the partition $AA_{1}|BB_{1}$.

That is to say, a given pure state $|\psi_{0}\rangle$ can generate $P$ only
when the size of $|\psi_{0}\rangle$ is at least
$\lceil\log_{2}\mbox{\tt{rank}${}_{\tt psd}$}(P)\rceil$. In fact, [JSWZ13]
proves a further conclusion, that is, $|\psi_{0}\rangle$ can generate $P$ if
and only if $|\psi_{0}\rangle$ has the same Schmidt coefficients with some
purification of $\rho$ in
$\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{B_{1}}$,
where the partition is chosen to be $AA_{1}|BB_{1}$.

This can be explained as follows. On the one hand, if $|\psi_{0}\rangle$ has
the same Schmidt coefficients with a purification $|\phi\rangle$ of $\rho$,
then Alice and Bob can transform $|\psi_{0}\rangle$ to $|\phi\rangle$ by local
unitaries (attach some blank ancilla qubits if needed). Then by throwing away
the qubits in $\mathcal{H}_{A_{1}}$ and $\mathcal{H}_{B_{1}}$, the obtained
quantum state will be exactly $\rho$. On the other hand, if $|\psi_{0}\rangle$
can generate $P$, it means that Alice and Bob can produce $\rho$ by performing
local quantum operations on $|\psi_{0}\rangle$. Note that these local
operations can be simulated by attaching necessary ancilla qubits, performing
local unitary operations, and then dropping part of the qubits, which
indicates that before dropping part of the qubits, the overall quantum state
is actually a purification of $\rho$, and it has the same Schmidt coefficients
with $|\psi_{0}\rangle$, as local unitaries do not change them.

Unfortunately, we now prove that it is generally NP-hard to determine whether
or not $|\psi\rangle$ has the same Schmidt coefficients will some purification
of $\rho$ in
$\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{B_{1}}$.

###### Theorem 2.1

The problem of deciding whether a given pure state $|\psi\rangle$ can generate
a given correlation $P$ is $\mathbf{NP}$-hard.

Proof. We first recall the fact that the $\mathsf{SUBSET\mathchar 45\relax
SUM}$ problem is NP-hard [GJ90]. Suppose we have a set of positive real
numbers $S=\\{a_{1},a_{2},...,a_{n}\\}$, and $T=\sum_{i}a_{i}/2$. The
$\mathsf{SUBSET\mathchar 45\relax SUM}$ problem is asking whether any subset
of $S$ sums to precisely $T$. We now try to reduce the
$\mathsf{SUBSET\mathchar 45\relax SUM}$ problem to the problem we are
studying.

Consider the following specific case of classical correlation,

$\displaystyle P=\frac{1}{2}I_{2\times 2}=\frac{1}{2}\begin{pmatrix}1&0\\\
0&1\\\ \end{pmatrix}.$

Let the Schmidt decomposition of $|\psi\rangle$ be

$\displaystyle|\psi\rangle=$
$\displaystyle\sum_{i=1}^{r}\sqrt{\lambda_{i}}|\alpha_{i}\rangle|\beta_{i}\rangle.$

Also let
$\Lambda=\mathrm{diag}(\sqrt{\lambda_{1}},\cdots,\sqrt{\lambda_{r}})$. Without
loss of generality, we assume that
$\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{r}>0$. Then $|\psi\rangle$ can
generate correlation $P$ if and only if Alice and Bob can perform binary-
outcome quantum measurements with operators $\\{A,I-A\\}$ and
$\\{B^{\top},I-B^{\top}\\}$ respectively such that it holds that

$\displaystyle\mathrm{tr}(|\psi\rangle\langle\psi|(A\otimes
B^{\top}))=\mathrm{tr}(\Lambda A\Lambda B)=$ $\displaystyle 1/2,$
$\displaystyle\mathrm{tr}(\Lambda(I-A)\Lambda(I-B))=$ $\displaystyle 1/2,$
$\displaystyle\mathrm{tr}(\Lambda A\Lambda(I-B))=$ $\displaystyle 0,$
$\displaystyle\mathrm{tr}(\Lambda(I-A)\Lambda B)=$ $\displaystyle 0,$

where $A$ and $B$ are $r\times r$ PSD matrices satisfying $0\leq A,B\leq I$,
and $B^{\top}$ is the transpose of $B$.

Note that $\mathrm{tr}(\Lambda A\Lambda(I-B))=0$ implies that

$\displaystyle\mathrm{tr}{(}(\Lambda^{1/2}A\Lambda^{1/2})(\Lambda^{1/2}(I-B)\Lambda^{1/2}){)}=$
$\displaystyle 0,$
$\displaystyle\mathrm{tr}{(}(\Lambda^{1/2}(I-B)\Lambda^{1/2})(\Lambda^{1/2}A\Lambda^{1/2}){)}=$
$\displaystyle 0.$

Since both $\Lambda^{1/2}A\Lambda^{1/2}$ and $\Lambda^{1/2}(I-B)\Lambda^{1/2}$
are PSD matrices, we immediately have that

$\displaystyle(\Lambda^{1/2}A\Lambda^{1/2})(\Lambda^{1/2}(I-B)\Lambda^{1/2})=$
$\displaystyle 0,$
$\displaystyle(\Lambda^{1/2}(I-B)\Lambda^{1/2})(\Lambda^{1/2}A\Lambda^{1/2})=$
$\displaystyle 0.$

By similar argument, $\mathrm{tr}(\Lambda(I-A)\Lambda B)=0$ implies that

$\displaystyle(\Lambda^{1/2}(I-A)\Lambda^{1/2})(\Lambda^{1/2}B\Lambda^{1/2})=$
$\displaystyle 0,$
$\displaystyle(\Lambda^{1/2}B\Lambda^{1/2})(\Lambda^{1/2}(I-A)\Lambda^{1/2})=$
$\displaystyle 0.$

Since $\Lambda$ and $\Lambda^{1/2}$ are invertible, the above conditions
indicate that

$\displaystyle A\Lambda B=$ $\displaystyle A\Lambda=\Lambda B,$ $\displaystyle
B\Lambda A=$ $\displaystyle B\Lambda=\Lambda A.$

This gives $B=\Lambda^{-1}A\Lambda=\Lambda A\Lambda^{-1}$. Meanwhile, note
that $\Lambda$ is diagonal, then we have that $B=A$ and that when
$\lambda_{i}\neq\lambda_{j}$ it holds that $A_{ij}=0$, which means that $A$
and $B$ are block diagonal matrices and each block corresponds to each
distinct value of $\lambda_{i}$.

Furthermore, we also have

$\displaystyle B=\Lambda^{-1}A\Lambda=\Lambda^{-1}A\Lambda
B=\Lambda^{-1}A^{2}\Lambda=B^{2},$

hence both $A$ and $B$ are projectors. Combining this fact and that $A$ and
$B$ are block diagonal matrices, we know that each blocks of $A$ and $B$ are
also projectors.

Finally, we obtain that

$\displaystyle\frac{1}{2}=\mathrm{tr}(\Lambda A\Lambda
B)=\mathrm{tr}(\Lambda^{2}A^{2})=\mathrm{tr}(\Lambda^{2}A)=\sum_{\lambda}\lambda\cdot\mathrm{rank}(A|_{\mathrm{ker}(\Lambda^{2}-\lambda
I)}),$

where $\lambda$ in the summation runs through all distinct values of
$\lambda_{i}$, and $A|_{\mathrm{ker}(\Lambda^{2}-\lambda I)}$ is the block of
$A$ that corresponds to the value of $\lambda$. It can be seen that this
summation is exactly a subset sum of $\\{\lambda_{1},\cdots,\lambda_{r}\\}$,
hence if $|\psi\rangle$ can generate $P$, we can recover a solution of the
corresponding $\mathsf{SUBSET\mathchar 45\relax SUM}$ instance. Conversely, if
the $\mathsf{SUBSET\mathchar 45\relax SUM}$ instance has a solution, then by
measuring $|\psi\rangle$ in its Schmidt basis and grouping the outcomes, we
can transform $|\psi\rangle$ into $P$. Hence we obtain a reduction of the
$\mathsf{SUBSET\mathchar 45\relax SUM}$ problem to the problem that determines
whether $P$ can be generated from $|\psi\rangle$. $\square$

###  2.2 The canonical form of PSD factorizations

For a given classical correlation $P=[P(x,y)]_{x,y}$ and the corresponding
quantum state $\rho=\sum_{x,y}P(x,y)\cdot|x\rangle\langle
x|\otimes|y\rangle\langle y|$ in $\mathcal{H}_{A}\otimes\mathcal{H}_{B}$, we
now know that generally it is hard to determine whether a seed quantum state
$|\psi_{0}\rangle$ has the same Schmidt coefficients with some purification of
$\rho$ in
$\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{B_{1}}$.
Here the major challenge is to characterize the Schmidt coefficients for all
possible purifications of $\rho$ in
$\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{B_{1}}$,
and any results of this kind will be very useful to determine whether a given
$|\psi\rangle$ can produce $P$ by local quantum operations only.

Interestingly, it turns out that there exists a close relation between Schmidt
coefficients of purifications of $\rho$ in
$\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{B_{1}}$
and a special form of PSD factorizations for $P$. Recall that the concept of
PSD factorization plays an important role in optimization theory, which
determines the computational power of semi-definite programming in
combinatorial optimization problems [Yan88, BPT12].

Specifically, we call this special form of PSD factorizations _the canonical
form of PSD factorizations_.

###### Definition 2.1

A _canonical form of PSD factorizations_ for a nonnegative matrix
$P\in\mbox{$\mathbb{R}$}_{+}^{n\times m}$ is a collection of PSD matrices
$C_{x},D_{y}\in\mbox{$\mathbb{C}$}^{k\times k}$ that satisfy

$P(x,y)=\mbox{\tt{tr}}(C_{x}D_{y}),\ x=1,...,n,\ y=1...,m$

and

$\sum_{x=1}^{n}C_{x}=\sum_{y=1}^{m}D_{y}=\Lambda,$

where $\Lambda\in\mbox{$\mathbb{C}$}^{k\times k}$ is a diagonal nonnegative
matrix. And if $k=\mbox{\tt{rank}${}_{\tt psd}$}(P)$, we say this is an
optimal canonical form of PSD factorizations.

It can be seen that if dropping the requirement that
$\sum_{x=1}^{n}C_{x}=\sum_{y=1}^{m}D_{y}=\Lambda$, this is a regular PSD
factorization. We also remark that for an arbitrary nonnegative matrix $M$,
one can always find an optimal canonical form of PSD factorizations, which is
implied by the following theorem. Note that to make the entries of $M$ sum to
$1$, a proper renormalization for $M$ by a constant factor may be needed.

###### Theorem 2.2

Let $P=[P(x,y)]_{x,y}$ be a classical correlation, and
$\rho=\sum_{x,y}P(x,y)\cdot|x\rangle\langle x|\otimes|y\rangle\langle
y|\in\mathcal{H}_{A}\otimes\mathcal{H}_{B}$. Suppose $|\psi\rangle$ is a
purification of $\rho$ in
$\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{B_{1}}$,
then there exists a canonical form of PSD factorization $\\{C_{x},D_{y}\\}$ of
$P$ such that the Schmidt coefficients of $|\psi\rangle$ with respect to the
partition $AA_{1}|BB_{1}$ are exactly the diagonal entries of
$\Lambda=\sum_{x=1}^{n}C_{x}=\sum_{y=1}^{m}D_{y}$.

Proof. Suppose the Schmidt rank of $|\psi\rangle$ is $r$, and the Schmidt
coefficients are $\sqrt{\lambda_{i}}$, $i\in[r]$. Suppose the corresponding
Schmidt decomposition can be written as

$|\psi\rangle=\sum_{i=1}^{r}\left(\sum_{x=1}^{n}|x\rangle\otimes|v_{x}^{i}\rangle\right)\otimes\left(\sum_{y=1}^{m}|y\rangle\otimes|w_{y}^{i}\rangle\right),$

where $|v_{x}^{i}\rangle\in\mathcal{H}_{A_{1}}$ and
$|w_{y}^{i}\rangle\in\mathcal{H}_{B_{1}}$ are unnormalized quantum states.
According to the definition of Schmidt decomposition, one can choose the norms
of $|v_{x}^{i}\rangle\in\mathcal{H}_{A_{1}}$ and
$|w_{y}^{i}\rangle\in\mathcal{H}_{B_{1}}$ properly such that

(2.3) $\sum_{x=1}^{n}\langle v_{x}^{j}|v_{x}^{i}\rangle=\sum_{y=1}^{m}\langle
w_{y}^{j}|w_{y}^{i}\rangle=0,\ \ \text{for any }i\neq j,$

and

(2.4) $\sum_{x=1}^{n}\langle v_{x}^{i}|v_{x}^{i}\rangle=\sum_{y=1}^{m}\langle
w_{y}^{i}|w_{y}^{i}\rangle=\sqrt{\lambda_{i}},\ \ \text{for any }i\in[r].$

Since $|\psi\rangle$ is a purification of $\rho$, it holds that

$\displaystyle\rho$
$\displaystyle=\mbox{\tt{tr}}_{\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{B_{1}}}|\psi\rangle\langle\psi|$
$\displaystyle=\sum_{x,y}|x\rangle\langle x|\otimes|y\rangle\langle
y|\left(\sum_{i,j=1}^{r}\langle v_{x}^{j}|v_{x}^{i}\rangle\cdot\langle
w_{y}^{j}|w_{y}^{i}\rangle\right).$

We now define $r\times r$ matrices $C_{x}$ such that $C_{x}(j,i)=\langle
v_{x}^{j}|v_{x}^{i}\rangle$ for all $i,j\in[r]$, and $r\times r$ matrices
$D_{y}$ such that $D_{y}(i,j)=\langle w_{y}^{j}|w_{y}^{i}\rangle$ for all
$i,j\in[r]$. Then for any $x\in[n]$ and $y\in[m]$, $C_{x}$ and $D_{y}$ are
positive semi-definite matrices, and Eqs.(2.3) and (2.4) imply that

$\sum_{x=1}^{n}C_{x}=\sum_{y=1}^{m}D_{y}=\Lambda,\ \ \text{for any }i\in[r],$

where $\Lambda=\text{diag}(\sqrt{\lambda_{1}},...,\sqrt{\lambda_{r}})$.
$\square$

An interesting fact is that a nonnegative matrix can have multiple optimal
canonical forms of PSD factorizations. For example, let

$P=\frac{1}{3}\begin{bmatrix}1&1\\\ 1&0\end{bmatrix},$

then it holds that $\mbox{\tt{rank}${}_{\tt psd}$}(P)=2$. We define two pure
states in
$\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{B_{1}}$
as

$|\psi_{1}\rangle=\sum_{x,y=0}^{1}\sqrt{P(x,y})|x\rangle|y\rangle|x\rangle|y\rangle$

and

${|\psi_{2}\rangle}=\sum_{x,y=0}^{1}\sqrt{P(x,y})|x\rangle|y\rangle{\rm
CNOT}|x\rangle|y\rangle,$

where the CNOT gate is performed on the subsystems $A_{1}$ and $B_{1}$. Then
it can be verified that $|\psi_{1}\rangle$ and $|\psi_{2}\rangle$ are two
different purifications of $\rho=\sum_{x,y}P(x,y)\cdot|x\rangle\langle
x|\otimes|y\rangle\langle y|$ in
$\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{B_{1}}$.
By calculating their Schmidt coefficients, we can obtain two different optimal
canonical forms of PSD factorizations for $P$, where the $\Lambda$ matrices
are $\Lambda_{1}\approx\text{diag}(0.9342,0.3568)$ and
$\Lambda_{2}\approx\text{diag}(0.8165,0.5774)$ respectively.

###  2.3 Several necessary conditions for that $|\psi\rangle$ generates $P$

Let $m(\cdot)$ be a measure of bipartite states which is monotone non-
increasing under local quantum operations. Then it is easy to see that
$m(|\psi\rangle\langle\psi|)\geq m(P)$ is a necessary condition for which
$|\psi\rangle$ can be locally transformed to the target classical correlation
$P$. Several information-theoretic quantities are known to be monotone non-
increasing under local operations such as mutual information. Thus, if the
mutual information $I(A:B)$ of $|\psi\rangle$ is less than that of $P$, then
$P$ cannot be generated from $|\psi\rangle$ under local operations only.

Another such measure of correlation is the _sandwiched Rényi divergence_
[MLDS+13], which is defined as

$\tilde{D}_{\alpha}(\rho\|\sigma)=\frac{1}{\alpha-1}\log\left(\frac{1}{\mbox{\tt{tr}}(\rho)}\mbox{\tt{tr}}\left[(\sigma^{\frac{1-\alpha}{2\alpha}}\rho\sigma^{\frac{1-\alpha}{2\alpha}})^{\alpha}\right]\right),$

where $\alpha\in(0,1)\cup(1,\infty)$. Let
$|\psi\rangle=\sum_{i}\sqrt{\lambda_{i}}|i_{A}\rangle|i_{B}\rangle,\rho=|\psi\rangle\langle\psi|$
and $\sigma=\sum_{x,y}P(x,y)\cdot|x\rangle\langle x|\otimes|y\rangle\langle
y|$, where $|i_{A}\rangle,|x\rangle\in\mathcal{H}_{A}$
($|i_{B}\rangle,|y\rangle\in\mathcal{H}_{B}$) are orthonormal bases for
systems $A$ ($B$). Since the data processing inequality holds for the
order-$\alpha$ Rényi divergence with $\alpha\in[\frac{1}{2},1)\cup(1,\infty)$,
i.e., it cannot be increased by local quantum operations, by requiring
$\tilde{D}_{\alpha}(\rho\|\rho_{A}\otimes\rho_{B})\geq\tilde{D}_{\alpha}(\sigma\|\sigma_{A}\otimes\sigma_{B})$
where $\rho_{A},\rho_{B},\sigma_{A},\sigma_{B}$ are reduced density matrices
for $\rho$ and $\sigma$ respectively, it derives

(2.5)
$\left\\{\begin{array}[]{cc}\left(\sum_{i}\lambda_{i}^{\frac{2}{\alpha}-1}\right)^{\alpha}\leq\sum_{xy}\frac{P(x,y)^{\alpha}}{(P(x)P(y))^{\alpha-1}},&\alpha\in[\frac{1}{2},1)\\\
\left(\sum_{i}\lambda_{i}^{\frac{2}{\alpha}-1}\right)^{\alpha}\geq\sum_{xy}\frac{P(x,y)^{\alpha}}{(P(x)P(y))^{\alpha-1}},&\alpha\in(1,\infty)\end{array}.\right.$

Therefore, if $|\psi\rangle$ and $P$ violate any inequality in Eq.(2.5),
$|\psi\rangle$ cannot generate $P$ under local operations.

In addition to the above natural conclusions, we now show that the insight
provided by Theorem 2.2 allows us to obtain several new necessary conditions
that $|\psi\rangle$ has to satisfy to generate $P=[P(x,y)]_{x,y}$, which can
be stronger than the above two necessary conditions. Again, we suppose the
Schmidt rank of $|\psi\rangle$ is $r$, and the squared Schmidt coefficients
are $\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{r}$. For simplicity, in
this subsection we suppose that $r=\mbox{\tt{rank}${}_{\tt psd}$}(P)$, i.e.,
$\lambda_{r}>0$.

####  2.3.1 A necessary condition for $\lambda_{r}$

As mentioned before, $|\psi\rangle$ can generate $P$ means that $|\psi\rangle$
has the same Schmidt coefficients with a purification of $\rho$. According to
Theorem 2.2, this means that $P$ has a canonical form of PSD factorizations
$C_{x}$ and $D_{y}$ with
$\sum_{x}C_{x}=\sum_{y}D_{y}=\Lambda=\text{diag}(\sqrt{\lambda_{1}},...,\sqrt{\lambda_{r}})$,
where $x\in[n]$ and $y\in[m]$. Then we have that

$\sum_{y}P(x,y)=\sum_{y}\mbox{\tt{tr}}(C_{x}D_{y})=\mbox{\tt{tr}}(C_{x}\cdot\Lambda).$

Since $\Lambda\geq\lambda_{r}\cdot I_{r\times r}$, it holds that
$\sum_{y}P(x,y)\geq\sqrt{\lambda_{r}}\mbox{\tt{tr}}(C_{x})$, where $I_{r\times
r}$ is the $r\times r$ identity matrix. Similarly, we also have
$\sum_{x}P(x,y)\geq\sqrt{\lambda_{r}}\mbox{\tt{tr}}(D_{y})$.

Meanwhile, according to the Cauchy-Schwarz inequality, the relation
$P(x,y)=\mbox{\tt{tr}}(C_{x}D_{y})$ implies that

$P(x,y)\leq\sqrt{\mbox{\tt{tr}}(C_{x}^{2})}\sqrt{\mbox{\tt{tr}}(D_{y}^{2})}\leq\mbox{\tt{tr}}(C_{x})\mbox{\tt{tr}}(D_{y}),$

where we have utilized the fact that for any PSD matrix $M$ it holds that
$(\mbox{\tt{tr}}(M))^{2}\geq\mbox{\tt{tr}}(M^{2})$. Combining the above facts,
we have that

$\sum_{x}P(x,y)\sum_{y}P(x,y)\geq\lambda_{r}\mbox{\tt{tr}}(C_{x})\mbox{\tt{tr}}(D_{y})\geq\lambda_{r}\cdot
P(x,y).$

Note that the above relation holds for any $x\in[n]$ and $y\in[m]$. Therefore,
we obtain the following conclusion.

###### Proposition 2.1

If $|\psi\rangle$ can produce $P=[P(x,y)]_{x,y}$ by local operations only,
then it holds that

(2.6) $\lambda_{r}\leq\min_{x,y}\frac{\sum_{x}P(x,y)\sum_{y}P(x,y)}{P(x,y)}.$

###### Example 1

Let us see an example showing that this condition can be stronger than the
ones given by the mutual information and the sandwiched Rényi divergence.
Suppose one tries to generate $P=\begin{bmatrix}0.3&0\\\ 0&0.7\end{bmatrix}$
from $|\psi\rangle=\frac{|00\rangle+|11\rangle}{\sqrt{2}}$ under local
operations. Firstly, it can be verified that $P$ and $|\psi\rangle$ satisfy
the conditions given by the mutual information condition and the sandwiched
Rényi divergence. However, note that the minimal squared Schmidt coefficient
$\lambda_{r}$ of $|\psi\rangle$ is 0.5, while the right-hand side of Eq.(2.6)
for $P$ is 0.3, implying that Eq.(2.6) is violated and the possibility of
producing $P$ by performing local operations on $|\psi\rangle$ is ruled out.

####  2.3.2 A necessary condition for the entropy of $\\{\lambda_{i}\\}$

Define
$V=\text{diag}(\sqrt[4]{\lambda_{1}},\sqrt[4]{\lambda_{2}},...,\sqrt[4]{\lambda_{r}})$.
Since $C_{x}$ and $D_{y}$ are a canonical form of PSD factorizations for $P$,
it is not hard to see that $C_{x}^{\prime}=VC_{x}V$ and
$D_{y}^{\prime}=V^{-1}D_{y}V^{-1}$ are still a valid PSD decomposition for
$P$, i.e., $P(x,y)=\mbox{\tt{tr}}(C_{x}^{\prime}D_{y}^{\prime})$. Furthermore,
we now have that
$\sum_{x}C_{x}^{\prime}=\text{diag}(\lambda_{1},\lambda_{2},...,\lambda_{r})$
and $\sum_{y}D_{y}^{\prime}=I_{r\times r}$.

At the same time, let $P_{x}$ denote the transpose of the $x$-th row of $P$,
where $x\in[n]$. Define $\text{sum}(P_{x})$ to be the sum of all the entries
of $P_{x}$, then it holds that
$\text{sum}(P_{x})=\sum_{y}\mbox{\tt{tr}}(C_{x}^{\prime}D_{y}^{\prime})=\mbox{\tt{tr}}(C_{x}^{\prime})$.
Since $C_{x}^{\prime}$ is PSD for any $x$ and
$\sum_{y}D_{y}^{\prime}=I_{r\times r}$, we now view $\\{D_{y}^{\prime}\\}$ as
a set of a positive-operator-valued measure (POVM), and
$\rho_{x}=C_{x}^{\prime}/\mbox{\tt{tr}}(C_{x}^{\prime})$ as a quantum state,
then $P_{x}/\mbox{\tt{tr}}(C_{x}^{\prime})$ is actually the outcome
probability distribution if we measure $\rho_{x}$ with the POVM
$\\{D_{y}^{\prime}\\}$.

We now consider the following virtual protocol performed by Alice and Bob.
With probability $\mbox{\tt{tr}}(C_{x}^{\prime})$, Alice prepares and sends
the quantum state $\rho_{x}$ to Bob. After receiving the quantum state, he
measures it using the POVM $\\{D_{y}^{\prime}\\}$ and records the outcome $y$.
This process can be regarded as a protocol that classical information is
transformed from Alice to Bob. According to the Holevo bound ([NC11], chapter
12), it holds that

$I(P)\leq
S\left(\sum_{x}\mbox{\tt{tr}}(C_{x}^{\prime})\cdot\rho_{x}\right)-\sum_{x}\mbox{\tt{tr}}(C_{x}^{\prime})\cdot
S(\rho_{x})\leq
S\left(\sum_{x}C_{x}^{\prime}\right)=-\sum_{i}\lambda_{i}\log(\lambda_{i}),$

where $I(P)$ is the mutual information between $x$ and $y$, $S(\rho)$ is the
von Neumann entropy of $\rho$, and we have utilized the fact that
$S(\rho_{y})\geq 0$ for any $y$. Therefore, we have the following conclusion.

###### Proposition 2.2

If $|\psi\rangle$ can produce $P=[P(x,y)]_{x,y}$ by local operations only,
then it holds that

(2.7) $I(P)\leq-\sum_{i}\lambda_{i}\log(\lambda_{i}).$

Note that the necessary condition provided by the monotonicity of mutual
information directly reads

$I(P)\leq-2\sum_{i}\lambda_{i}\log(\lambda_{i}),$

indicating that the above new condition is always stronger. Furthermore, the
new condition can also be stronger than the necessary condition given by
Eq.(2.6) in some cases.

###### Example 2

Consider generating the classical correlation
$P=\frac{1}{9}\begin{bmatrix}1&4\\\ 4&0\end{bmatrix}$ under local operation
from the 2-qubit seed state with Schmidt coefficients $1/3$ and $2\sqrt{2}/3$,
it is easy to verify that Eq.(2.6) is satisfied. However, by checking the
Eq.(2.7), we have $I\approx
0.59\leq-\sum_{i}\lambda_{i}\log(\lambda_{i})\approx 0.5033$, excluding the
possibility that generates $P$ from this seed state.

####  2.3.3 The first necessary condition for the sum of squares of
$\\{\lambda_{i}\\}$

We now show that a new necessary condition can also be obtained from the
correlation measure $V_{\alpha}(A;B)$ for bipartite quantum states proposed in
[MBG+19], which is defined as

(2.8) $\displaystyle
V_{\alpha}(A;B)=\|\left(I_{B}\otimes\rho_{A}^{-(\alpha-1)/2\alpha}\right)\rho_{BA}\left(I_{B}\otimes\rho_{A}^{-(\alpha-1)/(2\alpha)}\right)-\rho_{B}\otimes\rho_{A}^{1/\alpha}\|_{(1,\alpha)},$

where $\alpha\in[1,\infty)$, $\rho_{A}$ and $\rho_{B}$ are the reduced density
matrices for Alice and Bob respectively, and $\|\cdot\|_{(1,\alpha)}$ is the
$(1,\alpha)$ norm derived from the interpolation theory [Pis98]. For any
$0\leq p\leq q$ and
$M_{AB}\in\mathcal{H}_{A}\otimes\mathcal{H}_{B},\left\|M_{AB}\right\|_{(p,q)}$
is defined as

$\displaystyle\left\|M_{AB}\right\|_{(p,q)}=\inf_{\sigma_{A},\tau_{A}}\left\|\left(\sigma_{A}^{-\frac{1}{2r}}\otimes
I_{B}\right)M_{AB}\left(\tau_{A}^{-\frac{1}{2r}}\otimes
I_{B}\right)\right\|_{q},$

where $r\in(0,+\infty]$ is chosen such that
$\frac{1}{p}=\frac{1}{q}+\frac{1}{r}$, $\|\cdot\|_{p}$ is the Schatten
$p$-norm, and the infimum is taken over all density matrices
$\sigma_{A},\tau_{A}\in\mathcal{H}_{A}$.

In [MBG+19], the properties of the correlation measure $V_{\alpha}(A;B)$ have
been well studied, where it has been known that $V_{\alpha}(A;B)$ is
monotonically non-increasing under local operation, indicating that it can be
utilized to quantify the correlation between subsystems A and B. Note that
$V_{\alpha}(A;B)$ is hard to compute analytically, but for classical
correlation $P$, it can be represented as [MBG+19]

(2.9)
$V^{\prime}_{\alpha}(A;B)=\sum_{y}\left(\sum_{x}P(x)|P(y|x)-P(y)|^{\alpha}\right)^{1/\alpha}.$

Moreover, an equivalent expression for $V_{2}(A;B)$ when $\alpha=2$ has been
given [MBG+19], and it reads

(2.10) $\displaystyle
V_{2}(A;B)=\inf_{\tau_{B},\sigma_{B}}\left(\operatorname{tr}\left[\left(\rho_{A}^{-1/2}\otimes\tau_{B}^{-1/2}\right)\rho_{AB}\left(\rho_{A}^{-1/2}\otimes\sigma_{B}^{-1/2}\right)\rho_{AB}\right]\right.\left.-\operatorname{tr}\left[\tau_{B}^{-1/2}\rho_{B}\sigma_{B}^{-1/2}\rho_{B}\right]\right)^{1/2},$

where the infimum is taken over all density matrices
$\tau_{B},\sigma_{B}\in\mathcal{H}_{B}$. Using the same notations
$C_{x}^{\prime}$, $D_{y}^{\prime}$ and $\rho_{x}$ that we just defined in the
previous necessary condition, we construct a quantum state $\rho_{AB}$ shared
by Alice and Bob, which is expressed as

$\rho_{AB}=\sum_{x}P(x)|x\rangle\langle x|\otimes\rho_{x},$

It can be seen that $P$ can be generated directly by measuring this state by
the POVM $\\{|x\rangle\langle x|\otimes D_{y}\\}_{x,y}$, which implies that
$V_{2}(A;B)\geq V^{\prime}_{2}(A;B)$. Let $\tau_{B}=\sigma_{B}=I/r$, then
$V_{2}(A;B)^{2}$ can be upper bounded by

(2.11) $\displaystyle V_{2}(A;B)^{2}$
$\displaystyle\leq\mbox{\tt{tr}}\left(\sum_{x}P(x)|x\rangle\langle x|\otimes
r\rho_{x}^{2}\right)-r\mbox{\tt{tr}}(\rho_{B}^{2})$ $\displaystyle\leq
r\left(\mbox{\tt{tr}}\left(\sum_{x}P(x)\rho_{x}^{2}\right)-\sum_{i}\lambda_{i}^{2}\right)$
$\displaystyle\leq
r\left(\mbox{\tt{tr}}\left(\sum_{x}P(x)\rho_{x}\right)-\sum_{i}\lambda_{i}^{2}\right)$
$\displaystyle=r(1-\sum_{i}\lambda_{i}^{2}).$

In the second inequality we have used the fact that
$\rho_{A}=\sum_{x}P(x)|x\rangle\langle x|$ and
$\rho_{B}=\sum_{x}C_{x}=\Lambda$. According to the relation $V_{2}(A;B)\geq
V^{\prime}_{2}(A;B)$, we eventually obtain the following conclusion.

###### Proposition 2.3

If $|\psi\rangle$ can produce $P=[P(x,y)]_{x,y}$ by local operations only,
then it holds that

(2.12) $\sum_{i}\lambda_{i}^{2}\leq 1-V^{\prime}_{2}(A;B)^{2}/r,$

where $V^{\prime}_{2}(A;B)$ is given in Eq.(2.9).

Again, we now see an example showing that this condition can be useful.

###### Example 3

Suppose when the pure state
$|\psi\rangle=\frac{1}{\sqrt{10}}|00\rangle+\frac{3}{\sqrt{10}}|11\rangle$ is
given, Alice and Bob aim at generating the correlation
$P=\frac{1}{11}\begin{bmatrix}2&6\\\ 3&0\end{bmatrix}$ under local operations.
The previous necessary condition given in Eq.(2.7) is satisfied in this case,
nevertheless this task cannot be fulfilled since it violates Eq.(2.12):
$\sum_{i}\lambda_{i}^{2}=0.82>1-V^{\prime}_{2}(A;B)^{2}/2\approx 0.7769$.

####  2.3.4 The second necessary condition for the sum of squares of
$\\{\lambda_{i}\\}$

We continue using the notations $P_{x}$ and $\rho_{x}$ defined in Sec.2.3.2.
Note that for $x_{1},x_{2}\in[n]$, $P_{x_{1}}/\mbox{\tt{tr}}(\rho_{x_{1}})$
and $P_{x_{2}}/\mbox{\tt{tr}}(\rho_{x_{2}})$ can be seen as two probability
distributions produced by measuring $\rho_{x_{1}}$ and $\rho_{x_{2}}$ with the
same POVM $\\{D_{y}^{\prime}\\}$. Therefore, we have that

$F(P_{x_{1}}/\mbox{\tt{tr}}(\rho_{x_{1}}),P_{x_{2}}/\mbox{\tt{tr}}(\rho_{x_{2}}))^{2}\geq
F(\rho_{x_{1}},\rho_{x_{2}})^{2}\geq\mbox{\tt{tr}}(\rho_{x_{1}}\rho_{x_{2}}),$

where we have used the facts that the fidelity between two quantum states is
smaller than that between the two probability distributions produced by
measuring them with the same POVM, and that
$F(\rho,\sigma)^{2}\geq\mbox{\tt{tr}}(\rho\sigma)$ for any $\rho$ and $\sigma$
[LWdW17]. Therefore,

$F(P_{x_{1}},P_{x_{2}})^{2}\geq\mbox{\tt{tr}}(C_{x_{1}}^{\prime}C_{x_{2}}^{\prime}).$

Combining this with the fact that
$\sum_{x}C_{x}^{\prime}=\text{diag}(\lambda_{1},\lambda_{2},...,\lambda_{r})$,
we eventually obtain

$\sum_{i,j=1}^{n}F(P_{i},P_{j})^{2}\geq\sum_{i,j=1}^{n}\mbox{\tt{tr}}(C_{i}^{\prime}C_{j}^{\prime})=\sum_{i}\lambda_{i}^{2}.$

###### Proposition 2.4

If $|\psi\rangle$ can produce $P=[P(x,y)]_{x,y}$ by local operations only,
then it holds that

(2.13) $\sum_{i,j=1}^{n}F(P_{i},P_{j})^{2}\geq\sum_{i}\lambda_{i}^{2}.$

As usual, we demonstrate an example showing that this necessary condition is
not covered by the previous one given in Eq.(2.12).

###### Example 4

Consider the possibility of applying local operations on
$|\psi\rangle=\frac{2}{5}|00\rangle+\frac{\sqrt{21}}{5}|11\rangle$ to generate
a correlation $P=\frac{1}{11}\begin{bmatrix}2&6\\\ 3&0\end{bmatrix}$. By
calculating the value of the terms in Eq.(2.13), we have that
$\sum_{i,j=1}^{2}F(P_{i},P_{j})^{2}=\frac{85}{121}\approx 0.7025$ and
$\sum_{i}\lambda_{i}^{2}=\frac{457}{625}=0.7312$, ruling out the possibility
of generating $P$ from $|\psi\rangle$. However, $0.7312\leq
1-V^{\prime}_{2}(A;B)^{2}/2\approx 0.7769$, satisfying the necessary condition
in Eq.(2.12).

Lastly, we clarify that among the aforementioned four new necessary conditions
based on the canonical form of PSD decomposition, no one is always stronger
than the others, which means that these necessary conditions could be useful
in different scenarios. To show that this is indeed the case, we now see an
example for which the necessary condition given in Eq.(2.13) is satisfied, but
the necessary condition given in Eq.(2.6) is violated.

###### Example 5

Specifically, suppose the target correlation
$P=\frac{1}{10}\begin{bmatrix}4&1&1\\\ 1&1&0\\\ 1&0&1\end{bmatrix}$ with
$\operatorname{rank}_{\mathrm{psd}}(P)=2$, then let us consider whether the
Bell state can generate $P$ under local operations. In this case,
$\sum_{i}\lambda_{i}^{2}=0.5$ and $\sum_{i,j=1}^{3}F(P_{i},P_{j})^{2}=0.82$,
then the necessary condition Eq.(2.13) is satisfied. However, by directly
computing the upper bound of $\lambda_{r}$ given by the necessary condition
Eq.(2.6), we have that
$\min_{x,y}\frac{\sum_{x}P(x,y)\sum_{y}P(x,y)}{P(x,y)}=0.4<0.5$, which implies
that the Bell state can not serve as the seed state to generate this classical
correlation.

##  3 The general case that the seed state is mixed

###  3.1 A general necessary condition for the case of mixed seed

We now turn to the general case of the classical correlation generation
problem: If Alice and Bob share a mixed seed quantum state $\rho_{0}$, can
they generate $P$ by local operations without communication? According to
Theorem 2.1, it is unlikely to efficiently solve this problem.

In fact, based on the necessary conditions for that a pure seed quantum state
can generate $P$, one can also build necessary conditions that $\rho_{0}$ must
satisfy to generate $P$. For this, one can choose a specific purification of
$\rho_{0}$ in
$\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{B_{1}}$
_arbitrarily_ , denoted $|\psi_{0}\rangle$, and then determine whether
$|\psi_{0}\rangle$ can generate $P$ by using the results we have obtained. It
is not hard to see that if we find out that $|\psi_{0}\rangle$ cannot generate
$P$ by local operations only, we immediately know that $\rho_{0}$ cannot
generate $P$. In other words, a necessary condition for $\rho$ can generate
$P$ is that _any_ specific purification $|\psi\rangle$ of $\rho_{0}$ in
$\mathcal{H}_{A_{1}}\otimes\mathcal{H}_{A}\otimes\mathcal{H}_{B}\otimes\mathcal{H}_{B_{1}}$
can also generate $P$.

###### Example 6

Suppose the target correlation is $P=\begin{bmatrix}0.3&0\\\
0&0.7\end{bmatrix}$, which has been discussed in Sec.2.3.1. Alice and Bob
share a two-qubit mixed state $\rho=\frac{1}{2}|0_{A}0_{B}\rangle\langle
0_{A}0_{B}|+\frac{1}{2}|1_{A}1_{B}\rangle\langle 1_{A}1_{B}|$, and want to
generate $P$ by local operations. It can be verified that the pure state
$|\psi\rangle=\frac{1}{\sqrt{2}}|0_{A_{1}}0_{A}0_{B}0_{B_{1}}\rangle+\frac{1}{\sqrt{2}}|1_{A_{1}}1_{A}1_{B}1_{B_{1}}\rangle$
is a specific purification of $\rho$. According to Eq.(2.6), we know that the
square of the minimal Schmidt coefficient of the pure seed state must be less
than or equal to 0.3, which rules out the possibility of generating $P$ from
$|\psi\rangle$, hence the original mixed state $\rho$ cannot generate $P$.

###  3.2 When the seed is also a classical correlation

In this subsection, we study the case that both the seed and target are
classical correlations, denoted by $P=[P(x,y)]_{x,y}$ and $Q=[Q(x,y)]_{x,y}$,
respectively. We will show that this case is still NP-hard.

####  3.2.1 Quantum has no advantage in reachability

Suppose $P=[P(x,y)]_{x,y}$ and $Q=[Q(x,y)]_{x,y}$ are two different classical
correlations with the same size. We now prove the following conclusion.

###### Theorem 3.1

If $P$ can generate $Q$ by local quantum operations, then the same can be
achieved by local classical operations.

Proof. Suppose $\\{E_{i}\\}$ and $\\{F_{j}\\}$ are the Kraus operators for the
quantum operations performed by Alice and Bob respectively such that

$\displaystyle\sum_{i,j}(E_{i}\otimes F_{j})\rho(E_{i}^{\dagger}\otimes
F_{j}^{\dagger})=$ $\displaystyle\sigma,$

where

$\displaystyle\rho=$ $\displaystyle\sum_{x,y}P(x,y)|x\rangle\langle
x|\otimes|y\rangle\langle y|,$ $\displaystyle\sigma=$
$\displaystyle\sum_{x,y}Q(x,y)|x\rangle\langle x|\otimes|y\rangle\langle y|.$

We expand the above relation with three pairs of indices and obtain

$\displaystyle\sigma=$
$\displaystyle\sum_{i,j,x,y,x^{\prime},y^{\prime},x^{\prime\prime},y^{\prime\prime}}P(x,y)\langle
x^{\prime}|E_{i}|x\rangle\langle y^{\prime}|F_{j}|y\rangle\langle
x|E_{i}^{\dagger}|x^{\prime\prime}\rangle\langle
y|F_{j}^{\dagger}|y^{\prime\prime}\rangle|x^{\prime}\rangle\langle
x^{\prime\prime}|\otimes|y^{\prime}\rangle\langle y^{\prime\prime}|$
$\displaystyle=$
$\displaystyle\sum_{i,j,x,y,x^{\prime},y^{\prime}}P(x,y)\langle
x^{\prime}|E_{i}|x\rangle\langle y^{\prime}|F_{j}|y\rangle\langle
x|E_{i}^{\dagger}|x^{\prime}\rangle\langle
y|F_{j}^{\dagger}|y^{\prime}\rangle|x^{\prime}\rangle\langle
x^{\prime}|\otimes|y^{\prime}\rangle\langle y^{\prime}|$ $\displaystyle=$
$\displaystyle\sum_{i,j,x,y,x^{\prime},y^{\prime}}P(x,y)|\langle
x^{\prime}|E_{i}|x\rangle|^{2}|\langle
y^{\prime}|F_{j}|y\rangle|^{2}|x^{\prime}\rangle\langle
x^{\prime}|\otimes|y^{\prime}\rangle\langle y^{\prime}|.$

This implies that

$\displaystyle Q(x^{\prime},y^{\prime})=$
$\displaystyle\sum_{i,j,x,y}P(x,y)|\langle
x^{\prime}|E_{i}|x\rangle|^{2}|\langle y^{\prime}|F_{j}|y\rangle|^{2}$
$\displaystyle=$ $\displaystyle\sum_{x,y}P(x,y)\left(\sum_{i}|\langle
x^{\prime}|E_{i}|x\rangle|^{2}\right)\left(\sum_{j}|\langle
y^{\prime}|F_{j}|y\rangle^{2}|\right).$

We define

$\displaystyle\mathrm{P}(x^{\prime}|x)=$ $\displaystyle\sum_{i}|\langle
x^{\prime}|E_{i}|x\rangle|^{2},$ $\displaystyle\mathrm{P}(y^{\prime}|y)=$
$\displaystyle\sum_{j}|\langle y^{\prime}|F_{j}|y\rangle|^{2}.$

Then it can be verified that both $\mathrm{P}(x^{\prime}|x)$ and
$\mathrm{P}(y^{\prime}|y)$ are valid conditional probabilities. Thus if Alice
and Bob take them as local classical operations, they can generate $Q$ based
on the seed classical correlation $P$.

$\square$

####  3.2.2 The NP-hardness of the case of classical seed

We now show that even if the seed state is restricted to a classical
correlation, determining whether it can generate a target classical
correlation is NP-hard.

###### Theorem 3.2

The problem of deciding whether a given correlation $P_{1}$ can generate
another given correlation $P_{2}$ via local quantum operations is
$\mathbf{NP}$-hard.

Proof. We consider the case that

$\displaystyle P_{1}=$
$\displaystyle\mathrm{diag}(\lambda_{1},\cdots,\lambda_{r}),$ $\displaystyle
P_{2}=$ $\displaystyle\frac{1}{2}I_{2\times
2}=\frac{1}{2}\begin{pmatrix}1&0\\\ 0&1\\\ \end{pmatrix},$

where $\lambda_{i}\geq 0$ for any $1\leq i\leq r$, and
$\sum_{i=1}^{r}\lambda_{i}=1$. According to Theorem 3.1, we can assume that
the local operations performed by Alice and Bob are classical. As a result,
the correlation $P_{2}$ can be generated from $P_{1}$ if and only if there
exists $2\times r$ matrices $A,B$ such that

$\displaystyle{A(i,j)}\geq$ $\displaystyle 0,$ $\displaystyle\forall
i\in[2],j\in[r],$ $\displaystyle{B(i,j)}\geq$ $\displaystyle 0,$
$\displaystyle\forall i\in[2],j\in[r],$ $\displaystyle{A(1,j)+A(2,j)}=$
$\displaystyle{B(1,j)+B(2,j)}=1,$ $\displaystyle\forall j\in[r],$
$\displaystyle P_{2}=$ $\displaystyle AP_{1}B^{T}.$

Suppose such $A$ and $B$ indeed exist. we now fix some $j\in[r]$ and suppose
${A(1,j)}>0$. By ${P_{2}(1,2)}=0$, we have ${B(2,j)}=0$, hence ${B(1,j)}=1$.
Since ${P_{2}(2,1)}=0$, this implies that ${A(2,j)}=0$, hence ${A(1,j)}=1$.
Due to the symmetry of the problem, a similar conclusion can be drawn for
${A(2,j)}$, ${B(1,j)}$, and ${B(2,j)}$. Therefore, there exists
$S\subseteq[r]$ such that $(j\in S\implies{A(1,j)=B(1,j)}=1)$ and $(j\not\in
S\implies{A(2,j)=B(2,j)=1})$. This gives ${P_{2}(1,1)}=\sum_{j\in
S}\lambda_{j}=\frac{1}{2}$, hence we recover a solution of the corresponding
$\mathsf{SUBSET\mathchar 45\relax SUM}$ instance.

Therefore, we successfully construct a reduction from the
$\mathsf{SUBSET\mathchar 45\relax SUM}$ problem to the problem that generates
$P_{2}$ from $P_{1}$, implying that the latter is NP-hard.

$\square$

##  4 An algorithm that computes canonical forms of PSD factorizations

According to Theorem 2.2, to determine whether or not $|\psi\rangle$ can
produce $P$ by local operations only, one needs to characterize all possible
canonical forms of PSD factorizations for $P$, and find out whether one of
them is consistent with $|\psi\rangle$. In the current section, we propose an
algorithm to compute canonical forms of PSD factorizations for an arbitrary
correlation $P$.

For this, we now formulate the task of computing canonical forms of PSD
factorizations as an optimization problem, where the variables are two sets of
matrices $\\{C_{x}\\}$ and $\\{D_{y}\\}$ belonging to the positive
semidefinite cone:

(4.14) $\displaystyle\min_{\begin{subarray}{c}C_{x},D_{y}\geq 0\\\
x=1,\ldots,n\\\
y=1,\ldots,m\end{subarray}}\sum_{x=1}^{n}\sum_{y=1}^{m}\left(P(x,y)-\mbox{\tt{tr}}(C_{x}D_{y})\right)^{2}$
$\displaystyle\text{subject to
}\sum_{x=1}^{n}C_{x}=\sum_{y=1}^{m}D_{y}=\Lambda.$

This optimization problem is non-convex and NP-hard [Shi17]. Since the
constraints and objective function are polynomial functions of the variables,
some established methods such as quantifier elimination [Tar98] and Lasserre’s
hierarchy [Las01] could be employed to solve the optimization problem, albeit
with exponential running time. To obtain a heuristic approach for this
problem, we fix one of the two sets of matrices to simplify it to a convex
optimization problem, similar to the algorithm in [VGG18] for computing PSD
factorization. We accordingly develop an algorithm that computes canonical
forms of PSD factorizations by alternately optimizing over $\\{C_{x}\\}$ and
$\\{D_{y}\\}$. The pseudo-code is represented in Algorithm 1.

Algorithm 1 Alternating optimization for the canonical form of PSD
factorizations

INPUT: $P\in\mathbb{R}_{+}^{n\times m}$ and initially fixed $\\{D_{y}\\}$.
OUTPUT: $\\{C_{x}\\}$ and $\\{D_{y}\\}$.

1: while stopping criterion not satisfied do

2: $\\{C_{x}\\}\leftarrow$ sub-algorithm $\left(P,\\{D_{y}\\}\right)$

3: $\\{D_{y}\\}\leftarrow$ sub-algorithm $\left(P^{T},\\{C_{x}\\}\right)$

4: end while

Particularly, the initial input of each matrix $D_{y^{\prime}}\in\\{D_{y}\\}$
is given by

$D_{y^{\prime}}=\sum_{i=i}^{r}b^{i}b^{i^{T}}$

where $b^{i}$’s are $n$-dimensional vector whose entries are initialized using
the normal distribution $\mathcal{N}(0,1)$, and $r$ is the size of the
canonical form of PSD factorizations. Each sub-algorithm returns the solution
of a convex optimization problem. Taking sub-algorithm
$\left(P,\\{D_{y}\\}\right)$ for example, the corresponding convex
optimization problem can be written as

$\min_{\begin{subarray}{c}C_{x}\geq 0\\\
x=1,\ldots,n\end{subarray}}\sum_{x=1}^{n}\sum_{y=1}^{m}\left(P(x,y)-\mbox{\tt{tr}}(C_{x}D_{y})\right)^{2}$
$\text{subject to }\sum_{x=1}^{n}C_{x}=\Lambda,$

where $\\{D_{y}\\}$ are supposed to be fixed. We use CVXPY to solve these
subproblems [DB16], and the pseudo-code is given in Algorithm 2.

Algorithm 2 Sub-algorithm

INPUT: $P\in\mathbb{R}_{+}^{n\times m}$ and initially fixed $\\{D_{y}\\}$.
OUTPUT: $\\{C_{x}\\}$.

1: $\\{C_{x}\\}\leftarrow$ arg$\min_{\begin{subarray}{c}C_{x}\geq 0\\\
x=1,\ldots,n\end{subarray}}\sum_{x=1}^{n}\sum_{y=1}^{m}\left(P(x,y)-\mbox{\tt{tr}}(C_{x}D_{y})\right)^{2}$
$\text{subject to }\sum_{x=1}^{n}C_{x}=\Lambda$

We now see a nontrivial application of this algorithm. Suppose we need to
determine whether a pure state $|\psi\rangle$ can generate a target classical
correlation $P$. For this, we first test whether any one of the aforementioned
necessary conditions we have found is violated by this case. If we find such a
necessary condition, then we know that $|\psi\rangle$ cannot generate $P$; if
no such necessary condition is found, for the time being we suppose it is
possible to generate $P$ from $|\psi\rangle$ and then employ Algorithm 1 to
search for the possible protocols.

For example, let $|\psi\rangle$ be a 2-qubit pure state with Schmidt
coefficient $1/\sqrt{5}$ and $2/\sqrt{5}$, and
$P=\frac{1}{3}\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}$. Note that all the
necessary conditions we have listed are satisfied in this case. We set
$\Lambda=\text{diag}(1/\sqrt{5},2/\sqrt{5})$ and $r=2$, then run the
algorithm. It takes less than 1 second on a laptop to obtain the following
canonical form of PSD factorizations:

$\begin{array}[]{ll}\@add@centering\centering
A_{1}=\left[\begin{array}[]{ll}0.26801401&0.22523125\\\
0.22523125&0.61132503\end{array}\right],&A_{2}=\left[\begin{array}[]{ll}0.17919958&-0.22523125\\\
-0.22523125&0.28310216\end{array}\right],\\\ \\\
B_{1}=\left[\begin{array}[]{ll}0.12072403&-0.26145645\\\
-0.26145645&0.68499394\end{array}\right],&B_{2}=\left[\begin{array}[]{ll}0.32648956&0.26145646\\\
0.26145646&0.20943325\end{array}\right],\end{array}$

where the objective function equals $9.2\times 10^{-10}$. As a result, we
believe that this seed state can be used to generate the target correlation
under local operations.

### Acknowledgments

Z.W. thanks Jamie Sikora for the helpful discussions. Z.C., L.L., X.L., and
Z.W. are supported by the National Key R&D Program of China, Grant No.
2018YFA0306703, 2021YFE0113100, and the National Natural Science Foundation of
China, Grant No. 61832015, 62272259. P.Y. is supported by the National Natural
Science Foundation of China (Grant No. 61972191) and the Innovation Program
for Quantum Science and Technology (Grant No. 2021ZD0302900).

## References

  * [Bei13] Salman Beigi.  A new quantum data processing inequality.  Journal of Mathematical Physics, 54(8):082202, 2013.
  * [BPT12] Grigoriy Blekherman, Pablo A Parrilo, and Rekha R Thomas.  Semidefinite optimization and convex algebraic geometry.  SIAM, 2012.
  * [CFL+12] HF Chau, Chi-Hang Fred Fung, Chi-Kwong Li, Edward Poon, and Nung-Sing Sze.  Entanglement transformation between sets of bipartite pure quantum states using local operations.  Journal of mathematical physics, 53(12):122201, 2012.
  * [DB14] Payam Delgosha and Salman Beigi.  Impossibility of local state transformation via hypercontractivity.  Communications in Mathematical Physics, 332(1):449–476, Nov 2014\.
  * [DB16] Steven Diamond and Stephen Boyd.  CVXPY: A python-embedded modeling language for convex optimization.  The Journal of Machine Learning Research, 17(1):2909–2913, 2016\.
  * [FGP+15] Hamza Fawzi, João Gouveia, Pablo A Parrilo, Richard Z Robinson, and Rekha R Thomas.  Positive semidefinite rank.  Mathematical Programming, 153(1):133–177, 2015.
  * [FMP+12] Samuel Fiorini, Serge Massar, Sebastian Pokutta, Hans Raj Tiwary, and Ronald de Wolf.  Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds.  In Proceedings of the forty-fourth annual ACM symposium on Theory of computing, pages 95–106, 2012.
  * [GJ90] Michael R. Garey and David S. Johnson.  Computers and Intractability: A Guide to the Theory of NP-Completeness.  W. H. Freeman & Co., USA, 1990.
  * [GK73] Peter Gács and J Körner.  Common information is far less than mutual information.  Problems of Control and Information Theory, 2(2):149–162, 1973\.
  * [GKS16] Badih Ghazi, Pritish Kamath, and Madhu Sudan.  Decidability of non-interactive simulation of joint distributions.  In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science, pages 545–554, Los Alamitos, CA, USA, Oct 2016. IEEE Computer Society.
  * [JSWZ13] Rahul Jain, Yaoyun Shi, Zhaohui Wei, and Shengyu Zhang.  Efficient protocols for generating bipartite classical distributions and quantum states.  IEEE Transactions on Information Theory, 59(8):5171–5178, 2013\.
  * [KA16] S. Kamath and V. Anantharam.  On non-interactive simulation of joint distributions.  IEEE Transactions on Information Theory, 62(6):3419–3435, 2016\.
  * [Las01] Jean B Lasserre.  Global optimization with polynomials and the problem of moments.  SIAM Journal on Optimization, 11(3):796–817, 2001.
  * [LWdW17] Troy Lee, Zhaohui Wei, and Ronald de Wolf.  Some upper and lower bounds on PSD-rank.  Mathematical programming, 162(1-2):495–521, 2017.
  * [MBG+19] Mohammad Mahdi Mojahedian, Salman Beigi, Amin Gohari, Mohammad Hossein Yassaee, and Mohammad Reza Aref.  A correlation measure based on vector-valued ${L}_{p}$-norms.  IEEE Transactions on Information Theory, 65(12):7985–8004, 2019\.
  * [MLDS+13] Martin Müller-Lennert, Frédéric Dupuis, Oleg Szehr, Serge Fehr, and Marco Tomamichel.  On quantum rényi entropies: A new generalization and some properties.  Journal of Mathematical Physics, 54(12):122203, 2013.
  * [NC11] Michael A. Nielsen and Isaac L. Chuang.  Quantum Computation and Quantum Information: 10th Anniversary Edition.  Cambridge University Press, USA, 10th edition, 2011.
  * [Pis98] Gilles Pisier.  Non-commutative vector valued $L_{p}$-spaces and completely $p$-summing maps.  Société mathématique de France, 1998.
  * [QY21] Minglong Qin and Penghui Yao.  Nonlocal games with noisy maximally entangled states are decidable.  SIAM Journal on Computing, 50(6):1800–1891, 2021.
  * [QY23] Minglong Qin and Penghui Yao.  Decidability of fully quantum nonlocal games with noisy maximally entangled states.  In 50th International Colloquium on Automata, Languages, and Programming, to appear, 2023.
  * [Shi17] Yaroslav Shitov.  The complexity of positive semidefinite matrix factorization.  SIAM Journal on Optimization, 27(3):1898–1909, 2017.
  * [Tar98] Alfred Tarski.  A decision method for elementary algebra and geometry.  Springer, 1998.
  * [Vav10] Stephen A Vavasis.  On the complexity of nonnegative matrix factorization.  SIAM Journal on Optimization, 20(3):1364–1377, 2010.
  * [VGG18] Arnaud Vandaele, François Glineur, and Nicolas Gillis.  Algorithms for positive semidefinite factorization.  Computational Optimization and Applications, 71(1):193–219, 2018\.
  * [Wyn75] A. Wyner.  The common information of two dependent random variables.  IEEE Transactions on Information Theory, 21(2):163–179, 1975.
  * [Yan88] Mihalis Yannakakis.  Expressing combinatorial optimization problems by linear programs.  In Proceedings of the twentieth annual ACM symposium on Theory of computing, pages 223–228, 1988.
  * [Zha12] Shengyu Zhang.  Quantum strategic game theory.  In Proceedings of the 3rd Innovations in Theoretical Computer Science Conference, pages 39–59, 2012.


This is a pre-print of the following chapter: Sanil S. Gandhi, Arvind W.
Kiwelekar, Laxman D. Netak, Hansraj S. Wankhede; “Security Requirement
Analysis of Blockchain-based E-Voting Systems”, published in Intelligent
Communication Technologies and Virtual Mobile Networks, 2022, edited by G.
Rajakumar, Ke-Lin Du, Chandrasekar Vuppalapati, Grigorios N. Beligiannis,
2022, Publisher Springer Singapore. The authenticated version is available on
publisher site.

Cite this chapter as: Gandhi, S.S., Kiwelekar, A.W., Netak, L.D., Wankhede,
H.S.(2023). Security Requirement Analysis of Blockchain-Based E-Voting
Systems. In:Rajakumar, G., Du, KL., Vuppalapati, C., Beligiannis, G.N. (eds)
Intelligent Communication Technologies and Virtual Mobile Networks. Lecture
Notes on Data Engineering and Communications Technologies, vol 131. Springer,
Singapore. https://doi.org/10.1007/978-981-19-1844-5_6.

# Security Requirement Analysis of Blockchain-based E-Voting Systems

Sanil S. Gandhi, Arvind W. Kiwelekar, Laxman D. Netak, Hansraj S. Wankhede
Department of Computer Engineering
Dr. Babasaheb Ambedkar Technological University
Lonere, Raigad-402103, India
<EMAIL_ADDRESS><EMAIL_ADDRESS><EMAIL_ADDRESS>
###### Abstract

In democratic countries such as India, voting is a fundamental right given to
citizens of their countries. Citizens need to physically present and cast
their vote in ballot-paper based voting systems. Most of the citizens fail to
fulfill this constraint and have stayed away from their fundamental duty.
Electronic-voting systems are often considered as one of the efficient
alternatives in such situations. Blockchain Technology is an emerging
technology that can provide a real solution as it is characterized by
immutable, transparent, anonymous, and decentralized properties. This paper
presents a security requirement analysis for e-voting systems and evaluates
blockchain technology against these requirements.

###### Index Terms:

Blockchain Technology, E-Voting, Cryptography, Security Analysis.

##  I Introduction

In Democratic countries, an election plays a vital role in the selection of
the government of the respective country. A voter must cast the vote securely
and privately without interference from any political party’s agents. There
are enormous ways to cast the vote in the different countries. In the
traditional voting system, a paper is used to cast the vote. The drawbacks of
this system are invalid votes, printing of millions of ballot papers,
transportation, storage and distribution of ballot papers, stealing or
altering a ballot boxes, and the counting process is manual, which takes too
long time.

In India, the Postal Ballot system facility is available for the members of
the armed forces, members of the state police department, or any person who is
appointed on the election duty. Voter have to punch his / her choice on the
ballot paper and, then these votes are dispatched to the Returning Officer of
the respective assembly using postal services. The drawback of this system is,
sometimes ballots are not delivered on time, papers tore in between the
transportation or did not properly punch by voters lead to the cancellation of
the vote at the time of the vote counting process.

Electronic Voting Machine (EVM) [1] drastically changes this scenario in
India. It helps to overcome all the drawbacks of a paper-based voting system.
But in this, the voter has to visit the polling station on election day.
Another way to cast a vote is through an Internet-based or remote voting
system. As voter can cast vote from anywhere, leads to an increase in voter
participation. The system is designed as a web-based applications or as a
mobile applications.

Earlier, the web-based applications are connected with bio-metric devices,
cards, passwords or PINs, etc. and currently, mobile-based applications have
in-built functionality for voter authentication. The online voting system was
designed in 2003, by the Estonian government for the local government council
elections, where a National ID card with Public Key Infrastructure (PKI) used
to authenticate the voter [2]. P. Y. A. Ryan et at. [3] have been implemented
_Prêt à Voter_ , a secure electronic voting system with end-to-end
verifiability.

Such, Internet-based systems are centralized, and vulnerable to many attacks
as well as depended on a trusted third party to carry out the whole election
process. Internet-based systems are easy to penetrate and are less
transferable as there is possibility of data manipulation. Due to such issues
in the existing online voting systems, many researchers are working on the
development of full-proof remote voting systems using innovative and emerging
technologies such as blockchain technology. The primary design goal of this
kind of efforts is to build a voting system which shall preserve voter’s
privacy and it shall be resilient to anticipated and unforeseen security
threats.

Some of the platforms for mobile-based remote voting, such as Voatz, Votem,
etc. are recently used to conduct elections for citizens having physical
disabilities, busy in their daily routine, or leaving out of the city. Voatz
is used within certain jurisdictions where local US government offers their
citizens to remotely cast the vote in the election. Private election of the
organisation is also conducted. For example, the Ohio State Bar Association
election conducted using the Votem blockchain-based mobile voting platform
[4].

Follow my votes, TIVI, BitCongress, and Vote Watcher are the examples of the
blockchain based mobile and desktop applications. The details of the such
applications as follows:

  1. 1.

Follow My Vote [29]: It is the online, open-source voting platform with end-
to-end verifibility. Desktop application is working on live operating system,
and mobile based application needs the various administrative permissions at
the time of installation of application so there is less possibility of
malware attacks.

  2. 2.

TIVI [31]: TIVI is remote voting application with easily understandable user
interface to novice users available for all the devices. This application
ensures the voter identity and eligibility through authentication methods.
Every ballot is secured using the public key encryption as well as voter’s
digital signature. Zero-Knowledge Proof [22] is used for correct voting
process.

  3. 3.

BitCongress [30]: BitCongress is the peer-to-peer electronic voting platform.
The platform is designed using Bitcoin, Smart Contract, Counterparty, and
Blockchain APIs. Proof-of-Work, Proof-of-Tally such mechanisms are used for
data integrity.

  4. 4.

VoteWatcher [32]: It is the open source electoral system. The ‘Optical Mark
Recognition’ (OMR) sheet is used as a paper ballot. Data extracted as voter
cast the vote and stored on the blockchain.

In the paper [5], authors analyzed two e-voting systems. First one is the
Estonian E-Voting System (EstEVS) and another is the Secure Electronic
Registration and Voting Experiment (SERVE) to find out which is secured. The
authors proposed the game-theoretical methods to analysed the large-scale
attacks. It is based on the probabilities model. The required data for
analysis of this system is collected from 1000 machines. The possible large-
scale attacks in such systems can be large scale votes’ theft,
disenfranchisement of votes, votes buying and selling, and privacy violation.

In the next section II, we discuss the blockchain primer and related work in
the blockchain based e-voting systems. Section II presents the detailed
requirement analysis of the blockchain-based e-voting system. Finally, we
conclude this paper in section IV.

##  II Background and Related Work

###  II-A Blockchain

Bitcoin (Cryptocurrency) [6] is the first application designed using the
blockchain platform. Blockchain stores data in the forms of the chain of
blocks as shown in Figure 1 in append-only mode. If, adversary tries to alter
or delete the data/transactions stored in the block, it violates the consensus
rules. Number of transactions are stored in a block as per the maximum size of
the block.

Figure 1: Blockchain

The first block of blockchain is called a _genesis block_. In genesis block,
the previous hash field is set to a default value in the genesis block means
it sets to zero or null and for the remaining fields, values are set to
default. The key characteristics of blockchain technology such as
decentralised, immutable, anonymity, and transparency are described as
follows:

  1. 1.

Decentralized: The single-point failure, collapse the whole centralized system
leads to the decentralization of the data. In this, data is not controlled by
a single entity. As, it forms trustworthy platforms, no need of a third party
or inter-mediator when performing transactions with unknown parties.

  2. 2.

Immutable: This property guarantees that no one can able to change the data
stored on the blockchain. All the nodes that are part of network stored the
data. An eavesdropper alters or deletes the data on the blockchain if and only
if an eavesdropper has more than 51% control in the system.

  3. 3.

Anonymity: This property hides the original identity of the user from the rest
of the world. It is useful in fund transfer or e-voting activities where the
needs of hiding the identity of the person. This is achieved via
public/private key-pair addresses.

  4. 4.

Transparency: All the blocks consisting of data is stored in every node
present in the network. So, any node that joins the e-voting system can able
to verify or view every transaction.

These key elements help to design a full-proof and efficient e-voting system.
It removes most of the pitfalls that arose in the traditional and Internet-
based i.e. centralized e-voting system.

Blockchain implementation is based on the Distributed Ledger, Cryptography,
Consensus Protocol, and Smart Contract.

  1. 1.

Distributed Ledger (DL): Traditional ledgers are used in business for keeping
day-to-day accounting information, the same way in blockchain distributed
ledgers store all the transactions in all the peers that are part of the
network. Any alteration in the ledger leads to an update in all the
consecutive nodes. Voter’s information, votes cast by voters are recorded and
replicated on every ledger.

  2. 2.

Cryptography (Crypt.): Paillier encryption [18], Homomorphic encryption [19],
Mix-net [20], Ring signature [11], Blind Signature [21], as well as Zero-
Knowledge Proof (ZKP) [22] etc. cryptographic and encryption techniques prefer
to secure any systems. These techniques are used for user authentication,
message privacy by encrypting and decrypting the data and hiding the user’s
identity by a key-pair generated using asymmetric cryptographic algorithms.

  3. 3.

Consensus Protocol (CP): All nodes in the decentralized network reach a common
agreement regarding the current state of the ledger with the help of a
consensus algorithm. It eliminates the double-spending attack. Bitcoin [6]
uses Proof-of-Work (PoW), Ethereum shifted from PoW to Proof-of-Stake (PoS),
and Hyperledger prefers Practical Byzantine Fault Tolerance (PBFT) as a
consensus algorithms. As per business specifications, various consensus
algorithms such as Proof of Activity (PoA), Proof of Weight (PoW), Proof of
Importance (PoI), Delegated Proof of Stake (DPoS), Proof of Elapsed Time
(PoET), Proof of Capacity (PoC), etc. can be used.

  4. 4.

Smart Contract (SC) [24]: Like the legal agreement or contract signed between
two parties, to exchange some value as parties satisfy the constraint
mentioned in the agreement. In the same manner, a smart contract triggers a
particular event when the system meets the predefined condition specified in
the contract. Solidity, Vyper, Golang, etc. are some of the programming
languages to write smart contracts. In e-voting, smart-contracts can be used
to convey a message to a voter after the vote stored on the blockchain, carry
out election rules, keep the track of the start and end of election time, etc.

There are different e-voting systems are designed using the blockchain
platform. That can be classified as first is based on public or private
cryptocurrencies such as Bitcoin [6], Zcash [23], Zerocoin [8], etc.; the
second uses the smart contract to trigger events as met with defined
condition, and last is by making use of blockchain as ballot boxes [11].

###  II-B Related Work

Zhao Z. et al. [7] proposed the bitcoin-based e-voting system. In this system,
candidates have to deposit bitcoins on every voter’s account before the start
of the election. This system does not support large scale voting. In the
paper[9], the authors used the Homomorphic ElGamal encryption and Ring
Signature methods. The advantage of the system is that transactions performed
by the voters are confirmed in less time. Authors[10] proposed the blockchain-
based solution. It uses the cryptographic blind signatures technique. The
pitfalls of this system is that ballots are not encrypted after the vote cast
by the voter and it is possible to trace the IP address of voters and nodes
using the network analysis tools.

B. Yu et al.[11] suggested various cryptographic techniques such as Paillier
encryption, Ring signature, Zero-Knowledge Proof (ZKP) to efficiently run the
voting process. Anonymity is achieved through a key-pair of 1024 or 2048 bits
generated for every voter using short linkable ring signature technique. The
only downside of ZKP, if a voter forgets his/her passcode, he/she lose the
data forever. In the paper [12], the authors explained how blockchain
technology makes e-voting secure, but the authors have not implemented the
e-voting system using the blockchain platform.

A private blockchain-based e-voting system proposed by F. Hjàlmarsson et
al.[13]. Authors [14] suggested the Fake Password technique, which is the
combination of fake credentials [15] and panic password [16] to avoid voter
coercion. To avoid Danial-of-Service (DoS) attacks, authors used Challenge-
Response Protocol, e.g. CAPTCHA, at the time of the creation of fake passwords
by an adversary and also data servers to be distributed across the network to
store the ballots during the voting process. In this paper, the author did not
mention how many votes a voter can cast during the voting process.

In the paper [34], the author proposed a blockchain-based e-voting system
implemented using ethereum. It is the internet-based decentralized system
which is capable of self-tallying the votes in the counting phase, provides
voter privacy, and end-to-end verifiability. But, the system is not able to
scale for more than 50 voters and also system is vulnerable to Denial-of-
Service attacks. Dagher G. et al. [35] proposed the ethereum blockchain-based
system for conducting the students’ association elections at the university
level. The authors suggested homomorphic encryption techniques, cryptographic
algorithm to achieve the voter’s privacy.

Hardwick et al. [17] proposed a private, blockchain-based e-voting system
implemented using the Ethereum platform. The voter can alter his/her already
casted vote number of times till the end of vote casting phase. But, when the
counting process starts, only the voter’s last vote is considered for
counting. The downsides of the system are (i) There is need of the Central
Authority (CA) to verify the voter authorization; (ii) A voter can alter the
vote till the election end time. To store multiple votes from a voter, there
is a need of an extra storage space, and the cost of computation to eliminate
duplicate votes is too high; (iii) To count the vote in the counting phase,
voter receive the ballot opening message. This message is required to open or
count the vote stored on the system. Because of any issue, if voter unable to
send a ballot opening message to the counting authority, then his/her vote
will not be consider in the final tally.

##  III Requirement Analysis

Every eligible voter must participate in the election process, and Election
Commission (EC) tries to make available various reliable, trustworthy, and
secure platforms so no one can stay away from their fundamental rights. The
new voting platforms must have to satisfy all the legal constraints of the
existing and traditional voting process. The complete election process is
separated into several tasks. Dimitris [25] elaborated the system requirements
for secure e-voting. Software Engineering principles assist in identifying
these functional and non-functional requirements of the e-voting process.

###  III-A Functional Requirements (FR)

In this, we are specifying the various services or functionalities that are
offered by the system. These functional requirements specify the inputs and
their behavior as per the inputs provided by the user to the system. The
abstract view of all e-voting related functional requirements are described as
given below:

  1. 1.

Voter Registration [FR1]: Every voter has to register herself in front of
election authority with necessary documents. The screening criteria help to
identify the eligibility of the voter.

  2. 2.

Provide the Authentication Credentials to Voter [FR2]: Each voter, after
validation of the identity of voter, gets credential details in the form of
either user-id and password or public-private key pair. The credential hides
voters’ real identity from the rest of the world. At the time of vote casting,
every voter authenticated using credentials and this will help to prevent
double-voting.

  3. 3.

Prepare the Digital Ballot Paper [FR3]: As the candidates are finalized for
the election, the next phase is to prepare the ballot paper to cast the vote.
The ballot paper consists of the name of all the candidates. As the start of
vote casting phase, every voter received a ballot paper to cast a vote via
email or notification on client-side software.

  4. 4.

Casting the Vote [FR4]: Each voter, select one of the candidates from the list
of candidate mentioned on the ballot paper. No link between voter and vote is
available to prove the way a vote is cast by a voter. For this, each vote must
be encapsulated by a double layer. First by using the voter’s digital
signature and then vote encrypted by one of the encryption techniques. The
votes cast by voters are verified against the already available votes to avoid
the double-voting problem. After verification, a vote is stored on the
blockchain. A voter can cast a vote in a stipulated duration of time.

  5. 5.

Vote Tallying [FR5]: After the end of the vote casting phase, the system
starts to count the votes stored on the blockchain, after counting the result
is stored on the blockchain for the audit purpose, and then declare the
results of an election. In this phase, all the votes are fetched from the
blockchain, then read the field by decrypting every vote and added it into an
individual account.

As per the various constraints mentioned by Election Commission for each
functional requirements, we mapped these functional requirements to the
blockchain architectural elements are shown in the Table I given below:

TABLE I: Mapping of System’s FR to Blockchain Elements Functional Requirements | Blockchain Elements | Remark
---|---|---
DL | Crypt. | CP | SC
| Voter
---
Registration
[FR1]
x | x |  | x |  | It records a hash of
---
data in the DL. The
consensus protocol
shall ensure consist-
ency among all
copies of DL.
| Provide the
---
Authentication
Credentials to
Voter [FR2]
x | x |  |  |  | Assign unique key
---
using public-private
key generation [26].
| Prepare the
---
Digital Ballot
Paper [FR3]
x | x |  | x |  | Implement the logic
---
of automated generation
of ballot paper as a smart
contract.
| Casting the
---
Vote [FR4]
x | x | x | x |  | Distributed ledgers
---
used to record the
vote. The consensus
protocol shall ensure
consistency among
the multiple copies
of ledgers.
| Vote Tallying
---
[FR5]
x | x |  | x |  | Implemented as a
---
smart contract to count
the vote received by
each candidate.

###  III-B Non-Functional Requirements

Non-functional requirements define systems quality attributes that affect the
user experience. If unable to fulfill the non-functional requirements, then
the system will not satisfy the user’s expectations. The most of the systems
are designed for the small scale election but not for the large scale
election. Zhang et al. [27] implemented the blockchain-based e-voting system
for large-scale elections. In this, author evaluated the performance of the
Chaintegrity based on nine different non-functional requirements with the help
of numerous cryptographic algorithms and encryption techniques.

There are several non-functional requirements but, in this we are targeting
security related quality attributes. E-voting is a confidential process and
must protect against security attacks, such as Sybil attack, Denial-of-Service
(DoS) attack, Man-in-the-middle attack, etc. These non-functional requirements
are listed as a given below:

  1. 1.

Privacy: This requirement satisfies that no one (including the electoral
authorities) can be traced out to whom the vote is cast by the elector. It is
not possible to reveal the candidate chosen by the voter in the vote casting
phase, and all votes remain concealed. Voter name, elector’s public/private
key-pair, voters’ documents, etc., will not be shared with unauthorised users.

_Anonymity_ means voters can cast a vote with a pseudonymous identity using
the public key. This can be achieved through cryptographic algorithms such as
Blind or Ring Signature.

In _receipt-freeness_ [28], a receipt will not be generated after a vote cast
by an elector. It ensures that voters will not be able to prove to coercer to
whom they voted. Even if the opponent cracked the secret key of the elector,
he would not find out the elector’s vote choice.

_Coercion-resistance_ means the system must be designed in such a way that an
adversary can not force a voter to cast a vote to a specific candidate, or
voters can not prove to an adversary how they voted.

Both receipt-freeness and coercion-resistance are complementary to each other.

  2. 2.

Data Integrity: The adversary should not access or tamper with the data stored
on the system. Also, unauthorized users should not alter the vote cast by
electorates and the electorates’s personal information. Cryptographic hash
algorithms are one-way functions, so the integrity of data can remain intact.

  3. 3.

Confidentiality: means the system will not reveal the true identity of the
electorate to their public-key infrastructure. An authorized user may have
access to the system data. This confirms that the system has quality
attributes such as coercion-resistance and privacy.

  4. 4.

Authentication: The legal and eligible voters only access the system and cast
the vote, and it helps in preventing the system from data or information
leakage.

  5. 5.

Authorization: Different stakeholders of the system are provided with a wide
range of functionalities. These functionalities help in preventing illegal
access and tampering with the data.

  6. 6.

Auditability: After the counting process, any external auditors can recount
the votes stored on the blockchain. Also, voters verify whether their vote
counted in the final tally or not. This property helps to achieve the
verifiability and validity of the process.

There are also other non-functional requirements such as verifiability,
scalability, transparency, availability, reliability, etc., need to improve
the e-voting system’s performance. Usability and accessibility are non-
functional system requirements that also play a crucial role in making the
system successful. To satisfy these constraints, developers must select the
public, private, or consortium blockchain networks as per the need in the
system requirement.

TABLE II: Non-functional Requirements of Existing Blockchain-based E-Voting Systems Non-functional Requirements | Existing Blockchain-based Platforms
---|---
FollowMyVote | TIVI | BitCongress | VoteWatcher
Privacy | x | x | x |
Integrity | x | x | x | x
Confidentiality | x |  | x |
Authentication | x | x |  |
Auditability | x | x | x | x

Table II maps the non-functional requirements of e-voting system to the some
of the existing commercial Blockchain-based voting applications such as
FollowMyVote [29], BitCongress [30], and TIVI [31], VoteWatcher [32].

###  III-C Countermeasures on the Typical Attacks

Adversary continuously trying to damage the existing system using different
potential attacks. Blockchain technology combined with some other techniques
such as authentication makes the system robust against the vulnerabilities and
helps to minimize attacks. In this section, we are elaborating on the various
attacks in the e-voting system and countermeasures.

  1. 1.

Denial of Service (DoS) Attack: In DoS, attackers target weak nodes in the
network by continuously sending malicious packets to flood the network with
excessive traffic. These attacks are resisted by using various techniques such
as authentication, Challenge-Response protocol [33] e.g. CAPTCHA, etc. In a
blockchain, a distributed ledger prevents DoS attacks since data or services
are distributed on multiple nodes.

  2. 2.

Man-in-the-Middle Attack: In a Man-in-the-middle attack, an adversary
intercepts communication between two parties to tamper the messages. An
adversary uses the same transaction and re-transmits the same data to the
smart contract. Various methods such as validating every single vote presets
on the block before the block is stored on the blockchain along with the
voter’s public key after casting a vote are preventing such kind of attack.

  3. 3.

Replay Attack: This attack is the same as the Man-in-the-Middle attack. An
adversary tries to copy the original transactions from one blockchain along
with the user’s signature and performs a new transaction on the blockchain. In
the case of e-voting, it is the same as double voting. Using the random
key/token for a every single transaction, double voting avoiding strategies,
or current timestamp of the transaction, etc. can be used to prevent such
attacks from a malicious user.

  4. 4.

Sybil Attack: In this, a malicious user will create multiple accounts or runs
multiple nodes in the distributed network. Using permissioned blockchain
platforms or voter authentication functionality to allow only eligible voters
to cast the vote can defend against such attacks.

Basic building blocks of blockchain architecture helps in prevent and mitigate
the numerous attacks such as smart contract-based, consensus protocol-based,
mining-based, or wallet-based attacks.

###  III-D Security and Privacy Requirements of Voting

The following are some of the generic security and privacy requirements that
any voting system shall enforce.

  1. 1.

The voting system shall able to preserve the privacy of the voting
information, means it shall not disclose the information that who has casted a
vote to which candidate.

  2. 2.

The voting system shall able to preserve the privacy of ownership of ballot
means it shall not disclose the identity of voter associated to a particular
ballot. This is also known as anonymity of voters.

  3. 3.

The voting system shall prove to the voters and auditors that no ballots are
removed from the ballot box.

  4. 4.

The voting system shall be coercion resistant means that voting system shall
protect voters from casting a vote under threat or attack.

  5. 5.

The voting system shall not be able to tamper with the casted votes once
election is closed and in-process.

  6. 6.

No early results should be obtainable before the end of the voting process;
this provides the assurance that the remaining voters will not be influenced
in their vote.

##  IV Conclusion

The design of blockchain-based voting system for a large-scale of election
must be secure, reliable, trustworthy, robust and free from security
loopholes. The system’s workflow must be user-friendly, and the system is
easily access or operate by the masses. Still, remote voting using blockchain
for huge population is under development phase and needs to find out various
techniques for coercion-resistance, and smoothly conducting the voting
process.

This paper presents functional and non-functional requirements for blockchain-
based remote e-voting systems. Also, these functional and non-functional
requirements are mapped to the basic architectural elements of the blockchain.
Some of existing blockchain-based voting systems are also reviewed. Hence,
paper presents state of the research in the blockchain-based e-voting systems,
and how to implement countermeasures to overcome the various vulnerabilities.

## References

  * [1] “Electronic Voting Machine (EVM)”, [Online], Available: _$https://eci.gov.in/files/file/8756-status-paper-on-evm-edition-3/$_
  * [2] Vinkel P.; “Internet Voting in Estonia”, In: Laud P. (eds) _Information Security Technology for Applications_ , Lecture Notes in Computer Science, vol 7161. Springer, Berlin, Heidelberg, 2012.
  * [3] P. Y. A. Ryan, D. Bismark, J. Heather, S. Schneider and Z. Xia; “PrÊt À Voter: a Voter-Verifiable Voting System”, in _IEEE Transactions on Information Forensics and Security_ , vol. 4, no. 4, pp. 662-673, Dec. 2009.
  * [4] “Case Study - OBSA 2017 President-Elect Election”, [Online], Availaible: _$https://www.votem.com/wp-content/uploads/2017/06/OSBA-Case-Study.pdf$_
  * [5] Buldas A. and Mägi T.; “Practical Security Analysis of E-Voting Systems”, In: Miyaji A., Kikuchi H., Rannenberg K. (eds) _Advances in Information and Computer Security_ , IWSEC 2007, Lecture Notes in Computer Science, vol 4752, Springer, Berlin, Heidelberg, 2007.
  * [6] Nakamoto, Satoshi; “Bitcoin: A peer-to-peer electronic cash system”, Manubot, 2019.
  * [7] Zhao, Z., Chan, T.H.H.; “How to vote privately using bitcoin”, In: _International Conference on Information and Communications Security_ , pp. 82–96, Springer, 2015.
  * [8] Yu Takabatake, Daisuke Kotani, and Yasuo Okabe; “An anonymous distributed electronic voting system using Zerocoin”, _IEICE Technical Report_ , 116(282): 127-131, 2016.
  * [9] B. Wang, J. Sun, Y. He, D. Pang, and N. Lu; “Large-scale election based on blockchain”, _Procedia Computer Science_ , vol. 129, pp. 234 – 237, 2018.
  * [10] Y. Liu and Q. Wang; “An e-voting protocol based on blockchain”, _IACRCryptology ePrint Archive_ , vol. 2017, p. 1043, 2017.
  * [11] B. Yu, J. K. Liu, A. Sakzad, S. Nepal, R. Steinfeld, P. Rimba, and M. H. Au; “Platform-independent secure blockchain-based voting system,” in _Information Security_ (L. Chen, M. Manulis, and S. Schneider, eds.), pp. 369–386, Springer International Publishing, 2018.
  * [12] T. Moura and A. Gomes; “Blockchain voting and its effects on election transparency and voter confidence”, in Proceedings of _the 18th Annual International Conference on Digital Government Research_ , dg.o ’17, (New York, NY, USA), p. 574 – 575, Association for Computing Machinery, 2017.
  * [13] F. Hjálmarsson, G. K. Hreiarsson, M. Hamdaqa, and G. Hjálmtýsson; “Blockchain-based e-voting system”, in _IEEE 11th International Conference on Cloud Computing (CLOUD)_ , pp. 983–986, 2018.
  * [14] A. Aziz; “Coercion-resistant e-voting scheme with blind signatures”, in _Cybersecurity and Cyberforensics Conference (CCC)_ , pp. 143–151, 2019.
  * [15] A. Juels, D. Catalano, and M. Jakobsson; “Coercion-resistant electronic elections”, in Proceedings of _the ACM Workshop on Privacy in the Electronic Society_ , WPES ’05, (New York, NY, USA), p. 61–70, Association for Computing Machinery, 2005.
  * [16] J. Clark and U. Hengartner; “Panic passwords: Authenticating under duress,” in Proceedings of _The 3rd Conference on Hot Topics in Security_ , HOTSEC’08, (USA), USENIX Association, 2008.
  * [17] F. Sheer Hardwick, A. Gioulis, R. Naeem Akram, and K. Markantonakis; “E-voting with blockchain: An e-voting protocol with decentralisation and voter privacy”, in _IEEE International Conference on Internet of Things (iThings) and IEEE Green Computing and Communications (GreenCom) and IEEE Cyber, Physical and Social Computing (CPSCom) and IEEE Smart Data (SmartData)_ , pp. 1561–1567, 2018.
  * [18] Zhe Xia, Steve A. Schneider, James Heather, and Jacques Traoré; “Analysis, improvement and simplification of Prêt à voter with Paillier encryption” In _Proceedings of the conference on Electronic voting technology_ , EVT’08, USENIX Association, USA, Article 13, 1–15, 2008.
  * [19] Hirt, M. and Sako, K.; “Efficient receipt-free voting based on homomorphic encryption” In _Advances in Cryptology - EUROCRYPT 2000_ , pp. 539-556, Springer Berlin/Heidelberg, 2000.
  * [20] David L. Chaum; “Untraceable electronic mail, return addresses, and digital pseudonyms” _Communications of the ACM_ , 24, 2, 84–90, 1981.
  * [21] Hirt, M. and Sako, K.; “Efficient receipt-free voting based on homomorphic encryption”, In _Advances in Cryptology-EUROCRYPT_ , pp. 539-556, Springer Berlin/Heidelberg, 2000.
  * [22] Neff, C.A.; “A verifiable secret shuffle and its application to e-voting”, In _Proceedings of the 8th ACM conference on Computer and Communications Security_ , pp. 116–125, ACM, 2001.
  * [23] Tarasov, P. & Tewari, H.; “The Future of E-Voting”, _IADIS International Journal on Computer Science and Information Systems_ , 12, 2, pp. 148 - 165, 2017.
  * [24] Buterin, Vitalik; “A next-generation smart contract and decentralized application platform”, white paper, 3.37, 2014.
  * [25] Dimitris A. Gritzalis; “Principles and requirements for a secure e-voting system”, _Computer & Security_, 21, 6, pp. 539–556, 2002.
  * [26] Yakubov A., Shbair W., Wallbom A., Sanda D. et al.; “A blockchain-based PKI management framework”, In _The First IEEE/IFIP international workshop on managing and managed by blockchain_ , Man2Block colocated with IEEE/IFIP NOMS 2018, Taipei, Taiwan, 23–27, Apr-2018.
  * [27] Zhang, S., Wang, L. & Xiong, H.; “Chaintegrity: blockchain-enabled large-scale e-voting system with robustness and universal verifiability”, International Journal of Information Security, 19, 323–341, 2020.
  * [28] Okamoto, T.; “Receipt-free electronic voting schemes for large scale elections” In: _International Workshop on Security Protocols_ , pp. 25–35. Springer, Berlin, 1997.
  * [29] “FollowMyVote”, Blockchain Voting: The End To End Process, [Online], _$https://followmyvote.com/blockchain-voting-the-end-to-end-process/$_.
  * [30] “BitCongress: Control the world from your phone”, [Online], Available: _$http://www.bitcongress.org/BitCongress/Whitepaper.pdf$_.
  * [31] “TIVI: Accessible and verifiable online voting”, [Online], Available: _$https://www.smartmatic.com/fileadmin/user\\_upload/\\\ Smartmatic\\_Whitepaper\\_Online\\_Voting\\_Challenge\\_\\\ Considerations\\_June2020.pdf$_.
  * [32] “VoteWatcher: Cutting Edge Blockchain Voting System”, [Online], Available: _$http://votewatcher.com/\\#voting$_ ,
  * [33] Von Ahn, L., Blum, M., Hopper, N. J., & Langford, J.; “CAPTCHA: Using hard AI problems for security”, In _International Conference on the Theory and Applications of Cryptographic Techniques_ , pp. 294-311, Springer, Berlin, Heidelberg, 2003.
  * [34] McCorry, P., Shahandashti, S.F., Hao, F.; “A smart contract for boardroom voting with maximum voter privacy”, In _International Conference on Financial Cryptography and Data Security_ , pp. 357–375. Springer, Berlin, 2017.
  * [35] Dagher, G. G., Marella, P. B., Milojkovic, M., Mohler, J.: Broncovote; “secure voting system using ethereum’s blockchain”, In _Proceedings of the 4th International Conference on Information Systems Security and Privacy_ , ICISSP 2018, pp. 96–107, 2018.