1 Introduction

Today, we have entered the era of big data. Vigorous data analysis and processing technologies such as deep learning have been widely applied in many fields such as disease prediction and business decision-making. In order to acquiring more useful value, it is necessary to share data from multiple owners for analysis and processing. However, considering issues such as data security and personal privacy, most data owners show a very cautious attitude when sharing their data. For example, hospitals need to share their medical information with each other, but do not want to disclose the privacy of any patients; manufacturers want to test their products according to industry standards, but do not want to leak their actual production data to any competitors. In response to these “data island” problems, secure multi-party computation (MPC) technology has appeared and made a significant contribution to the realization of the secure sharing of data. MPC was originally proposed by Yao [1] in 1982. It allows multiple participants who do not trust each other to perform collaborative calculations and ensures that no participant can get anything except the desired results. In other words, MPC technology can help participants further mine the value of their data through sharing them without disclosing their privacy.

As a specific primitive of MPC, private set intersection cardinality (PSI-CA) can perform computation task that multiple participants want to calculate the intersection cardinality of their secret sets without revealing the intersection and the sets themselves. Similar to PSI-CA, private set union cardinality (PSU-CA) can help multiple participants calculate the union cardinality of their secret sets, and keep the union and the sets themselves secret. PSI-CA protocol was originally proposed by Freedman et al. [2] in EUROCRYPT 2004. Subsequently, some other PSI-CA protocols were presented in Refs [3,4,5,6], etc. These protocols are based on traditional mathematical problems such as large integer factorization and discrete logarithm. However, due to the emergency of Shor’s algorithm [7] that can solve these problems in polynomial time, the above-mentioned protocols may be potentially threatened by quantum computer.

In order to overcome the threat posed by quantum technology, one of the beneficial options is to utilize quantum mechanics to construct cryptographic primitives. For this work, it can be traced back to the proposal of BB84, which is a quantum key distribution protocol, and was put forward by Bennett and Brassard [8] in 1984. Since then, various quantum MPC protocols such as quantum protocol for millionaire problem [9], quantum private query [10, 11], quantum private comparison [12] and so on have been proposed and have shown great power due to the unconditional security they provide. Based on various technologies such as quantum Fourier transform and quantum counting [13], single photons [14], GHZ states [15], some quantum PSI-CA protocols were also constructed. However, in these proposed PSI-CA protocols, some complex oracle operators are required [13] or they are probabilistic [13, 14], besides, they can only support two or three participants to perform calculations. For these reasons, based on entanglement swapping between d-level Bell states and d-level cat states, we propose a secure quantum protocol to deterministically calculate private set intersection cardinality and private set union cardinality for multiple participants.

Our paper mainly consists of 7 sections. Besides the first section for introduction, the remaining sections are organized as below: Section 2 is devoted to introducing the preliminary knowledge used in our protocol, Section 3 is devoted to the details of the protocol. Sections 4 and 5 are devoted to analyzing the correctness and the security of our protocol, respectively, Section 6 is devoted to the comparison between our protocol and some existing protocols, the last section concludes our paper.

2 Preliminary Knowledge

In our proposed protocol, the d-level Bell states, the d-level cat states and the entanglement swapping between them are utilized usually. Below we firstly review some useful details about them to ensure the legibility of the rest of the content.

2.1 d-Level Bell States

The d-level Bell state originally introduced in Ref [16] is a generalization of the Bell states [17]. We can write out the explicit form of the d-level Bell states as follow,

$$ |\boldsymbol{{\varPsi}}(u_{1},u_{2})\rangle:=\frac{1}{\sqrt{d}}\sum\limits_{g=0}^{d-1}\left( e^{\frac{2\pi i}{d}}\right)^{gu_{1}}|{g, g+u_{2}\mod d}\rangle, $$

where \(u_{1},u_{2} \in \mathbb {Z}_{d}\). For d = 2, let u1 and u2 take values form 0,1, respectively, we can get the classical Bell states,

$$ \begin{array}{@{}rcl@{}} |{\boldsymbol{{\varPsi}}(0,0)}\rangle=\frac{1}{\sqrt{2}}\left( |{00}\rangle+|{11}\rangle\right), \\ |{\boldsymbol{{\varPsi}}(0,1)}\rangle=\frac{1}{\sqrt{2}}\left( |{01}\rangle+|{10}\rangle\right), \\ |{\boldsymbol{{\varPsi}}(1,0)}\rangle=\frac{1}{\sqrt{2}}\left( |{00}\rangle-|{11}\rangle\right), \\ |{\boldsymbol{{\varPsi}}(1,1)}\rangle=\frac{1}{\sqrt{2}}\left( |{01}\rangle-|{10}\rangle\right). \end{array} $$

Through simple calculations, we can conclude that the d-level Bell states are pairwise orthogonal.

$$ \begin{array}{@{}rcl@{}} \langle{\boldsymbol{{\varPsi}}(v_{1},v_{2})|\boldsymbol{{\varPsi}}(u_{1},u_{2})}\rangle &=& \frac{1}{d}\sum\limits_{g=0}^{d-1}\sum\limits_{h=0}^{d-1}\left( e^{\frac{2\pi i}{d}}\right)^{(gu_{1}-hv_{1})} \langle{h|g}\rangle\langle{h\!+v_{2}\!\!\mod d|g+u_{2}\!\!\mod d}\rangle \\ &= & \frac{1}{d}\sum\limits_{g=0}^{d-1}\left( e^{\frac{2\pi i}{d}}\right)^{g(u_{1}-v_{1})}\langle{g+v_{2}\mod d|g+u_{2}\mod d}\rangle\\ &= & \delta_{u_{1}v_{1}}\delta_{u_{2}v_{2}}, \end{array} $$

where

$$ \delta_{uv}= \begin{cases} 1, & u=v \\ 0, & u \neq v \end{cases} $$

is Kronecker delta.

We can also get |Ψ(0,0)〉 easily,

$$ |{\boldsymbol{{\varPsi}}(0,0)}\rangle=\frac{1}{\sqrt{d}}\sum\limits_{g=0}^{d-1}|{g,g}\rangle, $$

and by defining unitary operator

$$ U_{u,v}:=\sum\limits_{g=0}^{d-1}\left( e^{\frac{2\pi i}{d}}\right)^{gu}|{g+v}\rangle\langle{g}|, $$

we can get |Ψ(u1,u2)〉 from |Ψ(0,0)〉,

$$ \begin{array}{@{}rcl@{}} \left( I \otimes U_{u_{1},u_{2}} \right)|{\boldsymbol{{\varPsi}}(0,0)}\rangle &=& \left( I \otimes \sum\limits_{g^{\prime}=0}^{d-1}\left( e^{\frac{2\pi i}{d}}\right)^{g^{\prime}u_{1}}|{g^{\prime}+u_{2}}\rangle\langle{g^{\prime}}|\right) \left( \frac{1}{\sqrt{d}}\sum\limits_{g=0}^{d-1}|{g,g}\rangle \right)\\ &= & \frac{1}{\sqrt{d}} \sum\limits_{g=0}^{d-1} |{g}\rangle\left( \sum\limits_{g^{\prime}=0}^{d-1}\left( e^{\frac{2\pi i}{d}}\right)^{g^{\prime}u_{1}}|{g^{\prime}+u_{2}}\rangle\langle{g^{\prime}|g}\rangle\right)\\ &= & \frac{1}{\sqrt{d}} \sum\limits_{g=0}^{d-1}\left( e^{\frac{2\pi i}{d}}\right)^{gu_{1}}|{g}\rangle|{g+u_{2}}\rangle \\ &= & |{\boldsymbol{{\varPsi}}(u_{1},u_{2})}\rangle \end{array} $$
(1)

where I is identical operator.

2.2 d-Level n-Particle Cat States

The d-level n-particle cat state, which was firstly introduced in Ref [18], is a generalization of the d-level Bell states from two qudits to n qudits. We can write out the form explicitly as below,

$$ |{\boldsymbol{{\varPsi}}(u_{1},u_{2},\dots, u_{n})}\rangle:=\frac{1}{\sqrt{d}}\sum\limits_{g=0}^{d-1}\left( e^{\frac{2\pi i}{d}}\right)^{gu_{1}}|{g,g+u_{2},\dots, g+u_{n}}\rangle, $$

where \(u_{1},u_{2},\dots , u_{n} \in \mathbb {Z}_{d}\). It is not difficult to see that for n = 2, they are reduced to d-level Bell states. In addition, when n = 3 and d = 2 they are the familiar 3-particle GHZ states [19, 20]. For example, the standard 3-particle GHZ state can be expressed as

$$ |{\boldsymbol{{\varPsi}}(0,0,0)}\rangle=\frac{1}{\sqrt{2}}\left( |{000}\rangle+|{111}\rangle\right). $$

Similar to the d-level Bell states, d-level cat states are also pairwise orthogonal,

$$ \langle{\boldsymbol{{\varPsi}}(v_{1},v_{2},\dots, v_{n})|\boldsymbol{{\varPsi}}((u_{1},u_{2},\dots, u_{n}))}\rangle = \delta_{u_{1}v_{1}}\delta_{u_{2}v_{2}}\dots\delta_{u_{n}v_{n}}, $$

and they form a set of orthonomal basis of the dn-dementional Hilbert space composed by n qudits.

2.3 Entanglement Swapping Between d-Level Bell States and d-Level Cat States

Entanglement Swapping between d-Level Bell States and d-Level Cat States was firstly introduced in Ref [18]. Imagine that we have a d-level Bell state and a d-level cat state. By performing d-level Bell measurement on one particle in the d-level Bell state and one particle in the d-level cat state the entanglement swapping occurs, and we obtain a new d-level Bell state and a new d-level cat state. We can also use following mathematical expression to describe this process.

$$ \begin{array}{@{}rcl@{}} && |{\boldsymbol{{\varPsi}}(u,u^{\prime})}\rangle_{s,s^{\prime}} \otimes |{\boldsymbol{{\varPsi}}(v_{1},v_{2},\dots,v_{i},\dots, v_{n})}\rangle_{t_{1},{\dots} , t_{i}, {\dots} ,t_{n}}\\ &&= \frac{1}{d}\sum\limits_{g,h=0}^{d-1}\left( e^{\frac{2\pi i}{d}}\right)^{gh}|{\boldsymbol{{\varPsi}}(u-g,v_{i}-h)}\rangle_{s,t_{i}}\\ && \otimes |{\boldsymbol{{\varPsi}}(v_{1}+g,v_{2}, \dots, u^{\prime}+h, {\dots} v_{n})}\rangle_{t_{1},\dots,s^{\prime},\dots,t_{n}}, \end{array} $$
(2)

where s, \(s^{\prime }\) are the labels of the two particles in the d-level Bell state, \(t_{1},\dots \), ti, \(\dots \), tn are the labels of the n particles in the d-level cat state. Particle \(s^{\prime }\) and particle ti(2 ≤ i ≤ n) are the two particles on which the d-level Bell measurement is performed. Suppose that the measurement result is |Ψ(u − g,vs − h)〉, we obtain the new Bell state |Ψ(u − g,vs − h)〉 and the new cat state \(|{\boldsymbol {{\varPsi }}(v_{1}+g,v_{2}, \dots , u^{\prime }+h, {\dots } v_{n})}\rangle \).

In order to understand this process intuitively, we give out a figure (Fig. 1) to depict it. In the upper part of the figure, the horizontal line with n nodes represents the n-particle cat state, and the vertical line with two nodes represents the Bell state. The square nodes represent the first particles in the Bell state and the cat state which are not involved in the process of the entanglement swapping. The vertical downward arrow represents the d-level Bell measurement on the particle s and ti, and |Ψ(u − g,vi − h)〉 is the measurement result. \(|{\boldsymbol {{\varPsi }}(v_{1}+g,v_{2}, \dots , u^{\prime }+h, {\dots } v_{n})}\rangle \) indicated by the broken line in the lower part of the figure is the swapped cat state.

Fig. 1
figure 1

Entanglement swapping between a Bell state and a cat state

Full size image

3 The Proposed Protocol

Suppose that there exist m(m ≥ 2) participants named \(P_{1}, P_{2}, \dots , P_{m}\). Each \(P_{i}(i=1,2,\dots , m)\) holds a secret set Ai whose cardinality is less than or equal to N and whose elements are in \(\mathbb {Z}_{N}\). We can express Ai as \(\left ({a_{i}^{0}}, {a_{i}^{1}}, \dots , a_{i}^{n_{i}}\right )\), where \({a_{i}^{j}} \in \mathbb {Z}_{N}(0 \leq j \leq n_{i})\) and ni < N. The participants hope to calculate the cardinalities of the intersection and the union of their secret sets with keeping their secret sets unknown to each other.

In the following, we propose a secure protocol to perform this task with the aid of a semi-honest TP introduced in Ref [21]. The semi-honest TP may misbehave himself as long as without collude with any participant. That is to say, in addition to not colluding with any other participants, TP is allowed to try his best, including actively eavesdropping, to obtain the participants’ secrets. The protocol makes use of d-level Bell states and d-level cat states (d > m).

  • Step 1: Each participant \(P_{i}(i=1,2,\dots ,m)\) encodes his secret set \(A_{i}=\left ({a_{i}^{0}}, {a_{i}^{1}}, \dots ,a_{i}^{n_{i}}\right )\) as below. First, Pi maps Ai to a binary set \({\tilde B}_{i}=\left ({\tilde x}_{i}^{0}, {\tilde x}_{i}^{1}, \dots , {\tilde x}_{i}^{N-1}\right )\) according to the following rule: for each j in \(\mathbb {Z}_{N}\),

    $$ {\tilde x}_{i}^{j} = \begin{cases} 1, & \text{if } j \in A_{i}; \\ 0, & \text{if } j \notin A_{i}. \end{cases} $$
    (3)

    Second, Pi applies the permutation pre-shared privately by all participants except TP

    $$ \hat P=\left( \begin{array}{cccc} {1,} & {2,} & {\dots,} & {N} \\ {\hat P(1),} & {\hat P(2),} & {\dots,} & {\hat P(N)} \end{array} \right) $$

    on \({\tilde B}_{i}\) to mess it up and obtains a new binary set \({B}_{i}=\left ({x}_{i}^{0}, {x}_{i}^{1}, \dots , {x}_{i}^{N-1}\right )\), where \({x^{j}_{i}}={\tilde x}^{\hat P(j+1)-1}_{i}(j=0,1,\dots ,N-1)\). At last, Pi prepares N d-level Bell states |Ψ(0,0)〉 and encodes Bi into d-level Bell states according to Formula (1),

    $$ |{\boldsymbol{{\varPsi}}({u_{i}^{j}},{x_{i}^{j}})}\rangle_{{s_{i}^{j}},{s^{\prime}}_{i}^{j}}=\left( I \otimes U_{{u_{i}^{j}},{x_{i}^{j}}} \right)|{\boldsymbol{{\varPsi}}(0,0)}\rangle, $$

    where \(j=0,1,\dots ,N-1\), \({u_{i}^{j}}\) is randomly chose from \(\mathbb {Z}_{d}\), \({s_{i}^{j}},{s^{\prime }}_{i}^{j}\) are labels of the two particles of the j-th Bell state.

  • Step 2: TP first prepares N d-level m + 1 particle cat states

    $$ |{\boldsymbol{{\varPsi}}({v_{0}^{j}},{v_{1}^{j}},{v_{2}^{j}},\dots, {v_{m}^{j}})}\rangle_{{t_{0}^{j}},{t_{1}^{j}},\dots,{t_{m}^{j}}}, $$

    where \(j=0,1,2,\dots ,N-1\), \({v_{i}^{j}}\) is randomly chose from \(\mathbb {Z}_{d}\), \({t_{i}^{j}}\) is the label of the i-th particle of the j-th cat state \((i=0,1,2,\dots ,m)\). For \(i=1,2,\dots ,m\), TP extracts the i-th particle from each cat state to form a particle sequence labeled by \(({t_{i}^{0}},{t_{i}^{1}},{t_{i}^{2}},\dots ,t_{i}^{N-1})\), which is denoted as Qi. Then, TP prepares decoy particles for each Qi to prevent from eavesdropping by randomly choosing particles from \(\left \{|{k}\rangle , \frac {1}{\sqrt {d}}{\sum }_{j=0}^{d-1}\left (e^{\frac {2\pi i}{d}}\right )^{jk}|{j}\rangle \right \}(k=0,1,\dots ,d-1)\) and inserting them into Qi at random positions. The new particle sequence is denoted as \(Q^{\prime }_{i}\). Finally, TP sends particle sequence \(Q^{\prime }_{i}\) to participant Pi. Note that the particle sequence labeled \(({t_{0}^{0}},{t_{0}^{1}},{t_{0}^{2}},\dots ,t_{0}^{N-1})\) is kept by TP on his own.

  • Step 3: For each Pi, after he receives \(Q^{\prime }_{i}\), TP first informs Pi of the positions and the bases of the decoy particles in \(Q^{\prime }_{i}\), then Pi measures the decoy particles according to the information that TP has told him and sends the measurement results to TP, finally, TP checks whether there exist eavesdroppers in the quantum channel in accordance with the results sent by Pi. If TP confirms that the channel is not secure, he aborts the protocol and restart a new one, otherwise he continues to perform the protocol.

  • Step 4: Each \(P_{i}(i=1,2,\dots ,m)\) restores Qi from \(Q^{\prime }_{i}\) by discarding the decoy particles, and then performs N times d-level Bell measurements on the first particles from his own Bell states and the particles sent by TP. Concretely, for \(j=0, 1,\dots , N-1\), Pi jointly measures the particle labeled by \({s_{i}^{j}}\) from the Bell state \(|{\boldsymbol {{\varPsi }}({u_{i}^{j}},{x_{i}^{j}})}\rangle _{{s_{i}^{j}},{s^{\prime }}_{i}^{j}}\) and the particle labeled by \({t_{i}^{j}}\) from the cat state \(|{\boldsymbol {{\varPsi }}({v_{0}^{j}},{v_{1}^{j}},{v_{2}^{j}},\dots , {v_{m}^{j}})}\rangle _{{t_{0}^{j}},{t_{1}^{j}},\dots ,{t_{m}^{j}}}\). Suppose that the measurement results are \(|{\boldsymbol {{\varPsi }}({r_{i}^{j}},{r^{\prime }}_{i}^{j})}\rangle _{{s_{i}^{j}},{t_{i}^{j}}}\), where \({r_{i}^{j}}={u_{i}^{j}}-{g_{i}^{j}} \mod d, {r^{\prime }}_{i}^{j}={v_{i}^{j}}-{h_{i}^{j}} \mod d\).

  • Step 5: All participants cooperate to compute

    $$ R^{j}=\sum\limits_{i=1}^{m}{r^{\prime}}_{i}^{j} $$
    (4)

    for \(j=0,1,2,\dots ,N-1\). In order to prevent TP from eavesdropping on the data transmitted in this process, \({r^{\prime }}_{i}^{j}\) can be encrypted with a pre-shared key in advance. Next, the Rj and the particle sequences labeled by \(({s^{\prime }}_{i}^{0},{s^{\prime }}_{i}^{1},\dots , {s^{\prime }}_{i}^{N-1})\) are sent to TP. Similar to Step 3, the decoy state particles are used to prevent others from eavesdropping.

  • Step 6: After receiving all particle sequences sent by all participants, for \(j=0,1,2,\dots , N-1\), TP performs d-level cat state measurement on d-level m + 1 particle cat state labeled by \(({t_{0}^{j}},{s^{\prime }}_{1}^{j},{s^{\prime }}_{2}^{j},\dots ,{s^{\prime }}_{m}^{j})\), and gets the result, for example,

    $$ |{\boldsymbol{{\varPsi}}({\tilde r}_{0}^{j},{\tilde r}_{1}^{j},{\tilde r}_{2}^{j},\dots,{\tilde r}_{m}^{j})}\rangle, $$

    where

    $$ \begin{array}{@{}rcl@{}} {\tilde r}_{0}^{j} &=&{v_{0}^{j}}+\sum\limits_{i=1}^{m}{g_{i}^{j}} \mod d,\\ {\tilde r}_{i}^{j} &=&{x_{i}^{j}}+{h_{i}^{j}} \mod d, (i=1,2,\dots,m). \end{array} $$

    Next, TP generates two variables CI, CU and initiates them to zero. For each j in \(\mathbb {Z}_{N}\), TP computes

    $$ X_{j}=\sum\limits_{i=1}^{m}{\tilde r}_{i}^{j} + R^{j} - \sum\limits_{i=1}^{m}{v_{i}^{j}} \mod d, $$
    (5)

    and updates the values of CI, CU according to

    $$ C_{I}= \begin{cases} C_{I}+1, & \text{if } X_{j}=m; \\ C_{I}, & \text{if } X_{j} \ne m, \end{cases} $$
    $$ C_{U}= \begin{cases} C_{U}+1, & \text{if } X_{j} > 0; \\ C_{U}, & \text{if } X_{j} = 0. \end{cases} $$

    At last, TP obtains the intersection cardinality CI and the union cardinality CU and announces them to all participants.

4 Correctness Analysis

In this section we will explain why our protocol is correct. Each participant Pi has a secret set \(A_{i}=\left ({a_{i}^{0}}, {a_{i}^{1}}, \dots , a_{i}^{n_{i}}\right )\). In step 1, the set Ai is mapped to \({\tilde B}_{i}=\left ({\tilde x}_{i}^{0}, {\tilde x}_{i}^{1}, \dots , {\tilde x}_{i}^{N-1}\right )\) in accordance with Formula (3). That is, for \(j=0,1,\dots ,N-1\),

$$ {\tilde x}_{i}^{j} = \begin{cases} 1, & \text{if } j \in A_{i}; \\ 0, & \text{if } j \notin A_{i}. \end{cases} $$

Then the set \({\tilde B}_{i}\) is shuffled into \(B_{i}=\left ({x}_{i}^{0}, {x}_{i}^{1}, \dots , {x}_{i}^{N-1}\right )\) by a random permutation \(\hat P\), where \({x^{j}_{i}}={\tilde x}^{\hat P(j+1)-1}_{i}(j=0,1,\dots ,N-1)\). Let’s give a simple example. Assuming N = 7, Ai = (1,4,5) and

$$ \hat P = \left( \begin{array}{ccccccc} {0,} & {1,} & {2,} & {3,} & {4,} & {5,} & 6 \\ {3,} & {6,} & {4,} & {1,} & {5,} & {0,} & 2 \end{array} \right), $$

thus, \({\tilde B}_{i}=(0, 1, 0, 0, 1, 1, 0)\) can be obtained after mapping, and then Bi = (0,0,1,1,1,0,0) can be obtained after shuffling.

At the end of step 1, Bi is encoded into N d-level Bell states and the following particle sequence are formed,

$$ |{\boldsymbol{{\varPsi}}({u_{i}^{0}},{x_{i}^{0}})}\rangle_{{s_{i}^{0}},{s^{\prime}}_{i}^{0}}, |{\boldsymbol{{\varPsi}}({u_{i}^{1}},{x_{i}^{1}})}\rangle_{{s_{i}^{1}},{s^{\prime}}_{i}^{1}}, \dots, |{\boldsymbol{{\varPsi}}(u_{i}^{N-1},x_{i}^{N-1})}\rangle_{s_{i}^{N-1},{s^{\prime}}_{i}^{N-1}}. $$

TP prepares Nd-level m + 1 particle cat states

$$ \begin{array}{@{}rcl@{}} && |{\boldsymbol{{\varPsi}}({v_{0}^{0}},{v_{1}^{0}},{v_{2}^{0}},\dots, {v_{m}^{0}})}\rangle_{{t_{0}^{0}},{t_{1}^{0}},\dots,{t_{m}^{0}}},\\ && |{\boldsymbol{{\varPsi}}({v_{0}^{1}},{v_{1}^{1}},{v_{2}^{1}},\dots, {v_{m}^{1}})}\rangle_{{t_{0}^{1}},{t_{1}^{1}},\dots,{t_{m}^{1}}},\\ && \dots,\\ && |{\boldsymbol{{\varPsi}}(v_{0}^{N-1},v_{1}^{N-1},v_{2}^{N-1},\dots, v_{m}^{N-1})}\rangle_{t_{0}^{N-1},t_{1}^{N-1},\dots,t_{m}^{N-1}}. \end{array} $$

For \(j=0,1,\dots ,N-1\), Pi performs d-level Bell measurement on the particle \({s_{i}^{j}}\) from his own Bell state and the particle \({t_{i}^{j}}\) from TP’s cat state with the measurement result \(|{\boldsymbol {{\varPsi }}({u_{i}^{j}}-{g_{i}^{j}} \mod d, {v_{i}^{j}}-{h_{i}^{j}} \mod d)}\rangle \). After all participants complete Bell measurements, according to Formula (2), the j-th cat state becomes

$$ \begin{array}{@{}rcl@{}} |\boldsymbol{{\varPsi}}({v_{0}^{j}}+\sum\limits_{i=1}^{m}{g_{i}^{j}} & \mod d,\\ {x_{1}^{j}}+{h_{1}^{j}} & \mod d ,\\ {x_{2}^{j}}+{h_{2}^{j}} & \mod d ,\\ \dots,\\ {x_{m}^{j}}+{h_{m}^{j}} & \mod d ) \rangle. \end{array} $$

This process and result can be visually showed in Fig. 2 (the superscript j is omitted).

Fig. 2
figure 2

Entanglement swappings between n Bell states and a cat state

Full size image

We can rewrite Formula (4) as

$$ \begin{array}{@{}rcl@{}} \sum\limits_{i=1}^{m}{r^{\prime}}_{i}^{j} &=&\sum\limits_{i=1}^{m}\left( {v_{i}^{j}}-{h_{i}^{j}} \mod d \right) \\ &=&\sum\limits_{i=1}^{m}{v_{i}^{j}}-\sum\limits_{i=1}^{m}{h_{i}^{j}} + \alpha d, \end{array} $$

where α ≤ m is the number of occurrences of modular operations. In Formula (5), \({\sum }_{i=1}^{m}{\tilde r}_{i}^{j}\) can be rewritten as

$$ \begin{array}{@{}rcl@{}} \sum\limits_{i=1}^{m}{\tilde r}_{i}^{j} &=&\sum\limits_{i=1}^{m}\left( {x_{i}^{j}}+{h_{i}^{j}} \mod d \right) \\ &=&\sum\limits_{i=1}^{m}{x_{i}^{j}}+\sum\limits_{i=1}^{m}{h_{i}^{j}} - \beta d \end{array} $$

where β ≤ m is also the number of occurrences of modular operations. Thus, \(X_{j}={\sum }_{i=1}^{m}{x_{i}^{j}}\) can be calculated as follow,

$$ \begin{array}{@{}rcl@{}} X_{j}=\sum\limits_{i=1}^{m}{x_{i}^{j}} = \sum\limits_{i=1}^{m}{\tilde r}_{i}^{j} + \sum\limits_{i=1}^{m}{r^{\prime}}_{i}^{j} - \sum\limits_{i=1}^{m}{v_{i}^{j}} -(\alpha - \beta)d. \end{array} $$

Consider d > m and therefore \({\sum }_{i=1}^{m}{x_{i}^{j}} < d\), we have

$$ \begin{array}{@{}rcl@{}} X_{j}=\sum\limits_{i=1}^{m}{\tilde r}_{i}^{j} + R^{j} - \sum\limits_{i=1}^{m}{v_{i}^{j}} \mod d. \end{array} $$

Obviously, Xj is the number of “1”s in the j-th (starting from 0) position of all \(B_{i}(i=1, 2, \dots , m)\). If Xj = m, it means that every participant has \(\hat P^{-1}(j)\) in his secret set, namely, \(\hat P^{-1}(j)\) is in the \(\bigcap _{i=1}^{m}A_{i}\). By counting the number of Xj = m for \(j=0, 1, \dots , N-1\), we can obtain the cardinality of the intersection \(\bigcap _{i=1}^{m}A_{i}\), i.e. \(C_{I}=|\bigcap _{i=1}^{m}A_{i}|\). Similarly, If Xj > 0, it means that at least one participant has \(\hat P^{-1}(j)\) in his secret set, namely, \(\hat P^{-1}(j)\) is in the \(\bigcup _{i=1}^{m}A_{i}\). Through counting the number of Xj > 0 for \(j=0, 1, \dots , N-1\), we can get the cardinality of the union \(\bigcup _{i=1}^{m}A_{i}\), i.e. \(C_{U}=|\bigcup _{i=1}^{m}A_{i}|\). Therefor, the correct result can be acquired by performing our proposed protocol.

5 Security Analysis

In this section, it is showed that our protocol can resist three types of threats: external attack, participants’ attack and semi-honest TP’s attack. For defending against external attack, it is showed that the external eavesdroppers cannot steal the secret set held by every participant. For defending against participants’ attack, it is showed that at most n − 1 dishonest participants who collude together cannot succeed. For defending against semi-honest TP’s attack, it is showed that the TP cannot successfully steal the secrets as long as he does not collude with any participants.

5.1 External Attack

In this subsection, we analyze the reason why the eavesdroppers from outside cannot obtain the secrets in each step of the protocol.

In Step 1, Step 3 and Step 4, since neither quantum nor classical information is transmitted, any external eavesdroppers cannot obtain anything useful.

In Step 2, the qudits from d-level cat states prepared by semi-honest TP are transmitted. Therefor, some attacks, for example, intercept–resend attack, entangle–measure attack and measure–resend attack, may be launched by eavesdroppers. Our protocol use decoy states [22] to prevent outside eavesdroppers from stealing secrets through these attacks. Just like BB84 protocol [8], decoy state technology is an effective means to check whether there are outside eavesdroppers. In the process of transporting qudit particle sequences, decoy state particles are randomly inserted into them. Similar to the reason analyzed in Ref [23], the decoy states in d-level quantum system can also ensure the security of qudit sequences transportation. If an outside eavesdropper exists, he can be detected efficiently. Moreover, the qudit sequences transmitted in this step does not carry any participants’ secret information and therefore nothing can be stolen.

In Step 5, \(R^{j}(j=0,1,\dots ,N-1)\) is transmitted to TP. Because Rj is independent of \({x_{i}^{j}}\), there is no information about xi is leaked. In the quantum transmission stage, just as in Step 2, decoy particles are utilized and eavesdroppers can be detected. In addition, we can know that there are not any information leaked while particles \({s^{\prime }}_{i}^{j}\) are transmitted to TP through the following analysis. After each participant Pi completes the d-level Bell measurement, the density operator of the j-th quantum system \({i=1}^{m}|{\boldsymbol {\varPsi }({u_{i}^{j}},{x_{i}^{j}})}\rangle \otimes |{\boldsymbol {{\varPsi }}({v_{0}^{j}}, {v_{1}^{j}}, \dots , {v_{n}^{j}})}\rangle \) becomes where

$$ \begin{array}{@{}rcl@{}} u_{i} &=&{u_{i}^{j}}-{g_{i}^{j}}, \quad {u^{\prime}}_{i}={v_{i}^{j}}-{h_{i}^{j}},\\ v_{0} &=&{v_{0}^{j}}+\sum\limits_{i=1}^{m}{g_{i}^{j}},\\ v_{i} &=&{x_{i}^{j}}+{h_{i}^{j}}, \quad (i=1,2,\dots,m). \end{array} $$

Tracing out the other qudits, we get the reduced density operator of the qudit \({s^{\prime }}_{i}^{j}\),

$$ \begin{array}{@{}rcl@{}} \rho_{{s^{\prime}}_{i}^{j}}&=&\text{Tr}_{others}(\rho)\\ &=&\text{Tr}^{\prime}\left( |{\boldsymbol{{\varPsi}}(v_{0},v_{1},\dots,v_{m})}\rangle\langle{\boldsymbol{{\varPsi}}(v_{0},v_{1},\dots,v_{m})}|\right) \\ &=&\frac{1}{d}\text{Tr}^{\prime}\left[\bigg(\sum\limits_{g=0}^{d-1}\left( e^{\frac{2\pi i}{d}}\right)^{gv_{0}}|{g,\dots,g+v_{i}}\rangle \right) \\ && \quad\quad\quad\quad \bigg(\sum\limits_{g^{\prime}=0}^{d-1}\left( e^{\frac{-2\pi i}{d}}\right)^{g^{\prime}v_{0}}\langle{g^{\prime},\dots,g^{\prime}+v_{i}}| \bigg) \Bigg] \\ &=&\frac{1}{d}\sum\limits_{g=0}^{d-1}|{g+v_{i}}\rangle\langle{g+v_{i}}|\\ &=&\frac{I}{d}, \end{array} $$

where \(\text {Tr}^{\prime }\) stands for tracing out qudits labeled by \({t_{0}^{j}},{s^{\prime }}_{1}^{j},\dots ,{s^{\prime }}_{i-1}^{j},{s^{\prime }}_{i+1}^{j},\dots ,{s^{\prime }}_{m}^{j}\), I is identical operator. So, the qudit \({s^{\prime }}_{i}^{j}\) is completely depolarized and no information is leaked while it is being transmitted.

In Step 6, TP announces the final results and the external attackers can not obtain any participants’ secret.

5.2 Participants’ Attack

As a powerful form of attack, participants’ attack [24] is launched by either one or more dishonest participants. In situation involving multiple dishonest participants, the collusion between them need to be considered. Below, we will analyze the security of our protocol under the attacks launched by one dishonest participant and by multiple conspiring dishonest participants, respectively.

First, we analyze the security in the case of only one dishonest participant attacking the protocol. Without loss of generality, we suppose that P1 wants to steal other participants’ secret sets or the intersection or the union. In our protocol, there is no qudit particle transmission between P1 and other participants, and the qudit particle transmission only exists between participants and the semi-honest TP. If P1 wants to steal information, he must intercept the qudit particles transmitted between TP and other participants in Step 2 and Step 5. Thus, P1 can be revealed just like an outside eavesdropper due to the use of decoy particles and cannot obtain any useful information from the intercepted particles for the same reason analyzed in the above subsection. In Step 5, Rj can be known by P1, but it is helpless for P1 to get xi because xi and Rj are not related. In addition, because P1 does not collude with TP, he cannot know which “j” satisfies Xj = m or Xj > 0, namely, he cannot know the positions of the elements in the intersection or in the union. Even though he knows the random permutation, he cannot obtain the intersection or the union. Therefore, a dishonest participant cannot steal the corresponding secrets held by other participants.

Second, we analyze the security of the protocol when multiple dishonest participants collude together. In order to explain the security to a greater extent, we consider the extreme case, that is, there are m − 1 participants collude together to steal the set held by the remaining one participant or the intersection or the union. Without loss of generality, we suppose that \(P_{1},P_{2},\dots ,P_{m-1}\) collude together to steal the secret set of Pm. Since Pm only transmits qudit particles with TP, the conspiring dishonest participants need to intercept the particles transmitted between Pm and TP to obtain the secrets of Pm. Thus, they can be put in light as external attackers due to the utilization of decoy state technology and cannot obtain any useful information from the intercepted qudits since these qudits are completely depolarized. Besides, \(P_{1},P_{2},\dots ,P_{m-1}\) cannot get xm from Rj in Step 5 due to the independence of xm and Rj, and cannot know the intersection and the union for the same reason mentioned above. So, even though up to m − 1 dishonest participants collude together, they still cannot obtain the secrets they shouldn’t deserve.

5.3 Semi-honest TP’s Attack

In our proposed protocol, although the semi-honest TP can obtain \({x_{i}^{j}}+{h_{i}^{j}}\) and Rj, he still can not know \({x_{i}^{j}}\) because \({h_{i}^{j}}\) cannot be deduced from Rj if he does not collude with other participants. Furthermore, TP can not know the concrete elements in the intersection and the union of the secret sets since the random permutation is used. That is, TP cannot deduce the \(\hat P^{-1}(j)\) from j because he does not know \(\hat P\). So, a semi-honest TP, as long as he does not collude whit other participants, he cannot successfully obtain the secrets of the participants, including the secret sets themselves, the intersection and the union.

6 Comparison

In this section, we will compare our newly proposed protocol with some existing protocols in terms of quantum resource, quantum operators, quantum measurement, the maximum number of participants, the output and the type (probabilistic or deterministic). The details of the comparison are shown in Table 1. We can obviously find that our protocol has the significant advantages of simultaneously calculating the intersection cardinality and the union cardinality of multiple private sets with deterministic results.

Table 1 Comparison between our protocol and some existing protocols
Full size table

7 Conclusion

In this paper, based on the entanglement swapping between d-level Bell states and d-level cat states, we proposed a novel quantum protocol to simultaneously calculate private set intersection cardinality and private set union cardinality with the aid of a semi-honest TP. First, TP prepares d-level cat states and then distributes the corresponding part of them to each participant who wants to compute the intersection cardinality and the union cardinality without disclosing his own secret. Second, All participants encode their private sets into d-level Bell states and perform the measurements on the first particles of their own Bell states and the particles received from TP to complete the entanglement swapping. At last, TP performs d-level cat state measurements on the particles sent back by all participants and calculate the final result. In the case of TP and participants not colluding, our protocol can resist attacks from external attackers, participants and semi-honest TP, even though at most m − 1 participants collude together (m is the number of participants).