# Secure and Efficient Two-party Quantum Scalar Product Protocol With
Application to Privacy-preserving Matrix Multiplication

Wen-Jie Liu, Zi-Xian Li Manuscript created February 2, 2023; This work was
developed by National Natural Science Foundation of China (62071240), the
Innovation Program for Quantum Science and Technology (2021ZD0302900), and the
Research Innovation Program for College Graduates of Jiangsu Province, China
(KYCX23_1370).The authors are with the School of Software, Nanjing University
of Information Science and Technology, Nanjing 210044, China (e-mail:
<EMAIL_ADDRESS>zixianli157@163.com).

###### Abstract

Secure two-party scalar product (S2SP) is a promising research area within
secure multiparty computation (SMC), which can solve a range of SMC problems,
such as intrusion detection, data analysis, and geometric computations.
However, existing quantum S2SP protocols are not efficient enough, and the
complexity is usually close to exponential level. In this paper, a novel
secure two-party quantum scalar product (S2QSP) protocol based on Fourier
entangled states is proposed to achieve higher efficiency. Firstly, the
definition of unconditional security under malicious models is given. And
then, an honesty verification method called Entanglement Bondage is proposed,
which is used in conjunction with the modular summation gate to resist
malicious attacks. The property of Fourier entangled states is used to
calculate the scalar product with polynomial complexity. The unconditional
security of our protocol is proved, which guarantees the privacy of all
parties. In addition, we design a privacy-preserving quantum matrix
multiplication protocol based on S2QSP protocol. By transforming matrix
multiplication into a series of scalar product processes, the product of two
private matrices is calculated without revealing any privacy. Finally, we show
our protocol’s feasibility in IBM Qiskit simulator.

###### Index Terms:

Quantum computation, Quantum communication, Secure multi-party computation,
Scalar product, Matrix multiplication.

##  I Introduction

Secure Multi-party Computation (SMC) enables multiple parties who do not trust
each other to collaboratively compute a target function using their respective
private data, while preserving the privacy of all participants. Since Yao[1]
first proposed this concept in 1982, the main solutions for SMC proposed by
classical cryptographers include Garbled Circuit[2], Oblivious Transfer[3, 4,
5], Secret Sharing[6, 7, 8, 9], Homomorphic Encryption[10, 11, 12], etc.
However, protocols with higher generality typically exhibit greater
complexity. As a result, researchers often focus on developing specialized SMC
protocols tailored to specific problems. Secure Two-party Scalar Product
(S2SP) is a research area that investigates how two parties can securely
compute the scalar product of their respective private vectors. Many SMC
problems, such as intrusion detection[13, 14, 15], data analysis[16, 17, 18,
19], and geometry computation[20, 21, 22], can be reduced to S2SP, which makes
it a crucial building block for general secure computation. However, current
classical S2SP schemes either exhibit high complexity or rely on the
Computational Hardness Assumption for their security. Thus, there is an urgent
requirement for a novel scheme that achieves both high security and
computational efficiency.

In recent years, there has been a growing interest in utilizing quantum
mechanisms with potential for unconditional security to achieve secure
multiparty computation (SMC), which is referred to as quantum SMC (QSMC)[23,
24, 25, 26, 27]. However, existing Secure Two-party Quantum Scalar Product
(S2QSP) protocols are not efficient enough. In 2012, He et al.[28] pioneered a
S2QSP protocol, which requires a non-colluding third party to distribute
entangled states among the two participants. Furthermore, it demands
significant entanglement resources, which may exceed the required level when
operating on sparse private input vectors. In 2018, Wang et al.[29] proposed a
new S2QSP scheme using classical cryptography and continuous-variable
clusters. Their scheme no longer needs a third party, but still needs massive
redundant quantum resources and measurement operations. In 2019, Shi et
al.[30] proposed a strong privacy-preserving S2QSP protocol using Grover’s
algorithm[31] with constant communication complexity. However, while Grover’s
algorithm provides a quadratic speedup, its computational complexity remains
close to exponential. As a result, existing S2QSP protocols only offer
unconditional security with limited improvement in computational efficiency.

Compared with S2QSP, people have more fully studied two QSMC problems, i.e.,
Secure Multi-party Quantum Summation or Multiplication (SMQS or SMQM), where
several parties can secretly add or multiply up their private integers. In
2013, Yang et al.[32] proposed a secret sharing scheme based on Quantum
Fourier Transform $\mathcal{QFT}$. It takes advantage of a property of
$d$-level cat state[33], i.e., the ability to keep the sum unchanged after
applying the Modular Summation Gate $\mathcal{SUM}$. Based on this scheme,
people have proposed several SMQS protocols[34, 35, 36, 37, 38, 39]. However,
these protocols are limited to SMQS. In 2016, Shi et al.[40] provided another
way. They transformed the calculation from the bit domain to the phase domain,
then used the Rotation Gate $\mathcal{ROT}$ to perform the addition. This idea
is inspired by Draper’s Transform Adder[41]. Here, SMQM is implemented by
using the Modular Multiplication Gate $\mathcal{MUL}$. In addition, they used
Bitwise XOR Gate $\mathcal{XOR}$ (or $\mathcal{CNOT}$ gate) to construct the
$d$-level cat state, and applied again when returning to untie the
entanglement, and check the honesty of the other party. Considering that the
states appearing in the protocol have exceeded the category of cat states, we
define them as a more generalized state called Fourier Entangled (FE) State.

Although SMQS and SMQM protocols using FE states are efficient, they cannot be
directly applied to scalar product computations due to the interference
between addition and multiplication in such calculations. However, we discover
the following insight: Shi et al.’s method[40] allows both addition and
multiplication to be performed simultaneously without interference, as
addition is performed in the phase domain and multiplication is performed in
the bit domain. In this paper, we propose a novel secure quantum scalar
product protocol based on this nature, to achieve higher computational
efficiency. To transform this idea into a sufficiently secure S2QSP protocol,
we first use $\mathcal{SUM}$ to impose several random number in the bit domain
to prevent the measurement attack. What’s more, we apply a bi-particle version
of $\mathcal{SUM}$ ($\mathcal{BSUM}$) to entangle all particles, so as to
prevent verify the honesty of the sender. We refer to this operation as
Entanglement Bondage, and design an corresponding honesty test to check the
sender’s honesty. In this way, the two parties will get an almost fair
position, and can resist against forgery attacks without the assistance of a
third party. It is worth noting that since $\mathcal{QFT}$ is one of the few
quantum algorithms that can achieve exponential acceleration, our S2QSP scheme
can calculate scalar products with the highest known efficiency, namely
polynomial complexity.

Our contributions in this paper are summarized below.

  1. 1)

Based on the conceptions of Leakage Degree and Negligibility, the definition
of unconditional security under the malicious model is given in detail.

  2. 2)

An honesty verification method called Entanglement Bondage is proposed, which
is used in conjunction with the modular summation gate to resist various
malicious attacks.

  3. 3)

Based on the property of Fourier Entangled state and the methods in 2), we
propose a S2QSP protocol with polynomial complexity. and prove its
unconditional security.

  4. 4)

Based on the proposed S2QSP protocol, we present a privacy-preserving matrix
multiplication protocol, as an extended application of it.

  5. 5)

Finally, we verify the feasibility of the proposed S2QSP protocol in IBM
Qiskit simulator.

The rest of this paper is arranged as follows. In Section II, we define the
notations we used, give the quantum operations to be used, and introduce the
Fourier entangled state. In Section III, we define unconditional security in
the malicious model, propose the entanglement bondage, then present our
protocol. We analyze our protocol in Section IV, and give an application of it
in Section V. We conclude in Section VI.

##  II Preliminary

###  II-A Definitions of Notations

Table I shows the definitions of notations used.

TABLE I: Definitions of Notations Symbols | Meanings
---|---
$\imath$ | Imaginary unit
$n$ | Dimension of input vector
$\mathbf{x}=(x_{1},x_{2},\cdots,x_{n})$ | Alice’s input vector
$\mathbf{y}=(y_{1},y_{2},\cdots,y_{n})$ | Bob’s input vector
$v$ | Bob’s input random integer
$u$ | Alice’s output
$d,D=2^{d}$ | Particle’s qubit number and dimension
$a^{-1}$ | Multiplicative inverse of $a\ \mathrm{mod}\ D$
$\oplus$ | Bitwise XOR
$\omega$ | $e^{\frac{\imath 2\pi}{D}}=\cos(\frac{2\pi}{D})+\imath\sin(\frac{2\pi}{D})$
$m,N=2^{m}$ | Output’s bit number and modulus
$\left[N\right]$ | Set $\left\\{0,1,\cdots,N-1\right\\}$
$\left[N\right]^{o}$ | Set composed of odd numbers in $\left[N\right]$
$a\lvert b$ |  $a$ is a factor of $b$
$a\equiv b(\ \mathrm{mod}\ D)$ | $D|(a-b)$
$\left\lvert\psi\right\rangle_{h}$ | Particle $h$ is in state $\left\lvert\psi\right\rangle$
$\mathcal{U}_{h}$ | Quantum gate $\mathcal{U}$ performed on particle $h$
$a\parallel b$ | String connected by two strings $a,b$
$(h,t)$ | System composed of particles $h$ and $t$
$\left\lfloor a\right\rfloor,\left\lceil a\right\rceil$ | Round integer $a$ up and down respectively
$\left\lvert A\right\lvert$ | Cardinality of set $A$
$g:A\to B$ | Function $g$ from set $A$ to set $B$
$g^{-1}(b)$ | Solution set $\left\\{a\lvert g(a)=b,a\in A\right\\}$
$Im(g)$ | Image set $\left\\{b\lvert g(a)=b,a\in A\right\\}$
$\Pr(A)$ | Probability of event $A$
$H(A,B),H(A:B),$ | Joint entropy, mutual information and conditional
$H(A|B)$ | entropy of random variables $A,B$ [42]
$Z_{A},Z_{B}$ | View of Alice, Bob respectively
$X_{A},X_{B}$ | Privacy of Alice, Bob respectively
$I_{A},I_{B}$ | Leakage degree of Alice, Bob’s privacy respectively

###  II-B Quantum Operations

Taking two $d$-qubits particles $h=\left(h_{d-1},h_{d-2},\cdots,h_{0}\right)$
and $t=\left(t_{d-1},t_{d-2},\cdots,t_{0}\right)$ as example, the quantum
gates used in this paper are as follows (where addition and multiplication are
all performed mod $D$).

  1. 1)

Quantum Fourier Transform $\mathcal{QFT}$ and its inverse:

$\displaystyle\mathcal{QFT}_{h}:\left\lvert
a\right\rangle_{h}\rightarrow\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{aj}\left\lvert
j\right\rangle_{h},$ (1) $\displaystyle\mathcal{QFT}^{\dagger}_{h}:\left\lvert
a\right\rangle_{h}\rightarrow\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{-aj}\left\lvert
j\right\rangle_{h}.$ (2)

  2. 2)

Rotation Gate $\mathcal{ROT}(b)$ where $b\in\left[D\right]$:

$\mathcal{ROT}(b)_{h}:\left\lvert
a\right\rangle_{h}\rightarrow\omega^{ab}\left\lvert a\right\rangle_{h}.$ (3)

  3. 3)

Modular Summation Gate $\mathcal{SUM}(b)$ where $b\in\left[D\right]$:

$\mathcal{SUM}(b)_{h}:\left\lvert a\right\rangle_{h}\rightarrow\left\lvert
a+b\right\rangle_{h}.$ (4)

Note that $-b\equiv D-b\ (\ \mathrm{mod}\ D)$.

  4. 4)

Modular Multiplication Gate $\mathcal{MUL}(b)$ where $b\in\left[D\right]^{o}$:

$\mathcal{MUL}(b)_{h}:\left\lvert a\right\rangle_{h}\rightarrow\left\lvert
ab\right\rangle_{h}.$ (5)

Note that $b$ is odd, so it is coprime with $D=2^{d}$ and then has a unique
multiplicative inverse $b^{-1}\ \mathrm{mod}\ D$.

  5. 5)

Bi-particle Modular Summation Gate $\mathcal{BSUM}$:

$\mathcal{BSUM}_{(h,t)}:\left\lvert a\right\rangle_{h}\left\lvert
b\right\rangle_{t}\rightarrow\left\lvert a\right\rangle_{h}\left\lvert
b+a\right\rangle_{t}.$ (6)

  6. 6)

Bitwise XOR Gate $\mathcal{XOR}$:

$\mathcal{XOR}_{(h,t)}:\left\lvert a\right\rangle_{h}\left\lvert
b\right\rangle_{t}\rightarrow\left\lvert a\right\rangle_{h}\left\lvert b\oplus
a\right\rangle_{t}.$ (7)

###  II-C Fourier Entangled State

######  Definition 1 (Fourier Entangled (FE) State).

Let $X\in S_{X}$ be a secret, $C\in S_{C}$ be a random variable independent of
$X$, $\forall x\in S_{X},\forall C\in
S_{C},\Pr(X=x)=p_{x}=\frac{1}{\left\lvert
S_{X}\right\lvert},\Pr(C=c)=p_{c}=\frac{1}{\left\lvert S_{C}\right\lvert}$.
Given two quantum systems $P,Q$ with $l_{1},l_{2}$ qubits respectively, and
one $D=2^{d}$-dim FE state is as:

$\displaystyle\left\lvert\psi(x,c)\right\rangle_{(P,Q)}=$ $\displaystyle\ \
\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{jh(x,c)}\left\lvert
f(j,x,c)\right\rangle_{P}\left\lvert g(j,x,c)\right\rangle_{Q},$ (8)

where $f:\left[D\right]\times S_{X}\times S_{C}\to\left[2^{l_{1}}\right]$,
$g:\left[D\right]\times S_{X}\times S_{C}\to\left[L\right]$, $L=2^{l_{2}}$.
$\forall j^{\prime},j\in\left[D\right],\left\langle f(j^{\prime},x,c)\lvert
f(j,x,c)\right\rangle=\delta_{j^{\prime}j}$.

We call the systems $P$ and $Q$ local systems. We generally consider attacks
on $Q$, not $P$. The function $h(x,c)$ is called Phase domain,
correspondingly, the functions $f(j,x,c),g(j,x,c)$ are Bit domain. The
information these functions contain are called Phase-information and Bit-
information respectively.

Assume an FE state $\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{P}\left\lvert ja_{1}\right\rangle_{Q_{1}}\left\lvert
ja_{2}\right\rangle_{Q_{2}}$, where $a_{1},a_{2}\in\left[D\right]^{o}$, and it
has the following properties:

######  Property 1 (Addition-Multiplication Independence).

If using $\mathcal{ROT}(b_{1})$ on $Q_{1}$, it will be attached a phase factor
$\omega^{ja_{1}b_{1}}$. If using $\mathcal{ROT}(b_{2})$ on $Q_{2}$, there is a
new factor $\omega^{ja_{2}b_{2}}$. Therefore, the total phase is
$\omega^{j(a_{1}b_{1}+a_{2}b_{2})}$.

######  Property 2 (Addend’s Disappearance).

Apply $\mathcal{SUM}(c)$ on $Q_{1}$, then apply $\mathcal{ROT}(b)$ on
$\left\lvert ja_{1}+c\right\rangle_{Q_{1}}$. Since the global phase factor
$\omega^{bc}$ does not affect any measurement results [42], it can be omitted,
i.e., the addend $c$ does not affect the phase.

##  III Proposed Protocol

In this section, we first define the unconditional security under the
malicious model, then briefly introduce Entanglement Bondage we will use in
the protocol. We provide the specific protocol process at the end.

###  III-A Unconditional Security under the Malicious Model

######  Definition 2 (Malicious adversary model).

In this model, attacks other than a) forging input, b) not participating in
the protocol, and c) terminating the protocol halfway should be all defensed
or detected.

In addition, the following assumptions are also made to simplifies the
analysis:

  1. 1)

Malicious adversaries do not input, but only steal, since the information it
inputs will interfere with its attack.

  2. 2)

Malicious adversaries are to obtain information, not just destroy. We mainly
ensure the privacy of valid information.

  3. 3)

If either party is malicious, the other is not, since a protocol executed
between malicious participants is meaningless.

Considering the particularity of quantum protocols, we use information theory
language to define unconditional security under this model. Assume that in a
two-party protocol $\Pi$, there is an honest party $HP$ and a malicious party
$MP$ respectively. Denote the privacy of $HP$ is a random variable $X$, with a
Shannon entropy $H(X)=m_{X}$. Denote the expected result $MP$ should get as
$F$. Then

######  Definition 3 (Leakage Degree).

Under an attack $AT$, the view obtained by $MP$ is a random variable $Z$.
Mutual information $I=H(Z:X)$ measures the information increment to $X$ when
$Z$ is known. Stipulate that if attack $AT$ is detected by $HP$, $H(Z:X)=0$,
since the attack has failed. If $MP$ cannot get $F$ after its attack, then the
leakage degree of $X$ is defined as $H(Z:X)$; Otherwise, it equals to the
conditional mutual information[43] $H(Z:X|F)$, which measures how much
information $MP$ will obtain other than $F$.

######  Definition 4 (Negligibility).

A function $\mu(m_{X}):\mathbb{N}\to[0,1]$ is said to be negligible, if there
is no positive polynomial $poly(m_{X})$ about $m_{X}$ so that
$\mu(m_{X})=\Omega(1/poly(m_{X}))$.

######  Definition 5 (Unconditional Security under the Malicious Model).

Protocol $\Pi$ is said to has unconditional security under the malicious
model, if in one run of $\Pi$, the leakage degree of any party’s privacy is
negligible under all known malicious attacks.

###  III-B Entanglement Bondage

Assume that in a quantum protocol, $MP$ should send several particles
$t_{1},t_{2},g$ to $HP$, which are FE-entangled as
$\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{t_{1}}\left\lvert ja_{1}\right\rangle_{t_{2}}\left\lvert
ja_{2}\right\rangle_{g}$, $a_{1},a_{2}\in\left[D\right]^{o}$. However, $MP$
can perform a forgery attack, i.e., it doesn’t entangle $t_{1},t_{2},g$. Now
$HP$ wants to verify $MP$’s honesty, without disrupting the superposition
state of the particles. $HP$ applies $\mathcal{MUL},\mathcal{BSUM}$ to add the
state $j,ja_{1}$ to $ja_{2}$:

$\displaystyle ja_{2}\to
jk_{1}+jk_{2}a_{1}+jk_{3}a_{2}=j(k_{1}+k_{2}a_{1}+k_{3}a_{2}),$ (9)

where $k_{1},k_{2},k_{3}\in\left[D\right]^{o}$. This process is called
Entanglement Bondage. If $MP$ is dishonest, then this step will entangle the
three particles. Under the entanglement, $MP$ cannot steal information without
being detected.

After the above steps, $HP$ can perform an honesty test as follows. $HP$ sends
$k_{1},k_{2},k_{3}$ to $MP$, and $MP$ will return an answer
$r=(k_{1}+k_{2}a_{1}+k_{3}a_{2})^{-1}$, since the add of any three odds is
also an odd. $HP$ applies $\mathcal{MUL}(r)$ on $g$, then
$bra{j(k_{1}+k_{2}a_{1}+k_{3}a_{2})}_{g}\to\left\lvert j\right\rangle_{g}$.
Now $HP$ can perform $\mathcal{XOR}$ on $t_{1},g$, then $\left\lvert
j\right\rangle_{g}\to\left\lvert 0\right\rangle_{g}$. $HP$ can verify the
correctness of the state prepared by $MP$ by measuring $g$. If $g$ is in state
$\left\lvert 0\right\rangle$, then $MP$ passes; Otherwise, $MP$’s cheating is
detected. This process is actually a zero-knowledge proof, through which $HP$
can verify whether $MP$ really prepared the correct quantum state as promised,
without measuring the state itself. The effectiveness of this mechanism can be
seen in Section IV-B.

###  III-C Specific Protocol Process

######  Definition 6 (Secure Two-party Scalar Product (S2SP)).

Alice and Bob each have an $n$-dim vector
$\mathbf{x}=(x_{1},x_{2},\cdots,x_{n})$ and
$\mathbf{y}=(y_{1},y_{2},\cdots,y_{n})$ respectively, where
$x_{i},y_{i}\in\left[N\right]$, $N=2^{m}$. Alice is to get
$u=\mathbf{x}\cdot\mathbf{y}+v\ \mathrm{mod}\ N=\sum_{i=1}^{n}{x_{i}y_{i}}+v\
\mathrm{mod}\ N$, while $v\in\left[N\right]$ is known only by Bob. A secure
protocol should meet the following requirements:

$\bullet$ Alice’s Privacy: Bob learns no information about $\mathbf{x}$.

$\bullet$ Bob’s Privacy: Alice learns no information about $\mathbf{y},v$
other than $u=\mathbf{x}\cdot\mathbf{y}+v\ \mathrm{mod}\ N$.

######  Protocol 1.

Secure Two-party Quantum Scalar Product Protocol (S2QSPP).

1) Preparation Stage

  1. Step 1

Alice and Bob set $d=m+2$ and $D=2^{d}$.

  2. Step 2

Alice assigns $p_{i}=2x_{i}+1$ for each $i=1,2,\cdots,n$.

  3. Step 3

Bob selects randomly $v_{1},v_{2},\cdots,v_{n-1}\in\left[N\right]$, and then
sets $v_{n}=\frac{4v-4\sum_{i=1}^{n-1}{v_{i}}\ \mathrm{mod}\ D}{4}$, i.e.,
$4\sum_{i=1}^{n}{v_{i}}\equiv 4v(\ \mathrm{mod}\ D)$. He assigns
$q_{i}=2y_{i}+1$ and $s_{i}=4v_{i}-2y_{i}-1\ \mathrm{mod}\ D$.

2) Operation Stage
For each $i=1,2,\cdots,n$, do the following steps (all arithmetic operations
are performed mod $D$ here):

  1. Step 1

(Alice’s Inputing) Alice prepares $4$ $d$-qubit particles $h,t_{1},t_{2},g$
initialized as $\left\lvert 0\right\rangle$. She selects
$c_{1},c_{2},c_{4}\in\left[D\right]$ and $c_{3}\in\left[D\right]^{o}$
randomly, then does the following:

$\displaystyle\left\lvert 0\right\rangle_{h}\left\lvert
0\right\rangle_{t_{1}}\left\lvert 0\right\rangle_{t_{2}}\left\lvert
0\right\rangle_{g}$
$\displaystyle\overset{\mathcal{QFT}_{h}}{\longrightarrow}\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{h}\left\lvert 0\right\rangle_{t_{1}}\left\lvert
0\right\rangle_{t_{2}}\left\lvert 0\right\rangle_{g}$
$\displaystyle\overset{\mathcal{XOR}_{(h,t_{1})}\mathcal{XOR}_{(h,t_{2})}\mathcal{XOR}_{(h,g)}}{\longrightarrow}$
$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{h}\left\lvert j\right\rangle_{t_{1}}\left\lvert
j\right\rangle_{t_{2}}\left\lvert j\right\rangle_{g}$
$\displaystyle\overset{\mathcal{MUL}(p_{i})_{t_{2}}\mathcal{MUL}(c_{3})_{g}}{\longrightarrow}$
$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{h}\left\lvert j\right\rangle_{t_{1}}\left\lvert
jp_{i}\right\rangle_{t_{2}}\left\lvert jc_{3}\right\rangle_{g}$
$\displaystyle\overset{\mathcal{SUM}(c_{1})_{t_{1}}\mathcal{SUM}(c_{2})_{t_{2}}\mathcal{SUM}(c_{4})_{g}}{\longrightarrow}\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{h}$ $\displaystyle\left\lvert
j+c_{1}\right\rangle_{t_{1}}\left\lvert
jp_{i}+c_{2}\right\rangle_{t_{2}}\left\lvert jc_{3}+c_{4}\right\rangle_{g}.$
(10)

Now the particles $h,t_{1},t_{2},g$ are in an FE state. Alice then sends
$t_{1},t_{2},g$ to Bob.

  2. Step 2

(Entanglement Bondage) Bob selects $k_{1},k_{2},k_{3}\in\left[D\right]^{o}$
randomly, then does the following:

$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{h}\left\lvert j+c_{1}\right\rangle_{t_{1}}\left\lvert
jp_{i}+c_{2}\right\rangle_{t_{2}}\left\lvert jc_{3}+c_{4}\right\rangle_{g}$
$\displaystyle\overset{\mathcal{MUL}(k_{1})_{t_{1}}\mathcal{MUL}(k_{2})_{t_{2}}\mathcal{MUL}(k_{3})_{g}}{\longrightarrow}$
$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{h}\left\lvert
jk_{1}+c_{1}k_{1}\right\rangle_{t_{1}}\left\lvert
jp_{i}k_{2}+c_{2}k_{2}\right\rangle_{t_{2}}$ $\displaystyle\left\lvert
jc_{3}k_{3}+c_{4}k_{3}\right\rangle_{g}$
$\displaystyle\overset{\mathcal{BSUM}_{(t_{1},g)}\mathcal{BSUM}_{(t_{2},g)}}{\longrightarrow}$
$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{h}\left\lvert
jk_{1}+c_{1}k_{1}\right\rangle_{t_{1}}\left\lvert
jp_{i}k_{2}+c_{2}k_{2}\right\rangle_{t_{2}}$ $\displaystyle\left\lvert
j\left(k_{1}+p_{i}k_{2}+c_{3}k_{3}\right)+\left(c_{1}k_{1}+c_{2}k_{2}+c_{4}k_{3}\right)\right\rangle_{g}$
$\displaystyle=\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{h}\left\lvert
jk_{1}+c_{1}k_{1}\right\rangle_{t_{1}}\left\lvert
jp_{i}k_{2}+c_{2}k_{2}\right\rangle_{t_{2}}$ $\displaystyle\left\lvert
jr_{1}+r_{2}\right\rangle_{g}$
$\displaystyle\overset{\mathcal{MUL}(k_{1}^{-1})_{t_{1}}\mathcal{MUL}(k_{2}^{-1})_{t_{2}}}{\longrightarrow}\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{h}\left\lvert j+c_{1}\right\rangle_{t_{1}}$
$\displaystyle\left\lvert jp_{i}+c_{2}\right\rangle_{t_{2}}\left\lvert
jr_{1}+r_{2}\right\rangle_{g},$ (11)

where $r_{1}=k_{1}+p_{i}k_{2}+c_{3}k_{3}$,
$r_{2}=c_{1}k_{1}+c_{2}k_{2}+c_{4}k_{3}$.

  3. Step 3

(Bob’s Inputing) Bob does the following:

$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{h}\left\lvert j+c_{1}\right\rangle_{t_{1}}\left\lvert
jp_{i}+c_{2}\right\rangle_{t_{2}}\left\lvert jr_{1}+r_{2}\right\rangle_{g}$
$\displaystyle\overset{\mathcal{ROT}(s_{i})_{t_{1}}\mathcal{ROT}(q_{i})_{t_{2}}}{\longrightarrow}\frac{1}{\sqrt{D}}\omega^{(j+c_{1})s_{i}}\omega^{(jp_{i}+c_{2})q_{i}}$
$\displaystyle\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{h}\left\lvert j+c_{1}\right\rangle_{t_{1}}\left\lvert
jp_{i}+c_{2}\right\rangle_{t_{2}}\left\lvert jr_{1}+r_{2}\right\rangle_{g}$
$\displaystyle=\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{jM_{i}}\left\lvert
j\right\rangle_{h}\left\lvert j+c_{1}\right\rangle_{t_{1}}\left\lvert
jp_{i}+c_{2}\right\rangle_{t_{2}}$ $\displaystyle\left\lvert
jr_{1}+r_{2}\right\rangle_{g},$ (12)

where $M_{i}=s_{i}+p_{i}q_{i}$. We can omit the global phase
$\omega^{c_{1}s_{i}+c_{2}q_{i}}$.

  4. Step 4

(Alice’s Honesty Test) Bob now verifies Alice’s honesty as follows:

    1. a)

(Question) Bob tells Alice the values of $k_{1},k_{2},k_{3}$.

    2. b)

(Answer) Alice calculates $r_{3}=r_{1}^{-1}$ and $r_{4}=c_{1}-r_{2}r_{3}$,
then tells Bob the values of $r_{3},r_{4}$.

    3. c)

(Verification) Bob does the following:

$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{jM_{i}}\left\lvert
j\right\rangle_{h}\left\lvert j+c_{1}\right\rangle_{t_{1}}$
$\displaystyle\left\lvert jp_{i}+c_{2}\right\rangle_{t_{2}}\left\lvert
jr_{1}+r_{2}\right\rangle_{g}$
$\displaystyle\overset{\mathcal{MUL}(r_{3})_{g}}{\longrightarrow}\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{jM_{i}}\left\lvert
j\right\rangle_{h}\left\lvert j+c_{1}\right\rangle_{t_{1}}$
$\displaystyle\left\lvert jp_{i}+c_{2}\right\rangle_{t_{2}}\left\lvert
j+r_{2}r_{3}\right\rangle_{g}$
$\displaystyle\overset{\mathcal{SUM}(r_{4})_{g}}{\longrightarrow}\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{jM_{i}}\left\lvert
j\right\rangle_{h}\left\lvert j+c_{1}\right\rangle_{t_{1}}$
$\displaystyle\left\lvert jp_{i}+c_{2}\right\rangle_{t_{2}}\left\lvert
j+c_{1}\right\rangle_{g}$
$\displaystyle\overset{\mathcal{XOR}_{(t_{1},g)}}{\longrightarrow}\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{jM_{i}}\left\lvert
j\right\rangle_{h}\left\lvert j+c_{1}\right\rangle_{t_{1}}$
$\displaystyle\left\lvert jp_{i}+c_{2}\right\rangle_{t_{2}}\left\lvert
0\right\rangle_{g},$ (13)

and measures $g$. Alice passes only if he gets $\left\lvert
0\right\rangle_{g}$.

If the test is passed, then Bob returns $t_{1},t_{2}$ to Alice.

  5. Step 5

(Bob’s Honesty Test A) Alice now verifies Bob’s honesty as follows:

$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{jM_{i}}\left\lvert
j\right\rangle_{h}\left\lvert j+c_{1}\right\rangle_{t_{1}}\left\lvert
jp_{i}+c_{2}\right\rangle_{t_{2}}$
$\displaystyle\overset{\mathcal{SUM}(-c_{1})_{t_{1}}\mathcal{SUM}(-c_{2})_{t_{2}}}{\longrightarrow}$
$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{jM_{i}}\left\lvert
j\right\rangle_{h}\left\lvert j\right\rangle_{t_{1}}\left\lvert
jp_{i}\right\rangle_{t_{2}}$
$\displaystyle\overset{\mathcal{MUL}(p_{i}^{-1})_{t_{2}}}{\longrightarrow}\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{jM_{i}}\left\lvert
j\right\rangle_{h}\left\lvert j\right\rangle_{t_{1}}\left\lvert
j\right\rangle_{t_{2}}$
$\displaystyle\overset{\mathcal{XOR}_{(h,t_{1})}\mathcal{XOR}_{(h,t_{2})}}{\longrightarrow}\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{jM_{i}}\left\lvert
j\right\rangle_{h}$ $\displaystyle\left\lvert
0\right\rangle_{t_{1}}\left\lvert 0\right\rangle_{t_{2}},$ (14)

and measures $t_{1},t_{2}$. Bob passes the test only if Alice gets
$\left\lvert 0\right\rangle_{t_{1}}\left\lvert 0\right\rangle_{t_{2}}$.

  6. Step 6

(Alice’s Result) Alice preforms $\mathcal{QFT}^{\dagger}$ on $h$:

$\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{jM_{i}}\left\lvert
j\right\rangle_{h}\overset{\mathcal{QFT}^{\dagger}_{h}}{\longrightarrow}\left\lvert
M_{i}\right\rangle_{h}\ \mathrm{mod}\ D,$ (15)

and measures $h$ to obtain the result $M_{i}=s_{i}+p_{i}q_{i}$.

The quantum circuit of all the steps is shown in figure 1.

Figure 1: The quantum circuit of Operation stage.

3) Output Stage
Alice calculates as $Output=\frac{\sum^{n}_{i=1}\left(M_{i}-2x_{i}\right)\
\mathrm{mod}\ D}{4}$.

##  IV Protocol Analysis

###  IV-A Correctness

$\displaystyle Output=\frac{\sum^{n}_{i=1}\left(M_{i}-2x_{i}\right)\
\mathrm{mod}\ D}{4}$
$\displaystyle=\frac{\sum^{n}_{i=1}\left(s_{i}+p_{i}q_{i}-2x_{i}\right)\
\mathrm{mod}\ D}{4}$
$\displaystyle=\frac{\sum^{n}_{i=1}\left(4v_{i}+4x_{i}y_{i}\right)\
\mathrm{mod}\ D}{4}$
$\displaystyle=\frac{4\sum^{n}_{i=1}v_{i}+4\sum^{n}_{i=1}x_{i}y_{i}\
\mathrm{mod}\ D}{4}$ $\displaystyle=\frac{4v+4\sum^{n}_{i=1}x_{i}y_{i}\
\mathrm{mod}\ D}{4}=\frac{4(v+\sum^{n}_{i=1}x_{i}y_{i})-a2^{d}}{4}$
$\displaystyle=\frac{4(v+\sum^{n}_{i=1}x_{i}y_{i}-a2^{m})}{4}=v+\sum^{n}_{i=1}x_{i}y_{i}-a2^{m},$
(16)

where $4(v+\sum^{n}_{i=1}x_{i}y_{i})-a2^{d}\in\left[D\right]$ and $d=m+2$,
thus
$v+\sum^{n}_{i=1}x_{i}y_{i}-a2^{m}\in\left[\frac{D}{4}\right]=\left[N\right]$.
I.e.,

$\displaystyle Output=v+\sum^{n}_{i=1}x_{i}y_{i}-a2^{m}$
$\displaystyle=v+\sum^{n}_{i=1}x_{i}y_{i}\ \mathrm{mod}\ D=u.$ (17)

###  IV-B Security

Since all the interactions occur in Operation stage, an attacker may try the
following possible attacks.

1) Measurement Attack

Measurement attack is to directly perform a local general measurement on the
attacker’s own particles. “General quantum measurement” is equivalent to a
combination of introducing auxiliary systems, performing unitary operations
and projective measurements[42].

2) Entangle-measure Attack

After receiving a particle $t$, the attacker can prepare an auxiliary particle
$e$ and perform a unitary operation

$\mathcal{U}_{\varepsilon}:\left\lvert j\right\rangle_{t}\left\lvert
0\right\rangle_{e}\rightarrow\sqrt{\eta_{j}}\left\lvert
j\right\rangle_{t}\left\lvert\varepsilon(j)\right\rangle_{e}+\sqrt{1-\eta_{j}}\left\lvert
V(j)\right\rangle_{(t,e)},$ (18)

where $\eta$ is the probability that $\left\lvert j\right\rangle_{t}$ is not
changed. Then he sends $t$ back, and monitors its movement by measuring $e$.

3) Forgery Attack

Forgery attack is to send a particle in a forged rather than correct state to
steal information, as a type of malicious attack.

4) Intercept-Resend Attack

Similar to forgery attack, intercept-resend attack means to obtain information
from a particle after receiving it, and then return a forged particle back.

5) False Verification Information Attack

This attack may occur in Step 4 of Operation stage, which means to send fake
verification information, such as $k_{1},k_{2},k_{3}$ and $r_{3},r_{4}$.

6) External Attack

External attack means that any eavesdropper Eve wants to steal Alice or Bob’s
privacy.

7) Semi-honest attack

If the attacker is semi-honest, it may try to deduce information other than
the expected result it should get, from all the values it can obtain during
the protocol.

We has the following theorem.

######  Theorem 1.

Protocol 1 holds unconditional security under the malicious model, i.e., it
can resist the above attacks.

Proof:

1) Measurement Attack

First, we give the following Lemma 1. It is proved in Appendix A-A, relying on
the use of partial trace $tr_{P}(\cdot)$.

######  Lemma 1 (Security of Phase-information).

Under the entanglement of an FE state as Definition 1, any attacker who only
owns local system $Q$ cannot extract the phase-information.

$\bullet$ Alice’s Privacy: Denote $X_{A}=x_{i}$. To steal the largest
information, Bob can wait for $r_{3},r_{4}$, then measure $t_{1},t_{2},g$. For
the leakage degree of Alice’s privacy $I_{A}=H(Z_{B}:X_{A})$, we have the
following Lemma 2. Its proof relies on the Holevo bound[44], see Appendix A-B
for details.

######  Lemma 2 (Security of Bit-information).

Under the measurement attack, $I_{A}=0$, i.e., Bob cannot obtain any valid
information about $X_{A}$. Besides, this effect cannot be achieved without
particle $g$.

$\bullet$ Bob’s Privacy: Denote $X_{B}=(y_{i},v_{i})$. Until Step 5, Bob owns
a local system $(t_{1},t_{2},g)$ of the FE state. By Lemma 1, Alice cannot
obtain any information about $q_{i},s_{i}$, because they are all on the phase.
I.e., The leakage degree of Bob’s privacy $I_{A}=H(Z_{A}:X_{B})=0$.

2) Entangle-measure Attack

$\bullet$ Alice’s Privacy: Denote $X_{A}=x_{i}$. After Bob resent, it is
possible to obtain information by measuring only in Step 6, since only now
Alice carries on operations. Because Alice performs an honest test on the sent
particles $t_{1},t_{2}$ in Step 5, if they are no longer in their original
states, the attack will be detected. Therefore, $\eta_{j}$ should be set to
$1$, i.e., $\mathcal{U}_{\varepsilon}:\left\lvert
j\right\rangle_{t}\left\lvert 0\right\rangle_{e}\rightarrow\left\lvert
j\right\rangle_{t}\left\lvert\varepsilon(j)\right\rangle_{e}$.

Assume that Bob owns all particles $t_{1},t_{2},g,e$ to steal the largest
information, and performs $\mathcal{U}_{\varepsilon}$. Note that the Holevo
bound of Bob’s particle now equals to that in measurement attack, i.e.,
$H(Z_{B}:X_{A})=0$ (see the proof of Lemma 2), because
$\mathcal{U}_{\varepsilon}$ is a local quantum operation and does not increase
the Holevo bound (Chapter 12 Problem 12.1 of Ref. [42]). If he returns any
particle, he cannot steal more, since discarding quantum systems is also a
kind of quantum operations and does not increase the Holevo bound. Alice’s any
operations in Step 6 are equivalent to local quantum measurement, which
doesn’t affect Bob’s measurement results by the principle of implicit
measurement (Chapter 4.4 of Ref. [42]). Therefore, it also does not increase
the Holevo bound of Bob’s particles. In this way, we can immediately deduce
that $I_{A}=0$, consistent with the measurement attack.

$\bullet$ Bob’s Privacy: Alice cannot perform entangle-measure attacks, since
she may only send particles once.

3) Forgery Attack

$\bullet$ Alice’s Privacy: Since Alice won’t return the particles sent by Bob,
Bob cannot perform forgery attacks.

$\bullet$ Bob’s Privacy: Denote $X_{B}=(y_{i},v_{i})$. Since Bob’s information
only exists on the phase domain, the only known way to obtain it is to use
$\mathcal{QFT}^{\dagger}$. By Lemma 1, it is impossible to obtain phase-
information under entanglement, then particles $t_{1},t_{2}$ must be non-
entangled. Accordingly, we have the following Lemma 3. We prove it by using
the Holevo bound[44] in Appendix A-C.

######  Lemma 3 (Security under Forgery Attack).

Due to the entanglement bondage in Step 2 and the test in Step 4, the leakage
degree of Bob’s privacy under the forgery attack is
$I_{B}<\frac{d^{2}+d-2}{2\cdot 2^{d}}=O\left(\frac{d^{2}}{2^{d}}\right)$, with
an asymptotic coefficient $\frac{1}{2}$.

$I_{B}$ is negligible, since $2^{d}$ is exponential level. When $d$ reaches
its minimum value, i.e., $d=1+2=3$, then $\frac{d^{2}+d-2}{2\cdot
2^{d}}=\frac{5}{8}$. This bound will soon approach 0 as $d$ increases.

4) Intercept-Resend Attack

$\bullet$ Alice’s Privacy: If Bob sends any forged particle back in Step 4,
then as in the measurement attack, the leakage degree of Alice’s privacy
$I_{A}=0$.

$\bullet$ Bob’s Privacy: Similar to forgery attacks, it is impossible for
Alice to perform this attack.

5) False Verification Information Attack

$\bullet$ Alice’s Privacy: If Bob did not send the correct
$k_{1},k_{2},k_{3}$, we have $I_{A}=0$, just like the measurement attack.

$\bullet$ Bob’s Privacy: Similarly, if Alice sends incorrect $r_{3},r_{4}$,
then $I_{B}=0$, and Bob can detect it in Step 4 c).

6) External Attack

According to the analysis above, if Eve intercepts the particles sent by Alice
to Bob, obviously she will get nothing. Similarly, if she intercepts the
particles returned by Bob to Alice, she cannot get Bob’s privacy.

7) Semi-honest Attack

$\bullet$ Alice’s Privacy: If Bob is semi-honest, then all he can learn are
$r_{3},r_{4}$. He won’t obtain any information, as well as in the measurement
attack.

$\bullet$ Bob’s Privacy: Denote $X_{B}=(\mathbf{y},v)$. If Alice is semi-
honest, all she can learn are $M_{i}\equiv p_{i}q_{i}+s_{i}\equiv
4x_{i}y_{i}+4v_{i}(\ \mathrm{mod}\ D)$. She may try to learn any information
other than $u=\sum_{i=1}^{n}{x_{i}y_{i}}+v\ \mathrm{mod}\ N$. We have the
following Lemma 4, and prove it in Appendix A-D, by directly calculate the
Shannon entropy.

######  Lemma 4 (Security under Semi-honest Attack).

Even if Alice knows all $M_{i}$, the leakage degree of Bob’s privacy
$I_{B}=0$.

In total, Protocol 1 has unconditional security under the malicious model.∎

###  IV-C Performance

We take the basic 1-, 2- and 3-qubit quantum gates as the measurement unit of
computational complexity, such as Hadamard Gate $\mathcal{H}:\left\lvert
a\right\rangle\rightarrow\frac{\left\lvert 0\right\rangle+(-1)^{a}\left\lvert
1\right\rangle}{\sqrt{2}}$, Controlled-X Gate $\mathcal{CNOT}:\left\lvert
a\right\rangle\left\lvert b\right\rangle\rightarrow\left\lvert
a\right\rangle\left\lvert b\oplus a\right\rangle$, Z-axis Rotation Gate
$\mathcal{P}(i):\left\lvert a\right\rangle\rightarrow e^{\frac{\imath 2\pi
2^{i}}{D}a}\left\lvert a\right\rangle$ ($i\in\left[d\right]$), it’s controlled
version $\mathcal{CP}(i):\left\lvert a\right\rangle\left\lvert
b\right\rangle\rightarrow e^{\frac{\imath 2\pi 2^{i}}{D}ab}\left\lvert
a\right\rangle\left\lvert b\right\rangle$, and Toffoli Gate
$\mathcal{T}:\left\lvert a\right\rangle\left\lvert b\right\rangle\left\lvert
c\right\rangle\rightarrow\left\lvert a\right\rangle\left\lvert
b\right\rangle\left\lvert c\oplus a\cdot b\right\rangle$, etc.

In general, the complexity of the gates in Section II-B are all below
$O(d^{2})$ (see Appendix B-A for details). Since $d=O(m)$, the total
complexity of Protocol 1 is $O(nm^{2})$. Since there are only 4 $d$-qubit
particles are sent for each $i=1,2,\cdots,n$, the communication complexity is
$O(nm)$.

We use $m,n$ to represent the bit number and dimension of input vectors
respectively. See Table II for the comparison between our protocol and the
previous. In Ref. [28], $O\left(4^{m}n\log^{2}n\right)$ entanglements should
have been prepared and sent. In Ref. [29], for real vectors $\mathbf{x}$,
$\mathbf{y}$, $\left\langle\mathbf{x}\lvert\mathbf{y}\right\rangle$ was
evaluated with accuracy $\epsilon$. Its computational and communication
complexity are $O(n\epsilon^{-2})$ and $O(2\epsilon^{-2}+n^{2})$ respectively.
Let $\left\lvert\mathbf{x}\right\lvert$,
$\left\lvert\mathbf{y}\right\lvert=\Theta\left(2^{m}\right)$, then
$\epsilon=\Theta(2^{-2m})$ is needed for the error of
$\mathbf{x}\cdot\mathbf{y}$ to be less than $1$. Grover’s algorithm was used
in Ref. [30], with complexity $O\left(\sqrt{2^{m}}\right)$. It can be seen
that our protocol is polynomial in terms of computational and communication
complexity, while the previous protocols have at least one complexity close to
exponential. In addition, our protocol does not require a third party. The
above proves its advantages.

TABLE II: Performance Comparison Protocols | Third | Quantum | Computational | Communication
---|---|---|---|---
Party | Resource | Complexity | Complexity
He[28] | $\checkmark$ | Qubit | $O\left(4^{m}n\log^{2}n\right)$ | $O\left(4^{m}n\log^{2}n\right)$
Wang[29] | $\times$ | Qumode | $O\left(n2^{4m}\right)$ | $O\left(2^{4m}\right)$
Shi[30] | $\times$ | Qubit | $O\left(\sqrt{2^{m}}\right)$ | $O\left(m\right)$
Our | $\times$ | Qubit | $O\left(nm^{2}\right)$ | $O\left(nm\right)$

###  IV-D Experiment

We verify the correctness and the feasibility of our protocol by circuit
simulation experiments in IBM Qiskit simulator (Qiskit-0.41.0; Python-3.7; OS-
Windows). Without loss of generality, let’s set $m=2$ (i.e., $d=4$). The
circuits of all quantum gates we used are described in figure 2. Because the
complexity of classical simulation is sensitive to qubits’ number, we use
Draper’s adder[41], as shown in figure 2c and 2e. It requires no auxiliary
qubits, but has higher complexity $O(d^{2})$. Besides, we design a special
circuit for module multiplication on $\left[D\right]$ as shown in figure 2d to
further reduce qubits. See Appendix B-B for details of this design. Finally,
we omit the measurement of particles $t_{1},t_{2},g$ and only focus on the
output results on particle $h$. The total circuit of Protocol 1 is shown in
figure 3. We execute the experiment two times. Table III shows the first input
and output, with the selection of the intermediate parameters
$v_{i},c_{1},c_{2},c_{3},c_{4},k_{1},k_{2},k_{3}$. Similarly, table IV
describe the second experiment. Each quantum program for $i=1,2,3,4$ is
executed 1000 times, and figure 4 shows the results. It can be seen that our
protocol can be run successfully with 100% probability, so it is correct and
feasible.

(a)

(b)

(c)

(d)

(e)

(f)

Figure 2: The circuits of quantum gates. a), b), c), d), e), f) are circuits of $\mathcal{QFT}$, $\mathcal{ROT}$, $\mathcal{SUM}$, $\mathcal{MUL}$, $\mathcal{BSUM}$, $\mathcal{XOR}$, respectively. Figure 3: The total circuit of our protocol. TABLE III: Parameter of the First Experiment External Parameter | Input | Intermediate Parameter | Output
---|---|---|---
$m$ | $N$ | $i$ | $x_{i}$ | $y_{i}$ | $v$ | $d$ | $D$ | $v_{i}$ | $p_{i}$ | $q_{i}$ | $s_{i}$ | $c_{1}$ | $c_{2}$ | $c_{3}$ | $c_{4}$ | $k_{1}$ | $k_{2}$ | $k_{3}$ | $r_{1}$ | $r_{2}$ | $r_{3}$ | $r_{4}$ | $M_{i}$ | $u$
2 | 4 | 1 | 1 | 0 | 1 | 4 | 16 | 0 | 3 | 1 | 15 | 2 | 15 | 9 | 12 | 5 | 9 | 5 | 13 | 13 | 5 | 1 | 2 | 0
2 | 0 | 3 | 11 | 1 | 7 | 5 | 10 | 6 | 11 | 3 | 15 | 5 | 7 | 1 | 9 | 1 | 1 | 12
3 | 1 | 1 | 15 | 3 | 3 | 9 | 10 | 11 | 3 | 2 | 1 | 1 | 1 | 7 | 7 | 7 | 9 | 2
4 | 2 | 3 | 13 | 5 | 7 | 5 | 4 | 9 | 1 | 6 | 7 | 9 | 15 | 3 | 7 | 11 | 7 | 8
TABLE IV: Parameter of the Second Experiment External Parameter | Input | Intermediate Parameter | Output
---|---|---|---
$m$ | $N$ | $i$ | $x_{i}$ | $y_{i}$ | $v$ | $d$ | $D$ | $v_{i}$ | $p_{i}$ | $q_{i}$ | $s_{i}$ | $c_{1}$ | $c_{2}$ | $c_{3}$ | $c_{4}$ | $k_{1}$ | $k_{2}$ | $k_{3}$ | $r_{1}$ | $r_{2}$ | $r_{3}$ | $r_{4}$ | $M_{i}$ | $u$
2 | 4 | 1 | 2 | 3 | 3 | 4 | 16 | 14 | 5 | 7 | 1 | 7 | 3 | 5 | 1 | 1 | 7 | 5 | 13 | 1 | 5 | 2 | 4 | 2
2 | 3 | 1 | 10 | 7 | 3 | 5 | 1 | 14 | 5 | 11 | 5 | 11 | 7 | 5 | 12 | 13 | 5 | 10
3 | 1 | 2 | 15 | 3 | 5 | 7 | 14 | 12 | 1 | 9 | 1 | 3 | 3 | 13 | 13 | 5 | 13 | 6
4 | 0 | 1 | 0 | 1 | 3 | 13 | 4 | 1 | 1 | 1 | 13 | 3 | 15 | 15 | 6 | 15 | 10 | 0

(a)

(b)

(c)

(d)

(e)

(f)

(g)

(h)

Figure 4: a), b), c), d) are the results $M_{i}$ for $i=1,2,3,4$ of the first
experiment, respectively. Similarly, e), f), g), h) are the results of the
second experiment.

##  V Application

In this section, we present an application of Protocol 1, i.e., a Privacy-
preserving Two-party Matrix Multiplication (P2MM) protocol. This problem has
been extensively studied in classical SMC. The complex matrix computation is
mainly realized by generating product triples, among which cryptographic
techniques such as oblivious transfer[45, 46], homomorphic encryption[47, 48,
49] and so on are widely used. We point out that since we have implemented a
highly efficient two-party scalar product protocol, we no longer need to
perform these computationally expensive processes. To our knowledge, this is
the first quantum solution to solve this problem.

###  V-A Proposed P2MM Protocol

Firstly, we provide a precise definition of the problem.

######  Definition 7 (Privacy-preserving Two-party Matrix Multiplication
(P2MM)).

Alice and Bob have two $k\times n$ matrix

$\displaystyle\mathbf{A}=\left(a_{ij}\right)_{k\times
n}=\begin{pmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\\
a_{21}&a_{22}&\cdots&\vdots\\\ \vdots&\vdots&\ddots&\vdots\\\
a_{k1}&a_{k2}&\cdots&a_{kn}\end{pmatrix}$ (19)

and $\mathbf{B}=\left(b_{ij}\right)_{k\times n}$, respectively, where
$a_{ij},b_{ij}\in\left[N\right]$, $N=2^{m}$. Alice is to get
$\mathbf{U}=\mathbf{A}\cdot\mathbf{B}+\mathbf{V}$, while
$\mathbf{V}=\left(v_{ij}\right)_{k\times n},v_{ij}\in\left[N\right]$ is a
random matrix known only by Bob. Neither Alice nor Bob can get more
information. Here we omit “$\ \mathrm{mod}\ N$”.

The main scheme for calculating the matrix product of two participants is as
follows: By using the formula of matrix multiplication, the calculation of
$k\times n$ matrices is transformed into $kn$ times vector scalar product
process, which are solved using our proposed S2QSP protocol.

######  Protocol 2.

Privacy-preserving Two-party Quantum Matrix Multiplication Protocol (P2QMMP).

For each $1\leq i\leq k,1\leq j\leq n$, Alice and Bob do the following steps:

  1. Step 1

Alice separately extracts the $i$-th $n$-dimensional row vector of matrix
$\mathbf{A}$, i.e.,

$\displaystyle\mathbf{x}_{i}=\left(a_{i1},a_{i2},\cdots,a_{in}\right),$ (20)

as her input vector.

  2. Step 2

Similarly, Bob separately extracts the $j$-th $n$-dimensional column vector of
matrix $\mathbf{B}$, i.e.,

$\displaystyle\mathbf{y}_{j}=\left(b_{1j},b_{2j},\cdots,b_{nj}\right).$ (21)

Then he takes out the element $v_{ij}$ in the $i$-th row and $j$-column of
matrix $\mathbf{V}$. The vector $\mathbf{y}_{j}$ and integer $v_{ij}$ are his
inputs.

  3. Step 3

Now the two vectors $\mathbf{x}_{i}$, $\mathbf{y}_{j}$, and the random integer
$v_{ij}$ are valid inputs of Protocol 1. Alice and Bob execute Protocol 1,
where parameter $N$, $m$ and $n$ are all set to the same as here.

  4. Step 4

After all the steps of Protocol 1 are completed, Alice can obtain a
corresponding result

$\displaystyle Output_{ij}=\mathbf{x}_{i}\cdot\mathbf{y}_{j}+v_{ij}.$ (22)

After executing $m\times n$ times the above steps, Alice now has $m\times n$
integers $Output_{ij}$, for $1\leq i\leq k,1\leq j\leq n$. She now assembles
the result matrix by these integers as

$\displaystyle Output=(Output_{ij})_{k\times n}.$ (23)

###  V-B Protocol Analysis

1) Correctness

$\displaystyle
Output=\begin{pmatrix}\mathbf{x}_{1}\cdot\mathbf{y}_{1}+v_{11}&\cdots&\mathbf{x}_{1}\cdot\mathbf{y}_{n}+v_{1n}\\\
\mathbf{x}_{2}\cdot\mathbf{y}_{1}+v_{21}&\cdots&\vdots\\\
\vdots&\ddots&\vdots\\\
\mathbf{x}_{k}\cdot\mathbf{y}_{1}+v_{k1}&\cdots&\mathbf{x}_{k}\cdot\mathbf{y}_{n}+v_{kn}\end{pmatrix}$
$\displaystyle=\begin{pmatrix}\mathbf{x}_{1}\cdot\mathbf{y}_{1}&\mathbf{x}_{1}\cdot\mathbf{y}_{2}&\cdots&\mathbf{x}_{1}\cdot\mathbf{y}_{n}\\\
\mathbf{x}_{2}\cdot\mathbf{y}_{1}&\mathbf{x}_{2}\cdot\mathbf{y}_{2}&\cdots&\vdots\\\
\vdots&\vdots&\ddots&\vdots\\\
\mathbf{x}_{k}\cdot\mathbf{y}_{1}&\mathbf{x}_{k}\cdot\mathbf{y}_{2}&\cdots&\mathbf{x}_{k}\cdot\mathbf{y}_{n}\end{pmatrix}+\mathbf{V}$
$\displaystyle=\begin{pmatrix}\sum_{i=1}^{n}{a_{1i}b_{i1}}&\sum_{i=1}^{n}{a_{1i}b_{i2}}&\cdots&\sum_{i=1}^{n}{a_{1i}b_{in}}\\\
\sum_{i=1}^{n}{a_{2i}b_{i1}}&\sum_{i=1}^{n}{a_{2i}b_{i2}}&\cdots&\vdots\\\
\vdots&\vdots&\ddots&\vdots\\\
\sum_{i=1}^{n}{a_{ki}b_{i1}}&\sum_{i=1}^{n}{a_{ki}b_{i2}}&\cdots&\sum_{i=1}^{n}{a_{ki}b_{in}}\end{pmatrix}+\mathbf{V}$
$\displaystyle=\begin{pmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\\
a_{21}&a_{22}&\cdots&\vdots\\\ \vdots&\vdots&\ddots&\vdots\\\
a_{k1}&a_{k2}&\cdots&a_{kn}\end{pmatrix}\cdot\begin{pmatrix}b_{11}&b_{12}&\cdots&b_{1n}\\\
b_{21}&b_{22}&\cdots&\vdots\\\ \vdots&\vdots&\ddots&\vdots\\\
b_{k1}&b_{k2}&\cdots&b_{kn}\end{pmatrix}$
$\displaystyle+\mathbf{V}=\mathbf{A}\cdot\mathbf{B}+\mathbf{V}.$ (24)

2) Security

######  Theorem 2.

Protocol 2 has unconditional security under the malicious model.

Proof: For each $1\leq i\leq k$, $1\leq j\leq n$, Alice and Bob execute one
time Protocol 1, and then Alice gets
$Output_{ij}=\mathbf{x}_{i}\cdot\mathbf{y}_{j}+v_{ij}$, Bob only gets
$v_{ij}$. Since Protocol 1 is secure enough with high probability (see Section
IV-B), the result Alice can only obtain is $Output_{ij}$. Since $Output_{ij}$
is part of the result matrix $\mathbf{U}$, i.e. it can be regressed from
$\mathbf{U}$, it does not provide any information beyond what Alice deserves.
Similarly, Bob is unable to receive any improper benefits. Therefore, Protocol
2 is at least as secure as Protocol 1. ∎

3) Performance

Obviously, the computational and communication complexity of Protocol 2 are
$O(kn\cdot nm^{2})=O(kn^{2}m^{2})$ and $O(kn\cdot nm)=O(kmn^{2})$, since
Protocol 1 is executed $kn$ times.

##  VI Conclusion

In this paper, we propose a secure and efficient two-party quantum scalar
product protocol, where several special properties of Fourier entangled states
are used for calculation and security. Our protocol does not require any third
parties, and has unconditional security under the malicious adversary model.
It has polynomial level computational and communication complexity, which is
the most efficient than the state-of-the-art protocols. Furthermore, based on
the proposed S2QSP protocol, we present a privacy-preserving matrix
multiplication protocol as its extended application.

However, because our protocol involves high-dimensional entangled states, it
will be relatively fragile under noise. The transmission error may be reduced
by high-dimensional error correction code. Besides, there is a future research
direction on how to extend the protocol to multi-party scenario, which can
achieve a wider application.

## Declarations

  * •

Conflict of interest The authors declare that they have no conflict of
interest.

  * •

Ethical statement Articles do not rely on clinical trials.

  * •

Data availability Data sharing does not applicable to this article as no
datasets were generated or analysed during the current study.

##  Appendix A Proof of Lemmas

###  A-A Proof of Lemma 1

Let’s assume that there is an attacker who dose not know the values of $X,C$.
He may perform any type of measurement on local system $Q$ to obtain a measure
result $Z$. First, we calculate the global density operator as

$\displaystyle\rho^{(P,Q)}_{xc}=\left\lvert\psi(x,c)\right\rangle\left\langle\psi(x,c)\right\lvert_{(P,Q)}$
$\displaystyle=\frac{1}{D}\sum_{j^{\prime},j\in\left[D\right]}\omega^{(j^{\prime}-j)h(x,c)}\left\lvert
f(j^{\prime},x,c)\right\rangle\left\langle f(j,x,c)\right\lvert_{A}$
$\displaystyle\left\lvert g(j^{\prime},x,c)\right\rangle\left\langle
g(j,x,c)\right\lvert_{Q}.$ (25)

Remember $\left\langle f(j^{\prime},x,c)\lvert
f(j,x,c)\right\rangle=\delta_{j^{\prime}j}$. Then

$\displaystyle\rho^{Q}_{xc}=tr_{P}\left(\rho^{(P,Q)}_{xc}\right)$
$\displaystyle=\frac{1}{D}\sum_{j^{\prime},j\in\left[D\right]}\omega^{(j^{\prime}-j)h(x,c)}tr\left(\left\lvert
f(j^{\prime},x,c)\right\rangle\left\langle f(j,x,c)\right\lvert_{P}\right)$
$\displaystyle\left\lvert g(j^{\prime},x,c)\right\rangle\left\langle
g(j,x,c)\right\lvert_{Q}$
$\displaystyle=\frac{1}{D}\sum_{j^{\prime},j\in\left[D\right]}\omega^{(j^{\prime}-j)h(x,c)}\delta_{j^{\prime}j}\left\lvert
g(j^{\prime},x,c)\right\rangle\left\langle g(j,x,c)\right\lvert_{Q}$
$\displaystyle=\frac{1}{D}\sum_{j\in\left[D\right]}\left\lvert
g(j,x,c)\right\rangle\left\langle g(j,x,c)\right\lvert_{Q}.$ (26)

In this formula functions $h(x,c),f(j,x,c)$ disappear. Thus the attacker
cannot obtain any phase-information.∎

###  A-B Proof of Lemma 2

We first deduce a general upper bound of information disclosure. Follow
Definition 1 and Lemma 1, then we have

######  Proposition 1 (Upper Bound of Information Disclosure).

Under the attack described in Section A-A,

$\displaystyle H(Z$ $\displaystyle:X)\leq\log_{2}{\left\lvert
S_{X}\right\lvert}-$
$\displaystyle\frac{\sum_{b\in\left[L\right]}\beta_{b}\log_{2}{\beta_{b}}-\left\lvert
S_{X}\right\lvert\sum_{b\in\left[L\right]}\alpha_{bx}\log_{2}{\alpha_{bx}}}{D\left\lvert
S_{X}\right\lvert\left\lvert S_{C}\right\lvert},$ (27)

where $\alpha_{bx}=\left\lvert
g_{x}^{-1}(b)\right\lvert=\left\lvert\left\\{(j,c)\lvert
g(j,x,c)=b\right\\}\right\lvert$ and $\beta_{b}=\left\lvert
g^{-1}(b)\right\lvert=\left\lvert\left\\{(j,x,c)\lvert
g(j,x,c)=b\right\\}\right\lvert$.

Proof: As is deduced in Section A-A,

$\rho^{Q}_{xc}=\frac{1}{D}\sum_{j\in\left[D\right]}\left\lvert
g(j,x,c)\right\rangle\left\langle g(j,x,c)\right\lvert_{Q}.$ (28)

Remember $p_{x}=\frac{1}{\left\lvert S_{X}\right\lvert}$,
$p_{c}=\frac{1}{\left\lvert S_{C}\right\lvert}$. Then

$\displaystyle\rho^{Q}_{x}=\sum_{c\in S_{C}}\frac{1}{\left\lvert
S_{C}\right\lvert}\rho^{Q}_{xc}$ $\displaystyle=\frac{1}{\left\lvert
S_{C}\right\lvert}\sum_{c\in
S_{C}}\frac{1}{D}\sum_{j\in\left[D\right]}\left\lvert
g(j,x,c)\right\rangle\left\langle g(j,x,c)\right\lvert_{Q}$
$\displaystyle=\frac{1}{D\left\lvert
S_{C}\right\lvert}\sum_{b\in\left[L\right]}\sum_{g(j,x,c)=b}\left\lvert
b\right\rangle\left\langle b\right\lvert_{Q}$
$\displaystyle=\frac{1}{D\left\lvert
S_{C}\right\lvert}\sum_{b\in\left[L\right]}\alpha_{bx}\left\lvert
b\right\rangle\left\langle b\right\lvert_{Q}.$ (29)

Remember that $g:\left[D\right]\times S_{X}\times S_{C}\to\left[L\right]$.
Then we can get its Von Neumann entropy

$\displaystyle
S\left(\rho^{Q}_{x}\right)=-\sum_{b\in\left[L\right]}\frac{\alpha_{bx}}{D\left\lvert
S_{C}\right\lvert}\log_{2}\frac{\alpha_{bx}}{D\left\lvert S_{C}\right\lvert}$
$\displaystyle=\sum_{b\in\left[L\right]}\frac{\alpha_{bx}}{D\left\lvert
S_{C}\right\lvert}\left(\log_{2}\left(D\left\lvert
S_{C}\right\lvert\right)-\log_{2}\alpha_{bx}\right)$
$\displaystyle=\frac{\sum_{b\in\left[L\right]}\alpha_{bx}}{D\left\lvert
S_{C}\right\lvert}\log_{2}\left(D\left\lvert
S_{C}\right\lvert\right)-\frac{1}{D\left\lvert
S_{C}\right\lvert}\sum_{b\in\left[L\right]}\alpha_{bx}\log_{2}\alpha_{bx}$
$\displaystyle=\log_{2}\left(D\left\lvert
S_{C}\right\lvert\right)-\frac{1}{D\left\lvert
S_{C}\right\lvert}\sum_{b\in\left[L\right]}\alpha_{bx}\log_{2}\alpha_{bx},$
(30)

where $\sum_{b\in\left[L\right]}\alpha_{bx}=\left\lvert\left[D\right]\times
S_{C}\right\lvert=D\left\lvert S_{C}\right\lvert$. Now

$\displaystyle\rho^{Q}=\sum_{x\in S_{X}}\frac{1}{\left\lvert
S_{X}\right\lvert}\rho^{Q}_{x}$ $\displaystyle=\frac{1}{\left\lvert
S_{X}\right\lvert}\sum_{x\in S_{X}}\frac{1}{\left\lvert
S_{C}\right\lvert}\sum_{c\in
S_{C}}\frac{1}{D}\sum_{j\in\left[D\right]}\left\lvert
g(j,x,c)\right\rangle\left\langle g(j,x,c)\right\lvert_{Q}$
$\displaystyle=\frac{1}{D\left\lvert S_{X}\right\lvert\left\lvert
S_{C}\right\lvert}\sum_{b\in\left[L\right]}\beta_{b}\left\lvert
b\right\rangle\left\langle b\right\lvert_{Q}.$ (31)

Similar, its entropy is

$\displaystyle
S\left(\rho^{B}\right)=-\sum_{b\in\left[L\right]}\frac{\beta_{b}}{D\left\lvert
S_{X}\right\lvert\left\lvert
S_{C}\right\lvert}\log_{2}\frac{\beta_{b}}{D\left\lvert
S_{X}\right\lvert\left\lvert S_{C}\right\lvert}$
$\displaystyle=\log_{2}\left(D\left\lvert S_{X}\right\lvert\left\lvert
S_{C}\right\lvert\right)-\frac{1}{D\left\lvert S_{X}\right\lvert\left\lvert
S_{C}\right\lvert}\sum_{b\in\left[L\right]}\beta_{b}\log_{2}\alpha_{b},$ (32)

where $\sum_{b\in\left[L\right]}\beta_{b}=\left\lvert\left[D\right]\times
S_{X}\times S_{C}\right\lvert=D\left\lvert S_{X}\right\lvert\left\lvert
S_{C}\right\lvert$. Now

$\displaystyle H(Z:X)\leq S\left(\rho^{B}\right)-\sum_{x\in
S_{X}}p_{x}S\left(\rho^{B}_{x}\right)$
$\displaystyle=\log_{2}\left(D\left\lvert S_{X}\right\lvert\left\lvert
S_{C}\right\lvert\right)-\frac{1}{D\left\lvert S_{X}\right\lvert\left\lvert
S_{C}\right\lvert}\sum_{b\in\left[L\right]}\beta_{b}\log_{2}\alpha_{b}-$
$\displaystyle\ \left\lvert S_{X}\right\lvert\frac{1}{\left\lvert
S_{X}\right\lvert}\left(\log_{2}\left(D\left\lvert
S_{C}\right\lvert\right)-\frac{1}{D\left\lvert
S_{C}\right\lvert}\sum_{b\in\left[L\right]}\alpha_{bx}\log_{2}\alpha_{bx}\right)$
$\displaystyle=\log_{2}{\left\lvert S_{X}\right\lvert}-$ $\displaystyle\ \ \
\frac{\sum_{b\in\left[L\right]}\beta_{b}\log_{2}{\beta_{b}}-\left\lvert
S_{X}\right\lvert\sum_{b\in\left[L\right]}\alpha_{bx}\log_{2}{\alpha_{bx}}}{D\left\lvert
S_{X}\right\lvert\left\lvert S_{C}\right\lvert}.$ (33)

By the Holevo bound[44]. ∎

Now we can prove Lemma 2.

Proof of Lemma 2:  For convenience, we take the classical information
$r_{3}=r_{1}^{-1}$, $r_{4}=c_{1}-r_{2}r_{3}$ as quantum information
$\left\lvert r_{3}\right\rangle_{e_{1}}\left\lvert
r_{4}\right\rangle_{e_{2}}$. Denote $\mathbf{c}=(c_{1},c_{2},c_{3},c_{4})$.
Now Bob owns system $Q=(t_{1},t_{2},g,e_{1},e_{2})$, and we have a function

$g_{B}(j,x_{i},\mathbf{c})=j+c_{1}\parallel jp_{i}+c_{2}\parallel
jc_{3}+c_{4}\parallel r_{1}^{-1}\parallel c_{1}-r_{2}r_{3},$ (34)

and its value $b=b_{1}\parallel b_{2}\parallel b_{3}\parallel r_{3}\parallel
r_{4}$, i.e.,

$\left\\{\begin{matrix}j+c_{1}=b_{1}\\\ jp_{i}+c_{2}=b_{2}\\\
jc_{3}+c_{4}=b_{3}\\\ \left(k_{1}+p_{i}k_{2}+c_{3}k_{3}\right)^{-1}=r_{3}\\\
c_{1}-\left(k_{1}c_{1}+k_{2}c_{2}+k_{3}c_{4}\right)r_{3}=r_{4}\end{matrix}\right.,$
(35)

or,

$\left\\{\begin{matrix}c_{1}=b_{1}-j\\\ c_{2}=b_{2}-jp_{i}\\\
jc_{3}+c_{4}=b_{3}\\\ k_{3}c_{3}=r_{3}^{-1}-k_{1}-p_{i}k_{2}\\\
\left(k_{1}-r_{3}^{-1}\right)c_{1}+k_{2}c_{2}+k_{3}c_{4}=-r_{4}r_{3}^{-1}\end{matrix}\right..$
(36)

Take $c_{1},c_{2},c_{3},c_{4}$ as unknowns. We have its augmented matrix as

$\left[\begin{array}[]{c|c}\begin{matrix}1&0&0&0\\\ 0&1&0&0\\\ 0&0&j&1\\\
0&0&k_{3}&0\\\
k_{1}-r_{3}^{-1}&k_{2}&0&k_{3}\end{matrix}&\begin{matrix}b_{1}-j\\\
b_{2}-jp_{i}\\\ b_{3}\\\ r_{3}^{-1}-k_{1}-p_{i}k_{2}\\\
-r_{4}r_{3}^{-1}\end{matrix}\end{array}\right].$ (37)

It can be Gaussian eliminated to

$\displaystyle\left[\begin{array}[]{c|c}\begin{matrix}1&0&0&0\\\ 0&1&0&0\\\
0&0&1&0\\\ 0&0&0&1\\\ 0&0&0&0\end{matrix}&\begin{matrix}b_{1}-j\\\
b_{2}-jp_{i}\\\ k_{3}^{-1}\left(r_{3}^{-1}-k_{1}-p_{i}k_{2}\right)\\\
b_{3}-jk_{3}^{-1}\left(r_{3}^{-1}-k_{1}-p_{i}k_{2}\right)\\\
\left(k_{1}-r_{3}^{-1}\right)b_{1}+k_{2}b_{2}+k_{3}b_{3}+r_{4}r_{3}^{-1}\end{matrix}\end{array}\right].$
(39)

In order for the equation system to have a solution, there must be

$\left(k_{1}-r_{3}^{-1}\right)b_{1}+k_{2}b_{2}+k_{3}b_{3}+r_{4}r_{3}^{-1}=0.$
(40)

$\forall b_{1},b_{2},b_{3}\in\left[D\right],r_{3}\in\left[D\right]^{o}$, we
have

$r_{4}=-r_{3}\left[\left(k_{1}-r_{3}^{-1}\right)b_{1}+k_{2}b_{2}+k_{3}b_{3}\right],$
(41)

thus $\left\lvert
Im(g_{B})\right\lvert=D^{3}\cdot\frac{D}{2}=\frac{D^{4}}{2}$. If (41) is
satisfied, then the general solution of (36) is

$\left\\{\begin{matrix}c_{1}=b_{1}-j\\\ c_{2}=b_{2}-jp_{i}\\\
c_{3}=k_{3}^{-1}\left(r_{3}^{-1}-k_{1}-p_{i}k_{2}\right)\\\
c_{4}=b_{3}-jk_{3}^{-1}\left(r_{3}^{-1}-k_{1}-p_{i}k_{2}\right)\end{matrix}\right..$
(42)

We have $S_{x_{i}}=\left[N\right]$,
$S_{\mathbf{c}}=\left[D\right]^{3}\times\left[D\right]^{o}$.
$\forall(j,x_{i})\in\left[D\right]\times\left[N\right]$, we can uniquely
identify a solution of $\mathbf{c}$ as above. Therefore, if $b\in Im(g_{B})$,
then $\alpha_{bx_{i}}=D$, $\beta_{b}=DN$; Otherwise,
$\alpha_{b{x_{i}}}=\beta_{b}=0$. By (1), we have

$\displaystyle H(Z_{B}:X_{A})\leq\log_{2}{\left\lvert S_{x_{i}}\right\lvert}$
$\displaystyle-\frac{\sum_{b\in\left[L\right]}\beta_{b}\log_{2}{\beta_{b}}-\left\lvert
S_{x_{i}}\right\lvert\sum_{b\in\left[L\right]}\alpha_{b{x_{i}}}\log_{2}{\alpha_{b{x_{i}}}}}{D\left\lvert
S_{x_{i}}\right\lvert\left\lvert S_{\mathbf{c}}\right\lvert}$
$\displaystyle=\log_{2}{N}-\left\lvert
Im(g_{B})\right\lvert\frac{DN\log_{2}\left(DN\right)-ND\log_{2}D}{DN\frac{D^{4}}{2}}$
$\displaystyle=m-(d+m)+d=0.$ (43)

Therefore, we prove that $I_{A}=H(Z_{B}:X_{A})=0$, i.e., no information about
$x_{i}$ can be stolen.

On the other hand, if particle $g$ is not involved, i.e., $c_{3}=c_{4}=0$,
then Bob has $k_{1}+p_{i}k_{2}=r_{3}^{-1}$, and gets
$p_{i}=k_{2}^{-1}\left(r_{3}^{-1}-k_{1}\right)$. Therefore, its existence is
necessary. ∎

###  A-C Proof of Lemma 3

Similar, we first need the following proposition.

######  Proposition 2 (Solution of Modular Multiplication Equation).

Let $D=2^{d}$, where $d$ is a positive integer. Assume there are three random
integers $a,b,c\in\left[D\right]$, where
$a=2^{d_{1}}w_{1},b=2^{d_{2}}w_{2},c=2^{d_{3}}w_{3}$, and
$d_{1},d_{2},d_{3}\in\left[d+1\right],w_{i}\in\left[2^{d-d_{i}}\right]^{o}$.
Denote $0=D=2^{d}\times 1$. We have

  1. 1)

The necessary and sufficient condition for $ab\equiv c(\ \mathrm{mod}\ D)$ is:
$d_{1}+d_{2}\geq d_{3}$ if $d_{3}=d$; $d_{1}+d_{2}=d_{3}$ and
$w_{1}w_{2}\equiv w_{3}(\ \mathrm{mod}\ 2^{d-d_{3}})$ if $d_{3}<d$.

  2. 2)

Given $a,c$, select $b$ randomly, denote $p=\Pr\left(ab\equiv c(\
\mathrm{mod}\ D)\right)$. Then, $p=\frac{1}{2^{d-d_{1}}}$ if $d_{3}\geq
d_{1}$; $p=0$ if $d_{3}<d_{1}$.

Proof:

  1. 1)

$ab\equiv c(\ \mathrm{mod}\ D)$ is equivalent to
$2^{d_{1}+d_{2}}w_{1}w_{2}=2^{d_{3}}w_{3}+k2^{d}$, where $k$ is an integer. If
$d_{3}=d$, then $w_{3}=1$, and $2^{d_{1}+d_{2}}w_{1}w_{2}=(k+1)2^{d}$,
$d_{1}+d_{2}\geq d$; conversely, if $d_{1}+d_{2}\geq d$, then
$2^{d_{1}+d_{2}}w_{1}w_{2}=(k+1)2^{d}\equiv c(\ \mathrm{mod}\ D)$. If
$d_{3}<d$, then
$2^{d_{1}+d_{2}}w_{1}w_{2}=2^{d_{3}}\left(w_{3}+k2^{d-d_{3}}\right)$, where
$w_{3}+k2^{d-d_{3}}$ is odd. Therefore ,we have $d_{1}+d_{2}=d_{3}$,
$w_{1}w_{2}=w_{3}+k2^{d-d_{3}}$, i.e., $w_{1}w_{2}\equiv w_{3}(\ \mathrm{mod}\
2^{d-d_{3}})$.

  2. 2)

a) If $d_{3}=d$, then

$\displaystyle p_{1}=\Pr\left(ab\equiv c(\ \mathrm{mod}\ D)\lvert
d=d_{3}\right)$ $\displaystyle=\Pr\left(d_{1}+d_{2}\geq
d_{3}\right)=\Pr\left(d_{2}\geq d-d_{1}\right)$
$\displaystyle=\Pr\left(2^{d-d_{1}}\lvert
b\right)=\frac{2^{d-(d-d_{1})}}{2^{d}}=\frac{1}{2^{d-d_{1}}}.$ (44)

Note that there are $2^{d-(d-d_{1})}$ multiples of $2^{d-d_{1}}$ in
$\left[D\right]$.

b) If $d>d_{3}\geq d_{1}$, the conditions are $d_{2}=d_{3}-d_{1}$ and
$w_{2}\equiv w_{1}^{-1}w_{3}(\ \mathrm{mod}\ 2^{d-d_{3}})$, where
$w_{1}^{-1}\in\left[2^{d-d_{3}}\right]^{o}$ is the multiplicative inverse of
$w_{1}\ \mathrm{mod}\ 2^{d-d_{3}}$. First, $d_{2}=d_{3}-d_{1}$ means that
$2^{d_{3}-d_{1}}\lvert b$ and $2^{d_{3}-d_{1}+1}\nmid b$. Of the
$2^{d-(d_{3}-d_{1})}$ multiples of $2^{d_{3}-d_{1}}$, half are multiples of
$2^{d_{3}-d_{1}+1}$, thus

$\displaystyle p_{2a}=\Pr\left(d_{2}=d_{3}-d_{1}\right)$
$\displaystyle=\frac{2^{d-(d_{3}-d_{1})}2^{-1}}{2^{d}}=\frac{1}{2^{d_{3}-d_{1}+1}},$
(45)

If $d_{2}=d_{3}-d_{1}$, we need

$w_{2}=w_{1}^{-1}w_{3}+k2^{d-d_{3}}\in\left[2^{d-d_{3}+d_{1}}\right]^{o},$
(46)

i.e., $1\leq w_{1}^{-1}w_{3}+k2^{d-d_{3}}\leq 2^{d-d_{3}+d_{1}}-1$. No matter
how much $w_{1}^{-1}w_{3}$ equals, we can assume that

$l2^{d-d_{3}}+1\leq w_{1}^{-1}w_{3}\leq(l+1)2^{d-d_{3}}-1,$ (47)

where $l$ is an integer. Then, we can deduce that

$\displaystyle-(l+1)2^{d-d_{3}}+1\leq-w_{1}^{-1}w_{3}\leq k2^{d-d_{3}}$
$\displaystyle\leq 2^{d-d_{3}+d_{1}}-1-w_{1}^{-1}w_{3}\leq
2^{d-d_{3}+d_{1}}-1-l2^{d-d_{3}}-1$
$\displaystyle=2^{d-d_{3}}(2^{d_{1}}-l)-2,$ (48)

thus $-l\leq k\leq 2^{d_{1}}-l-1$, i.e., $k$ has $2^{d_{1}}$ possible values.
Then

$\displaystyle p_{2b}=\Pr\left(w_{2}=w_{1}^{-1}w_{3}+k2^{d-d_{3}}\lvert
d_{2}=d_{3}-d_{1}\right)$
$\displaystyle=\frac{2^{d_{1}}}{2^{d-d_{3}+d_{1}-1}}=\frac{1}{2^{d-d_{3}-1}}.$
(49)

Note that there are half odd integers in $\left[2^{d-d_{3}+d_{1}}\right]$. Now

$\displaystyle p_{2}=\Pr\left(ab\equiv c(\ \mathrm{mod}\ D)\lvert d>d_{3}\geq
d_{1}\right)=p_{2a}\cdot p_{2b}$
$\displaystyle=\frac{1}{2^{d_{3}-d_{1}+1}}\cdot\frac{1}{2^{d-d_{3}-1}}=\frac{1}{2^{d-d_{1}}}=p_{1}.$
(50)

Thus $p=p_{1}=p_{2}=\frac{1}{2^{d-d_{1}}}$.

c) If $d_{3}<d_{1}$, then $d_{1}+d_{2}\neq d_{3}$, thus $p=0$.

In total, we prove this proposition. ∎

Now we can prove Lemma 3.

Proof of Lemma 3: There are three possible cases:

  1. a)

Using $t_{1}$ to steal $s_{i}$ and $t_{2}$ to steal $q_{i}$ simultaneously.

Assume that Alice prepares
$\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{t_{1}},\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{t_{2}}$. For convenience, we set $h,g$ in $\left\lvert
0\right\rangle$, since they are used to protect herself, not Bob. In Step 2 of
Operation stage, the state will be

$\displaystyle\frac{1}{D}\sum_{j,j^{\prime}\in\left[D\right]}\left\lvert
j\right\rangle_{t_{1}}\left\lvert j^{\prime}\right\rangle_{t_{2}}\left\lvert
0\right\rangle_{g}\rightarrow$
$\displaystyle\frac{1}{D}\sum_{j,j^{\prime}\in\left[D\right]}\left\lvert
jk\right\rangle_{t_{1}}\left\lvert j^{\prime}\right\rangle_{t_{2}}\left\lvert
jk_{1}+j^{\prime}k_{2}\right\rangle_{g}.$ (51)

Now $t_{1},t_{2},g$ are entangled. In Step 4 of Operation stage, no matter
what value $r_{3},r_{4}$ she sends are, the total state will be

$\displaystyle\frac{1}{D}\sum_{j,j^{\prime}\in\left[D\right]}\omega^{js_{i}+j^{\prime}q_{i}}\left\lvert
j\right\rangle_{t_{1}}\left\lvert j^{\prime}\right\rangle_{t_{2}}\left\lvert
jk_{1}+j^{\prime}k_{2}\right\rangle_{g}\rightarrow$
$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{js_{i}}\left\lvert
j\right\rangle_{t_{1}}\frac{1}{\sqrt{D}}\sum_{j^{\prime}\in\left[D\right]}\omega^{j^{\prime}q_{i}}$
$\displaystyle\left\lvert
j^{\prime}\right\rangle_{t_{2}}\left\lvert(jk_{1}r_{3}+j^{\prime}k_{2}r_{3}+r_{4})\oplus
j\right\rangle_{g}.$ (52)

Now Bob will measure $g$. For each $j\in\left[D\right]$, we have

$\displaystyle\Pr\left((jk_{1}r_{3}+j^{\prime}k_{2}r_{3}+r_{4})\oplus
j=0\right)$
$\displaystyle=\Pr\left(jk_{1}r_{3}+j^{\prime}k_{2}r_{3}+r_{4}=j\right)$
$\displaystyle=\Pr\left(j^{\prime}=(k_{2}r_{3})^{-1}(j(1-k_{1}r_{3})-r_{4})\right)=\frac{1}{D}.$
(53)

Thus, he will find Alice’s attack easily, with probability $1-\frac{1}{D}$.

  2. b)

Using $t_{1}$ to steal $s_{i}$ only.

Similarly, Alice prepares
$\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{t_{1}},\left\lvert 0\right\rangle_{t_{2}},\left\lvert
0\right\rangle_{g}$. In Step 2 of Operation stage, it will be

$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{t_{1}}\left\lvert 0\right\rangle_{t_{2}}\left\lvert
0\right\rangle_{g}\rightarrow\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\left\lvert
j\right\rangle_{t_{1}}\left\lvert 0\right\rangle_{t_{2}}\left\lvert
jk_{1}\right\rangle_{g},$ (54)

and in Step 4 of Operation stage, it will be

$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{js_{i}}\left\lvert
j\right\rangle_{t_{1}}\left\lvert jk_{1}\right\rangle_{g}\rightarrow$
$\displaystyle\frac{1}{\sqrt{D}}\sum_{j\in\left[D\right]}\omega^{js_{i}}\left\lvert
j\right\rangle_{t_{1}}\left\lvert(jk_{1}r_{3}+r_{4})\oplus
j\right\rangle_{g}.$ (55)

When Bob measure $g$, he will get $\left\lvert 0\right\rangle$ if
$jk_{1}r_{3}+r_{4}=j$, i.e., $j(1-k_{1}r_{3})=r_{4}$. Let
$S_{J}=\\{j|j(1-k_{1}r_{3})=r_{4},j\in\left[D\right]\\}$. Bob can find the
cheating with probability $1-\frac{\left\lvert S_{J}\right\lvert}{D}$, and
ignore it with $\frac{\left\lvert S_{J}\right\lvert}{D}$. If he ignores, the
state of $t_{1}$ will be

$\left\lvert\psi_{s_{i}}\right\rangle=\frac{1}{\sqrt{\left\lvert
S_{J}\right\lvert}}\sum_{j\in S_{J}}\omega^{js_{i}}\left\lvert
j\right\rangle.$ (56)

$t_{1}$ will return to Alice in Step 5 of Operation stage. Now the density
operator is

$\displaystyle\rho_{s_{i}}=\left\lvert\psi_{s_{i}}\right\rangle\left\langle\psi_{s_{i}}\right\lvert=\frac{1}{\left\lvert
S_{J}\right\lvert}\sum_{j^{\prime},j\in
S_{J}}\omega^{(j^{\prime}-j)s_{i}}\left\lvert
j^{\prime}\right\rangle\left\langle j\right\lvert$ (57)

Since
$\rho_{s_{i}}=\left\lvert\psi_{s_{i}}\right\rangle\left\langle\psi_{s_{i}}\right\lvert$,
$S\left(\rho_{s_{i}}\right)=0$. For Alice who has no knowledge of odd integer
$s_{i}=4v_{i}-2y_{i}-1\ \mathrm{mod}\ D$, $s_{i}$ can be considered to follow
the uniform distribution on $\left[D\right]^{o}$, i.e.,
$p_{s_{i}}=\frac{2}{D}$. Let $s_{i}=2a+1$, then the total operator is

$\displaystyle\rho=\sum_{s_{i}\in\left[D\right]^{o}}\frac{2}{D}\rho_{s_{i}}$
$\displaystyle=\frac{2}{D\left\lvert S_{J}\right\lvert}\sum_{j\in
S_{J}}\sum_{j^{\prime}\in
S_{J}}\sum_{s_{i}\in\left[D\right]^{o}}\omega^{(j^{\prime}-j)s_{i}}\left\lvert
j^{\prime}\right\rangle\left\langle j\right\lvert.$ (58)

Note that if $j^{\prime}=j$ then
$\sum_{s_{i}\in\left[D\right]^{o}}\omega^{(j^{\prime}-j)s_{i}}=\frac{D}{2}$;
Or, if $j^{\prime}-j\equiv\frac{D}{2}(\ \mathrm{mod}\ D)$, then

$\displaystyle\sum_{s_{i}\in\left[D\right]^{o}}\omega^{(j^{\prime}-j)s_{i}}=\sum_{s_{i}\in\left[D\right]^{o}}e^{\imath\pi
s_{i}}=\sum_{s_{i}\in\left[D\right]^{o}}(-1)=-\frac{D}{2};$ (59)

Otherwise,

$\displaystyle\sum_{s_{i}\in\left[D\right]^{o}}\omega^{(j^{\prime}-j)s_{i}}=\sum_{a\in\left[\frac{D}{2}\right]}e^{\frac{\imath
2\pi}{D}\cdot(j^{\prime}-j)(2a+1)}$
$\displaystyle=\omega^{j^{\prime}-j}\sum_{a\in\left[\frac{D}{2}\right]}e^{\frac{\imath
2\pi}{D}\cdot 2(j^{\prime}-j)a}=\omega^{j^{\prime}-j}\frac{1-e^{\imath
2\pi(j^{\prime}-j)}}{1-e^{\frac{\imath 2\pi}{D}\cdot 2(j^{\prime}-j)}}$
$\displaystyle=0.$ (60)

Since $k_{1}r_{3}$ is odd, we have $D|(1-k_{1}r_{3})\frac{D}{2}$, thus

$\displaystyle(1-k_{1}r_{3})\left(j+\frac{D}{2}\right)\equiv(1-k_{1}r_{3})j\equiv
r_{4}(\ \mathrm{mod}\ D).$ (61)

I.e., if $j\in S_{J}$ then $j+\frac{D}{2}\ \mathrm{mod}\ D\in S_{J}$. Now we
can calculate the eigenvalue of $\rho$. By (b), we have

$\rho=\frac{1}{\left\lvert S_{J}\right\lvert}\sum_{j\in
S_{J}}\left(\left\lvert j\right\rangle-\left\lvert
j+\frac{D}{2}\right\rangle\right)\left\langle j\right\lvert.$ (62)

$\forall j\in S_{J}$, denote $\left\lvert\phi_{j\pm}\right\rangle=\left\lvert
j\right\rangle\pm\left\lvert j+\frac{D}{2}\right\rangle$, then

$\rho\left\lvert\phi_{j+}\right\rangle=0\left\lvert\phi_{j+}\right\rangle,\rho\left\lvert\phi_{j-}\right\rangle=\frac{2}{\left\lvert
S_{J}\right\lvert}\left\lvert\phi_{j+}\right\rangle.$ (63)

I.e., $\rho$ has $\frac{\left\lvert S_{J}\right\lvert}{2}$ non-zero
eigenvalues $\frac{2}{\left\lvert S_{J}\right\lvert}$. Then

$S\left(\rho\right)=-\frac{\left\lvert
S_{J}\right\lvert}{2}\cdot\frac{2}{\left\lvert
S_{J}\right\lvert}\log_{2}\frac{2}{\left\lvert
S_{J}\right\lvert}=\log_{2}\left\lvert S_{J}\right\lvert-1.$ (64)

If Alice measures $t_{1}$ to obtain any result $Z_{A}$, then

$\displaystyle H\left(Z_{A}:s_{i}|\rm{Alice\ passes\ the\ test}\right)$
$\displaystyle\leq
S\left(\rho\right)-\sum_{s_{i}\in\left[D\right]^{o}}p_{s_{i}}S\left(\rho_{s_{i}}\right)=\log_{2}\left\lvert
S_{J}\right\lvert-1$ (65)

Since the probability she pass Bob’s honesty test is $\frac{\left\lvert
S_{J}\right\lvert}{D}$, then the leakage degree of Bob’s privacy, i.e., the
average information Alice obtains is

$\displaystyle I_{B}=H(Z_{A}:s_{i})\leq\sum_{\left\lvert
S_{J}\right\lvert}\frac{\left\lvert S_{J}\right\lvert}{D}p_{\left\lvert
S_{J}\right\lvert}\log_{2}\left\lvert S_{J}\right\lvert-1.$ (66)

Let’s find $p_{\left\lvert S_{J}\right\lvert}$. Let
$1-k_{1}k_{3}=2^{d_{l}}w_{l}$, $r_{4}=2^{d_{r}}w_{r}$, $j=2^{d_{j}}w_{j}$. By
Proposition 2, $j(1-k_{1}r_{3})=r_{4}$ only if $d_{r}\geq d_{l}$, with
probability $\frac{1}{2^{d-d_{l}}}$, i.e., $\left\lvert
S_{J}\right\lvert=\frac{2^{d}}{2^{d-d_{l}}}=2^{d_{l}}$; Otherwise, if
$d_{r}<d_{l}$, then $\left\lvert S_{J}\right\lvert=0$. To maximize $I_{B}$,
Alice should set $d_{r}=d$, i.e., $r_{4}=0$, so that $d_{r}\geq d_{l}$ always
holds. Note that $1-k_{1}r_{3}$ is a random even, if $d_{l}<d$, then

$\displaystyle p_{\left\lvert
S_{J}\right\lvert}=\Pr\left(2^{d_{l}}\lvert(1-k_{1}r_{3}),\
2^{d_{l}+1}\nmid(1-k_{1}r_{3})\right)$
$\displaystyle=\frac{2^{d-d_{l}-1}}{2^{d-1}}=\frac{1}{2^{d_{l}}};$ (67)

If $d_{l}=d$, then $1-k_{1}r_{3}=0$, and $p_{\left\lvert
S_{J}\right\lvert}=\frac{2}{2^{d-1}}$. Therefore,

$p_{\left\lvert S_{J}\right\lvert}=\left\\{\begin{matrix}\frac{1}{\left\lvert
S_{J}\right\lvert},&\ \mathrm{if}\ \left\lvert S_{J}\right\lvert<D\\\
\frac{2}{\left\lvert S_{J}\right\lvert},&\ \mathrm{if}\ \left\lvert
S_{J}\right\lvert=D\end{matrix}\right..$ (68)

Now by (66), we have

$\displaystyle I_{B}\leq\sum_{\left\lvert S_{J}\right\lvert}\frac{\left\lvert
S_{J}\right\lvert}{D}p_{\left\lvert S_{J}\right\lvert}\log_{2}\left\lvert
S_{J}\right\lvert-1$
$\displaystyle=\sum_{d_{l}=1}^{d-1}\frac{2^{d_{l}}}{D}\cdot\frac{1}{2^{d_{l}}}\left(\log_{2}2^{d_{l}}-1\right)+\frac{2^{d}}{D}\cdot\frac{2}{2^{d}}\left(\log_{2}2^{d}-1\right)$
$\displaystyle=\frac{1}{D}\sum_{d_{l}=1}^{d-1}(d_{l}-1)+\frac{2}{D}(d-1)=\frac{1}{D}\frac{(d-1)(d-2)+4(d-1)}{2}$
$\displaystyle=\frac{1}{D}\frac{(d-1)(d+2)}{2}=\frac{d^{2}+d-2}{2\cdot
2^{d}}=O\left(\frac{d^{2}}{2^{d}}\right).$ (69)

  3. c)

Using $t_{2}$ to steal $q_{i}$ only.

This case is almost identical to b). We can calculate the total density
operator $\rho=\sum_{y_{i}\in\left[N\right]}\frac{1}{N}\rho_{y}$, and find
that the upper bound in this case equals to the one in b) if
$1-k_{2}r_{3}\not\equiv 0(\ \mathrm{mod}\ D)$, because if
$j-j^{\prime}\equiv\mathrm{odd}(\ \mathrm{mod}\ D)$, then $j,j^{\prime}$
cannot satisfy $j(1-k_{2}r_{3})\equiv r_{4}(\ \mathrm{mod}\ D)$ at the same
time. In this case, we have
$I_{B}=H(Z_{A}:s_{i})=O\left(\frac{d^{2}}{2^{d}}\right)$.

If $1-k_{2}r_{3}\equiv 0(\ \mathrm{mod}\ D)$ with probability $\frac{2}{D}$,
we can deduce a new upper bound $d$, since at most $d$ bits of classical
information can be extracted from the $d$-qubit state[42]. Considering the
probability $\frac{1}{2^{d-1}}$, the average upper bound is

$\displaystyle
I_{B}\leq\left(1-\frac{1}{2^{d-1}}\right)O\left(\frac{d^{2}}{2^{d}}\right)+\frac{1}{2^{d-1}}d\leq
O\left(\frac{d^{2}}{2^{d}}\right).$ (70)

In total, the leakage degree of Bob’s privacy is
$I_{B}=O\left(\frac{d^{2}}{2^{d}}\right)$, where the asymptotic coefficient is
$\frac{1}{2}$. ∎

###  A-D Proof of Lemma 4

Denote random variables $M=(M_{1},M_{2},\cdots,M_{n})$ and
$X_{B}=(\mathbf{y},v)$. At first, we have[43]

$\displaystyle I_{B}=H(M:X_{B}|u)=H(X_{B}:M,u)-H(X_{B}:u).$ (71)

Since $u$ is a function of $X_{B}$ (and $M$, since Alice can calculate $u$
only with $M$), we have $H(X_{B}:u)=H(u)$, $H(u|X_{B})=0$ and $H(M,u)=H(M)$
(Theorem 11.3 of Ref. [42]). By the chaining rule for conditional entropies
(Theorem 11.4 of Ref. [42]),
$H(M,u|X_{B})=H(u|M,X_{B})+H(M|X_{B})=H(M,X_{B})-H(X_{B})$. Then

$\displaystyle I_{B}=H(M:X_{B}|u)=H(X_{B}:M,u)-H(X_{B}:u)$
$\displaystyle=H(M,u)-H(M,u|X_{B})-H(u)$
$\displaystyle=H(M)-H(M,X_{B})+H(X_{B})-H(u)$
$\displaystyle=H(X_{B})-H(X_{B}|M)-H(u).$ (72)

Note that $\hat{M}_{i}\equiv M_{i}-2x_{i}\equiv 4v_{i}+4x_{i}y_{i}(\
\mathrm{mod}\ D)$ and $M_{i}$ correspond one-to-one, then
$H(X_{B}|\hat{M})=H(X_{B}|M)$, where
$\hat{M}=(\hat{M}_{1},\cdots,\hat{M}_{n})$. $\forall\hat{M_{i}}\in
4\left[N\right],y_{i}\in\left[N\right]$, only if $v_{i}$ satisfy
$4v_{i}\equiv\hat{M_{i}}-4x_{i}y_{i}(\ \mathrm{mod}\ D)$, $4v\equiv
4\sum_{i=1}^{n}v_{i}(\ \mathrm{mod}\ D)$ is valid. Therefore, there is only
one possible $4v\in\left[D\right]$, and thus one $v\in\left[N\right]$. Then we
have $p(X_{B}|\hat{M})=\frac{1}{N^{n}}$. On the other hand, $\forall
y_{i},v\in\left[N\right]$, if $v_{1},v_{2},\cdots,v_{n-1}\in\left[N\right]$
have been selected, then $4v_{n}\equiv 4v-4\sum_{i=1}^{n-1}v_{i}(\
\mathrm{mod}\ D)$ is determined, and so is $\hat{M}$. Therefore,
$p(\hat{M}|X_{B})=\frac{1}{N^{n-1}}$. By $p(X_{B})=\frac{1}{N^{n+1}}$, we have

$\displaystyle
H(X_{B}|\hat{M})=-\sum_{X_{B}\in\left[N\right]^{n+1}}\sum_{\hat{M}\in
4\left[N\right]^{n}}p(X_{B},\hat{M})\log_{2}{p(X_{B}|\hat{M})}$
$\displaystyle=-\sum_{X_{B}\in\left[N\right]^{n+1}}\sum_{v_{1},v_{2},\cdots,v_{n-1}\in\left[N\right]}p(\hat{M}|X_{B})p(X_{B})\log_{2}{p(X_{B}|\hat{M})}$
$\displaystyle=-{N}^{n+1}{N}^{n-1}\frac{1}{N^{n-1}}\frac{1}{N^{n+1}}\log_{2}{\frac{1}{N^{n}}}=nm.$
(73)

Similarly, because $\forall u\in\left[N\right]$, we can randomly select
$\mathbf{y}\in\left[N\right]^{n}$, then $v=u-\mathbf{x}\cdot\mathbf{y}$. That
is, each $u$ corresponds to $N$ possible values of $y$, i.e.,
$p(u)=\frac{1}{N}$. Then $H(X_{B})=(n+1)m$, $H(u)=m$, and
$I_{B}=(n+1)m-nm-m=0$. ∎

##  Appendix B Implementation of Quantum Gates

Here we analyze the complexity of the quantum operations we used, and how to
implement them in simulation.

###  B-A Complexity Analysis

  1. 1)

As shown in figure 2a, A $\mathcal{QFT}$ (or $\mathcal{QFT}^{\dagger}$) gate
can be decomposed into $O\left(d^{2}\right)$ $\mathcal{H}$ and $\mathcal{CP}$
gates[42].

  2. 2)

Let $a=\sum_{i\in\left[d\right]}a_{i}2^{i}$,
$b=\sum_{k\in\left[d\right]}b_{k}2^{k}$. As shown in figure 2b, we have
$\mathcal{ROT}_{h}=\prod_{i,k\in\left[d\right]}\mathcal{P}(i+k)^{b_{i}}_{h_{i}}$,
where $b_{i}$ means the controlling bit, i.e., if $b_{i}=1$, perform
$\mathcal{P}(i+k)_{h_{i}}$, otherwise do nothing. Because

$\displaystyle\prod_{i,k\in\left[d\right]}\mathcal{P}(i+k)^{b_{i}}_{h_{i}}\left\lvert
a\right\rangle_{h}=\prod_{i,k\in\left[d\right]}e^{\frac{\imath 2\pi
2^{i+k}a_{i}b_{i}}{D}}\left\lvert a\right\rangle_{h}$
$\displaystyle=e^{\frac{\imath
2\pi\sum_{i,k\in\left[d\right]}2^{i+k}a_{i}b_{i}}{D}}\left\lvert
a\right\rangle_{h}=e^{\frac{\imath 2\pi ab}{D}}\left\lvert a\right\rangle_{h}$
$\displaystyle=\mathcal{ROT}_{h}\left\lvert a\right\rangle_{h}.$ (74)

Thus, the complexity of $\mathcal{ROT}$ gate is also $O\left(d^{2}\right)$.

  3. 3)

As elementary arithmetic gates, the complexity of $\mathcal{SUM}$ and
$\mathcal{BSUM}$ are both $O(d)$, if we only use $\mathcal{T}$ and
$\mathcal{CNOT}$ gates corresponding to classical AND and XOR gate. Generally,
it requires an auxiliary qubit as a carrier.

  4. 4)

To realize $\mathcal{MUL}$, introduce an auxiliary register $\left\lvert
0\right\rangle_{t}$, then

$\displaystyle\left\lvert a\right\rangle_{h}\left\lvert
0\right\rangle_{t}\overset{\mathcal{SUM}(2^{0}b)^{h_{0}}_{t}}{\longrightarrow}\left\lvert
a\right\rangle_{h}\left\lvert
2^{0}a_{0}b\right\rangle_{t}\overset{\mathcal{SUM}(2^{1}b)^{h_{1}}_{t}}{\longrightarrow}$
$\displaystyle\cdots\overset{\mathcal{SUM}(2^{d-1}b)^{h_{d-1}}_{t}}{\longrightarrow}=\left\lvert
a\right\rangle_{h}\left\lvert ab\right\rangle_{t},$ (75)

where $\mathcal{SUM}^{h_{i}}$ means $\mathcal{SUM}$ is controlled by qubit
$h_{i}$. We denote the above gate as $\mathcal{BMUL}(b)_{(h,t)}$. To realize
$\mathcal{MUL}$, use
$\mathcal{SWAP}_{(h,t)}=\mathcal{XOR}_{(h,t)}\mathcal{XOR}_{(t,h)}\mathcal{XOR}_{(h,t)}:\left\lvert
a\right\rangle_{h}\left\lvert b\right\rangle_{t}\rightarrow\left\lvert
b\right\rangle_{h}\left\lvert a\right\rangle_{t}$. Then

$\displaystyle\left\lvert a\right\rangle_{h}\left\lvert
0\right\rangle_{t}\overset{\mathcal{BMUL}(b)_{(h,t)}}{\longrightarrow}\left\lvert
a\right\rangle_{h}\left\lvert
ab\right\rangle_{t}\overset{\mathcal{BMUL}(-b^{-1})_{(t,h)}}{\longrightarrow}$
$\displaystyle\left\lvert 0\right\rangle_{h}\left\lvert
ab\right\rangle_{t}\overset{\mathcal{SWAP}_{(h,t)}}{\longrightarrow}\left\lvert
ab\right\rangle_{h}\left\lvert 0\right\rangle_{t},$ (76)

as Shor described[50]. Its complexity is $O(d^{2})$.

  5. 5)

Obviously, an $\mathcal{XOR}$ gate can decomposed into $d$ $\mathcal{CNOT}$
gates, as shown in figure 2f. Thus its complexity is $O(d)$.

###  B-B Implementation of Quantum Gates

To save valuable qubit resources, we use Draper’s Transform Adder[41] to
implement $\mathcal{SUM}$ and $\mathcal{BSUM}$. It need no auxiliary qubits,
but increases the complexity. In this method, we have
$\mathcal{SUM}(b)=\mathcal{QFT}^{\dagger}\mathcal{ROT}(b)\mathcal{QFT}$ and
$\mathcal{BSUM}_{(h,t)}=\mathcal{QFT}^{\dagger}_{t}\mathcal{BROT}_{(h,t)}\mathcal{QFT}_{t}$,
with complexity $O(d^{2})$. The gate $\mathcal{BROT}$ is defined as
$\mathcal{BROT}_{(h,t)}:\left\lvert a\right\rangle_{h}\left\lvert
b\right\rangle_{t}\rightarrow\omega^{ab}\left\lvert
a\right\rangle_{h}\left\lvert b\right\rangle_{t}$, by replacing
$\mathcal{P}(i+k)^{b_{i}}_{h_{i}}$ with $\mathcal{CP}(i+k)_{(h_{i},t_{i})}$ in
$\mathcal{ROT}_{h}$. The circuit of them are shown in figure 2c and 2e
respectively.

In addition, the general $\mathcal{MUL}$ gate needs $O(d)$ auxiliary qubits.
Here we point out that for the special modulus $D=2^{d}$, we can design a
special circuit which requires no auxiliary qubits. To illustrate our design
idea, we first define a new gate $\mathcal{SUM}(b\ \mathrm{mod}\ 2^{l})$ as a
$\ \mathrm{mod}\ 2^{l}$ summation gate on register
$(h_{d-1},h_{d-2},\cdots,h_{d-l})$. E.g., $\mathcal{SUM}(b\ \mathrm{mod}\
2^{2})$ will change $\left\lvert a_{d-1}\right\rangle\left\lvert
a_{d-2}\right\rangle$ to
$\left\lvert\sum_{i\in\left[2\right]}2^{i}a_{i+d-2}+b\ \mathrm{mod}\
2^{2}\right\rangle$. Denote $w=\frac{b-1}{2}$ (must be an integer). We have

$\displaystyle\mathcal{MUL}(b)=\mathcal{SUM}(w\ \mathrm{mod}\
2^{d-1})^{h_{0}}\mathcal{SUM}(w\ \mathrm{mod}\ 2^{d-2})^{h_{1}}$
$\displaystyle\cdots\mathcal{SUM}(w\ \mathrm{mod}\
2^{2})^{h_{d-3}}\mathcal{SUM}(w\ \mathrm{mod}\ 2^{1})^{h_{d-2}},$ (77)

as shown in figure 2d. Now we prove its correctness.

Proof: We have

$\displaystyle ab\equiv a(2w+1)\equiv a+2w\sum_{i=0}^{d-1}2^{i}a_{i}\equiv
a+\sum_{i=1}^{d}2^{i}wa_{i-1}(\ \mathrm{mod}\ 2^{d})$ $\displaystyle\equiv
a+\sum_{i=1}^{d-1}2^{i}wa_{i-1}(\ \mathrm{mod}\ 2^{d}).$ (78)

Let $a^{(0)}=a$ and $a^{(l+1)}=a^{(l)}+wa_{d-1-l}2^{d-l}\ \mathrm{mod}\ D$,
then we have $a^{(d)}=a^{(d-1)}+wa_{0}2^{0}\ \mathrm{mod}\ D=ab$. Let
$a^{(l+1)}=\sum_{i=0}^{d-1}a_{i}^{(l+1)}2^{i}$,
$a^{(l)}=\sum_{i=0}^{d-1}a_{i}^{(l)}2^{i}$, then

$\displaystyle\sum_{i=0}^{d-1}a_{i}^{(l+1)}2^{i}=a^{(l)}+wa_{d-1-l}2^{d-l}\
\mathrm{mod}\ D$
$\displaystyle=\sum_{i=0}^{d-1}a_{i}^{(l)}2^{i}+wa_{d-1-l}2^{d-l}\
\mathrm{mod}\ D$
$\displaystyle=\sum_{i=0}^{d-l-1}a_{i}^{(l)}2^{i}+\sum_{i=d-l}^{d-1}a_{i}^{(l)}2^{i}+wa_{d-1-l}2^{d-l}-k2^{d}$
$\displaystyle=\sum_{i=0}^{d-l-1}a_{i}^{(l)}2^{i}+2^{d-l}\left(\sum_{i=0}^{l-1}a_{i+d-l}^{(l)}2^{l}+wa_{d-1-l}-k2^{l}\right)$
$\displaystyle=\sum_{i=0}^{d-l-1}a_{i}^{(l)}2^{i}$ $\displaystyle\ \ \ \
+2^{d-l}\left(\sum_{i=0}^{l-1}a_{i+d-l}^{(l)}2^{l}+wa_{d-1-l}\ \mathrm{mod}\
2^{l}\right),$ (79)

where $k$ is integer. Note that $a_{i}^{(l+1)}=a_{i}^{(l)}$, $0\leq i\leq
d-l-1$, thus

$\displaystyle\sum_{i=0}^{d-l-1}a_{i}^{(l+1)}2^{i}=\sum_{i=0}^{d-l-1}a_{i}^{(l)}2^{i}=$
$\displaystyle\cdots=\sum_{i=0}^{d-l-1}a_{i}^{(0)}2^{i}=\sum_{i=0}^{d-l-1}a_{i}2^{i}.$
(80)

Therefore,

$\displaystyle a^{(l+1)}=\sum_{i=0}^{d-l-1}a_{i}^{(l)}2^{i}$ $\displaystyle\ \
\ \ +2^{d-l}\left(\sum_{i=0}^{l-1}a_{i+d-l}^{(l)}2^{l}+wa_{d-1-l}^{(l)}\
\mathrm{mod}\ 2^{l}\right),$ (81)

which means that we can add $w$ on $\left\lvert
a_{d-1}\right\rangle\cdots\left\lvert a_{d-l}\right\rangle\ \mathrm{mod}\
2^{l}$ if $a_{d-l-1}=1$, for each $l=0,1,\cdots,d-1$. That’s why (B-B) and the
circuit in figure 2d are correct. ∎

## References

  * [1] A. C. Yao, “Protocols for secure computations,” in Proc. 23rd IEEE Symposium on Foundations of Computer Science, Piscataway, USA, pp. 160-164, 1982.
  * [2] A. C. Yao, “How to generate and exchange secrets,” in Proc. 27th Annual Symposium on Foundations of Computer Science, Toronto, ON, Canada, pp. 162-167, 1986.
  * [3] S. Even, O. Goldreich and A. Lempel, “A randomized protocol for signing contracts,” Commun. ACM, vol. 28, no. 6, pp. 637–647, 1985.
  * [4] G. Brassard, C. Crepeau and J.-M. Robert, “All-or-nothing disclosure of secrets,” in Proc. Advances in Cryptology — CRYPTO’ 86, Berlin, Heidelberg, Germany, pp. 234-238, 1987.
  * [5] C. Peikert, V. Vaikuntanathan and B. Waters, “A framework for efficient and composable oblivious transfer,” in Proc. Advances in Cryptology – CRYPTO 2008, Berlin, Heidelberg, Germany, pp. 554-571, 2008.
  * [6] O. Goldreich, S. Micali and A. Wigderson, “How to play ANY mental game,” in Proc. 19th Annual ACM Symposium on Theory of Computing, New York, USA, pp. 218–229, 1987.
  * [7] M. Ben-Or, S. Goldwasser and A. Wigderson, “Completeness lemmas for non-cryptographic fault-tolerant distributed computation,” in Proc. 20th annual ACM symposium on Theory of computing, Chicago, Illinois, USA, pp. 1-10, 1988.
  * [8] D. Beaver, “Efficient multiparty protocols using circuit randomization,” in Proc. Advances in Cryptology — CRYPTO ’91, Berlin, Heidelberg, Germany, pp. 420-432, 1992.
  * [9] L. Z. Xiong, W. H. Zhou, Z. H. Xia, Q. Gu and J. Weng, “Efficient privacy-preserving computation based on additive secret sharing,” ArXiv preprint, [Online]. Avaliable: https://arxiv.org/abs/2009.05356
  * [10] T. Elgamal, “A public key cryptosystem and a signature scheme based on discrete logarithms,” IEEE Trans. Inf. Theory, vol. 31, no. 4, pp. 469-472, 1985.
  * [11] P. Paillier, “Public-key cryptosystems based on composite degree residuosity classes,” in Proc. Advances in Cryptology — EUROCRYPT ’99, Berlin, Heidelberg, Germany, pp. 223-238, 1999.
  * [12] D. Ivan, G. Martin and K. Mikkel, “Homomorphic encryption and secure comparison,” Int. J. Appl. Cryptogr., vol. 1, no. 1, pp. 22–31, 2008.
  * [13] H. Huang, T. Gong, P. Chen, R. Malekian and T. Chen, “Secure two-party distance computation protocol based on privacy homomorphism and scalar product in wireless sensor networks,” Tsinghua Sci. Technol., vol. 21, no. 4, pp. 385-396, 2016.
  * [14] H. Zhu, F. Wang, R. Lu, F. Liu, G. Fu and H. Li, “Efficient and privacy-preserving proximity detection schemes for social applications,” IEEE Internet Things J., vol. 5, no. 4, pp. 2947-2957, 2018.
  * [15] S. K. Shen, B. Yang, K. G. Qian, Y. M. She and W. Wang, “On improved DV-Hop localization algorithm for accurate node localization in wireless sensor networks,” Chinese J. Electron., vol. 28, no. 3, pp. 658-666, 2019.
  * [16] W. L. Du and M. J. Atallah, “Privacy-preserving cooperative statistic alanalysis,” in Proc. Annual Computer Security Applications Conference, New Orleans, USA, pp. 102-110, 2001.
  * [17] J. Vaidya and C. Clifton, “Privacy preserving association rule mining in vertically partitioned data,” in Proc. 8th ACM SIGKDD international conference on Knowledge discovery and data mining, Edmonton, Alberta, Canada, N. New York, USA, pp. 639–644, 2002.
  * [18] B. Goethals, S. Laur, H. Lipmaa and T. Mielikäinen, “On private scalar product computation for privacy-preserving data mining,” in Proc. Information Security and Cryptology – ICISC 2004, Berlin, Heidelberg, Germany, pp. 104-120, 2005.
  * [19] D. H. Tran, W. K. Ng, H. W. Lim and H. L. Nguyen, “An efficient cacheable secure scalar product protocol for privacy-preserving data mining,” in Proc. Data Warehousing and Knowledge Discovery, Berlin, Heidelberg, Germany, pp. 354-366, 2011.
  * [20] M. J. Atallah and W. Du, “Secure multi-party computational geometry,” in Proc. WADS2001: Seventh International Workshop on Algorithms and Data Structures, Providence, Rhode Island, USA, pp.165–179, 2001.
  * [21] T. Thomas, “Secure two-party protocols for point Inclusion problem,” Int. J. Netw. Secur., vol. 9, no. 1, pp. 1-7, 2009.
  * [22] B. Yang, Z. Shao and W. Zhang, “Secure two-party protocols on planar convex hulls,” J. Inf. Comput. Sci., vol. 9, pp. 915-929, 2012.
  * [23] W. J. Liu, Y. Xu, J. C. N. Yang, W. B. Yu and L. H. Chi, “Privacy-preserving quantum two-party geometric intersection,” Comput. Mater. Continua, vol. 60, no. 3, pp. 1237-1250, 2018.
  * [24] L. Li and R. H. Shi, “A novel and efficient quantum private comparison scheme,” J. Korean Phys. Soc., vol. 75, no. 1, pp. 15-21, 2019.
  * [25] R. H. Shi, B. Liu and M. W. Zhang, “Secure two-party integer comparison protocol without any third party,” Quantum Inf. Process., vol. 20, no. 12, 402, 2021.
  * [26] R. H. Shi and Y. F. Li, “Quantum private set intersection cardinality protocol with application to privacy-preserving condition query,” IEEE Trans. Circuits Syst. I Regul. Pap., vol. 69, no. 6, pp. 2399-2411, 2022.
  * [27] R. H. Shi and Y. F. Li, “Quantum protocol for secure multiparty logical AND with application to multiparty private set intersection cardinality,” IEEE Trans. Circuits Syst. I Regul. Pap., vol. 69, no. 12, pp. 5206-5218, 2022.
  * [28] L. B. He, L. S. Huang, W. Yang and R. Xu, “A protocol for the secure two-party quantum scalar product,” Phys. Lett. A, vol. 376, no. 16, pp. 1323-1327, 2012.
  * [29] Y. Wang and G. He, “Quantum secure scalar product with continuous-variable clusters,” in Proc. 18th AQIS Conf., Nagoya, Japan, [Online]. Avaliable: http://www.ngc.is.ritsumei.ac.jp/$\sim$ger/static/AQIS18/OnlineB- ooklet/161.pdf
  * [30] R. H. Shi and M. W. Zhang, “Strong privacy-preserving two-party scalar product quantum protocol,” Int. J. Theor. Phys., vol. 58, no. 12, pp. 4249-4257, 2019.
  * [31] L. K. Grover, “Quantum mechanics helps in serching for a needle in a haystack,” Phys. Rev. Lett., vol. 79, no. 2, pp. 325-328, 1997
  * [32] W. Yang, L. S. Huang, R. H. Shi and L. B. He, “Secret sharing based on quantum Fourier transform,” Quantum Inf. Process., vol. 12, no. 7, pp. 2465-2474, 2013.
  * [33] V. Karimipour and A. Bahraminasab, “Entanglement swapping of generalized cat states and secret sharing,” Phys. Rev. A, vol. 65, no. 4, 042320, 2002.
  * [34] H. Y. Yang and T. Y. Ye, “Secure multi-party quantum summation based on quantum Fourier transform,” Quantum Inf. Process., vol. 17, no. 6, 129, 2018.
  * [35] Z. X. Ji, H. G. Zhang, H. Z. Wang, F. S. Wu, J. W. Jia and W. Q. Wu, “Quantum protocols for secure multi-party summation,” Quantum Inf. Process., vol. 18, no.6, 168, 2019.
  * [36] K. Sutradhar and H. Om, “A generalized quantum protocol for secure multiparty summation,” IEEE Trans. Circuits Syst. II, Exp. Briefs, vol. 67, no. 12, pp. 2978-2982, 2020.
  * [37] K. Sutradhar and H. Om, “Hybrid quantum protocols for secure multiparty summation and multiplication,” Sci. Rep., vol. 10, no. 1, 9097, 2020.
  * [38] K. Sutradhar and H. Om, “A cost-effective quantum protocol for secure multi-party multiplication,” Quantum Inf. Process., vol. 20, no. 11, 380, 2021.
  * [39] X. Yi, C. Cao, L. Fan and R. Zhang, “Quantum secure multi-party summation protocol based on blind matrix and quantum Fourier transform,” Quantum Inf. Process., vol. 20, no. 7, 249, 2021.
  * [40] R. H. Shi, Y. Mu, H. Zhong, J. Cui and S. Zhang, “Secure multiparty quantum computation for summation and multiplication,” Sci. Rep., vol. 6, 19655, 2016.
  * [41] T. G. Draper, “Addition on a Quantum Computer,” ArXiv preprint, [Online]. Avaliable: https://arxiv.org/abs/quant-ph/0008033
  * [42] M. A. Nielsen and I. L. Chuang, Quantum Computation and Quantum Information, ed. Cambridge, United Kingdom: Cambridge University Press, 2000.
  * [43] A. D. Wyner, “A definition of conditional mutual information for arbitrary ensembles,” Information and Control, vol. 38, no. 1, 51-59, 1978.
  * [44] A. S. Holevo, “Statistical problems in quantum physics,” in Proc. 2th Japan-USSR Symposium on Probability Theory, Berlin, Heidelberg, Germany, pp. 104-119, 1973.
  * [45] M. Keller, E. Orsini and P. Scholl, “MASCOT: faster malicious arithmetic secure computation with oblivious transfer,” in Proc. 2016 ACM SIGSAC Conference on Computer and Communications Security, ACM, New York, NY, USA, pp. 830-842, 2016.
  * [46] R. Cramer, I. Damgård, D. Escudero, D. Escudero, P. Scholl and C. P. Xing, “SPD $\mathbb{Z}_{2^{k}}$ : Efficient MPC mod $2^{k}$ for Dishonest Majority,” in Proc/ Annual International Cryptology Conference, Springer, Cham, pp. 769-798, 2018.
  * [47] M. Keller, V. Pastro and D. Rotaru, “Overdrive: Making SPDZ great again,” in Proc. Advances in Cryptology – EUROCRYPT 2018, Springer, Cham, pp. 158-189, 2018.
  * [48] D. Rathee, T. Schneider and K. K. Shukla, “Improved multiplication triple generation over rings via RLWE-based AHE,” in Proc. International Conference on Cryptology and Network Security, Springer, Cham, pp. 347-359, 2019.
  * [49] H. Chen, M. Kim, I. Razenshteyn, D. Rotaru, Y. S. Song and S. Wagh, “Maliciously secure matrix multiplication with applications to private deep learning,” in Proc. International Conference on the Theory and Application of Cryptology and Information Security, Springer, Cham, pp. 31-59, 2020.
  * [50] P. W. Shor, “Algorithms for quantum computation: Discrete logarithms and factoring,” in Proc. 35th Annual Symposium on Foundations of Computer Science, Los Alamitos, California, USA, pp. 124–134, 1994.