Multi-party quantum private comparison protocol based on $d$-dimensional entangled states

Abstract

In this paper, a novel quantum private comparison protocol with $l$-party and $d$-dimensional entangled states is proposed. In the protocol, $l$ participants can sort their secret inputs in size, with the help of a semi-honest third party. However, if every participant wants to know the relation of size among the $l$ secret inputs, these two-participant protocols have to be executed repeatedly $\frac{l(l-1)}{2}$ times. Consequently, the proposed protocol needs to be executed one time. Without performing unitary operation on particles, it only need to prepare the initial entanglement states and only need to measure single particles. It is shown that the participants will not leak their private information by security analysis.

1 Introduction

Since Bennett and Brassard [1] presented the first quantum key distribution protocol (BB84 protocol), quantum cryptography has been rapidly developed. Compared to classical cryptography, the main advantages is that an eavesdropper can easily be detected by using the characteristics of quantum mechanics. Therefore, a lot of results have been gained, such as quantum key distribution [1–4], quantum commitment [5–8], quantum secret sharing [9–12], quantum secure direct communication [13–16], quantum conversation [17] and so on.

In recent years, quantum privacy comparison (QPC) protocols attract many researchers’ attention. Privacy comparison protocol can be traced to the millionaire problem proposed by Professor Yao [18]. He pointed out that ‘Two millionaires wish to know who is richer; however, they do not want to find out inadvertently any additional information about each other’s wealth. How can they carry out such a conversation?’. By this question, Professor Yao introduced Secure computation. Then, Goldreich et al. [19] developed it as a secure multiparty computation. Unfortunately, Lo [20] pointed out that a quantum two-party secure computation is impossible. However, Yang and Wen [21] presented a QPC protocol with the assistance of a semi-trusted third party. In the ensuing years, there are numerous results on QPC protocol.

We put these studies into four stages. In the first stage, two distrustful participants compared the equivalence of their private information. According to what Liu et al summarized in Ref. [22], the research results of this stage have been divided into three categories: (1) the quantum cryptography QPC [23, 24], (2) the superdense coding QPC [21, 25–27], (3) the entanglement swapping QPC [28–30]. In the second stage, two participants compared the size of their secret inputs. Lin et al. [31] proposed a QPC protocol which can compare the size of two participants’ inputs based on $d$-dimensional Bell states, Zhang et al. [32] solved the millionaires problem based on it. In the third stage, multiple participants compared the equivalence of information, Chang et al. [33] proposed a QPC protocol which can compare the equivalence of multi-participants’ information using GHZ states. Liu et al. [34] presented a multi-party quantum private protocol based on $d$-dimensional basis states. In the fourth stage, multi-participants compare the size of their secret inputs. It is a pity that there are no research results appear so far. This paper focuses on this issue.

In this paper, we present a novel quantum private comparison protocol with $l$-party and $d$-dimensional entangled states, with the help of a semi-honest third party. $l$ participants’ secret inputs can be sorted in size. Here, semi-honest third party (TP) refers, he will be strictly in accordance with the implementation of the protocol. That is to say TP will not conspire with external attackers or participants, even though he may be very curious about participants’ secret information, and want to deduce it. The rest of this paper is organized as follows. In Sect. 2, the preliminaries are introduced. In Sect. 3, the protocol is described in details. In Sect. 4, the security and efficiency are analyzsed. Finally, a short conclusion is given in Sect. 5.

2 Preliminaries

In this section, we will discuss the pre-knowledge of the protocol, which includes modulo $d$ subtraction ‘$\ominus$’, maximally entangled states which are $l$-party and $d$-dimension, and their properties.

2.1 The property of subtraction modulo $d$

Subtraction operation ‘$\ominus$’ can be seen as the inverse operation of ‘$\oplus$’ in the remainder plus group of modulo $d$ $(Z_{d}, \oplus )$, i.e., for $\forall a,b\in Z_{d},a\ominus b=a\oplus b^{-1}$(where $b^{-1}$ is the inverse element of $b$ in group $Z_{d}$). So, ‘$\ominus$’ operation can be seen the binary operation in residue class $Z_{d}$. We assume that the strict total order of the elements in $Z_{d}$ is $\bar{0}<\bar{1}<\cdots <\bar{d-1}$(without confusion, we still denote the elements as $0,1\cdots d-1$). The ‘$\ominus$’ operation has the property which will be used in the following pages as follows:

For two natural numbers $n_{1},n_{2}\in \{0,1,\ldots ,n\}$, set $d=2n+1$, the relationship in size between $n_{1}$ and $n_{2}$ can be ascertained by the mapping $\sigma$, where

$$\begin{aligned} \sigma (n_{1}\ominus n_{2})= \left\{ \begin{array}{lll} n_{1}=n_{2}\quad :\quad \hbox {if} (n_{1}\ominus n_{2}=0)\\ n_{1}>n_{2}\quad :\quad \hbox {if}0<(n_{1}\ominus n_{2})\le n\\ n_{1}<n_{2}\quad :\quad \hbox {if}n<(n_{1}\ominus n_{2})\le 2n \end{array} \right. \end{aligned}$$

(1)

In fact, for $n_{1},n_{2}\in \{0,1,\ldots ,n\}$, in the remainder plus group $Z_{d}$(where $d=2n+1$), if $n_{1}=n_{2}$, then $n_{1}\ominus n_{2}=n_{1}\oplus n_{2}^{-1}=n_{1}\oplus n_{1}^{-1}=0$. Because the inverse of the element in the group is unique, it is true, vice versa. If $n_{1}>n_{2}$, set $n_{1}=n_{0}\oplus n_{2}$ (where $n_{0}\in \{1,2,\ldots ,n\}$), then $n_{1}\ominus n_{2}=n_{1}\oplus n_{2}^{-1}=n_{0}\oplus n_{2}\oplus n_{2}^{-1}=n_{0}$, so $0<(n_{1}\ominus n_{2})\le n$, and conversely. If $n_{1}<n_{2}$, set $n_{2}=n_{0}\oplus n_{1}$, then $n_{2}^{-1}=n_{1}^{-1}\oplus n_{0}^{-1}$, now $n_{1}\ominus n_{2}=n_{1}\oplus n_{2}^{-1}=n_{1}\oplus n_{1}^{-1}\oplus n_{0}^{-1}=n_{0}^{-1}$, since $n_{0}\in \{1,2,\ldots ,n\}$,$n_{0}^{-1}=d\ominus n_{0}\in \{n+1,n+2,\ldots ,2n\}$, we conclude that $n<(n_{1}\ominus n_{2})\le 2n$, and conversely.

2.2 $L$-party and $d$-dimensional entangled state

In this subsection, we introduce a maximally entangled state which is $l$-party and $d$-dimension, and its properties. Its application of superdense coding was discussed in Ref. [35].

$$\begin{aligned} |\psi ^{s}_{v_{2},v_{3},\ldots ,v_{l}}\rangle = \frac{1}{\sqrt{d}}\sum _{j=1}^{d-1}e^{\frac{2\pi ijs}{d}}|j\oplus 0\rangle \otimes |j\oplus v_{2}\rangle \otimes \cdots \otimes |j\oplus v_{l}\rangle \end{aligned}$$

(2)

Here, ‘$\oplus$’ is addition modulo $d$, where $s,v_{2},v_{3},\ldots ,v_{l}\in \{0,1,\ldots ,d-1\}$, we set the increment of the first particle: $v_{1}=0$.

As same as Ref. [32], two mutually unbiased orthogonal bases are utilized. One is $MB=\{|0\rangle ,|1\rangle ,\ldots ,|d-1\rangle \}$, the other is $MF=\{F|0\rangle ,F|1\rangle ,\ldots ,F|d-1\rangle \}$, where ‘$F$’is discrete Fourier transform defined as follows

$$\begin{aligned} F|j\rangle =\frac{1}{\sqrt{d}}\sum _{k=1}^{d-1}e^{\frac{2\pi ijk}{d}}|k\rangle , j=0,1,\ldots ,d-1. \end{aligned}$$

(3)

Suppose the measurement value of the single-particle states $|0\rangle$ is $0$, $|1\rangle$ is $1$, $\ldots$, $|d-1\rangle$ is $d-1$ in the basis $MB=\{|0\rangle ,|1\rangle ,\ldots ,|d-1\rangle \}$. If the initial maximally entangled state in $(1)$ has been known, the measurement value of $i$th and $j$th particle do ‘$\ominus$’ operation, the value is $v_{i}\ominus v_{j}$.

In order to clearly explain the property, let us take the four-particle entangled state in $(1)$ as an example. The four-particle entangled state is shown as follows:

$$\begin{aligned} |\psi ^{0}_{130}\rangle =\frac{1}{2} (|0130\rangle +|1201\rangle +|2312\rangle +|3023\rangle ) \end{aligned}$$

(4)

set the measurement value of $i$th is $k_{i}(i=1,2,3,4)$, we know these value, $k_{1}\ominus k_{2}=3$, $k_{1}\ominus k_{3}=1$, $k_{1}\ominus k_{4}=0$, $k_{2}\ominus k_{3}=2$, $k_{2}\ominus k_{4}=1$, $k_{3}\ominus k_{4}=3$; $k_{4}\ominus k_{1}=0$, $k_{4}\ominus k_{2}=3$, $k_{4}\ominus k_{3}=1$, $k_{3}\ominus k_{1}=3$, $k_{3}\ominus k_{2}=2$, $k_{2}\ominus k_{1}=1$.

3 Protocol

In this section, a multi-participant QPC protocol is proposed in detail. Suppose $l$ participants want to compare their private information in size. Then, they can proceed as follows:

• Step 1. The $l$ participants turn their private information into $n$-ary numbers ($n>l$), suppose after transformation, the private information of $i$th participant is $M_{i}=(M_{i}^1 M_{i}^2 \ldots M_{i}^m)$, where $i\in \{1,2,\ldots ,l\}$ (If the number of some digits is less than $m$, then plus adequate $0$ on their high-digit). then, the $l$ participants share a group of appropriate long private key with a multiparty quantum key agreement (QKA) protocol [36–38], and turn them into $n$-ary keys, note the key as $K=(K^{1}K^{2} \ldots K^{m})$.

• Step 2. TP randomly prepares $m$ $|\psi ^{s}_{v_{2},v_{3},\ldots ,v_{l}}\rangle$($s,v_{2},v_{3},\ldots ,v_{l}\in \{0,1,\ldots ,d-1\}$, $d=2n+1$) maximally entangled states. The first particles of these states form the sequence $S_{1}$, the second particles form the sequence $S_{2}$,$\ldots$, the $l$th particles form the sequence $S_{l}$. To check the presence of eavesdroppers, TP generates $k'ml$ decoy particles from $\{|0\rangle ,|1\rangle ,\ldots ,|d-1\rangle , F|0\rangle ,F|1\rangle ,\ldots ,F|d-1\rangle \}$, and uniformly insert them into the sequences $S_{1},S_{2},\ldots ,S_{l}$ to get the new quantum sequences $S'_{1},S'_{2},\ldots ,S'_{l}$, where $k'$ is the detection rate. Finally, TP sends them to participant 1, participant 2, $\ldots$, participant $l$, respectively.

• Step 3. After the $l$ participants receive the sequences, they send the acknowledgements to TP. Then, TP announces the positions and bases of the decoy particles, the $l$ participants measure these particles and return the measurement results to TP. TP verifies these results and checks whether eavesdroppers exist in the quantum channels. If the error rate is less than the predetermined threshold ($\tau =2 \sim 8.9\,\%$ [33]), move to next step, Otherwise, the protocol is aborted.

• Step 4. Each of the $l$ participants measure the remaining $m$ particles. Here, distributing quantum measurement which is described in Ref. [39] is used, this measurement is indirect and non-destructive. Suppose the $i$th participant gets $m$ measurement results ($k_{i}^1,k_{i}^2,\ldots ,k_{i}^m$) and combine them to $k_{i}(i=1,2,\ldots ,l)$.

• Step 5. Each of the $l$ participants encoding their private information, i.e., compute $C_{1}=M_{1}\oplus K \oplus k_{1},C_{2}=M_{2}\oplus K \oplus k_{2},\ldots ,C_{l}=M_{l}\oplus K \oplus k_{l}$. Then, they send the encoding information to TP via the authenticated classical channels, respectively.

• Step 6. TP will finish sorting the private information in size according to the encoding information that he/she received. So, TP have to take out each digit from $C_{1},C_{2},\ldots , C_{l}$ to compare them. In order to improve the efficiency of sorting, quick sort is used when each digit of these is sorted, while radix sort is used when the whole is sorted. If the numbers of the $t$th digit between $M_{i}$ and $M_{j}$ will be compared, TP has known $C_{i}$,$C_{j}$ and the initial quantum state $|\psi _{v_{2}^t,v_{3}^t,\ldots ,v_{l}^t}^{s^{t}}\rangle$, so he/she can compute $r_{i,j}^t=C_{i}^t\ominus C_{j}^t\oplus (v_{j}^t\ominus v_{i}^t)$, the relationship between $M_{i}^t$ and $M_{j}^t$ in size can be gained as follows:

  $$\begin{aligned} \sigma (r_{i,j}^t)= \left\{ \begin{array}{ll} M_{i}^t=M_{j}^t: &{}\quad \hbox {if}\; (r_{i,j}^t=0)\\ M_{i}^t>M_{j}^t: &{}\quad \hbox {if}\;0<r_{i,j}^t\le n\\ M_{i}^t<M_{j}^t: &{}\quad \hbox {if}\;n<r_{i,j}^t\le 2n \end{array} \right. \end{aligned}$$

  (5)

  In fact,

  $$\begin{aligned} r_{i,j}^t&= C_{i}^t\ominus C_{j}^t\oplus (v_{j}^t\ominus v_{i}^t)\end{aligned}$$

  (6)
  $$\begin{aligned}&= (M_{i}^t \oplus K^{t} \oplus k_{i}^t)\ominus (M_{j}^t \oplus K^{t} \oplus k_{j}^t)\oplus (v_{j}^t\ominus v_{i}^t)\end{aligned}$$

  (7)
  $$\begin{aligned}&= (M_{i}^t \ominus M_{j}^t)\oplus (K^{t} \ominus K^{t}) \oplus (k_{i}^t \ominus k_{j}^t)\oplus (v_{j}^t\ominus v_{i}^t)\end{aligned}$$

  (8)
  $$\begin{aligned}&= M_{i}^t \ominus M_{j}^t \end{aligned}$$

  (9)

  So, TP can sort these private information according to the compared results. After sorting the end, TP announces results.

An example is given for better understanding the presented protocol. Suppose there are 3 participants (Alice, Bob and Charlie), their private information are 3, 11 and 9, if they want to sort their secret inputs without leaking private information. According to protocol, set $n=4$, $d=9$. The protocol is executed as follows:

• Step 1. Participants turn their private information into quaternary number $M_{1}=3=(03)_{4},M_{2}=11=(23)_{4},M_{3}=9=(21)_{4}$, then private key $K=(31)_{4}$ is shared, and $m=2$.

• Step 2. TP prepares two 3-party and 9-dimensional maximally entangled states, suppose they are $|\psi _{4,1}^0\rangle ,|\psi _{2,7}^3\rangle$. Next, the entangled states are divided into 3 particles sequences $S_{1},S_{2},S_{3}$. After enough decoy particles are inserted into quondam sequences to form new sequences $S'_{1},S'_{2},S'_{3}$, TP send them to Alice, Bob and Charlie, respectively.

• Step 3. Suppose no eavesdropper is detected, then move to step 4.

• Step 4. Alice, Bob and Charlie measure the remaining particles to gain keys. When one participant measure his/her particles to get results, the other participants’ results will be certain, so $81$ kinds of possible results will be generated with equal probability in this example. If the measurement results of Alice are $k_{1}^1=5,k_{1}^2=1$, then, the results of Bob and Charlie will be settled, they are $k_{2}^1=0,k_{2}^2=3;k_{3}^1=6,k_{3}^2=8$.

• Step 5. In this step, Alice, Bob and Charlie can gain their ciphertext $C_{1}=85,C_{2}=57,C_{3}=21$, and send them to TP.

• Step 6. TP will sort the private information by computing $r_{i,j}^t(i,j\in \{1,2,3\},t=1,2)$. according to radix sort, the low digit (here is the second digit) will be compared firstly. suppose $M_{1}^2$ has been selected as pivot element, next compare $M_{1}^2$ and $M_{2}^2$,so compute $r_{1,2}^2=(C_{1}^2\ominus C_{2}^2)\oplus (v_{2}^2\ominus v_{1}^2)=(5\ominus 7)\oplus (2\ominus 0)=0$,$M_{1}^2=M_{2}^2$ can be get. in the same way, compute $r_{1,3}^2=2$, then, $M_{1}^2>M_{3}^2$, so, $M_{1}^2=M_{2}^2>M_{3}^2$ can be gained when comparing the number on the second digit. TP can also get $M_{2}^1>M_{3}^1=M_{1}^1$ by comparing the number on the first digit. The final order can be gained by radix sort, it is $M_{2}>M_{3}>M_{1}$. TP announces the result.

4 Security and efficiency analysis

In this section, the security of the proposed protocol will be analyzed. There are 3 attacks for our protocol; they are outsider attack, participant attack and TP attack. Now, we will prove that our protocol is secure against these attacks (Sect. 4.1, 4.2, 4.3) respectively. The efficiency of protocol is discussed in Sect. 4.4.

4.1 Outsider attack

If a malicious attacker Eve wonders the secret inputs of participants, the most general strategy for him is as follows: he first intercepts the transmitted sequences from TP, then he performs a joint operation $U$ on the intercepted particles and the auxiliary particles $|\phi \rangle$, at last, he sends the operated particles to the participants. According to Schmidt decomposition, the states after operation can be written as:

$$\begin{aligned} U(|j\rangle |\phi \rangle )_{SE}=\sum _{k=0}^{d-1}\lambda _{k}^{j}|s_{k}^{j}\rangle |E_{k}^{j}\rangle , j=0,1,\ldots ,d-1. \end{aligned}$$

(10)

where $\sum _{k=0}^{d-1}(\lambda _{k}^{j})^2=1$, $|s_{k}^{j}\rangle$ and $|E_{k}^{j}\rangle (j=0,1,\ldots ,d-1)$ are standard orthogonal basis of the systems which the states $|j\rangle$ and $|\phi \rangle$ belong to. If Eve wants to extract the information precisely, the reduced density matrixes of his system $\sum _{k=0}^{d-1}(\lambda _{k}^{j})^2 |E_{k}^{j}\rangle \langle E_{k}^{j}| (j=0,1,\ldots ,d-1)$ must be discriminated precisely. It requires that $\langle E_{k}^{j}|E_{k'}^{j'}\rangle =0$, when $j\ne j'$ or $k\ne k'$ (where$j,j',k,k'=0,1,\ldots ,d-1$). with this condition, the unitary operation $U$ performs on the decoy particles and additional particles has the universal form as follows:

$$\begin{aligned} U(F|p\rangle |\phi \rangle )&= U\left( \frac{1}{\sqrt{d}}\sum _{J=1}^{d-1}e^{\frac{2\pi ipj}{d}}|j\rangle |\phi \rangle \right) \end{aligned}$$

(11)

$$\begin{aligned}&= \frac{1}{\sqrt{d}}\sum _{J=1}^{d-1}e^{\frac{2\pi ipj}{d}} U(|j\rangle |\phi \rangle )\end{aligned}$$

(12)

$$\begin{aligned}&= \frac{1}{\sqrt{d}}\sum _{J=1}^{d-1}\sum _{k=0}^{d-1} \lambda _{k}^{j}e^{\frac{2\pi ipj}{d}}|s_{k}^{j}\rangle |E_{k}^{j}\rangle \end{aligned}$$

(13)

where $p=0,1,\ldots ,d-1$. The reduced density matrixes of participants’ system are as follows:

$$\begin{aligned} \frac{1}{d}\sum _{j=1}^{d-1}\sum _{k=0}^{d-1} (\lambda _{k}^{j})^2|s_{k}^{j}\rangle \langle s_{k}^{j}|. \end{aligned}$$

(14)

It is obviously that the density matrix has nothing to do with the variable $p$. That is to say, all the subsystems on the decoy particles’ position in participants’ hand are identical. So the error rate in the detection stage is maximized. Hence, we have proved that an eavesdropper cannot eavesdrop the participants’ information without bringing in any disturbance.

4.2 Participant attack

In this subsection, we will analyze the participant attack. Participant attack is an usual attack mode in the protocols that the participants do not trust each other. In our protocol, all the participants have negotiated a same private key $K$ which is unknown to TP. Another key is generated through $l$-party and $d$-dimensional entangled states, and the key is different and unknown to each participant. For a dishonest participant (without loss of generality, suppose that participant 1 is a dishonest one), when he/she intercepted the other’s particle sequences, it is same as outsider attack. This case will be detected in step 3. Thus, the only possible way for participant 1 to do is to perform unitary transformation on his/her particles to extract other participants’ information, the operation can be shown as:

$$\begin{aligned} (U_1\otimes I_2\otimes \cdots \otimes I_l) \left( \frac{1}{\sqrt{d}}\sum _{j=1}^{d-1}e^{\frac{2\pi ijs}{d}}|j\oplus 0\rangle \otimes |j\oplus v_{2}\rangle \otimes \cdots \otimes |j\oplus v_{l}\rangle \right) \!.\qquad \end{aligned}$$

(15)

The reduced density matrix of participant 1’s subsystem is $\frac{1}{d}\sum _{j=1}^{d-1} U_{1}|j\rangle \langle j| U_{1}^{\dagger }$. When he/she does nothing on the particles, the reduced density matrix is $\frac{1}{d}\sum _{j=1}^{d-1} |j\rangle \langle j|$. Hence, he/she cannot extract any other participants’ information by this way. By now, we have proved that our protocol is safe against participant attack.

4.3 TP attack

In this subsection, we will discuss TP attack from two aspects. On the one hand, it will be analyzed whether TP can gain the participants’ key by some measures. On the other hand, if TP cannot acquire the participants’ key, can he/she deduce the participants’ secret through ciphertext? For the first aspect, TP can prepare m $(l+1)$-party entangled states rather than $l$-party entangled ones in step 2, and leave a particle sequence for himself. So he/she can deduce the participants’ key in step 4 through the initial sates and the measurement result of his/her particle sequence. But according to the security analysis of QKA protocol [36–38], TP cannot gain the key in step 1; hence, TP cannot obtain the whole key of participants. For the second one, suppose TP sorts the numbers of $t$-digit of private information through their cipher text, when $M_{i}^t$ and $M_{j}^t(i,j=1,2,\ldots ,l)$ are sorted, TP will not gain the specific value except the size. After $M_{1}^t,M_{2}^t,\ldots ,M_{l}^t$ have been sorted, if all values are different and every number is $l$-ary, TP can infer that the smallest number is $0$, the second smallest one is $1,\ldots$, the biggest one is $l-1$. But in our protocol, $n>l$ is required, TP will not infer the value of $M_{1}^t,M_{2}^t,\ldots ,M_{l}^t$. So, he/she will also not infer the information $M_{1},M_{2},\ldots ,M_{l}$.

In addition, the analysis is similar to Ref. [33] on lossy and noisy channel, not repeat them here.

4.4 Efficiency analysis

Because there is no an appropriate model to describe the efficiency of our protocol, we illustrate this subject through the analysis of the number of quantum resources required in our protocol. Suppose there are $l$ participants who want to rank the private information of $m$ digit $n$-ary numbers in size. In step 1 of the protocol, a QKA protocol is used. If the QKA Protocol in Ref. [36] is employed, $x(x-1)(k+1)$ single particles are used (where $k$ is the detection rate in Ref. [36]), when $x$ bits key are negotiated. However, every digit is $n$-ary in our proposed protocol, so $\lceil m (m-1)\text {log} n \rceil (k+1)$ single particles are used in step 1. In step 2, $m$ entangled states which are $l$-party and $d$-dimension are prepared randomly by TP, and $k'ml$ decoy particles are used. No other quantum resource is generated in the remaining steps. This has been summarized in Table 1.

Table 1 The quantum resources used in our protocol

5 Conclusion

This paper proposes an $l$-participant QPC protocol using entangled states which is $l$-party and $d$-dimension. In this protocol, $l$ participants can sort their private information in size within one execution, with the help of a semi-honest third party. Because it is feasible that the single particles are generated and measured without unitary transformation in QKA protocol such as Ref. [36], we only need to prepare the initial entanglement states and measure single particle in proposed protocol. It is known that the participants’ private information does not leak through the analysis of outsider attack, participant attack and TP attack.