# Quantum Secure Protocols for Multiparty Computations

Tapaswini Mohanty, Vikas Srivastava, Sumit Kumar Debnath, Pantelimon Stănică
Tapaswini Mohanty is with the Department of Mathematics, National Institute of
Technology, Jamshedpur 831 014, India (e-mail: mtapaswini37@gmail.com). Vikas
Srivastava is with the Department of Mathematics, National Institute of
Technology, Jamshedpur 831 014, India (e-mail: vikas.math123@gmail.com). Sumit
Kumar Debnath is with the Department of Mathematics, National Institute of
Technology, Jamshedpur 831 014, India (e-mail<EMAIL_ADDRESS>sdebnath.math@nitjsr.ac.in). Pantelimon Stănică is with the Department of
Applied Mathematics, Naval Postgraduate School, Monterey, CA 93943, USA;
(email: pstanica@nps.edu).

###### Abstract

Secure multiparty computation (MPC) schemes allow two or more parties to
conjointly compute a function on their private input sets while revealing
nothing but the output. Existing state-of-the-art number-theoretic-based
designs face the threat of attacks through quantum algorithms. In this
context, we present secure MPC protocols that can withstand quantum attacks.
We first present the design and analysis of an information-theoretic secure
oblivious linear evaluation (OLE), namely qOLE in the quantum domain, and show
that our qOLE is safe from external attacks. In addition, our scheme satisfies
all the security requirements of a secure OLE. We further utilize qOLE as a
building block to construct a quantum-safe multiparty private set intersection
(MPSI) protocol.

###### Index Terms:

quantum computing, multiparty computation, private set intersection, oblivious
linear evaluation

##  I Introduction

Secure multiparty computation (MPC) is crucial in safeguarding sensitive data.
It allows two or more parties to jointly do the calculations on their private
data without revealing anything but the output. Thus, MPC guarantees security
features like privacy and confidentiality. The oblivious evaluation of a
function is one of the most important primitives in cryptographic designs. In
the work of Rabin [1], the idea of oblivious transfer (OT) was introduced. OT
considers the setting where there are two parties: sender and receiver. The
sender has two bits $s_{0}$ and $s_{1}$, and the receiver can only learn one
of the bits $s_{b}$ depending on his choice of bit $b$. Later, it was shown in
[2] that OT can be used for oblivious evaluation of any cryptographic
function. Over the past three decades, considerable advancements have been
made in the design of generic OT-based MPC protocols. However, it is worth
noting that specific types of functions can be evaluated more efficiently
using direct constructions, bypassing the need for MPC. Considering this view,
Naor et al. [3] designed the oblivious polynomial evaluation (OPE). It is a
useful primitive which solves the problem of obliviously evaluating a
polynomial $P$ on an input $\alpha$. To be more precise, OPE is a two-party
protocol between two distrustful parties, where one party (say Bob) holds a
private polynomial $P(x)$, and another party (say Alice) has a private input
$\alpha$. The goal of a secure OPE protocol is that Alice obtains $P(\alpha)$
and nothing else while Bob learns nothing. Oblivious linear evaluation (OLE)
(which is just a special case of OPE) has been studied as an important
primitive in secure MPC schemes for garbled arithmetic circuits [4, 5].
Instead of obliviously evaluating a polynomial $P$, we restrict ourselves to a
linear function $f(x)=ax+b$ in OLE. As noted in [6], OLE can also be used as
an important building block in the design of Private Set Intersection (PSI)
and its variants. We aim to work on this line of research in the quantum
domain. PSI is an efficient and secure MPC protocol that facilitates clients
to compute the intersection of private sets, ensuring that the confidential
information of one party is not known to the others. Multiparty PSI (MPSI) is
a naturally generalized version of the PSI protocol employed to find common
elements in multiple sets without exposing and leaking information about the
data except for the intersection.

There exist many OLE and MPSI protocols [7, 8, 9, 10, 11, 12, 13, 14] but, as
known, their security relies on some number theoretic hardness assumptions
[15, 16, 17] such as integer factorization problem and discrete logarithm
problem. Because of Shor’s algorithm [18], these schemes face a huge security
threat, and once big enough quantum computers are available, these existing
state-of-the-art designs will become obsolete. It has led cryptographers
worldwide to find alternative ways to construct MPC protocols such as OLE and
MPSI. One line of research involves developing protocols based on mathematical
problems resistant to quantum attacks, forming what we call post-quantum
cryptography (PQC) [19, 20, 21]. However, PQC does not provide long-term
security. Quantum cryptography (QC) offers a logical solution to nullify the
future threat. It is because QC provides long-term protection and safety from
the threat of quantum attacks. Therefore, it is need of hour to make use of QC
for the construction of secure MPC protocols.

Related works: Several quantum two-party private set intersection (PSI)
protocols have been developed over the last decade. In 2016, Shi et al. [22]
introduced a quantum protocol for calculating the intersection of private
sets. However, their design had a vulnerability that allowed the server to
manipulate the intersection results unilaterally. To address this issue, Cheng
et al. [23] involved a passive third party in protocol [22] to ensure
fairness. Shi et al. [24] later designed a protocol for the oblivious set
member decision problem, which could be applied to private set intersection
and union. In 2018, Maitra et al. [25] proposed a two-party computation for
set intersections involving rational players. Recently, Debnath et al. [26,
27] developed quantum two-party PSI protocols that utilized single-photon
quantum resources, enhancing feasibility. Liu et al. [28] presented a novel
QPSI protocol based on the quantum Fourier transform, and an improved version
employing the Hadamard gate was later introduced by Liu et al. [29].
Furthermore, Liu et al. [30] developed a quantum private set intersection
cardinality (PSI-CA) protocol based on a bloom filter, and Wang et al. [31]
proposed a quantum protocol for PSI-CA and union cardinality using
entanglement swapping. Shi et al. [32] designed a quantum PSI-CA protocol with
privacy-preserving condition queries. In 2020, Liu et al. [33] introduced a
quantum secure MPSI-CA protocol utilizing quantum transformation,
measurements, and parallelism. Shi et al. [34] developed a novel quantum
protocol for MPSI-CA and provided corresponding quantum circuits, highlighting
the advantages of quantum computing parallelism and measurement randomness.
Mohanty et al. [35] designed a special variant of PSI (called threshold PSI)
which outputs an intersection if and only if the intersection size is greater
than a given threshold value. In 2023, Imran [36] proposed a quantum MPSI by
providing a framework for transforming the PSI problem into a problem of
computing the greatest common divisor (GCD). Additionally, in 2023 Shi et al.
[37] designed a scheme for XOR computation of multiple private bits. In the
following, they used it to create a secure multiparty logical AND, which in
turn was used to design a quantum secure MPSI.

Our contribution: The major contributions of this paper are the following:

  * •

We first present an efficient and information theoretic secure oblivious
linear evaluation (namely qOLE). To the best of our knowledge, there is only
one design of OLE (Santos et al. [38]) in the current-state-of-the-art of the
quantum domain. We show that our protocol is more efficient and practical
compared to [38]. qOLE involves three entities: Alice, Bob, and a third party
TP. It is made up of three phases, namely, key generation phase ( qOLE.Kg),
initialization phase (qOLE.Int), and computation phase (qOLE.Comp). Bob is in
possession of a private linear function $f(x)=ax+b$ defined over
$\mathbb{Z}_{p}$. On the other hand, Alice holds $\alpha\in\mathbb{Z}_{p}$ and
aims to obtain $f(\alpha)$, obliviously. In the key generation phase qOLE.Kg,
Alice, Bob, and TP shares secret keys with each other by utilizing a quantum
key distribution (QKD). In the initialization phase (qOLE.Int), TP selects a
random linear function $S(x)=a_{1}x+b_{1}$ and prepares the corresponding
quantum state $\ket{S(x)}$. The state $\ket{S(x)}$ is transferred to Bob in
the quantum encrypted form over a quantum channel. Additionally, TP randomly
selects $d$, computes $g=S(d)$, and sends the quantum encrypted forms of
$\ket{d}$ and $\ket{g}$ to Alice through quantum communication. In the final
computation phase (qOLE.Comp), Alice sends $l=\alpha-d$ to Bob. In the
following, Bob computes $V(x)=f(x+l)+S(x)$ and sends it to Alice. Ultimately,
Alice uses $V(x)$ to obtain $f(\alpha)$. All the communication between Alice
and Bob in the computation phase takes over a quantum communication channel.

  * •

Based on qOLE, we design a secure quantum protocol for MPSI (namely qMPSI).
qMPSI uses qOLE as the fundamental building block. Thus, we also show that
quantum secure OLEs can be used to design MPSI protocols. In fact, the design
of qMPSI is generic, in the sense that it can be instantiated with any
information theoretic secure OLE.

##  II Preliminaries

###  II-A Quantum Encryption

We describe in detail the procedure of the quantum one time pad (qOTP) [39]
among an encryptor Alice and decryptor Bob. It consists of three algorithms:
KeyGen, Enc and Dec which are discussed below:

  * •

$K\leftarrow KeyGen(n)$. On input a positive integer $n$ (length of message),
KeyGen outputs a $\kappa(\leq 2n)$ bit key $K$ which is shared between Alice
and Bob by using some quantum key distribution protocol (e.g., [40]).

  * •

$E_{K}(|P\rangle)\leftarrow Enc(|P\rangle,K)$. On input the quantum message
$|P\rangle=\otimes^{n}_{i=1}|p_{i}\rangle$ with
$|p_{i}\rangle=a_{i}|0\rangle+b_{i}|1\rangle$ and $|a_{i}|^{2}+|b_{i}|^{2}=1$,
and the key $K$, Alice encrypts the message $|P\rangle$ in the following way:

Computes $\otimes^{n}_{i=1}X^{K_{2i}}|p_{i}\rangle$, i.e., if the $(2i)$-th
bit of $K$ is $1$ then operates the unitary operator $X$ on the $i$-th qubit
of the message $|P\rangle$; otherwise does nothing, for $i=1,\ldots,n$.

Executes
$E_{K}(|P\rangle)=\otimes^{n}_{i=1}Z^{K_{2i-1}}X^{K_{2i}}|p_{i}\rangle$by
operating Z on the $i$-th qubit of $X^{K_{2i}}|p_{i}\rangle$ if the
$(2i-1)$-th bit of $K$ is $1$ for $i=1,\ldots,n$.

  * •

$|P\rangle\leftarrow Dec(E_{K}(|P\rangle))$. Bob decrypts $E_{K}(|P\rangle)$
by performing the following steps:

To get $X^{K_{2i}}|p_{i}\rangle$, operates the unitary operator $Z$ on the
$i$-th qubit of
$E_{K}(|P\rangle)=\otimes^{n}_{i=1}Z^{K_{2i-1}}X^{K_{2i}}|p_{i}\rangle$, if
the $(2i-1)$-th bit of $K$ is $1$, for $i=1,\ldots,n$.

Computes $|P\rangle$ by operating the unitary operator $X$ on the $i$-th qubit
of the $X^{K_{2i}}|p_{i}\rangle$, if the $(2i)$-th bit of $K$ is $1$, else
does nothing.

##  III Proposed Quantum Oblivious Linear Evaluation

We now discuss the design and analysis of quantum secure OLE (namely, qOLE).
The protocol qOLE involves three parties: Alice, Bob, and a third party TP,
and consists of three phases: key generation phase ( qOLE.Kg), initialization
phase (qOLE.Int), and computation phase (qOLE.Comp). Bob holds a private
linear function denoted by $f(x)=ax+b$ defined over $\mathbb{Z}_{p}$. Alice
has a private input $\alpha\in\mathbb{Z}_{p}$ and aims to obtain $f(\alpha)$,
obliviously. In the key generation phase qOLE.Kg, Alice, Bob, and TP share
secret keys with each other by utilizing a quantum key distribution (QKD). In
the next phase (qOLE.Int), TP selects a random linear function $S(x)$ and
sends it to Bob through the quantum channel. Additionally, TP randomly selects
$d$, computes $g=S(d)$, and sends $d$ and $g$ to Alice through quantum
communication. In the final computation phase (qOLE.Comp), Alice sends
$l=\alpha-d$ to Bob. In the following, Bob computes $V(x)=f(x+l)+S(x)$ and
sends it to Alice. Ultimately, Alice uses $V(x)$ to obtain $f(\alpha)$. All
the communication between Alice and Bob in the computation phase takes over a
quantum communication channel.

qOLE.Kg: In the key generation phase, TP shares the keys $K_{A}$, $K_{B}$ with
Alice and Bob, respectively, using a QKD (for example, see [40]). Similarly,
Alice and Bob also share a secret key $K_{AB}$ between themselves by utilizing
a QKD.

qOLE.Int: In this phase, the following steps are to be executed:

  1. 1.

In the initialization phase, TP randomly selects a linear function
$S(x)=a_{1}x+b_{1}$. For ease of notation, we write this polynomial as
$S(x)=(a_{1},b_{1})$. Let $\bar{a}_{1}$, $\bar{b}_{1}$ denote the bit strings
corresponding to $a_{1}$ and $b_{1}$ respectively. TP converts these bit
strings into qubits and prepares a quantum state
$|S(x)\rangle=(|\bar{a}_{1}\rangle,|\bar{b}_{1}\rangle)$ corresponding to the
linear function $S(x)$. Here, $|\bar{a}_{1}\rangle$ and $|\bar{b}_{1}\rangle$
are sequences of photons, i.e.,
$|\bar{a}_{1}\rangle=\\{|\bar{a}_{11}\rangle,\ldots,|\bar{a}_{1\log_{2}{p}}\rangle\\}$,
$|\bar{b}_{1}\rangle=\\{|\bar{b}_{11}\rangle,\ldots,|\bar{b}_{1\log_{2}{p}}\rangle\\}$
and $\bar{a}_{1j},\bar{b}_{1j}\in\\{0,1\\}$. TP encrypts $|S(x)\rangle$ using
quantum OTP with key $K_{B}$ and gets $|S^{\prime}(x)\rangle$.

  2. 2.

In the following, TP inserts some decoy particles (randomly chosen from
$\\{|0\rangle,|1\rangle,|+\rangle,|-\rangle\\}$) into $|S^{\prime}(x)\rangle$
and obtains $|S^{\prime\prime}(x)\rangle$. TP notes the position and initial
states of the decoy photons and sends $|S^{\prime\prime}(x)\rangle$ to Bob.

  3. 3.

TP randomly selects $d$ and computes $S(d)=g$ (say). TP first converts $d$ and
$g$ into binary string. Later, it prepares the quantum states $|d\rangle$ and
$|g\rangle$ corresponding to $d$ and $g$ respectively. In the following, it
encrypts $|d\rangle$ and $|g\rangle$ using quantum OTP with key $K_{A}$ and
gets $|d^{\prime}\rangle,|g^{\prime}\rangle$. TP also inserts some decoy
photons (randomly chosen from $\\{|0\rangle,|1\rangle,|+\rangle,|-\rangle\\}$)
into $|d^{\prime}\rangle,|g^{\prime}\rangle$ and gets
$|d^{\prime\prime}\rangle,|g^{\prime\prime}\rangle$. TP notes the position and
initial states of the decoy photons and sends $|d"\rangle,|g"\rangle$ to
Alice.

qOLE.Comp: The following steps are to be performed between Alice and Bob in
the computation phase:

  1. 1.

On receiving $|d^{\prime\prime}\rangle,|g^{\prime\prime}\rangle$, Alice first
checks for eavesdropping. TP provides the position and initial states of the
decoy particles. Alice aborts the protocol if the error rate exceeds the
predefined threshold value; otherwise, proceeds to the next step.

  2. 2.

Alice discards all decoy photons and gets
$|d^{\prime}\rangle,|g^{\prime}\rangle$. Then Alice decrypts
$|d^{\prime}\rangle,|g^{\prime}\rangle$ using $K_{A}$ and gets
$|d\rangle,|g\rangle$. Alice measures the quantum state and obtains $d,g$.

  3. 3.

Alice computes $l=\alpha-d$ and converts it into binary string and then into a
sequence of photons $|l\rangle$. She encrypts $|l\rangle$ using a quantum OTP
with $K_{AB}$. To avoid eavesdropping, she adds some decoy particles randomly
chosen from $\\{|0\rangle,|1\rangle,|+\rangle,|-\rangle\\}$ into
$|l^{\prime}\rangle$, and obtains $|l^{\prime\prime}\rangle$. Alice notes the
position and initial states of the decoy particles, and sends
$|l^{\prime\prime}\rangle$ to Bob.

  4. 4.

On receiving $|S^{\prime\prime}(x)\rangle$ from TP, Bob and TP checks for
eavesdropping; if the error rate exceeds the predefined threshold value then
they abort the protocol; otherwise, they proceed to the next step. Bob also
checks for eavesdropping with Alice. If the error rate exceeds a predefined
threshold then they abort the protocol, otherwise they proceed to the next
step. Bob discards all decoy photons from $|S^{\prime\prime}(x)\rangle$,
$|l^{\prime\prime}\rangle$ and gets $|S^{\prime}(x)\rangle$,
$|l^{\prime}\rangle$. Bob decrypts $|S^{\prime}(x)\rangle$,
$|l^{\prime}\rangle$ using keys $K_{B}$, $K_{AB}$, respectively, and gets
$|S(x)\rangle$, $|l\rangle$. He measures the state $|S(x)\rangle$, $|l\rangle$
using a computational basis and obtains $S(x)$ and $l$.

  5. 5.

Bob computes $V(x)=f(l+x)+S(x)$. He converts $V(x)$ sequence of photons
$|V(x)\rangle$. In the following, $|V(x)\rangle$ is encrypted using a quantum
OTP with key $K_{AB}$ to produce $|V^{\prime}(x)\rangle$. Bob inserts some
decoy photons from $\\{|0\rangle,|1\rangle,|+\rangle,|-\rangle\\}$ into
$|V^{\prime}\rangle$ and prepares $|V^{\prime\prime}\rangle$. Finally,
$|V^{\prime\prime}\rangle$ is sent to Alice.

  6. 6.

On receiving $|V^{\prime\prime}\rangle$ from Bob, Alice checks for
eavesdropping. If the error rate is more than the the threshold, she aborts
the protocol; otherwise, she proceeds. After discarding all the decoy photons
from $|V^{\prime\prime}(x)\rangle$, she obtains $|V^{\prime}(x)\rangle$. Alice
decrypts $|V^{\prime}(x)\rangle$ using the key $K_{AB}$ to get $|V(x)\rangle$.
Now $|V(x)\rangle$ is measured using the computational basis to obtain $V(x)$.
Next, Alice computes $V(d)-g=f(l+d)+S(d)-g=f(\alpha)$.

Correctness: It is very easy to see that qOLE is correct, i.e., at the end of
the protocol Alice correctly obtains $f(\alpha)$. This follows because

$\displaystyle V(d)-g$ $\displaystyle=f(l+d)+S(d)-g$
$\displaystyle=f(\alpha-d+d)+S(d)-g$ $\displaystyle=f(\alpha)+g-g$
$\displaystyle=f(\alpha).$

###  III-A Toy Example

Let $p=8$ and suppose Bob uses $f(x)=2x+3$ and Alice picks
$\alpha=4\in\mathbb{Z}_{8}$. Assume that TP shares $K_{A}=011101010011$ with
Alice and $K_{B}=101001110001$ with Bob. Let the secret key of Alice and Bob
be $K_{AB}=111001000101$. TP chooses $S(x)=3x+1$ randomly. He picks $d=2$ and
computes $g=S(d)=7$.

Note that, $a_{1}=3$, $b_{1}=1$ so $\bar{a}_{1}=011$, $\bar{b}_{1}=001$,
therefore,
$|S(x)\rangle=|0\rangle|1\rangle|1\rangle,|0\rangle|0\rangle|1\rangle$. Now,
$|S^{\prime}(x)\rangle=E_{K_{B}}(|S(x)\rangle)=Z^{1}X^{0}(|0\rangle)Z^{1}X^{0}(|1\rangle)Z^{0}X^{1}(|1\rangle)Z^{1}X^{1}(|0\rangle)Z^{0}X^{0}(|0\rangle)Z^{0}X^{1}(|1\rangle)$.
i.e.,
$|S^{\prime}(x)\rangle=|0\rangle(-|1\rangle)|0\rangle(-|1\rangle)|0\rangle|0\rangle$.
Suppose that decoy particles are added at the $2^{nd},5^{th},6^{th}$ and
$9^{th}$ positions. Let
$|S^{\prime\prime}(x)\rangle=|0\rangle|+\rangle(-|1\rangle)|0\rangle|0\rangle|-\rangle(-|1\rangle)|0\rangle|0\rangle|0\rangle$.

Note that
$|d\rangle,|g\rangle=|0\rangle|1\rangle|0\rangle,|1\rangle|1\rangle|1\rangle$
so
$|d^{\prime}\rangle,|g^{\prime}\rangle=E_{K_{A}}(|d\rangle,|g\rangle)=Z^{0}X^{1}(|0\rangle)Z^{1}X^{1}(|1\rangle)Z^{0}X^{1}(|0\rangle)Z^{0}X^{1}(|1\rangle)Z^{0}X^{0}(|1\rangle)Z^{1}X^{1}(|1\rangle)$
i.e.,
$|d^{\prime}\rangle,|g^{\prime}\rangle=|1\rangle|0\rangle|1\rangle,|0\rangle|1\rangle|0\rangle$.
Let the positions of the decoy photons be $1,2,6$ and $9$. Therefore,
$|d^{\prime\prime}\rangle,|g^{\prime\prime}\rangle=|1\rangle|1\rangle|1\rangle|0\rangle|1\rangle|+\rangle|0\rangle|1\rangle|+\rangle|0\rangle$.
On receiving $|S^{\prime\prime}(x)\rangle$ from TP, Bob checks for
eavesdropping and discards all the decoy photons. After this step, Bob gets
$|S^{\prime}(x)\rangle=|0\rangle(-|1\rangle)|0\rangle(-|1\rangle)|0\rangle|0\rangle$.
Later, he computes
$|S(x)\rangle$=$D_{K_{B}}(|S(x)\rangle)=$
$X^{0}Z^{1}(|0\rangle)X^{0}Z^{1}(-|1\rangle)X^{1}Z^{0}(|0\rangle)\\\
X^{1}Z^{1}(-|1\rangle)X^{0}Z^{0}(|0\rangle)X^{1}Z^{0}(|0\rangle)$, i.e.,
$|S(x)\rangle=|0\rangle|1\rangle|1\rangle|0\rangle|0\rangle|1\rangle$. After
measurement, Bob gets $\bar{a}_{1}=011$, $\bar{b}_{1}=001$, i.e., $S(x)=3x+1$.

On receiving $|d^{\prime\prime}(x)\rangle,|g^{\prime\prime}\rangle$ from TP,
Alice checks for eavesdropping and discards all the decoy photons. Alice gets
$|d^{\prime}\rangle,|g^{\prime}\rangle=|1\rangle|0\rangle|1\rangle,|0\rangle|1\rangle|0\rangle$.
In the next step, Alice computes
$|d\rangle,|g\rangle=D_{K_{A}}(|d^{\prime}\rangle,|g^{\prime}\rangle)=X^{1}Z^{0}(|1\rangle)X^{1}Z^{1}(|0\rangle)X^{1}Z^{0}(|1\rangle),X^{1}Z^{0}(|0\rangle)X^{0}Z^{0}(|1\rangle)X^{1}Z^{1}(|0\rangle)$
i.e.,
$|d\rangle,|g\rangle=|0\rangle|1\rangle|0\rangle,|1\rangle|1\rangle|1\rangle$.
Alice does the measurements and obtains $d=2$, and $g=7$. Now Alice computes
$l=\alpha-d=2$, converts it into qubits and gets
$|l\rangle=|0\rangle|1\rangle|0\rangle$. Alice computes
$|l^{\prime}\rangle=E_{K_{AB}}(|l\rangle)=Z^{1}X^{1}(|0\rangle)Z^{1}X^{0}(|1\rangle)Z^{0}X^{1}(|0\rangle)$
i.e.,$|l^{\prime}\rangle=(-|1\rangle)(-|1\rangle)|1\rangle$. Let the positions
of the decoy photons be $1,2$ and $4$, then
$|l^{\prime\prime}\rangle=|+\rangle|-\rangle(-|1\rangle)|0\rangle(-|1\rangle)|1\rangle$
Alice sends $|l^{\prime\prime}\rangle$ to Bob.

Bob checks for eavesdropping and discards all decoy photons and gets
$|l^{\prime}\rangle=(-|1\rangle)(-|1\rangle)|1\rangle$. Bob computes
$|l\rangle=D_{K_{AB}}(|l^{\prime}\rangle)=X^{1}Z^{1}(-|1\rangle)X^{0}Z^{1}(-|1\rangle)X^{1}Z^{0}(|1\rangle)$,
i.e., $|l\rangle=|0\rangle|1\rangle|0\rangle$. He measures the quantum state
and gets $l=2$. Now Bob computes
$V(x)=f(l+x)+S(x)=f(2+x)+3x+1=2(2+x)+3+3x+1=5x$ convert it into qubits
$|V(x)\rangle=|1\rangle|0\rangle|1\rangle|0\rangle|0\rangle|0\rangle$,
computes
$|V^{\prime}(x)\rangle=E_{K_{AB}}(|V(x)\rangle)=Z^{1}X^{1}(|1\rangle)Z^{1}X^{0}(|0\rangle)Z^{0}X^{1}(|1\rangle)Z^{0}X^{0}(|0\rangle)Z^{0}X^{1}(|0\rangle)Z^{0}X^{1}(|0\rangle)$,
i.e.,
$|V^{\prime}(x)\rangle=|0\rangle|0\rangle|0\rangle|0\rangle|1\rangle|1\rangle$.
Let the positions of the decoy photons be $3,4,5$, and $8$, then
$|V^{\prime\prime}(x)\rangle=|0\rangle|0\rangle|0\rangle|1\rangle|0\rangle|0\rangle|0\rangle|+\rangle|1\rangle|1\rangle$.
Bob send $|V^{\prime\prime}(x)\rangle$ to Alice.

On receiving $|V^{\prime\prime}(x)\rangle$ from Bob, Alice checks for
eavesdropping and discards all the decoy photons. Alice gets
$|V^{\prime}(x)\rangle=|0\rangle|0\rangle|0\rangle|0\rangle|1\rangle|1\rangle$.
Now, she computes
$|V(x)\rangle=D_{K_{AB}}(|V^{\prime}(x)\rangle)=X^{1}Z^{1}(|0\rangle)X^{0}Z^{1}(|0\rangle)X^{1}Z^{0}(|0\rangle)X^{0}Z^{0}(|0\rangle)X^{1}Z^{0}(|1\rangle)X^{1}Z^{0}(|1\rangle)$
i.e., $|V(x)\rangle=|1\rangle|0\rangle|1\rangle|0\rangle|0\rangle|0\rangle$
Alice measures and gets $V(x)=5x$. Finally, she computes
$V(d)-g=V(2)-7=2-7=-5\equiv 3\pmod{8}$ to obtain $f(\alpha=4)=3$.

###  III-B Security Analysis

####  III-B1 External attacks

In this setting, an external attacker wants to obtain some information
$\alpha$, $f(x)$, or $f(\alpha)$ by interfering the communication channel. The
attacker only gets $|S^{\prime\prime}(x)\rangle$,
$|d^{\prime\prime}\rangle,|g^{\prime\prime}\rangle$,
$|l^{\prime\prime}\rangle$, and $|V^{\prime\prime}(x)\rangle$. As the attacker
does not know the actual position of the decoy particles, he therefore cannot
obtain $|S^{\prime}(x)\rangle$, $|d^{\prime}\rangle,|g^{\prime}\rangle$,
$|l^{\prime}\rangle$, and $|V^{\prime}(x)\rangle$.

We now discuss the situation when an attacker applies the  entangled
measurement attack on a decoy photon, say
$|\phi\rangle\in\\{|0\rangle,|1\rangle,|+\rangle,|-\rangle\\}$. On receiving
the decoy particle $|\phi\rangle$ he prepares an ancillary qubit
$|0\rangle_{a}$ and operates an oracle operator
$\mathcal{U}_{f}|x\rangle|y\rangle\mapsto|x\rangle|y\oplus f(x)\rangle$.

Case I:

If $|\phi\rangle$ is $|0\rangle$ or $|1\rangle$,

$\displaystyle\mathcal{U}_{f}|\phi\rangle|0\rangle_{a}=\begin{cases}|0\rangle|f(0)\rangle_{a}&\text{if
$|\phi\rangle=|0\rangle$,}\\\ |1\rangle|f(1)\rangle_{a}&\text{if
$|\phi\rangle=|1\rangle$.}\end{cases}$

Case II:

If $|\phi\rangle$ is $|+\rangle$ or $|-\rangle$,

$\displaystyle\mathcal{U}_{f}|\phi\rangle|0\rangle_{a}=$
$\displaystyle\frac{\mathcal{U}_{f}|0\rangle|0\rangle_{a}\pm\mathcal{U}_{f}|1\rangle|0\rangle_{a}}{\sqrt{2}}$
$\displaystyle=$
$\displaystyle\frac{1}{\sqrt{2}}{\frac{|0\rangle\pm|1\rangle}{\sqrt{2}}\otimes\frac{|f(0)\rangle_{a}\pm|f(1)\rangle_{a}}{\sqrt{2}}}.$

By the above analysis, we see that if
${|\phi\rangle}\in\\{|0\rangle,|1\rangle\\}$, then the external attacker can
guess correctly, but if ${|\phi\rangle}\in\\{|+\rangle,|-\rangle\\}$, then the
success probability is $\frac{1}{2}$. In addition, all these photons are non
orthogonal so these states are indistinguishable. Therefore, an outsider fails
to obtain any information.

Intercept and resend attack: During these kinds of attacks, an adversary
intercepts and resends the sequence of photons
$|\bar{S^{\prime\prime}}(x)\rangle$ to Bob by intercepting the stream of
photons $|S^{\prime\prime}(x)\rangle$ sent by TP to Bob. TP had added the
decoy photons before sending $|S^{\prime\prime}(x)\rangle$ to Bob. Now, the
adversary is unaware of the actual position and the state of decoy photons.
Note that decoy photons are randomly chosen out of
$\\{|0\rangle,|1\rangle,|+\rangle,|-\rangle\\}$. Therefore, any external
interception can be detected with a probability $1-(\frac{3}{4})^{\delta}$.
When $\delta\ggg 0$, the probability of detecting an eavesdropping converges
to $1$.

Trojan Horse attacks: qOLE may be susceptible to two types of Trojan horse
attacks: delayed photon attacks and invisible photon attacks. These attacks
involve manipulating photons during transmission to compromise the security of
the protocol. To counter these attacks, participants can incorporate specific
quantum optical devices, such as wavelength quantum filters and photon number
splitters, during the protocol execution. To address the issue of invisible
photons that may arise during transmission, a wavelength quantum filter can be
employed to filter out these photons, ensuring that only legitimate photons
are considered. Similarly, for delayed photons that may be present, photon
number splitters can be utilized to split each legitimate photon, thereby
detecting any delayed photons. This enables the participants to identify and
mitigate the effects of delayed photon attacks.

####  III-B2 Internal Attack

To consider internal attacks, we assume that qOTP is information theoretic
secure [39]. In addition, the following results hold.

######  Theorem 1.

Alice cannot obtain $f(x)$.

###### Proof.

Alice cannot obtain $f(x)$ because of two reasons. Firstly, she does not know
the actual position of decoy particles. Secondly, the computation of $f(x)$
requires the knowledge of $S(x)$, but she cannot obtain $S(x)$, since
obtaining $S(x)$ from $|S^{\prime\prime}(x)\rangle$ implies a break in the
information theoretic security of qOTP. ∎

######  Theorem 2.

Bob cannot obtain $\alpha$ and $f(\alpha)$.

###### Proof.

Similar to the prior theorem, Bob can not obtain $\alpha$ and $f(\alpha)$
because of two reasons. Firstly, he also does not know the actual position of
decoy particles. Secondly, the computation of $\alpha$ and $f(\alpha)$
requires the knowledge of $d$ and $g$. It is not possible to obtain any
information about $d$ and $g$ because gaining any knowledge about $d$ and $g$
from $|d^{\prime\prime}\rangle$ and $|g^{\prime\prime}\rangle$ implies a break
in the information theoretic security of qOTP. ∎

######  Theorem 3.

TP cannot obtain $f(x)$, $\alpha$, and $f(\alpha)$.

###### Proof.

To obtain any knowledge $f(x)$, $\alpha$, and $f(\alpha)$, TP needs
information about $V(x)$ and $l$. The information theoretic security of qOTP
makes it impossible for TP to obtain $V(x)$ and $l$ from
$|V^{\prime\prime}(x)\rangle$ and $|l^{\prime\prime}\rangle$.∎

###  III-C Efficiency and Comparison

In this section, we will discuss the communication and computational overhead
of our proposed design qOLE. The linear function $f(x)=ax+b$ is defined over
$\mathbb{Z}_{p}$. TP sends $2\log_{2}{p}$ qubits to Bob and sends
$\log_{2}{p}$ qubits to Alice. In addition, Alice sends $\log_{2}{p}$ qubits
to Bob and Bob sends $\log_{2}{p}$ qubits to Alice. Therefore, the total
communication cost is $\mathcal{O}(\log_{2}{p})$. We now discuss the quantum
computation required for the execution of qOLE. A total of
$\mathcal{O}(\log_{2}{p})$ qubits are needed to be prepared by Alice, Bob and
TP. In addition, Pauli operators $X$ and $Z$ are used for doing the quantum
computation. Projective measurements of $\mathcal{O}(\log_{2}{p})$ single
qubits are required during the initialization and computation phase.

To the best of our knowledge, there is only one OLE protocol in the quantum
domain. Santos et al. [38] in 2022 developed the first OLE protocol in the
quantum domain. Similar to qOLE, [38] does not rely on quantum oblivious
transfer. Unlike qOLE, the design presented in [38] uses high-dimensional
quantum states to obliviously compute the linear function $f(x)$. qOLE in
contrast used only single photons which are very easy to prepare and operate.
[38] utilize the Heisenberg-Weyl operators, while qOLE only needs two
dimensional quantum gates like $X$ gate and $Z$ gate. To summarize, qOLE is
more practical and efficient when compared to the design presented in [38].
qOLE only uses single photons quantum resources, and thus, has the potential
to be implemented in the near future. A comparative summary of qOLE with [38]
is given in Table I.

Protocols |  Quantum Resources |  Quantum Operators |  Quantum
Measurements |  Security
---|---|---|---|---
Santos et al. [38] |  higher dimensional quantum states |  Heisenberg-Weyl operators |  Projective measurements in $d$-dimension Hilbert space |  Quantum
UC-security
This protocol |  $2$-dimensional quantum states |  $2$-dimensional $X$ and $Z$ gate |  Projective measurements in $2$-dimension Hilbert space |  Information theoretic security
TABLE I: Comparative summary of qOLE

##  IV Proposed Quantum MPSI

In this section, we present the construction and analysis of an MPSI protocol
(namely, qMPSI) in the quantum domain. Our design utilizes the OLE protocol
(qOLE) described in Section III. We first give a high level overview of the
protocol, followed by a detailed explanation.
A high level overview. In the design of qMPSI, there are $m$ parties
$A_{1},A_{2}\ldots A_{m}$, each having private sets
$S_{A_{1}},S_{A_{2}},\ldots,S_{A_{m}}$, respectively. These sets are defined
over $\mathbb{Z}_{p}$ with $|S_{A_{j}}|=n$. In the preparation stage, each
$A_{i}$ forms a polynomial corresponding to their private sets. Without loss
of generality, we set $A_{1}$ to be initiator of the protocol. At the end of
the execution of qMPSI, $A_{2}$ computes the desired intersection and
announces it for everybody. We assume that all the parties involved in our
protocol are semi-honest.

qMPSI.PrepStage: There are $m$ parties $A_{1},A_{2},\ldots,A_{m}$ with private
sets $S_{A_{1}},S_{A_{2}},\ldots,S_{A_{m}}$. Corresponding to their private
sets $S_{A_{j}}$, each of the $A_{j}$ define a polynomial $P_{A_{j}}$ of
degree $n$ such that $P_{A_{j}}(\gamma)=0$ for all $\gamma\in S_{A_{j}}$. Let
$Z$ be the set of all zeros of polynomials
$P_{A_{1}},P_{A_{2}},\ldots,P_{A_{m}}$ and $\mathcal{S}$ be the set of
polynomials whose zeros are not in $Z$. Next, each party $A_{j}$,
$j=1,2,\ldots,m$, randomly chooses polynomials $r_{A_{j}},r_{j}\in\mathcal{S}$
of degree at most $n$. The sets $A_{j}$, $j=1,2,\ldots,m$, mask their private
polynomial $P_{A_{j}}$ with $r_{A_{j}}$ and gets $P^{\prime}_{A_{j}}$ .
$A_{1}$ chooses a polynomial $u_{A_{1}}$ of degree $n$, computes
$P_{1}=P^{\prime}_{A_{1}}+u_{A_{1}}$. $A_{1},A_{2},\ldots,A_{m}$, and selects
$\alpha_{1},\alpha_{2},\ldots,\alpha_{3n+1}$.

qMPSI.Intersection: The following steps are performed to compute the
intersection:

  1. 1.

$A_{1}$ and $A_{2}$ jointly execute the qOLE protocol with the help of TP. The
input of $A_{1}$ and $A_{2}$ to qOLE is $(P^{i}_{1},r^{i}_{1})$ and $P^{\prime
i}_{A_{2}}$, respectively. The output of the protocol is $P^{i}_{2}={P^{\prime
i}_{A_{2}}}{r^{i}_{1}}+P^{i}_{1}$, where $P^{\prime
i}_{A_{2}}=P^{\prime}_{A_{2}}(\alpha_{i})$, $P^{i}_{1}=P_{1}(\alpha_{i})$ and
$r^{i}_{1}=r_{1}(\alpha_{i})$. $A_{1}$ and $A_{2}$ execute qOLE protocol, for
$i=1,2,\ldots,3n+1$.

  2. 2.

For $j=3,\ldots,m$, similarly, $A_{j-1}$ and $A_{j}$ jointly execute the qOLE
protocol with the help of TP. The input of $A_{i-1}$ to qOLE is
$(P^{i}_{j-1},r^{i}_{j-1})$ while the input of $A_{j}$ to qOLE is $P^{\prime
i}_{A_{j}}$. The output of the protocol is $P^{i}_{j}={P^{\prime
i}_{A_{j}}}{r^{i}_{j-1}}+P^{i}_{j-1}$, where $P^{\prime
i}_{A_{j}}=P^{\prime}_{A_{j}}(\alpha_{i})$, $P^{i}_{j-1}=P_{j-1}(\alpha_{i})$
and $r^{i}_{j-1}=r_{j-1}(\alpha_{i})$. $A_{j-1}$ and $A_{j}$ execute this qOLE
protocol for $i=1,2,\ldots,3n+1$.

  3. 3.

$A_{2},A_{3},\ldots,A_{m}$ share a common polynomial $u$ with each other.

  4. 4.

$A_{m}$ computes $R^{i}=P^{i}_{m}+u^{i}={P^{\prime
i}_{A_{m}}}{r^{i}_{m-1}}+P^{i}_{m-1}+u^{i}$, for $i=1,2,\ldots,3n+1$, where
$u^{i}=u(\alpha_{i})$ and sends the resulting values to $A_{1}$.

  5. 5.

$A_{1}$ subtract $u^{i}_{A_{1}}$ from $R^{i}$, for all $i=1,2,\ldots,3d+1$ and
sends it to $A_{2}$. $A_{2}$ subtracts $u^{i}$ for all $i=1,2,\ldots,3n+1$ and
interpolates these $3n+1$ points and gets the desired intersection polynomial
$P_{\cap}$. At the end of the protocol, $A_{2}$, outputs all $\gamma\in
S_{A_{2}}$ for which $P_{\cap}(\gamma)=0$. $A_{2}$ announces the intersection.

###  IV-A Correctness

The correctness of qMPSI follows in a straightforward manner from the
correctness of qOLE. $A_{2}$ received $R^{i}-u^{i}_{A_{1}}$ with
$i=1,2,\ldots,3n+1$ from $A_{1}$. $A_{2}$ subtracts $u^{i}$ for all
$i=1,2,\ldots,3n+1$ and interpolates these $3n+1$ points and gets the desired
intersection polynomial $P_{\cap}$, where

$\displaystyle P_{\cap}$
$\displaystyle=P_{A_{m}}r_{A_{m}}r_{m-1}+P_{A_{m-1}}r_{A_{m-1}}r_{m-2}$
$\displaystyle\qquad+\cdots+P_{A_{2}}r_{A_{2}}r_{1}+P_{A_{1}}r_{A_{1}}.$

We know that $P_{A_{j}}$, for $j=1,2,\ldots,m$ is the polynomial corresponding
to the set $S_{A_{j}}$, for $j=1,2,\ldots,m$, i.e., for $j=1,2,\ldots,m$ if
$x\in S_{A_{j}}$, then $P_{A_{j}}(x)=0$ and $r_{A_{j}}$, $r_{j}$ are nonzero
and belongs to $Z$, for all $j=1,2,\ldots,m$.

If $x\in S_{A_{1}}\cap S_{A_{2}}\cap\ldots\cap S_{A_{m}}$, then $x\in
S_{A_{j}}$ for all $j=1,2,\ldots,m$, so $P_{A_{j}}(x)=0$ for all
$j=1,2,\ldots,m$, which renders $P_{\cap}(x)=0$.

If $P_{\cap}(x)=0$, then
$[P_{A_{m}}r_{A_{m}}r_{m-1}+P_{A_{m-1}}r_{A_{m-1}}r_{m-2}+\cdots+P_{A_{2}}r_{A_{2}}r_{1}+P_{A_{1}}r_{A_{1}}](x)=0$,
so $P_{A_{j}}(x)=0$ for all $j=1,2,\ldots,m$ as for $j=1,2,\ldots,m$,
$r_{A_{j}}(x)\neq 0$ and $r_{j}(x)\neq 0$, and therefore $x\in S_{A_{j}}$ for
all $j=1,2,\ldots,m$ i.e., $x\in S_{A_{1}}\cap S_{A_{2}}\cap\ldots\cap
S_{A_{m}}$.

###  IV-B Security Analysis

######  Theorem 4.

$A_{1}$ cannot learn anything about the private sets of other parties.

###### Proof.

$A_{1}$ has $P_{A_{1}}$, $r_{A_{1}}$, $u_{A_{1}}$, $P_{1}$, and $r_{1}$. At
the end, $A_{m}$ sends
$P^{i}_{m}=P^{i}_{A_{m}}r^{i}_{A_{m}}r^{i}_{m-1}+P^{i}_{A_{m-1}}r^{i}_{A_{m-1}}r^{i}_{m-2}+\cdots+P^{i}_{A_{2}}r^{i}_{A_{2}}r^{i}_{1}+P^{i}_{A_{1}}r^{i}_{A_{1}}+u^{i}_{A_{1}}+u^{i}$,
for $i=1,2\ldots,3n+1$ to $A_{1}$. $A_{1}$ subtracts
$P^{i}_{A_{1}}r^{i}_{A_{1}}+u^{i}_{A_{1}}$ from $P^{i}_{m}$, for
$i=1,2,\ldots,3n+1$ and gets
$P^{i}_{A_{m}}r^{i}_{A_{m}}r^{i}_{m-1}+P^{i}_{A_{m-1}}r^{i}_{A_{m-1}}r^{i}_{m-2}+\cdots+P^{i}_{A_{2}}r^{i}_{A_{2}}r^{i}_{1}+u^{i}$,
for $i=1,2,\ldots,3n+1$. Since $A_{1}$ does not know $u^{i}$ for
$i=1,2,\ldots,3n+1$, therefore $A_{1}$ cannot get any information about the
private set of other parties and also cannot obtain the intersection
polynomial for computing the intersection $S_{A_{2}}\cap
S_{A_{3}}\cap\ldots\cap S_{A_{m}}$.

∎

######  Theorem 5.

qMPSI protocol is collusion resistant provided $A_{1}$ and $TP$ are non-
collusive parties.

###### Proof.

Suppose $A_{2},A_{3},\ldots,A_{k-1},A_{k+1},\ldots,A_{m}$ want to know some
information about the private set $S_{A_{k}}$ of $A_{k}$. If they can extract
$P^{i}_{A_{k}}$ for all $i=1,2,\ldots,3n+1$, they can get $P_{A_{k}}$ and from
$P_{A_{k}}$ they may obtain $S_{A_{k}}$. From
$P^{i}_{m}=P^{i}_{A_{m}}r^{i}_{A_{m}}r^{i}_{m-1}+P^{i}_{A_{m-1}}r^{i}_{A_{m-1}}r^{i}_{m-2}+\cdots+P^{i}_{A_{2}}r^{i}_{A_{2}}r^{i}_{1}+P^{i}_{A_{1}}r^{i}_{A_{1}}+u^{i}_{A_{1}}+u^{i}$
they subtract their inputs and gets
$P^{i}_{A_{k}}r^{i}_{A_{k}}r^{i}_{k-1}+P^{i}_{A_{1}}r^{i}_{A_{1}}+u^{i}_{A_{1}}+u^{i}$
for all $i=1,2,\ldots,3n+1$. As they only know $r^{i}_{k-1}$ for all
$i=1,2,\ldots,3n+1$, therefore cannot obtain $P^{i}_{A_{k}}$ for any
$i=1,2,\ldots,3n+1$. Hence, they cannot obtain any information about the
private set of $A_{k}$. ∎

######  Theorem 6.

TP cannot get any information about the private set of any party.

###### Proof.

TP only initializes the qOLE protocol. We already showed that any external
party cannot obtain anything about anyone’s private set and TP cannot obtain
any information during the qOLE protocol. When $A_{m}$ sends
$P^{i}_{m}=P^{i}_{A_{m}}r^{i}_{A_{m}}r^{i}_{m-1}+P^{i}_{A_{m-1}}r^{i}_{A_{m-1}}r^{i}_{m-2}+\cdots+P^{i}_{A_{2}}r^{i}_{A_{2}}r^{i}_{1}+P^{i}_{A_{1}}r^{i}_{A_{1}}+u^{i}_{A_{1}}+u^{i}$
to $A_{1}$ and $A_{1}$ sends
$P^{i}_{A_{m}}r^{i}_{A_{m}}r^{i}_{m-1}+P^{i}_{A_{m-1}}r^{i}_{A_{m-1}}r^{i}_{m-2}+\cdots+P^{i}_{A_{2}}r^{i}_{A_{2}}r^{i}_{1}+P^{i}_{A_{1}}r^{i}_{A_{1}}+u^{i}$
to $A_{2}$, TP may intercept to gain the intersection of the private sets of
$A_{1},A_{2},\ldots,A_{m}$. Since TP does not know $u^{i}_{A_{1}}$ and $u^{i}$
for any $i=1,2,\ldots.3n+1$, therefore it obtains nothing about the private
sets or intersection of the private sets. ∎

###  IV-C Efficiency Analysis and Comparison

In this section, we will discuss the communication and computational overhead
of our proposed design qMPSI. The private polynomials are defined over
$\mathbb{Z}_{p}$. qOLE protocol is used as a building block in the deisgn of
qMPSI. qOLE is executed $(m-1)(3n+1)$ number of times during the execution of
qMPSI, where $m$ is the number of parties and $n$ is the size of the private
set. Therefore, the communication and computation costs of qMPSI are
$\mathcal{O}(mn\log_{2}{p})$ and $\mathcal{O}(mn\log_{2}{p})$, respectively.

To the best of our knowledge, there are two MPSI protocol in the quantum
domain. Shi et al. [37] in 2023 developed a quantum MPSI which ensures perfect
security. Shi et al. [37] introduced a semi-honest edge server and two non-
collusive fog nodes, and design a secure and feasible edge-assisted quantum
protocol for MPSI. The design of [37] utilized secure multiparty XOR and
secure multiparty logical AND. Imran et al. [36] also designed a secure MPSI
in the quantum domain. It uses exact the quantum period-finding algorithm
(EQPA) as a subroutine. They constructed a quantum multiparty private set
intersection (PSI) by transforming the PSI problem into the problem of
computing the GCD. The protocol given in [36] uses rather complicated quantum
operators. Since it uses Shor’s algorithm and other quantum heavy resources,
it is not practical to realize on a large scale with existing quantum
computing hardware capabilities. The communication complexity of [36] is
higher than the communication complexity of qMPSI. The design of [37] is
comparable to the design of qMPSI in terms of quantum resources used and
quantum operators employed. Also, qMPSI has a slight edge over [37] in
communication complexity. The communication complexity of [37] increases at a
quadratic rate in terms of the number of parties involved. qMPSI is based on
qOLE which is seen as a more fundamental building block for secure multiparty
computation. qMPSI is generic in the sense that any quantum secure OLE can be
used to instantiate the protocol. The results of the comparison are summarized
in Table II.

Protocols |  Quantum resources |  Quantum operators |  Quantum measurements |  Quantum Communication cost
---|---|---|---|---
[36] |  Shor’s algorithm quantum resources |  Quantum Fourier transforms and CNOT gate |  Projective measurements in higher dimensional |  $\mathcal{O}(m^{2}(\log_{2}{p})^{2})$
[37] |  Single qubits photons |  single qubit $P$ gate and $H$ gate |  Projective measurements in $2$ -dimension Hilbert space |  $\mathcal{O}(m^{2}n)$
qMPSI |  Single qubit photons |  single qubit $X$ gate and $Z$ gate |  Projective measurements in $2$-dimension Hilbert space |  $\mathcal{O}(mn\log_{2}{p})$
TABLE II: Comparative summary of qMPSI

##  V Conclusion

In this paper, quantum secure protocols for secure multiparty computation
(MPC) were designed. The previously introduced number theoretic based MPC
protocols are not secure because quantum algorithms like Shor’s algorithm [18]
can be employed to break their security. Firstly, a design of the information
theoretic secure quantum secure oblivious linear evaluation (qOLE) is
proposed. Next, qOLE is used to develop a quantum secure multiparty private
set intersection (namely qMPSI). We believe that it is worth investigating and
designing other types of MPC protocols in the quantum domain.

## Declarations

#### Conflict of interest

The authors state that they have not known competing financial interests or
personal connections that may seem to have influenced the work described in
this study.

#### Data availability

Data sharing is not applicable to this article as no new data were generated
or analyzed to support this research.

## References

  * [1] O. R. Michael and M. Rabin, “How to exchange secrets by oblivious transfer,” Technical report, Aiken Computation Laboratory. Harvard University, Tech. Rep., 1981.
  * [2] J. Kilian, “Founding crytpography on oblivious transfer,” in _Proceedings of the twentieth annual ACM symposium on Theory of computing_ , 1988, pp. 20–31.
  * [3] M. Naor and B. Pinkas, “Oblivious polynomial evaluation,” _SIAM Journal on Computing_ , vol. 35, no. 5, pp. 1254–1281, 2006.
  * [4] I. Damgård, V. Pastro, N. Smart, and S. Zakarias, “Multiparty computation from somewhat homomorphic encryption,” in _Annual Cryptology Conference_. Springer, 2012, pp. 643–662.
  * [5] B. Applebaum, Y. Ishai, and E. Kushilevitz, “How to garble arithmetic circuits,” _SIAM Journal on Computing_ , vol. 43, no. 2, pp. 905–929, 2014\.
  * [6] L. Cianciullo and H. Ghodosi, “Efficient information theoretic multi-party computation from oblivious linear evaluation,” in _IFIP International Conference on Information Security Theory and Practice_. Springer, 2018, pp. 78–90.
  * [7] A. B. Efraim, O. Nissenbaum, E. Omri, and A. Paskin-Cherniavsky, “Psimple: Practical multiparty maliciously-secure private set intersection,” Cryptology ePrint Archive, Report 2021/122, 2021. https://eprint. iacr. org, Tech. Rep., 2021.
  * [8] R. A. Mahdavi, T. Humphries, B. Kacsmar, S. Krastnikov, N. Lukas, J. A. Premkumar, M. Shafieinejad, S. Oya, F. Kerschbaum, and E.-O. Blass, “Practical over-threshold multi-party private set intersection,” in _Annual Computer Security Applications Conference_ , 2020, pp. 772–783.
  * [9] R. Inbar, E. Omri, and B. Pinkas, “Efficient scalable multiparty private set-intersection via garbled bloom filters,” in _International Conference on Security and Cryptography for Networks_. Springer, 2018, pp. 235–252.
  * [10] A. Abadi, S. Terzis, and C. Dong, “Feather: lightweight multi-party updatable delegated private set intersection,” 2020.
  * [11] S. Badrinarayanan, P. Miao, S. Raghuraman, and P. Rindal, “Multi-party threshold private set intersection with sublinear communication,” in _IACR International Conference on Public-Key Cryptography_. Springer, 2021, pp. 349–379.
  * [12] A. Bay, Z. Erkin, M. Alishahi, and J. Vos, “Multi-party private set intersection protocols for practical applications,” in _18th International Conference on Security and Cryptography, SECRYPT 2021_. SciTePress, 2021, pp. 515–522.
  * [13] E. Zhang, F.-H. Liu, Q. Lai, G. Jin, and Y. Li, “Efficient multi-party private set intersection against malicious adversaries,” in _Proceedings of the 2019 ACM SIGSAC Conference on Cloud Computing Security Workshop_ , 2019, pp. 93–104.
  * [14] V. Kolesnikov, N. Matania, B. Pinkas, M. Rosulek, and N. Trieu, “Practical multi-party private set intersection from symmetric-key techniques,” in _Proceedings of the 2017 ACM SIGSAC Conference on Computer and Communications Security_ , 2017, pp. 1257–1272.
  * [15] R. L. Rivest, A. Shamir, and L. Adleman, “A method for obtaining digital signatures and public-key cryptosystems,” _Communications of the ACM_ , vol. 21, no. 2, pp. 120–126, 1978.
  * [16] D. W. Kravitz, “Digital signature algorithm,” Jul. 27 1993, uS Patent 5,231,668.
  * [17] N. Koblitz, “Elliptic curve cryptosystems,” _Mathematics of computation_ , vol. 48, no. 177, pp. 203–209, 1987.
  * [18] P. W. Shor, “Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer,” _SIAM review_ , vol. 41, no. 2, pp. 303–332, 1999.
  * [19] V. Srivastava, A. Baksi, and S. K. Debnath, “An overview of hash based signatures,” _Cryptology ePrint Archive_ , 2023.
  * [20] D. Micciancio and O. Regev, “Lattice-based cryptography,” in _Post-quantum cryptography_. Springer, 2009, pp. 147–191.
  * [21] J. Ding and A. Petzoldt, “Current state of multivariate cryptography,” _IEEE Security & Privacy_, vol. 15, no. 4, pp. 28–36, 2017.
  * [22] R.-h. Shi, Y. Mu, H. Zhong, J. Cui, and S. Zhang, “An efficient quantum scheme for private set intersection,” _Quantum Information Processing_ , vol. 15, no. 1, pp. 363–371, 2016.
  * [23] X. Cheng, R. Guo, and Y. Chen, “Cryptanalysis and improvement of a quantum private set intersection protocol,” _Quantum Information Processing_ , vol. 16, no. 2, pp. 1–8, 2017.
  * [24] R.-h. Shi, Y. Mu, H. Zhong, and S. Zhang, “Quantum oblivious set-member decision protocol,” _Physical Review A_ , vol. 92, no. 2, p. 022309, 2015\.
  * [25] A. Maitra, “Quantum secure two-party computation for set intersection with rational players,” _Quantum Information Processing_ , vol. 17, no. 8, pp. 1–21, 2018.
  * [26] S. K. Debnath, K. Dey, N. Kundu, and T. Choudhury, “Feasible private set intersection in quantum domain,” _Quantum Information Processing_ , vol. 20, no. 1, pp. 1–11, 2021.
  * [27] S. K. Debnath, V. Srivastava, T. Mohanty, N. Kundu, and K. Sakurai, “Quantum secure privacy preserving technique to obtain the intersection of two datasets for contact tracing,” _Journal of Information Security and Applications_ , vol. 66, p. 103127, 2022.
  * [28] W. Liu and H.-W. Yin, “A novel quantum protocol for private set intersection,” _International Journal of Theoretical Physics_ , vol. 60, no. 6, pp. 2074–2083, 2021.
  * [29] W.-J. Liu, W.-B. Li, and H.-B. Wang, “An improved quantum private set intersection protocol based on hadamard gates,” _International Journal of Theoretical Physics_ , vol. 61, no. 3, pp. 1–11, 2022.
  * [30] W. Liu and H.-W. Yin, “A quantum protocol for private substitution problem,” _Quantum Information Processing_ , vol. 20, no. 5, pp. 1–11, 2021.
  * [31] Y. Wang, P. Hu, and Q. Xu, “Quantum protocols for private set intersection cardinality and union cardinality based on entanglement swapping,” _International Journal of Theoretical Physics_ , vol. 60, no. 9, pp. 3514–3528, 2021.
  * [32] R.-H. Shi and Y.-F. Li, “Quantum private set intersection cardinality protocol with application to privacy-preserving condition query,” _IEEE Transactions on Circuits and Systems I: Regular Papers_ , 2022.
  * [33] B. Liu, M. Zhang, and R. Shi, “Quantum secure multi-party private set intersection cardinality,” _International Journal of Theoretical Physics_ , vol. 59, no. 7, pp. 1992–2007, 2020.
  * [34] R.-H. Shi, “Quantum multiparty privacy set intersection cardinality,” _IEEE Transactions on Circuits and Systems II: Express Briefs_ , vol. 68, no. 4, pp. 1203–1207, 2020.
  * [35] T. Mohanty, V. Srivastava, S. K. Debnath, A. K. Das, and B. Sikdar, “Quantum secure threshold private set intersection protocol for iot-enabled privacy preserving ride-sharing application,” _IEEE Internet of Things Journal_ , 2023.
  * [36] M. Imran, “Secure multiparty quantum computations for greatest common divisor and private set intersection,” _arXiv preprint arXiv:2303.17196_ , 2023.
  * [37] R.-h. Shi and X.-q. Fang, “Edge-assisted quantum protocol for secure multiparty logical and and its applications,” _iScience_ , 2023.
  * [38] M. B. Santos, P. Mateus, and C. Vlachou, “Quantum universally composable oblivious linear evaluation,” 2022.
  * [39] P. O. Boykin and V. Roychowdhury, “Optimal encryption of quantum bits,” _Physical review A_ , vol. 67, no. 4, p. 042317, 2003.
  * [40] C. H. Bennett and G. Brassard, “Quantum cryptography: Public key distribution and coin tossing,” _arXiv preprint arXiv:2003.06557_ , 2020.

|  Tapaswini Mohanty is currently working as a Ph.D. student in the Department
of Mathematics, NIT Jamshedpur. He completed his Masters degree from Institute
of Science, BHU in 2019. Her research interests include Quantum Cryptography,
and Private Set Operations.
---|---
|  Vikas Srivastava is working as research scholar in the Department of
Mathematics, National Institute of Technology, Jamshedpur, India. He has
completed his B.S.-M.S. dual degree in Mathematics from Indian Institute of
Science Education and Research (IISER), Mohali, India in 2017. His research
interests include cryptography, network security and blockchain technology.
---|---
|  Sumit Kumar Debnath received a M.Sc. degree in Mathematics from IIT
Kharagpur in 2012, and also a Ph.D. degree in Cryptology and Network Security
from the Department of Mathematics, IIT Kharagpur in 2017. He is currently an
Assistant Professor at the Department of Mathematics, National Institute of
Technology, Jamshedpur, India. He is a life member of the Cryptology Research
Society of India (CRSI). His research interests include multivariate
cryptography, lattice-based cryptography, network security and blockchain. He
has published more than 28 papers in international journals and conferences in
his research areas.
---|---
|  Pantelimon Stănică received a Masters of Arts in Mathematics from Bucharest
University, Romania in 1992. He received a Ph.D./Doctorate in Algebra from the
Institute of Mathematics of the Romanian Academy in 1998 also a Ph.D. degree
in Mathematics from State University of New York at Buffalo in 1998. He is
currently an Professor and Manager of the Secure Communication program in the
Department of Applied Mathematics at Naval Postgraduate School, Monterey, CA
93943, USA. He has published more than 150 papers in refereed journals. He has
also published more than 35 papers in refereed conference proceedings. He has
also won the 2021 George Boole International Prize for considerable
contributions to the theory of Boolean functions.
---|---