An Improved Quantum Private Set Intersection Protocol Based on Hadamard Gates

Abstract

Recently, Liu and Yin (Int. J. Theor. Phys. 60, 2074-2083 (2021)) proposed a two-party private set intersection protocol based on quantum Fourier transform. We find the participant can deduce the other party’s private information, which violates the security requirement of private set computation. In order to solve this problem, an improved private set intersection protocol based on Hadamard gate is proposed. Firstly, the more feasible Hadamard gates are used to perform on the original n qubits instead of the quantum Fourier transform, which may reduce the difficulty of implementation. In addition, through the exclusive OR calculation, the participant’s private information is randomly chosen and encoded on the additional n qubits, which prevents participants from obtaining the result of the difference set S_diff, and then avoids the internal leakage of private information. Finally, the correctness and security analysis are conducted to show the proposed protocol can guarantee the correctness of computation result as well as resist outside attacks and participant internal attacks.

1 Introduction

Secure multiparty computation (SMC) is a collaborative computing problem that derived from the “Millionaire” problem [1] raised by Yao in 1982. Under the premise of correct computation, the private information of participants who do not trust each other will not be leaked. Private set computation (PSC) is an important aspect of SMC. It is the computing foundation of data mining and machine learning based on privacy protection, and it is also one of the active research topics in the classic information security field in recent years. At present, the security of classical PSC protocol is basically based on computational complexity, and its security can be guaranteed under the condition of limited computing power. However, quantum computing has shown super-parallel computing capabilities that classical computing cannot match, such as solving RSA large prime factorization problem [2], secondary acceleration of out-of-order database retrieval [3], and quantum forgery attacks on COPA, AES-COPA and marble authenticated encryption algorithms [4] etc. The security of most classical protocols is not guaranteed in this situation. In this regard, many scholars have begun to study quantum algorithm [5, 6]. The privacy and security of quantum algorithm is based on the physical properties of quantum mechanics, such as the No-Cloning theorem [7], uncertainty principle [8], quantum entanglement, potential unconditional security [9], etc. At present, the corresponding study of QPSC mainly includes quantum private set intersection (QPSI) [10,11,12,13,14] and quantum private set cardinality [15,16,17,18].

Private set intersection is an important cryptographic primitive that performs joint operations on data sets in a privacy-protected manner. Specifically, multiple participants calculate the intersection without revealing their privacy to others (including internal participants). In 2016, Shi et al. [10] first proposed a quantum scheme for the intersection of private sets. However, the server could unilaterally manipulate the intersection results in this protocol. In order to solve this problem, Cheng et al. [11] introduced a passive third party to achieve the fairness of the protocol. After that, based on the decision-making protocol for oblivious set members [19], Maitra [12] proposed quantum secure two-party computation for set intersection with rational players. These studies [10,11,12] require “multi-particle entangled states” as quantum resources and some “complex oracle operators”, which are difficult to achieve under current technology. In 2021, Debnath [13] proposed a QPSI protocol between the client and the server, which has higher feasibility using single photon quantum resources. But the result of the intersection in this protocol can only be obtained by one participant (i.e., client). Recently, Liu et al. proposed a novel QPSI protocol [14] (we call it the NQPSI protocol) based on quantum Fourier transform. According to the published results, all participants can obtain the intersection. However, private information will be leaked inside the participants. In order to solve this problem, an improved QPSI protocol based on Hadamard (H) gate is proposed. This protocol has two obvious advantages. Firstly, the more feasible H gate is used to replace the original quantum Fourier transform, which reduces the difficulty of implementing the protocol. More importantly, through exclusive OR calculation, the participant’s private information is randomly chosen and encoded on the additional n qubits, which prevents participants from getting the result of difference set, and then avoids the internal leakage of private information.

The rest of the paper is organized as follows. Section 2 reviews the NQPSI protocol and analyzes its loopholes. In Section 3, an improved private set intersection protocol is proposed. Section 4 verifies the correctness of the two protocols through examples and analyzes the security when facing outside attacks and participant attacks. Section 5 gives a brief summary of the content of this paper and prospects for future work.

2 Review and Analysis of NQPSI Protocol

For clarity, the NQPSI protocol [14] of Liu et al. is reviewed and analyzed here. The specific content is as follows.

2.1 Review on the NQPSI Protocol

First, they deduced that the second quantum Fourier transform of a single qubit is $QF{T^{2}}\left | j \right \rangle = -\left | j \right \rangle$, then $QF{T^{4}}\left | j \right \rangle = \left | j \right \rangle$. Suppose there is a complete set $U = \left \{ {{x_{1}},{x_{2}}, {\cdots } {x_{n}}} \right \}$. Participants Alice and Bob have private sets ${S_{A}} = \left \{ {{s_{1}^{A}},{s_{2}^{A}}, {\cdots } s_{{l_{A}}}^{A}} \right \}$ and ${S_{B}} = \left \{ {{s_{1}^{B}},{s_{2}^{B}}, {\cdots } s_{{l_{A}}}^{B}} \right \}$ respectively, where ${S_{A}},{S_{B}} \subseteq U$. Alice and Bob coded their private set codes as ${C_{A}} = \left \{ {c_{_{1}}^{A},c_{_{2}}^{A}, {\cdots } {c_{n}^{A}}} \right \}$ and ${C_{B}} = \left \{ {c_{_{1}}^{B},c_{_{2}}^{B}, {\cdots } {c_{n}^{B}}} \right \}$ respectively. The coding rules are shown in (1) .

$$ {c_{i}^{A}} = \left\{ \begin{array}{rcl} {1,if} & {{x_{i}} \in {S_{A}}}\\ {0,if} & {{x_{i}} \notin {S_{A}}} \end{array} \right., {c_{i}^{B}} = \left\{ \begin{array}{rcl} {1,if} & {{x_{i}} \in {S_{B}}}\\ {0,if} & {{x_{i}} \notin {S_{B}}} \end{array} \right.. $$

(1)

Calvin is a semi-honest third party. The steps of their protocol are as follows.

• Step 1 Calvin prepares a particles sequence ${P_{C}} = \left \{ {{p_{1}^{C}},{p_{2}^{C}}, {\cdots } ,{p_{n}^{C}}} \right \}$. He inserts the decoy photon into P_C to form a new quantum sequence and sent it to Alice.

• Step 2 Alice verifies the decoy particles. If the verification result is correct, she discards the decoy photon and continues the next step. Otherwise, the protocol will be aborted.

• Step 3 Alice prepares two n-length strings ${R_{A}} = \left \{ {{r_{1}^{A}},{r_{2}^{A}}, {\cdots } ,{r_{n}^{A}}} \right \}$ (The subscript n here is written as n + l in the original protocol, which is probably a typing error of the author) and ${H_{A}} = \left \{ {{h_{1}^{A}},{h_{2}^{A}}, {\cdots } ,{h_{n}^{A}}} \right \}$, where ${r_{i}^{A}}\left ({i = 1, {\cdots } ,n} \right )$ is randomly chosen from $\left \{ {0,1} \right \}$ and ${h_{i}^{A}}\left ({i = 1, {\cdots } ,n} \right )$ is a random positive integer. Then she gets the quantum sequence ${P_{A}} = \left \{ {{p_{1}^{A}},{p_{2}^{A}}, {\cdots } ,{p_{n}^{A}}} \right \}$, where ${p_{i}^{A}} = QF{T^{{c_{i}^{A}} \times 2}}QF{T^{{r_{i}^{A}} \times {h_{i}^{A}}}}{p_{i}^{C}}\left ({i = 1, {\cdots } ,n} \right )$. She inserts the decoy photon into P_A to form a new quantum sequence and sends it to Bob.

• Step 4 Bob verifies the decoy particles. If the verification result is correct, he discards the decoy photon and continues the next step. Otherwise, the protocol will be aborted.

• Step 5 Bob prepares two n-length strings R_B and H_B, and he gets the quantum sequence ${P_{B}} = \left \{ {{p_{1}^{B}},{p_{2}^{B}}, {\cdots } ,{p_{n}^{B}}} \right \}$, where ${p_{i}^{B}} = QF{T^{{c_{i}^{B}} \times 2}}QF{T^{{r_{i}^{B}} \times {h_{i}^{B}}}}{p_{i}^{A}}$ $\left ({i = 1, {\cdots } ,n} \right )$. The rules are similar to Step 3. He inserts the decoy photon into P_A to form a new quantum sequence and sends it to Calvin.

• Step 6 Calvin verifies the decoy particles. If the verification result is correct, he discards the decoy photon and continues the next step. Otherwise, the protocol will be aborted.

• Step 7 Alice and Bob compute ${h_{i}^{C}} = 4 - {\left ({\left ({{r_{i}^{A}} \times {h_{i}^{A}}} \right ) + \left ({{r_{i}^{B}} \times {h_{i}^{B}}} \right )} \right )\bmod 4} \left ({i = 1, {\cdots } ,n} \right )$ and send ${h_{1}^{C}}, {\cdots } ,{h_{n}^{C}}$ to Calvin. Calvin calculates $p_{i}^{C^{\prime }} = QF{T^{{h_{i}^{C}}}}{p_{i}^{B}}$ and measures it. If the measurement result of $p_{i}^{C^{\prime }}$ is the same as ${p_{i}^{C}}$, Calvin knows whether ${c_{i}^{A}}$ and ${c_{i}^{B}}$ are equal. Calvin gets S_A ∩ S_B.

2.2 Vulnerability Analysis

In Step 7, Calvin can get

$$ p_{i}^{C^{\prime}} = QF{T^{{h_{i}^{C}}}}{p_{i}^{B}} = QF{T^{{c_{i}^{A}} \times 2 + {c_{i}^{B}} \times 2}}{p_{i}^{C}}. $$

(2)

Table 1 shows the value of $p_{i}^{C^{\prime }}$ for several paired ${c_{i}^{A}}$ and ${c_{i}^{B}}$. Each of the four different pairs (${c_{i}^{A}}$, ${c_{i}^{B}}$) corresponds to results: $p_{i}^{C^{\prime }}={p_{i}^{C}}$ or $p_{i}^{C^{\prime }}=-{p_{i}^{C}}$. Specifically, as shown in Case 1 and Case 4, $p_{i}^{C^{\prime }}={p_{i}^{C}}$ is the measurement result corresponding to the “complement-intersection” set, ${{S}_{c-in}}={{S}_{com}}\cup {S_{in}}={{\mathcal C}_{U}}\left ({{S_{A}} \cup {S_{B}}} \right )\cup ({S_{A}} \cap {S_{B}})$. In Case 2 and Case 3, $p_{i}^{C^{\prime }}=-{p_{i}^{C}}$ is the result of difference set, ${S_{diff}} = \left ({{S_{A}} - {S_{B}}} \right ) \cup \left ({{S_{B}} - {S_{A}}} \right )$.

Table 1 Results of the NQPSI protocol

Alice and Bob can obtain S_in according to whether the i-th information corresponding to $p_{i}^{C^{\prime }}={p_{i}^{C}}$ is included in their private set or not. However, they can know the i-th information corresponding to $p_{i}^{C^{\prime }}=-{p_{i}^{C}}$ only contained in the own or the others private set. In Case 2, Alice can deduce that the i-th information is in the S_B. In Case 3, Bob can deduce that the i-th information is in the S_A. The privacy of set intersection requires that Alice (Bob) cannot know Bob’s (Alice’s) private set elements outside S_in. Obviously, the privacy of the NQPSI protocol cannot be guaranteed.

Furthermore, the author claims that Calvin can get S_in, which is impossible according to the protocol. And the author did not write the operation after Calvin got ${c_{i}^{A}} = {c_{i}^{B}}$ in the protocol.

3 QPSI Protocol Based on H Gates

From the analysis in the previous section, participants can obtain private information outside S_in of others based on S_diff, which leads to privacy leakage. In order to solve this problem, an improved QPSI protocol based on H gates is proposed, where $\mathrm {H} \equiv {1 \over {\sqrt 2 }}\left (\begin {array}{ll} 1 & 1 \\ 1 & { - 1} \end {array}\right )$. The detailed procedures of our protocol are as follows (also shown in Fig. 1).

• Step 1 Calvin prepares the quantum sequence ${P_{C}} = \mathop \otimes \limits _{i = 1}^{2n} {P_{i}^{C}}$, where ${p_{i}^{C}}$ is randomly selected from $\left \{ {\left | 0 \right \rangle ,\left | 1 \right \rangle ,\left | + \right \rangle ,\left | - \right \rangle } \right \}$. Then he executes the operation of inserting decoy particle. Specifically, he prepares l_C decoy particles ${q_{j}^{C}}$ and selects the measurement basis. After inserting ${q_{j}^{C}}$ into P_C to form a new sequence ${P^{\prime }_{C}}$, Calvin records the position ${m_{t}^{C}}\left ({t = 1,2, {\cdots } {l_{C}}} \right )$ of ${q_{j}^{C}}$ in sequence ${P^{\prime }_{C}}$ and sends sequence ${P^{\prime }_{C}}$ to Alice.

• Step 2 After receiving the sequence ${P^{\prime }_{C}}$, Alice executes the eavesdropper detection. To be specific, Calvin sends the position ${m_{t}^{C}}$ of the decoy particle ${q_{j}^{C}}$ in the sequence ${P^{\prime }_{C}}$ and the corresponding measurement basis to Alice. Alice compares the measurement result at this position with ${q_{j}^{C}}$. If ${{q_{j}^{C}}}^{\prime }$ is different from ${q_{j}^{C}}$, return to Step 1. Otherwise, she discards ${q_{j}^{C}}$ and proceeds to the next step.

• Step 3 Alice prepares 2n-length strings ${R_{A}} = \left \{{{r_{i}^{A}}\left | {r_{i}^{A}} \in {\mathrm {N}^ + }, {i = 1,2, {\cdots } 2n} \right . } \right \}$ and $\text {H}_{\text {A}} = \left \{ {{h_{i}^{A}}\left | {{h_{i}^{A}} \in \left \{ {0,1} \right \},n < i \le 2n} \right .} \right \}$. And she gets

  $$ \begin{array}{rcl} {P_{A}} &&= \mathop \otimes \limits_{i = 1}^{2n} {P_{i}^{A}} \\ &&= \mathop \otimes \limits_{i = 1}^{n} {\mathrm{H}^{{1 \over 3}\left( {{c_{i}^{A}} + 2} \right)}}{\mathrm{H}^{{r_{i}^{A}}}}{P_{i}^{C}}\left\| {\mathop \otimes \limits_{i = n + 1}^{2n} {\mathrm{H}^{{1 \over 3}\left( {{h_{i}^{A}}{c_{i}^{A}} + 2} \right)}}{\mathrm{H}^{{r_{i}^{A}}}}} \right., \end{array} $$

  (3)

  where ${{c_{i}^{A}}}={c_{i-n}^{A}}$ (i > n). Then she executes the operation of inserting decoy particles, which is similar to Step 1. After this, she sends sequence ${P^{\prime }_{A}}$ and H_A to Bob.

• Step 4 After receiving sequence ${P^{\prime }_{A}}$, Bob executes the eavesdropper detection, which is similar to Step 2.

• Step 5 Bob prepares 2n-length strings ${R_{B}} = \left \{ {{r_{i}^{B}}\left | {r_{i}^{B}} \in {\mathrm {N}^ + }, {i = 1,2, {\cdots } 2n} \right .} \right \}$ and $\text {H}_{\text {B}} = \left \{ {{h_{i}^{B}}\left | {{h_{i}^{B}} = {h_{i}^{A}} \oplus 1,n < i \le 2n} \right .} \right \}$. And he gets

  $$ \begin{array}{rcl} {P_{B}} &&= \mathop \otimes \limits_{i = 1}^{2n} {P_{i}^{B}} \\ &&= \mathop \otimes \limits_{i = 1}^{n} {\mathrm{H}^{{1 \over 3}\left( {{c_{i}^{B}} + 2} \right)}}{\mathrm{H}^{{r_{i}^{B}}}}{P_{i}^{A}}\left\| {\mathop \otimes \limits_{i = n + 1}^{2n} {\mathrm{H}^{{1 \over 3}\left( {{h_{i}^{B}}{c_{i}^{B}} + 2} \right)}}{\mathrm{H}^{{r_{i}^{B}}}}{P_{i}^{A}}} \right., \end{array} $$

  (4)

  where ${{c_{i}^{B}}}={c_{i-n}^{B}}$ (i > n). Then he executes the operation of inserting decoy particles, which is similar to Step 1. After this, he sends sequence ${P^{\prime }_{B}}$ to Calvin.

• Step 6 After receiving sequence ${P^{\prime }_{B}}$, Calvin executes the eavesdropper detection, which is similar to Step 2.

• Step 7 Alice and Bob calculate ${r_{i}^{C}} = {r_{i}^{A}} + {r_{i}^{B}}$ and send the result to Calvin. Calvin gets

  $$ \begin{array}{rcl} {P_{C}}^{\prime \prime } &&= \mathop \otimes \limits_{i = 1}^{2n} {P_{i}}^{{C}^{\prime \prime }} \\ &&= \mathop \otimes \limits_{i = 1}^{2n}{\mathrm{H}^{{r_{i}^{C}}}}{P_{i}^{B}} \\ &&= \mathop \otimes \limits_{i = 1}^{n} {\mathrm{H}^{{1 \over 3}\left( {{c_{i}^{B}} + {c_{i}^{A}} + 4} \right)}}{P_{i}^{C}}\left\| {\mathop \otimes \limits_{i = n + 1}^{2n} {\mathrm{H}^{{1 \over 3}\left( {{h_{i}^{B}}{c_{i}^{B}} + {h_{i}^{A}}{c_{i}^{A}} + 4} \right)}}{P_{i}^{C}}} \right., \end{array} $$

  (5)

  (H² = I, and applying H twice to single-qubit does nothing to it). Charlie then announces the position information i (i ≤ n) that satisfies ${P_{i}}^{{C}^{\prime \prime }}= {P_{i}^{C}}$ and ${P_{i+n}}^{{C}^{\prime \prime }} \ne P_{i+n}^{C}$.

• Step 8 Alice and Bob get S_in based on the results announced by Calvin.

Fig. 1

Schematic diagram of QPSI protocol based on H gates. The line is the process from Step 1 to Step 6 in the protocol. Insertion of decoy photons and the eavesdropper detection are omitted here

It is worth noting that in Step 3 and Step 5, through exclusive OR calculation, the private information of a participant is randomly encoded in the last n qubits, which prevents participants from getting S_diff and avoids the problem of their internal private information leakage.

4 Correctness and Security Analysis

4.1 Correctness Analysis

The corresponding results of ${P_{i}}^{{C}^{\prime \prime }}$ for several paired ${c_{i}^{A}}$ and ${c_{i}^{B}}$ are shown in Table 2. The spectral decomposition form of the H gate can be expressed as $\mathrm {H} = \left | {{y_{1}}} \right \rangle \left \langle {{y_{1}}} \right | - \left | {{y_{2}}} \right \rangle \left \langle {{y_{2}}} \right |$, where $\left | {{y_{1}}} \right \rangle = \left (\begin {array}{ll} {\sqrt 2 - 1} \\ {3 - 2\sqrt 2 } \end {array}\right )$ and $\left | {{y_{2}}} \right \rangle = \left (\begin {array}{ll} {3 - 2\sqrt 2 } \\ {1 - \sqrt 2 } \end {array} \right )$. We can calculate ${\mathrm {H}^{{4 \over 3}}} = \left | {{y_{1}}} \right \rangle \left \langle {{y_{1}}} \right | + {\left (-1 \right )^{{4 \over 3}}}\left | {{y_{2}}} \right \rangle \left \langle {{y_{2}}} \right | = I$, and ${\mathrm {H}^{{5 \over 3}}} = \left | {{y_{1}}} \right \rangle \left \langle {{y_{1}}} \right | + {\left (-1 \right )^{{5 \over 3}}}\left | {{y_{2}}} \right \rangle \left \langle {{y_{2}}} \right | =\text {H}$. Therefore, if ${c_{i}^{A}}={c_{i}^{B}}$ (i ≤ n), Calvin can get ${P_{i}}^{{C}^{\prime \prime }} = {P_{i}^{C}}$. Otherwise, ${P_{i}}^{{C}^{\prime \prime }} \ne {P_{i}^{C}}$. If $c_{i+n}^{A}=c_{i+n}^{B}=0$, Calvin can get ${P_{i+n}}^{{C}^{\prime \prime }} = P_{i+n}^{C}$. If $c_{i+n}^{A}=c_{i+n}^{B}=1$, Calvin can get ${P_{i+n}}^{{C}^{\prime \prime }} \ne P_{i+n}^{C}$. If $c_{i+n}^{A} \ne c_{i+n}^{B}$, ${P_{i+n}}^{{C}^{\prime \prime }}$ and $P_{i+n}^{C}$ may be equal or not. So, if ${P_{i}}^{{C}^{\prime \prime }} ={P_{i}^{C}}$ and ${P_{i+n}}^{{C}^{\prime \prime }} \ne P_{i+n}^{C}$, the i-th number is the S_in element.

Table 2 QPSI protocol results

We use an example to verify the correctness of the protocol. In this section, insertion of decoy photons and the eavesdropper detection are omitted. Suppose Alice and Bob have private sets ${S_{A}} = \left \{ {5,7,17,20} \right \}$ and ${S_{B}} = \left \{ {7,13,17,35} \right \}$, respectively. The universal set is $U = \left \{ {2,5,7,9,13,17,20,35} \right \}$. They encode sets S_A and S_B as ${C_{A}} = \left \{ {0,1,1,0,0,1,1,0} \right \}$ and ${C_{B}} = \left \{ {0,0,1,0,1,1,0,1} \right \}$, respectively.

In Step 1, Calvin prepares the quantum sequence ${P_{C}} = \left | {101 + 00 - + +01 + -0 - 1 } \right \rangle$. In Step 3, Alice prepares ${R_{A}} = \left \{ {3,6,4,2,4,1,9,7,3,6,4,2,4,1,9,7} \right \}$ and $\text {H}_{\text {A}} = \left \{ {1,1,0,0,1,0,0,1} \right \}$. And she executes the H gates on the P_C, she gets

$$ \begin{array}{rcl} {P_{A}} =&& \mathop \otimes \limits_{i = 1}^{8} {\mathrm{H}^{{1 \over 3}\left( {{c_{i}^{A}} + 2} \right) + {r_{i}^{A}}}}P_{i}^{C1}\left\| {\mathop \otimes \limits_{i = 9}^{16} {\mathrm{H}^{{1 \over 3}\left( {{h_{i}^{A}}{c_{i}^{A}} + 2} \right) + {r_{i}^{A}}}}} \right.\\ =&& {\mathrm{H}^{{2 \over 3} + 3}}\left| {\text{1}} \right\rangle \otimes \mathrm{H}{\mathrm{H}^{{\text{1 + 6}}}}\left| {\text{0}} \right\rangle \otimes {\mathrm{H}^{{\text{1 + 4}}}}\left| 1 \right\rangle \otimes {\mathrm{H}^{{2 \over 3} + 2}}\left| + \right\rangle \\ && \otimes {\mathrm{H}^{{2 \over 3} + 4}}\left| 0 \right\rangle \otimes {\mathrm{H}^{{\text{1 + 1}}}}\left| 0 \right\rangle \otimes {\mathrm{H}^{{\text{1 + 9}}}}\left| - \right\rangle \otimes {\mathrm{H}^{{2 \over 3} + 7}}\left| + \right\rangle \\ &&\otimes {\mathrm{H}^{\text{3}}}\left| + \right\rangle \otimes {\mathrm{H}^{{5 \over 3}{\text{ + 5}}}}\left| {\text{0}} \right\rangle \otimes {\mathrm{H}^{6}}\left| 1 \right\rangle \otimes \mathrm{H}\left| + \right\rangle \\ && \otimes {\mathrm{H}^{3}}\left| - \right\rangle \otimes {\mathrm{H}^{9}}\left| 0 \right\rangle \otimes {\mathrm{H}^{2}}\left| - \right\rangle \otimes {\mathrm{H}^{4}}\left| 1 \right\rangle . \end{array} $$

(6)

In Step 5, Bob prepares random numbers ${R_{B}} = \left \{ {7,9,8,5,4,2,3,6,7,9,8,5,4,2,3,6} \right \}$. He calculates $\text {H}_{\text {B}} = \left \{ {0,0,1,1,0,1,1,0} \right \}$ and executes the H gates on the P_A. He gets:

$$ \begin{array}{rcl} {P_{B}}=&& \mathop \otimes \limits_{i = 1}^{8} {\mathrm{H}^{{1 \over 3}\left( {{c_{i}^{B}} + {c_{i}^{A}} + 4} \right) + {r_{i}^{B}} + {r_{i}^{A}}}}{P_{i}^{C}}\left\| {\mathop \otimes \limits_{i = 9}^{16} {\mathrm{H}^{{1 \over 3}\left( {{h_{i}^{B}}{c_{i}^{B}} + {h_{i}^{A}}{c_{i}^{A}} + 4} \right) + {r_{i}^{B}} + {r_{i}^{A}}}}{P_{i}^{C}}} \right.\\ =&&{\mathrm{H}^{{4 \over 3} + 10}}\left| {\text{1}} \right\rangle \otimes {\mathrm{H}^{{5 \over 3} + 15}}\left| {\text{0}} \right\rangle \otimes {\mathrm{H}^{2 + 12}}\left| 1 \right\rangle \otimes {\mathrm{H}^{{4 \over 3} + 7}}\left| + \right\rangle \\ && \otimes {\mathrm{H}^{{5 \over 3} + 8}}\left| 0 \right\rangle \otimes {\mathrm{H}^{2 + 3}}\left| 0 \right\rangle \otimes {\mathrm{H}^{{5 \over 3} + 12}}\left| - \right\rangle \otimes {\mathrm{H}^{{5 \over 3} + 13}}\left| + \right\rangle \\ &&\otimes{\mathrm{H}^{{4 \over 3} + 4}}\left| + \right\rangle \otimes {\mathrm{H}^{{5 \over 3} + 8}}\left| {\text{0}} \right\rangle \otimes {\mathrm{H}^{{5 \over 3} + 11}}\left| 1 \right\rangle \otimes {\mathrm{H}^{{4 \over 3} + 3}}\left| + \right\rangle \\ && \otimes {\mathrm{H}^{{4 \over 3} + 7}}\left| - \right\rangle \otimes {\mathrm{H}^{{5 \over 3} + 12}}\left| 0 \right\rangle \otimes {\mathrm{H}^{{4 \over 3} + 8}}\left| - \right\rangle \otimes {\mathrm{H}^{{4 \over 3} + 13}}\left| 1 \right\rangle . \end{array} $$

(7)

In Step 7, Alice and Bob calculate ${r_{i}^{C}} = {r_{i}^{A}} + {r_{i}^{B}}$ and send the results to Calvin. Calvin gets:

$$ \begin{array}{rcl} {P_{C}}^{\prime \prime }=&& \mathop \otimes \limits_{i = 1}^{n} {\mathrm{H}^{{r_{i}^{C}}}}{P_{i}^{B}}\\ =&&{\mathrm{H}^{10}}{\mathrm{H}^{{4 \over 3} + 10}}\left| {\text{1}} \right\rangle \otimes {\mathrm{H}^{15}}{\mathrm{H}^{{5 \over 3} + 15}}\left| {\text{0}} \right\rangle \otimes {\mathrm{H}^{12}}{\mathrm{H}^{2 + 12}}\left| 1 \right\rangle \otimes {\mathrm{H}^{7}}{\mathrm{H}^{{4 \over 3} + 7}}\left| + \right\rangle \\ && \otimes {\mathrm{H}^{8}}{\mathrm{H}^{{5 \over 3} + 8}}\left| 0 \right\rangle \otimes {\mathrm{H}^{3}}{\mathrm{H}^{2 + 3}}\left| 0 \right\rangle \otimes {\mathrm{H}^{12}}{\mathrm{H}^{{5 \over 3} + 12}}\left| {\text{ - }} \right\rangle \otimes {\mathrm{H}^{13}}{\mathrm{H}^{{5 \over 3} + 13}}\left| + \right\rangle \\ &&\otimes{\mathrm{H}^{4}}{\mathrm{H}^{{4 \over 3} + 4}}\left| + \right\rangle \otimes {\mathrm{H}^{8}}{\mathrm{H}^{{5 \over 3} + 8}}\left| {\text{0}} \right\rangle \otimes {\mathrm{H}^{11}}{\mathrm{H}^{{5 \over 3} + 11}}\left| 1 \right\rangle \otimes {\mathrm{H}^{3}}{\mathrm{H}^{{4 \over 3} + 3}}\left| + \right\rangle \\ && \otimes {\mathrm{H}^{7}}{\mathrm{H}^{{4 \over 3} + 7}}\left| - \right\rangle \otimes {\mathrm{H}^{12}}{\mathrm{H}^{{5 \over 3} + 12}}\left| 0 \right\rangle \otimes {\mathrm{H}^{8}}{\mathrm{H}^{{4 \over 3} + 8}}\left| - \right\rangle \otimes {\mathrm{H}^{13}}{\mathrm{H}^{{4 \over 3} + 13}}\left| 1 \right\rangle \\ =&&{\mathrm{H}^{{4 \over 3}}}\left| {\text{1}} \right\rangle \otimes {\mathrm{H}^{{5 \over 3}}}\left| {\text{0}} \right\rangle \otimes \left| 1 \right\rangle \otimes {\mathrm{H}^{{4 \over 3}}}\left| + \right\rangle \\ &&\otimes {\mathrm{H}^{{5 \over 3}}}\left| 0 \right\rangle \otimes \left| 0 \right\rangle \otimes {\mathrm{H}^{{5 \over 3}}}\left| {\text{ - }} \right\rangle \otimes {\mathrm{H}^{{5 \over 3}}}\left| + \right\rangle \\ &&\otimes{\mathrm{H}^{{4 \over 3}}}\left| + \right\rangle \otimes {\mathrm{H}^{{5 \over 3}}}\left| {\text{0}} \right\rangle \otimes {\mathrm{H}^{{5 \over 3}}}\left| 1 \right\rangle \otimes {\mathrm{H}^{{4 \over 3}}}\left| + \right\rangle \\ && \otimes {\mathrm{H}^{{4 \over 3}}}\left| - \right\rangle \otimes {\mathrm{H}^{{5 \over 3}}}\left| 0 \right\rangle \otimes {\mathrm{H}^{{4 \over 3}}}\left| - \right\rangle \otimes {\mathrm{H}^{{4 \over 3}}}\left| 1 \right\rangle \\ =&&\left| {\text{1}} \right\rangle \otimes \mathrm{H}\left| {\text{0}} \right\rangle \otimes \left| 1 \right\rangle \otimes \left| + \right\rangle \otimes \mathrm{H}\left| 0 \right\rangle \otimes \left| 0 \right\rangle \otimes \mathrm{H}\left| {\text{ - }} \right\rangle \otimes \mathrm{H}\left| + \right\rangle \\ &&\otimes\left| + \right\rangle \otimes \mathrm{H}\left| {\text{0}} \right\rangle \otimes \mathrm{H}\left| 1 \right\rangle \otimes \left| + \right\rangle \otimes \left| - \right\rangle \otimes \mathrm{H}\left| 0 \right\rangle \otimes \left| - \right\rangle \otimes \left| 1 \right\rangle . \end{array} $$

(8)

He obtains ${P_{1}}^{{C}^{\prime \prime }} = {P_{1}^{C}}$, ${P_{3}}^{{C}^{\prime \prime }} = {P_{3}^{C}}$, ${P_{4}}^{{C}^{\prime \prime }} = {P_{4}^{C}}$, ${P_{6}}^{{C}^{\prime \prime }} = {P_{6}^{C}}$, $P_{10}^{C} \ne {P_{10}}^{{C}^{\prime \prime }}$, $P_{11}^{C} \ne {P_{11}}^{{C}^{\prime \prime }}$, $P_{14}^{C} \ne {P_{14}}^{{C}^{\prime \prime }}$. Calvin gets the 3rd and 6th position to meet the conditions and announces it to Alice and Bob. In the end, Alice and Bob get ${S_{in}} = \left \{ {7,17} \right \}$.

4.2 Security Analysis

In this section, we conduct security analysis from two aspects: participant attack and outside attack.

4.2.1 Participant Attack

Participant attack [20, 21] means that dishonest participants try to steal other’s information during the calculation process, which will lead to the leakage of private information inside the participants. Ensuring the internal information security of participants is one of the important criteria for evaluating the security of the protocol.

Case 1:

Alice tries to steal Bob’s private information.

During the protocol process, Alice can only receive the quantum sequence ${P_{C}} = \mathop \otimes \limits _{i = 1}^{n} {P_{i}^{C}}$ sent by Calvin, and ${p_{i}^{C}}$ is randomly determined by Calvin, so Alice cannot obtain Bob’s private information in this case.

At the end of the protocol, Alice gets the information of ${c_{i}^{A}} = {c_{i}^{B}} = 1$, and then gets S_in. In other cases, she does not know whether the element satisfies ${c_{i}^{A}} = {c_{i}^{B}} = 0$ or ${c_{i}^{A}} \ne {c_{i}^{B}}$, so she cannot deduce ${c_{i}^{B}} = 1$ and cannot obtain Bob’s private information outside S_in.

Case 2:

Bob tries to steal Alice’s private information.

Bob gets sequence P_A (as shown in (3)) after receiving the decoy photon information published by Alice. If dishonest Bob wants to use the measure-resend attack to get Alice’s private information, he prepares the ancillary qubits $\left | 0 \right \rangle _{B}^{n}$ and entangles Alice’s quantum sequence ${P_{i}^{A}}$ that has been received with the ancillary qubits. He wants to get Alice’s private information ${c_{i}^{A}}$ by measuring the ancillary qubits sequence. After receiving ${P_{i}^{A}}$, Bob uses the unitary operator ${\tilde U_{AB}}$ to operate on ${P_{i}^{A}}$ and $\left | 0 \right \rangle _{B}^{n}$. According to Ref. [22], Bob’s attack process is as follows:

$$ {\tilde U_{AB}}{P_{i}^{A}}\left| 0 \right\rangle_{B}^{n} = \sqrt \eta {P_{i}^{A}}\left| {u\left( {{P_{i}^{A}}} \right)} \right\rangle + \sqrt {1 - \eta } {\left| {v\left( {{P_{i}^{A}}} \right)} \right\rangle_{AB}} , $$

(9)

where ${P_{i}^{A}}\left | {u\left ({{P_{i}^{A}}} \right )} \right \rangle$ and ${\left | {v\left ({{P_{i}^{A}}} \right )} \right \rangle _{AB}}$ are orthogonal vectors.

$$ {\left\langle {v\left( {{P_{i}^{A}}} \right)} \right|_{AB}}{P_{i}^{A}}\left| {u\left( {{P_{i}^{A}}} \right)} \right\rangle = 0. $$

(10)

In order to successfully pass the eavesdropping detection stage, Eve’s operation will not change the state of the original photon, so η should be equal to 1. He can get:

$$ \begin{array}{rcl} {{\tilde U}_{AB}}{P_{i}^{A}}\left| 0 \right\rangle_{B}^{n} &&= {P_{i}^{A}}\left| {u\left( {{P_{i}^{A}}} \right)} \right\rangle \\ &&= {\mathrm{H}^{{1 \over 3}\left( {{h_{i}^{A}}{c_{i}^{A}} + 2} \right) + {r_{i}^{A}}}}{P_{i}^{C}}\left| {u\left( {{P_{i}^{A}}} \right)} \right\rangle \\ && =\left\{ \begin{array}{rcl} {{\mathrm{H}^{{2 \over 3} + {r_{i}^{A}}}}{P_{i}^{C}}\left| {u\left( {{P_{i}^{A}}} \right)} \right\rangle ,if {c_{i}^{A}} = 0}\\ {{\mathrm{H}^{1+{r_{i}^{A}}}}{P_{i}^{C}}\left| {u\left( {{P_{i}^{A}}} \right)} \right\rangle ,if {c_{i}^{A}} = 1} . \end{array} \right. \end{array} $$

(11)

Bob cannot extract the global phase information from the partial qubits of the entangled quantum, so he cannot obtain any information about Alice.

At the end of the protocol, Bob gets the information of ${c_{i}^{A}} = {c_{i}^{B}} = 1$ and gets S_in. In other cases, similar to Alice, he does not know whether the element satisfies ${c_{i}^{A}} = {c_{i}^{B}} = 0$ or ${c_{i}^{A}} \ne {c_{i}^{B}}$, so he cannot deduce ${c_{i}^{A}} = 1$ and cannot obtain Alice’s private information outside S_in.

Case 3:

Calvin tries to steal Alice’s and Bob’s private information.

After Calvin receives the decoy photon information published by Bob, he gets the sequence P_B.

$$ {P_{B}} = \mathop \otimes \limits_{i = 1}^{n} {\mathrm{H}^{{1 \over 3}\left( {{c_{i}^{B}} + 2} \right)}}{\mathrm{H}^{{r_{i}^{B}}}}{P_{i}^{A}}\left\| {\mathop \otimes \limits_{i = n + 1}^{2n} {\mathrm{H}^{{1 \over 3}\left( {{h_{i}^{B}}{c_{i}^{B}} + 2} \right)}}{\mathrm{H}^{{r_{i}^{B}}}}{P_{i}^{A}}} \right.. $$

(12)

Calvin receives ${r_{i}^{C}}$ and operates on sequence P_B to get the new sequence ${P_{C}}^{\prime \prime }$.

$$ {P_{C}}^{\prime \prime } = \mathop \otimes \limits_{i = 1}^{n} {\mathrm{H}^{{1 \over 3}\left( {{c_{i}^{B}} + {c_{i}^{A}} + 4} \right)}}{P_{i}^{C}}\left\| {\mathop \otimes \limits_{i = n + 1}^{2n} {\mathrm{H}^{{1 \over 3}\left( {{h_{i}^{B}}{c_{i}^{B}} + {h_{i}^{A}}{c_{i}^{A}} + 4} \right)}}{P_{i}^{C}}} \right.. $$

(13)

Because the last n qubits information is randomly determined by Alice and Bob, Charlie can only infer the private information of Alice and Bob based on the first n qubits. If ${P_{i}}^{{C}^{\prime \prime }} \ne {P_{i}^{C}}$ (i ≤ n) , Calvin can deduce that the i-th position element is in the private set of Alice or Bob (i.e. ${c_{i}^{A}} = 1$ or ${c_{i}^{B}} = 1$), but he is not sure which one. Therefore, Calvin cannot obtain all the private information of Alice or Bob, and the protocol satisfies privacy.

4.2.2 Outside Attack

At present, the common quantum channel attacks include intercept-measuring-retransmission attack, Trojan horse attack [23], man-in-the-middle attack [24], invisible photon attack [25], etc. In the communication between the two parties, the third-party attacker Eve is the object with strong attack ability, and its eavesdropping technology is only limited by the basic principles of quantum mechanics. The decoy photon eavesdropping detection method [26, 27] is an important method to detect whether there is eavesdropping in the quantum communication process. Its safety has been proved in refs [28].

In our protocol, the external attacker Eve can attack the quantum channel during the transmission of the photon sequence between Calvin, Alice and Bob. In these steps, the participants insert some particles into the quantum sequence in the form of decoy states. Take the information transfer between Calvin and Alice in Step 1 to Step 2 as an example. When Calvin sends the quantum sequence inserted into the decoy photon to Alice, if Eve launches an attack, he will inevitably change the original sequence after stealing the information. After receiving the quantum sequence, Alice can judge whether there is a malicious attack based on the position information of the decoy photon and the measurement base information given by Calvin.

5 Conclusion

In this paper, we point out the problem of private information leakage between participants in the NQPSI protocol [14]. To solve this problem, we propose an improved QPSI protocol based on H gates. We use the more feasible H gates to replace the original quantum Fourier transform, which may reduce the difficulty of the protocol implementation. Through the exclusive OR calculation on the last n qubits, this scheme ensures that participants cannot get S_diff, which prevents them from getting the private information of the others outside S_in. It is worth noting that if the third party is malicious or there is an error in the protocol process, the participant will get wrong results without knowing it. In this regard, attention should be paid to the verifiability of QPSC and the integrity of third parties. At present, the verifiable blind quantum computing framework based on the idea of delegating private computations [29] has attracted much attention. We believe that learning from this idea to solve the PSC problem is a feasible way.