Cryptanalysis and Improvement of Quantum Private Comparison without Classical Computation

Abstract

Recently, Lang suggested a quantum private comparison (QPC) without classical computation (Int J Theor Phys, 59(2020)2984). Lang claimed that this QPC protocol is secure against both the participant attack and the outside attack. It is pointed out in this paper that the third party (TP) can totally obtain the private binary sequences of two communicants by launching a special measurement attack; and moreover, an outside attacker can make this protocol fail by launching the disturbance attack. The corresponding methods are further put forward to overcome these drawbacks.

1 Introduction

In 2009, Yang and Wen [1] put forward the first quantum private comparison (QPC) protocol by using Bell entangled states. Hereafter, a lot of researchers focused their attentions on QPC so that numerous QPC protocols have been constructed [2,3,4,5,6,7]. It is apparent that there is always a classical computation process in most of existing QPC protocols, which outputs the comparison outcome of the private inputs of communicants. Recently, Lang [8] proposed the first fully quantum QPC protocol, which substitutes the classical exclusive-or operations with quantum controlled-not gates to implement comparison. Duan [9] pointed out the weaknesses of Ref. [8] and suggested the corresponding strategies to improve them. Subsequently, Lang [10] suggested another fully quantum QPC protocol without classical computation by using GHZ states. In Ref. [10], Lang claimed that his protocol is secure against both the participant attack and the outside attack. However, it is not the truth. In this paper, the security loopholes of the protocol of Ref. [10] is illustrated in detail, and the corresponding methods are further put forward to overcome these drawbacks.

The remaining part of this paper is arranged as follows: Sect.2 reviews Lang’s QPC protocol without classical computation; Sect.3 points out the security loopholes of Lang’s QPC protocol without classical computation; Sect.4 put forwards the corresponding improving methods; and finally, Sect.5 gives the conclusion.

2 Review of Lang’s QPC Protocol without Classical Computation

It has been proven by Lang in Ref. [10] that

$$ \boldsymbol{CNOT}\left|+\right\rangle \left|+\right\rangle =\left|+\right\rangle \left|+\right\rangle, $$

(1)

$$ \boldsymbol{CNOT}\left|-\right\rangle \left|+\right\rangle =\left|-\right\rangle \left|+\right\rangle, $$

(2)

$$ \boldsymbol{CNOT}\left|+\right\rangle \left|-\right\rangle =\left|-\right\rangle \left|-\right\rangle, $$

(3)

$$ \boldsymbol{CNOT}\left|-\right\rangle \left|-\right\rangle =\left|+\right\rangle \left|-\right\rangle, $$

(4)

where$\mid \pm \Big\rangle =\left(1/\sqrt{2}\right)\left(|0\Big\rangle \pm |1\Big\rangle \right)$, $CNOT=\left[\begin{array}{cccc}1& 0& 0& 0\\ {}0& 1& 0& 0\\ {}0& 0& 0& 1\\ {}0& 0& 1& 0\end{array}\right]$. Apparently, the above four equations imply that if both of two qubits are from{| +〉, | −〉}, the first qubit and the second qubit will serve as a target qubit and a control qubit, respectively. Therefore, it can be easily derived that

$$ \boldsymbol{CNOT}\left|v\right\rangle \left|w\right\rangle =\left(\left|v\right\rangle \oplus \left|w\right\rangle \right)\left|w\right\rangle, $$

(5)

where∣v〉, ∣ w〉 ∈ {| +〉, | −〉},∣ + 〉 ⊕  ∣  + 〉 =  ∣  + 〉,∣ − 〉 ⊕  ∣  + 〉 =  ∣  − 〉,∣ + 〉 ⊕  ∣  − 〉 =  ∣  − 〉, − 〉 ⊕  ∣  − 〉 =  ∣  + 〉.

Suppose that Alice owns the private binary sequenceA = (a_L − 1…a₁a₀) while Bob has the private binary sequence B = (b_L − 1…b₁b₀), where a_j, b_j ∈ {0, 1},j ∈ {0, 1, …, L − 1}. If∣ + 〉and∣ − 〉denote the classical bits 0 and 1, respectively, the quantum counterparts of A and B will be QA = (qa_L − 1, …, qa₁, qa₀) and QB = (qb_L − 1, …, qb₁, qb₀), respectively, where qa_j, qb_j ∈ {| +〉, | −〉},j ∈ {0, 1, …, L − 1}. Lang’s QPC protocol without classical computation is composed of the following steps.

• Step 1: The semi-honest TP generates LGHZ states $\mid GHZ\left\rangle =\left(\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$\sqrt{2}$}\right.\right)\left(|000\Big\rangle +|111\Big\rangle \right)=\left(1/2\right)\left(|++\Big\rangle +|--\Big\rangle \right)\mid +\right\rangle +\left(1/2\right)\left(|+-\Big\rangle +|-+\Big\rangle \right)\mid -\Big\rangle$. TP picks out the first, the second and the third particles of theseLGHZ states to make up sequencesSA,SBandST, respectively. Afterward, TP generates two sets of decoy photons DA and DB, which are randomly chosen from the four states{| 0〉, | 1〉, | +〉, | −〉}. Then, TP randomly mixes DA with SA to compose the new sequence SA^∗, and DB with SB to compose the new sequence SB^∗. Finally, TP measures ST with the X basis to obtain the measurement results MT = {mt_L − 1, …, mt₁, mt₀}, where the X basis is{| +〉, | −〉}, mt_j ∈ {| +〉, | −〉},j ∈ {0, 1, …, L − 1}, and transmits SA^∗ and SB^∗ to Alice and Bob, respectively. Obviously, the decoy photon technology [11, 12] is used to guarantee the transmission security of SA^∗ and SB^∗.

• Step 2: After confirming that Alice (Bob) has received SA^∗ (SB^∗), TP tells Alice (Bob) the positions and the measuring bases of decoy photons in SA^∗ (SB^∗). Then, Alice (Bob) uses the correct measuring bases to measure the decoy photons in SA^∗ (SB^∗) and tells TP her (his) measurement results. Afterward, TP judges whether the quantum channel is secure or not. If the error rate is small enough, the protocol will be continued; otherwise, it will be terminated.

• Step 3: Alice (Bob) discards the decoy photons in SA^∗(SB^∗) to restore SA (SB). Alice measures SA with the X basis to obtain the measurement results SA^' = {sa_L − 1, …, sa₁, sa₀}, where sa_j ∈ {| +〉, | −〉},j ∈ {0, 1, …, L − 1}. As a result, SB is collapsed into{sb_L − 1, …, sb₁, sb₀}, where sb_j ∈ {| +〉, | −〉},j ∈ {0, 1, …, L − 1}. Then, Alice preforms the controlled-not gate G0 on two particles sa_j and qa_j which act as the target and control qubits, respectively. Bob preforms the controlled-not gate G1 on two particles sb_j and qb_j which act as the target and control qubits, respectively. As a result, RA = {ra_L − 1, …, ra₁, ra₀} and RB = {rb_L − 1, …, rb₁, rb₀}are derived by Alice and Bob, respectively,where ra_j = sa_j ⊕ qa_j ∈ {| +〉,  −〉},rb_j = sb_j ⊕ qb_j ∈ {| +〉, | −〉},j ∈ {0, 1, …, L − 1}. Finally, Alice and Bob send RA and RB to TP, respectively.

• Step 4: TP preforms the controlled-not gate G2 on two particles rb_j and ra_j which act as the control and target qubits, respectively. As a result, ra_j is changed into rt_j = ra_j ⊕ rb_j, where rt_j ∈ {| +〉, | −〉},j ∈ {0, 1, …, L − 1}. Then, TP preforms the controlled-not gate G3 on two particles rt_j and mt_j which act as the target and control qubits, respectively. As a result, rt_j is changed into r_j = rt_j ⊕ mt_j = ra_j ⊕ rb_j ⊕ mt_j = sa_j ⊕ qa_j ⊕ sb_j ⊕ qb_j ⊕ mt_j, where r_j ∈ {| +〉, | −〉}, j ∈ {0, 1, …, L − 1}.

• Step 5: TP measures the particle r_j with the X basis. If TP discovers one r_j in the state of∣ − 〉, she will terminate the protocol immediately and announce that A and B are not equal; otherwise, she will terminate the protocol and announce that A and B are identical.

3 Security Loopholes of Lang’s QPC Protocol without Classical Computation

3.1 The Disturbance Attack of an Outside Attacker

In Lang’s QPC protocol without classical computation, Alice and Bob need to send RA and RB to TP, respectively. However, both RA and RB are sent to TP without any protection effort. If an outside attacker launches the disturbance attack, i.e., permuting the orders of particles of RA or RB, TP will inevitably obtain the wrong comparison result of A and B in the end. In this case, this protocol fails.

3.2 The Measurement Attack of TP

In the realm of QPC, Chen et al. [2] defined the first kind of semi-honest TP, i.e., TP executes the protocol loyally, keeps a record of all its intermediate computations and might try to steal the users’ private information from the record, but cannot be corrupted by others. Yang et al. [13] defined the second kind of semi-honest TP, i.e., TP is allowed to misbehave on her own but cannot conspire with others. It is well known that Yang et al.’s definition of semi-honest TP is much more reasonable in reality than Chen et al.’s definition of semi-honest TP. Lang’s QPC protocol without classical computation is secure towards Chen et al.’s definition of semi-honest TP. However, it is unsecure towards Yang et al.’s definition of semi-honest TP. In the following, this point will be illustrated in detail.

In order to steal Alice and Bob’s private binary sequences without being discovered, TP takes the following extra actions: (1) in Step 1, before randomly mixing DA (DB) with SA (SB), TP measures SA (SB) with the X basis to know the state of sa_j (sb_j), where j ∈ {0, 1, …, L − 1}; (2) in Step 4, after receiving RA (RB) from Alice (Bob), TP measures ra_j (rb_j) with the X basis to know its state, where j ∈ {0, 1, …, L − 1}. Then, TP decodes out qa_j (qb_j) by calculating sa_j ⊕ ra_j (sb_j ⊕ rb_j), where j ∈ {0, 1, …, L − 1}. In this way, TP can totally know A(B) without being discovered.

4 Improvement of Lang’s QPC Protocol without Classical Computation

In order to resist the disturbance attack of an outside attacker and the measurement attack of TP, Lang’s original QPC protocol without classical computation is changed into the following one.

• Step 1: The semi-honest TP generatesL + δGHZ states $\mid GHZ\left\rangle =\left(\raisebox{1ex}{$1$}\!\left/ \!\raisebox{-1ex}{$\sqrt{2}$}\right.\right)\left(|000\Big\rangle +|111\Big\rangle \right)=\left(1/2\right)\left(|++\Big\rangle +|--\Big\rangle \right)\mid +\right\rangle +\left(1/2\right)\left(|+-\Big\rangle +|-+\Big\rangle \right)\mid -\Big\rangle$. TP picks out the first, the second and the third particles of these L + δGHZ states to make up sequences SA, SB and ST, respectively. Afterward, TP generates two sets of decoy photons DA and DB, which are randomly chosen from the four states{| 0〉, | 1〉, | +〉, | −〉}. Then, TP randomly mixes DA with SAto compose the new sequence SA^∗, and DB with SB to compose the new sequence SB^∗. Finally, TP measures ST with the X basis to obtain the measurement results MT = {mt_L − 1, …, mt₁, mt₀}, where mt_j ∈ {| +〉, | −〉},j ∈ {0, 1, …, L − 1}, and transmits SA^∗ and SB^∗ to Alice and Bob, respectively. Obviously, the decoy photon technology [11, 12] is used to guarantee the transmission security of SA^∗ and SB^∗.

• Step 2: After confirming that Alice (Bob) has received SA^∗ (SB^∗), TP tells Alice (Bob) the positions and the measuring bases of decoy photons in SA^∗ (SB^∗). Then, Alice (Bob) uses the correct measuring bases to measure the decoy photons in SA^∗ (SB^∗) and tells TP her (his) measurement results. Afterward, TP judges whether the quantum channel is secure or not. If the error rate is small enough, the protocol will be continued; otherwise, it will be terminated.

• Step 3: Alice (Bob) discards the decoy photons in SA^∗ (SB^∗). Then, Alice and Bob randomly select δGHZ states from L + δones to check the authenticity of GHZ states prepared by TP in Step 1 as follows. (1) Alice randomly chooses the Z-basis (| 0〉, | 1〉)or the X basis to measure the particles of these δGHZ states in her hand; (2) Alice tells Bob and TP her measurement basis for these δGHZ states; (3) Bob and TP use the measurement basis same to Alice’s to measure the corresponding particles in their respective hands: (4) TP tells Alice and Bob her measurement results of the particles of these δGHZ states in her hand; (5) Alice and Bob judges the authenticity of GHZ states prepared by TP in Step 1 by comparing their measurement results with TP’s measurement results. If the error rate is small enough, the protocol will be continued; otherwise, it will be terminated.

• Step 4: Alice (Bob) discards the particles of δGHZ states in SA^∗(SB^∗) to obtainSA^'(SB^'). Alice measures SA^' with the X basis to obtain the measurement results {sa_L − 1, …, sa₁, sa₀}, where sa_j ∈ {| +〉, | −〉},j ∈ {0, 1, …, L − 1}. As a result, SB^' is collapsed into {sb_L − 1, …, sb₁, sb₀}, where sb_j ∈ {| +〉, | −〉},j ∈ {0, 1, …, L − 1}. Then, Alice preforms the controlled-not gate G0 on two particles sa_j and qa_j which act as the target and control qubits, respectively. Bob preforms the controlled-not gate G1on two particles sb_j and qb_j which act as the target and control qubits, respectively. As a result, RA = {ra_L − 1, …, ra₁, ra₀} and RB = {rb_L − 1, …, rb₁, rb₀} are derived by Alice and Bob, respectively, where ra_j = sa_j ⊕ qa_j ∈ {| +〉, | −〉},rb_j = sb_j ⊕ qb_j ∈ {| +〉, | −〉},j ∈ {0, 1, …, L − 1}. Finally, Alice (Bob) sends RA (RB) to TP with the decoy photon technology.

• Step 5: Alice (Bob) checks the transmission security of RA (RB) with TP by using the method similar to that of Step 2.

• Step 6: TP preforms the controlled-not gate G2 on two particles rb_j and ra_j which act as the control and target qubits, respectively. As a result, ra_j is changed into rt_j = ra_j ⊕ rb_j, where rt_j ∈ {| +〉, | −〉},j ∈ {0, 1, …, L − 1}. Then, TP preforms the controlled-not gate G3 on two particles rt_j and mt_j which act as the target and control qubits, respectively. As a result, rt_j is changed into r_j = rt_j ⊕ mt_j = ra_j ⊕ rb_j ⊕ mt_j = sa_j ⊕ qa_j ⊕ sb_j ⊕ qb_j ⊕ mt_j, where r_j ∈ {| +〉, | −〉}, j ∈ {0, 1, …, L − 1}.

• Step 7: TP measures the particle r_j with the X basis. If TP discovers one r_j in the state of ∣ − 〉, she will terminate the protocol immediately and announce that A and B are not equal; otherwise, she will terminate the protocol and announce that A and B are identical.

In the improved QPC protocol, the decoy photon technology is adopted to protect the transmissions of RA (RB) from Alice (Bob) to TP. If an outside attacker launches the disturbance attack described in Sect.3, she will inevitably leave her trace on the decoy photons so that she will be discovered undoubtedly by the eavesdropping check processes of Step 5. In addition, if TP launches the measurement attack described in Sect.3, TP’s attack will inevitably be detected by the check processes of Step 3.

5 Conclusion

In summary, this paper points out the security loopholes of Lang’s QPC protocol without classical computation firstly, i.e., TP can totally obtain the private binary sequences of two communicants by launching a special measurement attack and an outside attacker can make it fail by launching the disturbance attack, and then put forwards the corresponding methods to overcome these drawbacks.