Efficient quantum private comparison protocol based on one direction discrete quantum walks on the circle

Jv-Jie Wang(王莒杰) Zhao Dou(窦钊) Xiu-Bo Chen(陈秀波)Yu-Ping Lai(赖裕平) and Jian Li(李剑)

1Information Security Center,State Key Laboratory of Networking and Switching Technology,Beijing University of Posts and Telecommunications,Beijing 100876,China

2Information Security Center,School of Cyberspace Security,Beijing University of Posts and Telecommunications,Beijing 100876,China

Keywords: quantum private comparison protocol,one direction quantum walks,efficiency,brute-force attack

1. Introduction

In 1982, Yao introduced the millionaire problem.[1]The millionaire problem describes a circumstance in which two millionaires desire to know who is wealthier without divulging their property. Since then, secure multi-party computation(SMPC), as a new branch of cryptography, has been established.Nowadays,SMPC is a cryptographic primitive that can be used for many tasks,such as electronic election[2–4]and secret sharing.[5–7]

However, with the rapid development of quantum technology, classical cryptography has been substantially challenged because of the quantum parallelism.[8]Therefore,the security of SMPC is worth discussing. With more and more researchers turning to the quantum cryptography protocols’ study, plenty of efforts have been made, such as quantum key distribution (QKD),[9–13]quantum secret sharing (QSS),[14–18]quantum secure direct communication(QSDC).[19–22]In 2009, Yang and Wen proposed the first quantum private comparison(QPC)protocol,[23]which is the extension area of the SMPC. The QPC seeks to compare the size of the two participants’ private input without revealing the true values. Most QPC protocols require a semi-honest third party (TP) to assist the mutually distrustful participants in completing the protocols,while some of the QPC protocol only needs an untrusted third party. So far, several protocols for QPC have been presented. There are protocols based on Bell states,[24–29]GHZ entangled states,[30–34]entanglement swapping,[35–38]superdense coding,[39]etc. To take more participants into comparison,the multi-party quantum private comparison(MQPC)has been firstly proposed by Changet al.in 2013.[40]

The participants constantly try to obtain others’ secret information, on which is the most severe hazard we concentrate. The QPC protocols can be divided into two categories according to the type of the particles.They are protocols based on the single-particle[41–46]and protocols based on the multiparticle.[26–31]Most of the multi-particle-based protocols are using entangled states. In 2012,Wenet al.proposed the QPC protocol based on Bell states.[24]In 2013, Guoet al.[35]proposed a protocol based on GHZ state,which solves the feasibility to expand in network service. In 2021, Zhouet al.[29]put forward a new semi-quantum QPC protocol based onddimensional Bell states. As for the protocols based on the single-particle, in 2012, Yanget al. proposed the first QPC protocol without entanglement.[41]In 2018, Lang proposed a QPC protocol using single photons,[45]delivering a new direction of single-particle protocols. In 2019, Linet al.[46]came up with a practical and efficient semi-quantum QPC protocol using single photons.

The protocol based on single-particle has several advantages. Firstly, it has fewer potential security risks than the multi-particle-based protocols. There are multiple attacks on entangled states. For example, Gaoet al. proposed the correlation-elicitation attack for entanglement states.[47]Besides, the entanglement states pervasively require predistribution before the execution of the protocol. That is another potential security risk. Secondly,the single-particle can be easily prepared under the circumstance of nowadays quantum technology. Therefore, the utilization of single-particle has the potential to minimize costs and equipment requirements.

Inspired by Chenet al.’s protocol,[48]we propose a QPC protocol based on one-direction quantum walks on the circle(ODQWC). Our protocol can compare the size between the two participants, not only the equality. With the ODQWC,TP can set the walker state|0〉pas a flag to judge the comparison result. In our proposed protocol, the participants’secret messages are in{0,1,...,d-1}which improves the qubit efficiency. Besides, we analyze various attacks such as the intercept-resend attack, entangle-measure attack and brute-force attack.[54]Moreover, Alice and Bob’s operations are symmetric in our protocol, which means they are equivalent. That reduces the security risk from the participants. Our protocol also has the advantages of the protocols based on the single-particle,because QWs particle is easy to prepare.

In Section 2,we introduce the basic knowledge of quantum walks and the property of the ODQWC.In Section 3,we give a detailed illustration of our proposed protocol. In Section 4,the correctness and security of our protocol are proved.Subsequently,we demonstrate the advantages of our protocol in Section 5. In the last part of our paper,we make a conclusion.

2. Preliminaries

We introduce some fundamental quantum walks knowledge and properties in this section, which will be used in our proposed protocol.We mention the discrete quantum walks on a line(DQWL)because the ODQWC is evolved from it.

2.1. Discrete quantum walks on a line

Quantum walks are a variation of the traditional random walk. It consists of two quantum systems: the walker system,which describes the particle’s position, and the coin system,which determines the particle’s direction. The Hilbert spaceHwhere QWs is located is composed of the tensor product of the coin’s Hilbert space and the walker’s Hilbert space. Hence,Hcould be presented asH=Hc⊗Hp. We denote the quantum state of the walker as|position〉pand the coin as|c〉c, where position∈(-d,+d)andc ∈{0,1}. Therefore,we can write a QWs state as|ψ〉=|c〉c⊗|position〉p.

2.2. Evolution operator

Subsequently, we will go over a crucial operator called the evolution operator, which plays an important role in our protocol. The evolution operator,also known as the step operator,is used to regulate the movement of particles. The quantum walks, like the classical random walk, start by flipping a coin to select the particle’s walking direction. The shift operator is then used to move one step. We specify that the|0〉state of the coin represents the particle going right, while the|1〉goes left.Generally,we use the Hadamard gate for the coin toss,which is also called the Hadamard walk.[55]That is

If the QWs particles desire to moveksteps, thenkevolution operators should be applied. We denote thekevolution operators asUkand its inverse operator asU-k.

2.3. Measurement and properties of QWs

In the protocols based on QWs,one of the foremost tasks is measurement. The distinction between classical random walks and quantum walks resides in the quantum state’s superposition. Of course, it is no different from a traditional random walk if we measure the particles after each step and let the particles collapse into a specific state.

We measure the coin state by utilizing the operator

Table 1 suggests that the QWs particle with an initial state|1〉c|0〉pis more likely to move along the left side. However,we can still obtain the measurement result on the other side,demonstrating that the QWs particles can move on both sides simultaneously. HereTrepresents the moving steps,Pis the position of the QWs particles and the initial state is|1〉c|0〉p.

Table 1. Probability distribution of|1〉c|0〉p in first 3 step.

2.4. One direction discrete quantum walks on circle

If the endpoints of the DQWL are linked,it is called discrete quantum walks on circle.This slight change makes the QWs particle move in one direction. We denote the one direction evolution operator as

We list the particle’s probability distribution of the first 3 steps ODQWC in Table 2 (Tis steps,Pis position, and the initial state is|0〉c|0〉p).

Table 2. Probability distribution of|0〉c|0〉p in ODQWC in first 3 step.

We can find that the furthest position of the particle is equal to the moving steps.

3. The proposed QPC protocol based on one direction discrete quantum walks on circle

The following work illustrates our proposed protocol based on the one-direction discrete quantum walks on circle.We assume that the proposed protocol runs in ideal conditions,in which there are no technical errors and the transmission channels are lossless and noiseless. The proposed protocol requires a semi-honest third party and can judge the size of two parties’secret messages.

Fig.1. Schematic diagram of DQWC.

The following shift operator should be used if we want the particle to go in one direction:The measurement bases of|i〉andF|i〉are{|0〉,|1〉,...,|d-1〉}and{F|0〉,F|1〉, ...,F|d-1〉}. Then TP sendsS′0to Alice.

Step 3 Alice will report to TP after receiving the particles.Then TP will announce the position of the decoy particles and the measurement basis to Alice.After that,Alice performs the measurements on the decoy particle using the corresponding measurement bases, and reports the measurement results to TP.By comparing the measurement results from Alice and the initial states of the particles, TP can check the error rate of the measurement results to determine whether there is an eavesdropper. If the error rate is higher than the safety threshold, they will abandon the particles and restart the protocol.Otherwise,Alice will remove the decoy particles and continue the protocol.

Fig.2. Flow graph of our proposed protocol.

4. Analyses

We will analyze our proposed protocol from two perspectives in this section: correctness and security.

4.1. Correctness

In this subsection, we will prove the correctness of our proposed protocol.

4.2. Outside attack

During the execution of our protocol, there might exist an outside attacker Eve. We assume that she tries a variety of approaches to obtain the secret messages such as interceptresend attack,entangle-measure attack.

4.2.1. Intercept-resend attack

The intercept-resend attack means the eavesdropper will measure the particles and send fake quantum particles to the receiver according to the measurement results.[27]Our protocol performs well in detecting this kind of attack.

We utilize the decoy particle in our proposed protocol,which has been widely used in other protocols,[26,29–31]to detect the intercept-resend attack. It is familiar with the method adopted in the BB84 protocol,[9]and the security of BB84 has been proven already.

In our proposed protocol, we insert 2λdecoy particles,which belong to the set{|0〉,|1〉,...,|d-1〉,F|0〉,F|1〉,...,F|d-1〉}, into the QWs particles. Under the circumstance of the decoy particles’randomizing,Eve would not know the measurement basis and the position of the decoy particles. As a result, each particle has a probability ofd-12din introducing mistakes. Ifλis large enough,the probability of detecting the existence of the eavesdropper will close to 1.

Furthermore, even if the attack is undetected, the eavesdropper cannot obtain any useful message because we encrypt the QWs particles usingPk1/Pk2/Pk3before each transmission.

4.2.2. Entangle-measure attack

The entangle-measure attack means the attacker Eve intercepts the particles from the quantum channel. Then she applies a unitary operator on the particles to entangle them with his auxiliary quantum state.So that she may achieve the secret messages with the help of the auxiliary quantum state.We will demonstrate that our proposed protocol can withstand such an attack.

We adopt thed-dimensional quantum state as the decoy particle. Eve’s unitary transformation can be expressed as

The reduced density matrices clearly have little to do with the variablejTherefore,after the eavesdropper entangles the auxiliary particles with the participants’particles, all the subsystems of decoy particles are the same to the eavesdropper That means Eve cannot obtain any useful messages.

Above all, our protocol can detect the usual outside attack.

4.3. Internal attack

In this subsection we will discuss the probability of the attack from Alice, Bob and TP. In our proposed protocol, if Alice(Bob)wants to obtain the secret messages by intercepting the particles sent through the quantum channel, they are the same as the outside attackers. Thus, the proof in Subsection 4.2 can ensure the detection of their attacks.

The brute-force attack[54]means the attacker measures the particles to obtain the secret messages,even though he is at the risk of being detected.In our proposed protocol,there is no chance for the participants to launch attacks. (1)In Step 4,Alice may try to send fake particles|0〉c|0〉pto TP and adopts the brute-force attack in Step 6 to obtain Bob’s secret messages.However, TP makes another encryptionPk2in Step 5, which makes Alice would not obtain any useful messages through this kind of method. (2)Bob may launch a brute-force attack in Step 4. Since Bob does not know the original encryptionPk1of TP,he will not be aware of Alice’s secret messages even if he adopts the brute-force attack.[54](3) TP may launch an attack at Step 4 and Step 6. However,Alice makes an encryptionPk3to prevent TP from obtaining the secrets in Step 4.The QWs state in Step 6 isUm1-m2|0〉c|0〉p, therefore, TP would not obtain the secret messages of each participant in Step 6.

In conclusion, the participants have little probability of gaining the secret messages.

5. Comparison

We analyze the advantages of our protocol from three perspectives: efficiency, security and implementation. Because the QPC protocol based on quantum walks is novel,we mainly focus on the comparison of our protocol with Chenet al.’s protocol.[48]

5.1. Qubit efficiency

Qubit efficiency is a widely used method to measure the efficiency of protocol execution. It is defined asη=c/q,wherecrepresents the maximum compared bits of the secret messages,andqdenotes the consumed qubit during the protocol execution. Because the qubits in our protocol are inddimensions,we redefine the qubit efficiency asη′=c/q′,whereq′=q×log2d.

Although our definition of qubit efficiency differs from the standard one,it can still accurately describe the protocol’s efficiency.The comparison result above suggests that the maximum compared classical bits in our protocol have one more than the bits in Chenet al.’s protocol.[48]As a result, Alice and Bob’s maximum secret messages in our protocol are double those in Chenet al.’s protocol.[48]

5.2. Security

The QWs particle has its uniqueness in security.Compared with the protocols that adopt the entanglement state,[27–31]there is no pre-distribution with the QWs particle.Thus,plenty of attacks on the entangled states can be avoided.

Furthermore, there is no security check in Chenet al.’s protocol[48]to ensure that the transmitted particles are the original particles prepared by TP. Therefore, Alice has a variety of attack options such as the brute-force attack. We fix this slight defect by changing the structure of the protocols,ensuring all the participants are unable to launch attacks.

5.3. Implementation

The initial QWs state is|0〉c|0〉p,which is a product state.Compared with the entangled state, it has some clear advantages. The measurement and the preparation of the QWs state are much easier than that of the entangled state.[44]Furthermore, we only use the evolution operatorUoduring the execution of our protocol, which makes our proposed protocol can be easily realized by the quantum gate and circuits. This reduced the costs and equipment requirements Above all,our protocol is easy to be implemented.

6. Conclusion

In summary,the previous QWs-based QPC protocol is not efficient enough. We proposed a protocol based on ODQWC with a semi-honest third party. The QWs particles do not exist entanglement in the initial state,and it moves by applying the evolution operator. This makes our protocol has the advantages of the single-particle protocol, which is easy to be implemented. In terms of efficiency,we enlarged twice the range of the participants’ messages than the previous protocols by setting a flag to judge the comparison results. The correctness of our protocol has been proven. Moreover, we analyzed the security of our protocol from the participants’attacks and the outside attacks. Our protocol can protect against well-known attacks and brute-force attacks from the participants.

Although our proposed protocol has several advantages,however, it still needs more discussions and investigations.Such as the extension of QWs-based QPC protocols to multiparty comparison. Besides,the number of QWs particles consumed in our proposed protocol still needs diminution.

Acknowledgements

Project supported by the National Key R&D Program of China(Grant No.2020YFB1805405), the 111 Project(Grant No.B21049),the Foundation of Guizhou Provincial Key Laboratory of Public Big Data(Grant No.2019BDKFJJ014),and the Fundamental Research Funds for the Central Universities,China(Grant No.2020RC38).