# Cryptanalysis and Improvements on Quantum Key Agreement Protocol Based on Quantum Search Algorithm

Authors: Hussein Abulkasim; Eatedal Alabdulkreem; Faten Karim; Nada Ahmed; Mona Jamjoom; Myriam Hadjouni; Safia Abbas
Journal: Security and Communication Networks
 (2022)

---

## Abstract

Recently, Huang et al. (2021) presented a quantum key agreement schemeto securely negotiate on a secret key employing the properties of a quantumsearch algorithm. First, the authors proposed the two-party quantum key agreement, and then they extended their work to the three-party case. Huang et al.‘s protocol employs the unitary operation and single-particle measurements to negotiate on a secret key without using complex quantum technologies such as quantum memory or entangled quantum particles. The authors claimed that their protocol is secure and efficient. However, this work shows that Huang et al.‘s protocol has a significant pitfall, where the private key of one user could be easily leaked to the attackers. Hence, the properties of security and fairness are not achieved. Accordingly, thetwo-party and three-party of Huang et al.’s protocol have been reviewed, and an improvementto address the shortcoming is suggested.


---

## Body

## 1. Introduction

Key agreement is a security protocol that aims to generate and exchange secure key encryption among two or more distant users. Due to its greatest significance, key agreement protocols have been employed to generate encryption keys in today’s IT applications such as IoT applications [1], healthcare systems [2], vehicular communications [3], smart networks [4], satellite communications [5], cloud applications [6], and others. To resist quantum attacks, several security protocols have been proposed based on the principles of quantum physics for addressing various security problems [7–26]. The pioneering quantum-based key agreement (QKA) protocol was proposed in 2004 [27]. Subsequently, several QKA protocols have been introduced [11, 12, 16, 22]. Generally, there are different types of quantum key agreement protocols in terms of QKA’s structure and efficiency [28]: (1) the tree-QKA protocols, in which each user sends their private data to all other users via a quantum channel; (2) the complete-graph-QKA protocol, in which each user sends his encoded private data as a sequence of particles to each user participated in the protocol; and (3) the circle-QKA protocol, which is the most adopted type, in which each user pra sequence of particles representing his private key and sends it to the next user in a circle to encode his private data until it is returned to the sender (the first user). The circle-QKA protocol is more efficient than the other QKA types and is better at achieving the characteristic of fairness. In contrast, the complete-graph-QKA is more secure than the other QKA types. Thus, designing a secure and efficient QKA protocol has become a challenging task and got more and more attention.Recently, Huang et al. [29] presented a new QKA scheme based on Grover’s algorithm []. Theirprotocol enables authorized users to negotiate on a shared secure key, and noneof the authorized users can fully get the final agreement key alone. Grover’s search algorithm is used for accelerating the search process for the marked items. Their proposed protocol is feasible and does not use quantum memory or complex quantum devices. However, the Huang-QKA protocol cannot maintain the property of fairness since the level of security of the key agreement of users is not equal. A quick review of the Huang-QKA scheme is shown in Section 2. The security analysis of the Huang-QKA protocol and the suggested improvementsare presented in Section 3 and Section 4, respectively. The security analysis based on the modified steps is presented in Section 5. Section 6 concludes this work.


## 2. Review of Huang-QKA Protocol

Huang-QKA protocol employed the Grover quantum search algorithm (QSA) [30] to agree on a two-user QKA protocol. Basically, the Grover QSA is one of the most significant quantum computing algorithms which can be used to search for marked items in an unsorted database faster than all known classical search algorithms. For more clarification, assume that we we are searching for a target ωω∈00,01,10,11 in a two-qubit Grover QSA, and the targeted database is a two-qubit quantum system |s=|++=|00,|01,|10,|11/2. Two unitary operations Uω,Us can be used to evolve the quantum system |s. The measurement Z−basis=|0,|1 can be used to measure |s. Wecan describe the two unitary operations as follows:(1)Uω=I−2ωω,Us=2ss−I,where I is identity operation, ω∈00,01,10,11, and the quantum system s∈|++,|+−,|−+,|−−.|sω can be defined as follows:(2)|sω=++,whereω=00,−+,whereω=01,+−,whereω=10,++,whereω=11.Two common properties of Grover QSA van be stated as follows.Property 1 (see [31]).
Fori=1,2,3,4, let ωi∈00,01,10,11. If we have ω1⊕ω2⊕ω3=ω4, then we can say that Uω1Uω2Uω2|s11〉=±Uω4|s11〉.Property 2 (see [32]).
Assume that we havev,ω1,ω2∈00,01,10,11, and ω1⊕v=ω2. Then, we can say that Us11Uω1|sv〉=±ω2.


### 2.1. The Two-Party Huang-QKA Protocol

Assume that there are two remoteusers (e.g., Alice and Bob) who want to negotiate on an agreement keyK=Ka⊕Kb. Aliceand Bob agree on generating two random 2n bit classical secret keys Ka and Kb, respectively.(3)Ka=Ka1,Ka2,…,Kam,Kb=Kb1,Kb2,…,Kbm,where Ka1,Kb1∈00,01,10,11 and i∈1,2,…,m.By combining the idea of two-qubit Grover’s QSA with the QKA protocol, Huang-QKA protocol has been proposed. The steps of Huang-QKA protocol can be described as follows (see also Figure1).(1)
Alice generates an ordered sequenceSa of the two-qubit quantum state according to her private information Kai, that is, if Alice’s two classical bits are 00, 01, 10, or 11, Alice generates the quantum state |++〉, |+−〉, |−+〉, or |−−〉, respectively. Alice also employs the decoy qubit protocol to protect the quantum channel by preparing a sequence of 2m decoy qubit states randomly selected from the group states |0〉,|1〉,|+〉,|−〉. The selected decoy qubits are inserted randomly into Sa obtaining new sequence Sa′ and Alice records their positions. Subsequently, Alice sends the evolved sequence Sa′ to Bob through a quantum channel.(2)
Upon getting the evolved sequenceSa′, Bob publicly announces his secret key Kb through an authenticated classical channel.(3)
After receiving the secret key of BobKb, Alice computes the expression K=Ka⊕Kb to get the final agreement key K.(4)
Alice publicly announces the positions of the decoy qubits inSa′ and their measurement bases to Bob. Alice and Bob start evaluating the error rate ofmeasurement. If the computed error rate exceeds a preset threshold, the users should stop the protocol and restart from the first step. Otherwise, they proceed to the last step.(5)
Bob discards the measured decoy qubits and gets the ordered sequenceSa. Based on his private key Kbi, Bob applies the two unitary operations UKbi and US11 to Sa getting a new quantum sequence Sa. Bob measures the new sequence Sa using Z−basis=|0〉,|1. The measurement result that Bob gets is the final agreement key K.Figure 1
(a) represents the two-party Huang-QKA protocol; (b) represents the three-party Huang-QKA protocol; (c) represents the modified two-party Huang-QKA protocol. The dashed and solid lines represent the quantum and classical channels, respectively.
(a)(b)(c)


### 2.2. The Three-Party Huang-QKA Protocol

Assume that there are three remote users (e.g.,Alice, Bob, Charlie) who want to negotiate on an agreement keyKabc=Ka⊕Kb⊕Kc. Alice, Bob, and Charlie agree on generating three random2n bit classical secret keys Ka, Kb, and Kc, respectively.(4)Ka=Ka1,Ka2,…,Kam,Kb=Kb1,Kb2,…,Kbm,Kc=Kc1,Kc2,…,Kcm,where Ka1,Kb1,Kb1∈00,01,10,11 and i∈1,2,…,m.The steps of the three-party Huang-QKA protocol are as follows:(1)
Alice generates an ordered sequenceSa of the two-qubit quantum state according to her private information Kai, that is, if Alice’s two classical bits are 00, 01, 10, or 11, Alice generates the quantum state |++〉, |+−〉, |−+〉, or |−−〉, respectively. Alice also employs the decoy qubit protocol to protect the quantum channel by preparing a sequence of 4m decoy qubit states randomly selected from the group states |0〉,|1〉,|+〉,|−〉. The selected decoy qubits are inserted randomly into Sab and Sac obtaining new sequences Sab′ and Sac′. Subsequently, Alice sends the evolved sequences Sab′ and Sac′ to Bob and Charlie, respectively, through two quantum channels.(2)
Upon getting the evolved sequencesSab′Sab′, Bob (Charlie) publicly announces his secret key KbKc through an authenticated classical channel.(3)
After receiving the secret key of Bob (Charlie), Alice computes the expressionKabc=Ka⊕Kb⊕Kc to get the final agreement key Kabc.(4)
Alice publicly reveals positions of the decoy qubits inSab′Sac′ and their measurement bases to Bob (Charlie). Alice and Bob (Charlie) start evaluating the error rate ofmeasurement. If the computed error rate exceeds a preset threshold, the users should stop the protocol and restart from the first step. Otherwise, they proceed to the last step.(5)
Bob (Charlie) discards the measured decoy qubits and gets the ordered sequenceSabSac. Based on his private key KbiKci, Bob (Charlie) applies the two unitary operations UKbiUKci and US11 to SabSac getting a new quantum sequence SbSc Bob measures the new sequence SbSa using Z−basis=|0〉,|1. The measurement result that Bob (Charlie) gets is the final agreement key Kabc.


## 2.1. The Two-Party Huang-QKA Protocol

Assume that there are two remoteusers (e.g., Alice and Bob) who want to negotiate on an agreement keyK=Ka⊕Kb. Aliceand Bob agree on generating two random 2n bit classical secret keys Ka and Kb, respectively.(3)Ka=Ka1,Ka2,…,Kam,Kb=Kb1,Kb2,…,Kbm,where Ka1,Kb1∈00,01,10,11 and i∈1,2,…,m.By combining the idea of two-qubit Grover’s QSA with the QKA protocol, Huang-QKA protocol has been proposed. The steps of Huang-QKA protocol can be described as follows (see also Figure1).(1)
Alice generates an ordered sequenceSa of the two-qubit quantum state according to her private information Kai, that is, if Alice’s two classical bits are 00, 01, 10, or 11, Alice generates the quantum state |++〉, |+−〉, |−+〉, or |−−〉, respectively. Alice also employs the decoy qubit protocol to protect the quantum channel by preparing a sequence of 2m decoy qubit states randomly selected from the group states |0〉,|1〉,|+〉,|−〉. The selected decoy qubits are inserted randomly into Sa obtaining new sequence Sa′ and Alice records their positions. Subsequently, Alice sends the evolved sequence Sa′ to Bob through a quantum channel.(2)
Upon getting the evolved sequenceSa′, Bob publicly announces his secret key Kb through an authenticated classical channel.(3)
After receiving the secret key of BobKb, Alice computes the expression K=Ka⊕Kb to get the final agreement key K.(4)
Alice publicly announces the positions of the decoy qubits inSa′ and their measurement bases to Bob. Alice and Bob start evaluating the error rate ofmeasurement. If the computed error rate exceeds a preset threshold, the users should stop the protocol and restart from the first step. Otherwise, they proceed to the last step.(5)
Bob discards the measured decoy qubits and gets the ordered sequenceSa. Based on his private key Kbi, Bob applies the two unitary operations UKbi and US11 to Sa getting a new quantum sequence Sa. Bob measures the new sequence Sa using Z−basis=|0〉,|1. The measurement result that Bob gets is the final agreement key K.Figure 1
(a) represents the two-party Huang-QKA protocol; (b) represents the three-party Huang-QKA protocol; (c) represents the modified two-party Huang-QKA protocol. The dashed and solid lines represent the quantum and classical channels, respectively.
(a)(b)(c)


## 2.2. The Three-Party Huang-QKA Protocol

Assume that there are three remote users (e.g.,Alice, Bob, Charlie) who want to negotiate on an agreement keyKabc=Ka⊕Kb⊕Kc. Alice, Bob, and Charlie agree on generating three random2n bit classical secret keys Ka, Kb, and Kc, respectively.(4)Ka=Ka1,Ka2,…,Kam,Kb=Kb1,Kb2,…,Kbm,Kc=Kc1,Kc2,…,Kcm,where Ka1,Kb1,Kb1∈00,01,10,11 and i∈1,2,…,m.The steps of the three-party Huang-QKA protocol are as follows:(1)
Alice generates an ordered sequenceSa of the two-qubit quantum state according to her private information Kai, that is, if Alice’s two classical bits are 00, 01, 10, or 11, Alice generates the quantum state |++〉, |+−〉, |−+〉, or |−−〉, respectively. Alice also employs the decoy qubit protocol to protect the quantum channel by preparing a sequence of 4m decoy qubit states randomly selected from the group states |0〉,|1〉,|+〉,|−〉. The selected decoy qubits are inserted randomly into Sab and Sac obtaining new sequences Sab′ and Sac′. Subsequently, Alice sends the evolved sequences Sab′ and Sac′ to Bob and Charlie, respectively, through two quantum channels.(2)
Upon getting the evolved sequencesSab′Sab′, Bob (Charlie) publicly announces his secret key KbKc through an authenticated classical channel.(3)
After receiving the secret key of Bob (Charlie), Alice computes the expressionKabc=Ka⊕Kb⊕Kc to get the final agreement key Kabc.(4)
Alice publicly reveals positions of the decoy qubits inSab′Sac′ and their measurement bases to Bob (Charlie). Alice and Bob (Charlie) start evaluating the error rate ofmeasurement. If the computed error rate exceeds a preset threshold, the users should stop the protocol and restart from the first step. Otherwise, they proceed to the last step.(5)
Bob (Charlie) discards the measured decoy qubits and gets the ordered sequenceSabSac. Based on his private key KbiKci, Bob (Charlie) applies the two unitary operations UKbiUKci and US11 to SabSac getting a new quantum sequence SbSc Bob measures the new sequence SbSa using Z−basis=|0〉,|1. The measurement result that Bob (Charlie) gets is the final agreement key Kabc.


## 3. The Security Analysis of Huang-QKA Protocol

The quantum key agreement aims to agree on a secret key among two or more users fairly. There are three properties that should be guaranteed while designing a QKA protocol as follows.Security. External eavesdroppers cannot obtain the final key or any useful information about it without being caught.Correctness. Each legal user is guaranteed that the key agreement that it gets is correct.Fairness. All involved users influence the final agreement key equally. One user receives her/his agreement key if and only if the other user receives their agreement key with the same level of security, power, and feasibility.In the Huang-QKA protocol, there are two proposed protocols, the two-party QKA protocol and the extended three-party QKA protocol. Since the two proposed protocols are similar, we only here discuss the security of the two-party case of Huang-QKA protocol. In step (1), only Alice prepares a quantum sequenceSa based on her private key Ka through a quantum channel. In step (2), Bob sends his private key Kb though an authenticated classical channel. While in step (3), Alice can get the agreement key by computing Kab=Ka⊕Kb. If the used classical channel in step (2) is secure enough to share the private key of Bob, why do we not use a similar channel to share the private key of Alice? Of course, there is no need to employ quantum technology to achieve the key agreement if we do this. Also, this is against the aim of the Huang-QKA protocol. Obviously, there are shortcomings in the design of the Huang-QKA protocol, as eavesdroppers can clone the key transmitted over the classic channel if they have sufficient computing power or a quantum computer. Even if this shortcoming does not affect the security of the agreement key, at least it can lead to the leakage of Bob’s private key. The attackers can easily clone the private key of Bob Kb. Therefore, the Huang-QKA protocol cannot maintain the property of fairness based on the suggested strategy.


## 4. Improvement on Huang-QKA Protocol

To address the shortcoming of the Huang-QKA protocol, three steps of the Huang-QKA protocol should be modified and the remaining steps will remain unchanged as follows:(1)
Alice (Bob) generates an ordered sequenceSaSb of the two-qubit quantum state according to her private information KaiKbi, that is, if Alice’s (Bob’s) two classical bits are 00, 01, 10, or 11, Alice (Bob) generates the quantum state |++〉, |+−〉, |−+〉, or |−−〉, respectively. Alice (Bob) also employs the decoy qubit protocol to protect the quantum channel by preparing a sequence of 2m decoy qubit states selected from the group states {|0〉,|1〉,|+〉,|−〉 randomly. The selected decoy qubits are inserted into SaSb obtaining new sequence Sa′Sb′ and Alice (Bob) records their positions. Subsequently, Alice (Bob) sends the evolved sequence Sa′Sb′ to Bob (Alice) through a quantum channel.(2)
Upon getting the evolved sequenceSa′Sb′, Bob (Alice) publicly reveals positions of the decoy qubits in Sa′Sb′ and their measurement bases to Bob (Alice). Alice and Bob start evaluating the error rate ofmeasurement. If the computed error rate exceeds a preset threshold, the users should stop the protocol and restart from the first step. Otherwise, they proceed to the last step.(3)
Bob (Alice) discards the measured decoy qubits and gets the ordered sequenceSaSb. Based on his private key KaiKbi, Bob (Alice) applies the two unitary operations UKbi and US11 to Sa (UKai and US11 to Sb) getting a new quantum sequence Sa (Sb). Bob (Alice) measures the new sequence SaSb using Z−basis=|0〉,|1〉. The measurement result that Bob (Alice) gets is the final key (K).


## 5. Security Analysis

In addition to the security analysis shown in the original protocol [29], this section shows how the modified steps overcome the security flaw in the Huang-QKA protocol (see Figure 1). In step (1) of the modified protocol, Alice and Bob send their private information (Sa (Sb)) through a quantum channel. Alice (Bob) uses the decoy photon protocol to check transmission security. If an eavesdropper tries to get useful information from the quantum channel, she/he must stop the traveled sequence and measure it; then, she/he must resend it to the receiver. The probability of selecting correct measurement bases is 50%, and the probability of choosing correct initial bases to regenerate the traveled photons is 50%. So, the probability of passing the security check is 50%×50%=25%. The probability of detecting the malicious behavior of the eavesdropper is close to one (1−3/42m) when the decoy sequence (2m) is large enough. Thus, the modified protocol is secure against eavesdroppers and achieves the principle of fairness.


## 6. Conclusion

This work studies the security of the Huang-QKA schemeto securely negotiate on a secret key employing the properties of a quantumsearch algorithm. Their work uses the technique of decoy photons to secure thetransmission against external eavesdroppers. Besides, Grover’s search algorithm is used for accelerating the search process for the marked items in an unsorted database. This work found that the Huang-QKA protocol cannot maintain the properties of security and fairness since the level of security of the key agreement of users is not equal. Finally, we suggested an improved version of the Huang-QKA protocol that achieves the properties of fairness and security.



---

*Source: 3803621-2022-03-17.xml*