# Novel Quantum Encryption Algorithm Based on Multiqubit Quantum Shift Register and Hill Cipher

Authors: Rifaat Zaidan Khalaf; Alharith Abdulkareem Abdullah
Journal: Advances in High Energy Physics
 (2014)

---

## Abstract

Based on a quantum shift register, a novel quantum block cryptographic algorithm
that can be used to encrypt classical messages is proposed. The message is encoded and decoded
by using a code generated by the quantum shift register. The security of this algorithm is
analysed in detail. It is shown that, in the quantum block cryptographic algorithm, two keys
can be used. One of them is the classical key that is used in the Hill cipher algorithm where
Alice and Bob use the authenticated Diffie Hellman key exchange algorithm using the concept
of digital signature for the authentication of the two communicating parties and so eliminate
the man-in-the-middle attack. The other key is generated by the quantum shift register and
used for the coding of the encryption message, where Alice and Bob share the key by using
theBB84 protocol. The novel algorithm can prevent a quantum attack strategy as well as
a classical attack strategy. The problem of key management is discussed and circuits for the
encryption and the decryption are suggested.


---

## Body

## 1. Introduction

Cryptography is the science of protection of private information from unauthorized access, ensuring data integrity, authentication, and other related features. In order to succeed in achieving this goal, a cryptography algorithm is employed to produce a cryptogram which includes some additional information that finally determines which key is used. Classical cryptography is divided into two main types depending on the actions of the two conventional parties Alice and Bob. The first type is a symmetrical system with Alice and Bob using the same key. The second type, the asymmetrical system, is so named when Alice and Bob use a different key. The one-time-pad algorithm also belongs to classical cryptography [1]. Quantum cryptography is an emerging technology based on quantum mechanics and the phenomena and the properties of light. Quantum cryptography was developed in 1984 by the physicist Charles Henry Bennett when he developed what he claimed was an unconditionally secure quantum key distribution protocol called BB84 which guaranteed secure communication between parties who had not initially shared secret information [2]. The science is grounded in the uncertainty principle and was proven scientifically in 1992 [3]. Over the following years this science began to evolve rapidly and to have significant effects. Recently, a quantum encryption algorithm has been proposed but it has been noticed that the quantum encryption algorithm is very similar to the classical encryption algorithm with the crucial difference that the quantum algorithm is based on quantum laws whilst the classical algorithms are based on mathematical ones [4–7]. This development in the field of quantum computation may threaten and replace traditional encryption systems by utilizing algorithms such as Shor’s quantum factoring algorithms, discrete algorithms, and Grover’s algorithm. Thus, we should be looking to design new algorithms to resist the attacks against quantum algorithms whose contribution and progress in this field has become of significant importance and crucial necessity in the protection of information. Unlike classical algorithms, where Eve can be detected easily, the defining characteristics of quantum algorithms provide a much more secure system because the nonorthogonal quantum states protect the information from reliable detection. Unlike classical algorithms, where Eve can be detected easily, the defining characteristics of quantum algorithms provide a much more secure system because the nonorthogonal quantum states protect the information from reliable detection [8]. In other words, in practical terms an unconditionally secure algorithm is of far greater significance and value as a protection system of information than the classical algorithm approach wishing to achieve the same goal. Therefore, the quantum algorithms are the best candidates to provide for these needs. In this paper we will propose a novel and practical quantum block encryption algorithm based on a quantum shift register.The planning of the paper is as follows. In Section1, we briefly review classical cryptography and quantum cryptography. Section 2 discusses the quantum shift register and how to generate a matrix code used in the Diffie-Hellman algorithm to match the key between Alice and Bob to be used later in the Hill cipher algorithm [1] and then generate another matrix code used as a one-time pad (OTP). Section 3 is on a quantum encryption algorithm based on the quantum shift register where the encryption, decryption, and transmission of the proposed algorithm are discussed. In Section 4, the security and evaluation of the proposed algorithm are analysed. Finally, we give a brief conclusion in Section 5.


## 2. Quantum Shift Register

There are many applications of a quantum shift register. The shift registers are mainly used in coding theory, especially in quantum error correction and quantum convolution code [9–12]. This study focuses on the utilization of a quantum shift register to generate a matrix code used in the Diffie-Hellman algorithm to match the key between Alice and Bob in our proposed algorithm and then generate a matrix code used as one-time pad in the encryption of plaintext of our proposed algorithm as well.


### 2.1. Circuit of the Quantum Shift Register

The quantum shift register circuit is represented by a set of input qubits, memory qubits, a set of output qubits, and updated memory qubits. It feeds the memory back into the application for the next cycle and this concept is similar to the operation of a classical shift register. A quantum shift register circuit consists of swap gates, which can be quantum computationally represented using three CNOT gates as in Figure1. The properties of CNOT are discussed in [13]. One possible physical realization of the quantum CNOT gate was presented by Linden et al. [14]. The quantum shift register circuit can shift all data qubits to the nearest qubit in a specific direction and apply applications like arithmetic calculation and bitwise operations on two quantum registers where these operations are very useful for quantum computers and quantum computation. The circuit of the quantum shift register is presented and considered in [11] in which shift and rotation operations on qubits are performed by swap gates and controlled swap gates.Figure 1
SWAP gate using CNOT gates.


### 2.2. Discussion of the Quantum Shift Register in the Proposed Algorithm

The quantum shift register has a number of positions. Each of these positions contains one qubit. In quantum register all qubits can be shifted one or more positions to the left or to the right. The length of the quantum shift register is determined by the number of qubits (states), the contents of each qubit are shifted to the next qubit in each pulse, and the outputs of the final qubit show a quantum feedback function and the resulting sequence from the quantum shift register is the content of the first qubit. This includes the following steps:(i)
quantum shift register,(ii)
quantum CNOT gate,(iii)
quantum feedback shift register.The quantum shift register is the shift operation that depends on the swap gate. The shift is done between data and the process continues until the qubit repeats itself. The quantum CNOT gate acts on the connection states in the quantum register and chooses the connect state that achieves the maximum period. The quantum CNOT gate action on two or more qubits,where one or more qubits acts as a control. For instance, the CNOT operation acts on two qubits, and performs the NOT operation on the second qubit only when the first qubit is1, and otherwise leave it unchanged, so the quantum CNOT of 10 became 11. Clearly the quantum linear feedback shift register is essential in building the quantum stream cipher algorithm. The quantum feedback shift register represents the outputs of the quantum CNOT function and is positioned in the final state (qubit) of quantum register.In this study this example was taken to understand the mechanism, for instance, if we have a quantum shift register with length three and has initial value ares1=a10+b11, s2=a20+b21, s3=a30+b31, the function linking is between s1 and s2. The tensor product between states be:
(1)ψ=s1⊗s2⊗s3ψ=010203+010213+011203+011213+110203+110213+111203+111213.The quantum linear feedback shift register was applied on the first stateψ and the computation compute as follows:
(2)Shift1=CNOT1,2010203·SWAP1,2010203·SWAP2,3010203+CNOT1,2010213·SWAP1,2010213·SWAP2,3010213+CNOT1,2011203·SWAP1,2011203·SWAP2,3011203+CNOT1,2011213·SWAP1,2011213·SWAP2,3011213+CNOT1,2110203·SWAP1,2110203·SWAP2,3110203+CNOT1,2110213·SWAP1,2110213·SWAP2,3110213+CNOT1,2111203·SWAP1,2111203·SWAP2,3111203+CNOT1,2111213·SWAP1,2111213·SWAP2,3111213.This then continues to the second shift using the same procedure and by taking the output of the first shift as input to the second shift. The accumulation at every stage of output proceeds in this way until it reaches the seventh and final shift. Therefore, each stage of the process is conducted and implemented in the same way. It is now possible to select any shift from those completed: for example, if shiftShift6 is chosen, the corresponding matrix to this shift is called matrix A, where the rows for matrix A equal
(3)g0=10000000=0,g1=00100000=1,g2=00001000=2,g3=00000010=3,g4=00010000=4,g5=01000000=5,g6=00000001=6,g7=00000100=7.Now, from the above matrixA the matrix code can be generated by using the XOR operation between the rows of matrix A. The matrix code that was used in our proposed algorithm as a code for the matching key in the Diffie-Hellman concept once and one-time-pad matrix used to encode the plaintext once again. For example, if the above matrix A is used for desired n=3 we can generate the matrix code as:
(4)g0=10000000,g1=00100000,g2=00001000,g3=00000010,
continuing to generate matrix code, where
(5)g0⊕g1=10100000,g0⊕g1⊕g2=10101000.
In similar way we can generate matrix code of any desired order and generate any number of codes from it.


## 2.1. Circuit of the Quantum Shift Register

The quantum shift register circuit is represented by a set of input qubits, memory qubits, a set of output qubits, and updated memory qubits. It feeds the memory back into the application for the next cycle and this concept is similar to the operation of a classical shift register. A quantum shift register circuit consists of swap gates, which can be quantum computationally represented using three CNOT gates as in Figure1. The properties of CNOT are discussed in [13]. One possible physical realization of the quantum CNOT gate was presented by Linden et al. [14]. The quantum shift register circuit can shift all data qubits to the nearest qubit in a specific direction and apply applications like arithmetic calculation and bitwise operations on two quantum registers where these operations are very useful for quantum computers and quantum computation. The circuit of the quantum shift register is presented and considered in [11] in which shift and rotation operations on qubits are performed by swap gates and controlled swap gates.Figure 1
SWAP gate using CNOT gates.


## 2.2. Discussion of the Quantum Shift Register in the Proposed Algorithm

The quantum shift register has a number of positions. Each of these positions contains one qubit. In quantum register all qubits can be shifted one or more positions to the left or to the right. The length of the quantum shift register is determined by the number of qubits (states), the contents of each qubit are shifted to the next qubit in each pulse, and the outputs of the final qubit show a quantum feedback function and the resulting sequence from the quantum shift register is the content of the first qubit. This includes the following steps:(i)
quantum shift register,(ii)
quantum CNOT gate,(iii)
quantum feedback shift register.The quantum shift register is the shift operation that depends on the swap gate. The shift is done between data and the process continues until the qubit repeats itself. The quantum CNOT gate acts on the connection states in the quantum register and chooses the connect state that achieves the maximum period. The quantum CNOT gate action on two or more qubits,where one or more qubits acts as a control. For instance, the CNOT operation acts on two qubits, and performs the NOT operation on the second qubit only when the first qubit is1, and otherwise leave it unchanged, so the quantum CNOT of 10 became 11. Clearly the quantum linear feedback shift register is essential in building the quantum stream cipher algorithm. The quantum feedback shift register represents the outputs of the quantum CNOT function and is positioned in the final state (qubit) of quantum register.In this study this example was taken to understand the mechanism, for instance, if we have a quantum shift register with length three and has initial value ares1=a10+b11, s2=a20+b21, s3=a30+b31, the function linking is between s1 and s2. The tensor product between states be:
(1)ψ=s1⊗s2⊗s3ψ=010203+010213+011203+011213+110203+110213+111203+111213.The quantum linear feedback shift register was applied on the first stateψ and the computation compute as follows:
(2)Shift1=CNOT1,2010203·SWAP1,2010203·SWAP2,3010203+CNOT1,2010213·SWAP1,2010213·SWAP2,3010213+CNOT1,2011203·SWAP1,2011203·SWAP2,3011203+CNOT1,2011213·SWAP1,2011213·SWAP2,3011213+CNOT1,2110203·SWAP1,2110203·SWAP2,3110203+CNOT1,2110213·SWAP1,2110213·SWAP2,3110213+CNOT1,2111203·SWAP1,2111203·SWAP2,3111203+CNOT1,2111213·SWAP1,2111213·SWAP2,3111213.This then continues to the second shift using the same procedure and by taking the output of the first shift as input to the second shift. The accumulation at every stage of output proceeds in this way until it reaches the seventh and final shift. Therefore, each stage of the process is conducted and implemented in the same way. It is now possible to select any shift from those completed: for example, if shiftShift6 is chosen, the corresponding matrix to this shift is called matrix A, where the rows for matrix A equal
(3)g0=10000000=0,g1=00100000=1,g2=00001000=2,g3=00000010=3,g4=00010000=4,g5=01000000=5,g6=00000001=6,g7=00000100=7.Now, from the above matrixA the matrix code can be generated by using the XOR operation between the rows of matrix A. The matrix code that was used in our proposed algorithm as a code for the matching key in the Diffie-Hellman concept once and one-time-pad matrix used to encode the plaintext once again. For example, if the above matrix A is used for desired n=3 we can generate the matrix code as:
(4)g0=10000000,g1=00100000,g2=00001000,g3=00000010,
continuing to generate matrix code, where
(5)g0⊕g1=10100000,g0⊕g1⊕g2=10101000.
In similar way we can generate matrix code of any desired order and generate any number of codes from it.


## 3. Proposed Quantum Encryption Algorithm

The idea of our proposed algorithm is very straightforward. Before proceeding to talk about the algorithm itself, it should be noted that the conventional parties in the cryptography, Alice, Bob, and the meddler Eve, are used. Likewise, the algorithm is divided into the encryption, decryption, and transmission as follows.


### 3.1. Encryption Part

In the beginning, Alice computes word length from the plaintext and executes modulus 2 operation if she wants to encrypt plaintext with2*2 matrix in accordance with the Hill cipher algorithm [1]. If the result is 0 she sends the word length to Bob or else increments the word length by 1 to make the word length even and then sends it to Bob. Both Alice and Bob compute seven times the word length and generate the matrix A of the desired n depending on the result. For example, if the word length is 4, then 4×7=28. Thus, a matrix A of order 32 is generated which means the length of the quantum shift register is 5 qubits. She encrypts the plaintext by using the Hill cipher algorithm as follows:
(6)EncryptPlaintext=KeyMatrix2*2×PlaintextMatrix.
Alice converts each encrypted plaintext character into its equivalent 7-bit ASCII representation. She uses the matrix of the quantum shift register again to generate one-time pad or the key, depending on her route of choice. This one-time pad serves as the symmetric key for the cryptographic process. For example,
(7)g1⊕g10⊕g15⊕g18⊕g55.Finally, she performs the XOR operation between the qubits of the encoded message and the one-time pad (key) to produce the quantum ciphertext.


### 3.2. Transmission Part

In this part, Alice and Bob have two keys they should be sharing. One of them is the classical key that is used in the Hill cipher algorithm where Alice and Bob use the authenticated Diffie-Hellman key exchange algorithm utilizing the idea of a digital signature in order to verify and confirm the identity of the two connecting parties and defend against a man-in-the-middle attack. For example, Alice generates the matrixA where the rows of the matrix are
(8)g0=10000000=000=0,g1=00010000=001=1,g2=01000000=010=2,g3=00000100=011=3,g4=00100000=100=4,g5=00000010=101=5,g6=00001000=110=6,g7=00000001=111=7.
Alice, for instance, selects three random numbers:
(9)g0=10000000,g1=00010000,g2=01000000,g0+g1+g2=11010000.
Now Alice has four numbers: g0,g1,g2,g0+g1+g2; Alice send to Bob three numbers and hides, for instance, g2 number: g0,g1,g0+g1+g2=10000000,00010000,11010000; Bob selects a number called g3=00000100; then he computes g0+g1+g3=10010100 leading to g0+g1+g3 and sends it to Alice.The key for Alice isg0+g1+g3+g2=11010100, The key for Bob is g0+g1+g2+g3=11010100.The above example explains the concept of Diffie-Hellman clearly in our approach. Now, suppose they exchange a secret key as 210. Then, both parties perform operation:(10)g0⊕g1⊕g10⊕g16⊕g56⊕g60⊕g210.
The operation is performed by ignoring the values that do not exist in the generated matrix. The gs represent the corresponding row numbers to be selected for the key creation. After the completion of the operation above, both parties generate the same bit sequence of 1s and 0s. Alice then informs Bob by sending a plaintext message where she indicates her choices, as in 1 as rectilinear and 0 as diagonal and so on. The other key or the one-time pad transmits to Bob by converting the key into binary bit string and again setting up a similar basis at both ends. Then the bits are transmitted across the secure channel where both parties set their basis according to previously generated bit sequences and the agreed-upon pattern for the representation of the bits. In turn, the bits are transmitted securely to Bob. This process is called deterministic one-step quantum key distribution using theBB84 protocol. The key for the Hill cipher algorithm is again transmitted by Alice in a similar manner by converting the key into a binary bit string and again setting up a similar basis at both ends. After that, the bits are transmitted across the insecure channel securely.


### 3.3. Decryption Part

After the keys are received by Bob, he uses the one-time pad to decode the message. After that, Bob computes the inverse key of the Hill cipher and recovers the plaintext message in the original form. Figure2 clarifies the representation of the proposed algorithm.Figure 2
Encryption, transmission, and decryption process.


## 3.1. Encryption Part

In the beginning, Alice computes word length from the plaintext and executes modulus 2 operation if she wants to encrypt plaintext with2*2 matrix in accordance with the Hill cipher algorithm [1]. If the result is 0 she sends the word length to Bob or else increments the word length by 1 to make the word length even and then sends it to Bob. Both Alice and Bob compute seven times the word length and generate the matrix A of the desired n depending on the result. For example, if the word length is 4, then 4×7=28. Thus, a matrix A of order 32 is generated which means the length of the quantum shift register is 5 qubits. She encrypts the plaintext by using the Hill cipher algorithm as follows:
(6)EncryptPlaintext=KeyMatrix2*2×PlaintextMatrix.
Alice converts each encrypted plaintext character into its equivalent 7-bit ASCII representation. She uses the matrix of the quantum shift register again to generate one-time pad or the key, depending on her route of choice. This one-time pad serves as the symmetric key for the cryptographic process. For example,
(7)g1⊕g10⊕g15⊕g18⊕g55.Finally, she performs the XOR operation between the qubits of the encoded message and the one-time pad (key) to produce the quantum ciphertext.


## 3.2. Transmission Part

In this part, Alice and Bob have two keys they should be sharing. One of them is the classical key that is used in the Hill cipher algorithm where Alice and Bob use the authenticated Diffie-Hellman key exchange algorithm utilizing the idea of a digital signature in order to verify and confirm the identity of the two connecting parties and defend against a man-in-the-middle attack. For example, Alice generates the matrixA where the rows of the matrix are
(8)g0=10000000=000=0,g1=00010000=001=1,g2=01000000=010=2,g3=00000100=011=3,g4=00100000=100=4,g5=00000010=101=5,g6=00001000=110=6,g7=00000001=111=7.
Alice, for instance, selects three random numbers:
(9)g0=10000000,g1=00010000,g2=01000000,g0+g1+g2=11010000.
Now Alice has four numbers: g0,g1,g2,g0+g1+g2; Alice send to Bob three numbers and hides, for instance, g2 number: g0,g1,g0+g1+g2=10000000,00010000,11010000; Bob selects a number called g3=00000100; then he computes g0+g1+g3=10010100 leading to g0+g1+g3 and sends it to Alice.The key for Alice isg0+g1+g3+g2=11010100, The key for Bob is g0+g1+g2+g3=11010100.The above example explains the concept of Diffie-Hellman clearly in our approach. Now, suppose they exchange a secret key as 210. Then, both parties perform operation:(10)g0⊕g1⊕g10⊕g16⊕g56⊕g60⊕g210.
The operation is performed by ignoring the values that do not exist in the generated matrix. The gs represent the corresponding row numbers to be selected for the key creation. After the completion of the operation above, both parties generate the same bit sequence of 1s and 0s. Alice then informs Bob by sending a plaintext message where she indicates her choices, as in 1 as rectilinear and 0 as diagonal and so on. The other key or the one-time pad transmits to Bob by converting the key into binary bit string and again setting up a similar basis at both ends. Then the bits are transmitted across the secure channel where both parties set their basis according to previously generated bit sequences and the agreed-upon pattern for the representation of the bits. In turn, the bits are transmitted securely to Bob. This process is called deterministic one-step quantum key distribution using theBB84 protocol. The key for the Hill cipher algorithm is again transmitted by Alice in a similar manner by converting the key into a binary bit string and again setting up a similar basis at both ends. After that, the bits are transmitted across the insecure channel securely.


## 3.3. Decryption Part

After the keys are received by Bob, he uses the one-time pad to decode the message. After that, Bob computes the inverse key of the Hill cipher and recovers the plaintext message in the original form. Figure2 clarifies the representation of the proposed algorithm.Figure 2
Encryption, transmission, and decryption process.


## 4. The Security and Evaluation of the Proposed Algorithm

It is known that, based on the algorithm of Bennett and Brassard [2], there are a lot of qubits that acquire distortion during the process of transmission because of the difference in the selection of bases between Alice and Bob. Therefore, in this proposal, Alice and Bob use the same basis during the transmission by reconciling on a common basis before they start transmitting the message which is based on quantum key distribution. This proves that our proposal is deterministic. In addition, this represents an enhancement of the feature of the Bennett and Brassard algorithm.The scheme used in this study is a quantum linear feedback shift register to generate2n-1 of shifting. Each shift represents a matrix and this matrix contains binary bits. The Diffie-Hellman key exchange concept was also used between Alice and Bob in such a way that Eve does not possess all the keys between Alice and Bob. As a result, the ciphertext-only attack, the known-plaintext attack, and the chosen-plaintext attack are impossible. In classical cryptography, Eve can duplicate the ciphertext without modifying it through intercepting the channel or illegitimately accessing the ciphertext bank. This allows Eve to attempt to decrypt it time after time. However, using a quantum encryption algorithm, given a quantum ciphertext QC, Eve cannot derive M without the information of the encrypted matrix and one-time pad (key). In addition to that, if Eve manages to obtain the encrypted matrix, she cannot manage to determine the bits message because, for each bit, the probability is bound by 1/2. Supposing the length of the encrypted message block is n, the probability is bound by 1/2n, which is negligible.Furthermore, if Eve manages to obtain the qubit, she cannot determine the bitM. For example, if she obtains 0 and knows each qubit, she is not able to determine M because there are two preimages, 0⊕0 and 1⊕1.Likewise, from the encryption process of our algorithm, the known-plaintext and the chosen-plaintext attack are unfeasible because Eve could not know without the key what the ciphertext corresponding to the known-plaintext is. This property results from the uncertainty principle in quantum mechanics.


## 5. Conclusion

Quantum technology is new and being improved and sophisticated constantly, specifically in the field of quantum cryptography. it is an undisputed fact that the advances made in science and technology are one of the greatest challenges for the future and innovation in the field is advancing at an enormous pace and that, sooner or later, the quantum computers will assume a very significant role in this world. So it is not possible to treat or transfer all of the existing information in the classical form which is familiar to the people in quantum information and preshared classical keys as long as the security cannot be guaranteed. Therefore, it is proposed that a new algorithm encrypts the classical data using a classical encryption algorithm and transfers it by quantum data, where the classical encryption algorithm is represented by the Hill cipher algorithm and the quantum algorithm is represented by the quantum shift register. The security and the physical implementation of the proposed algorithm are analyzed in detail and it is concluded that the new proposed algorithm can prevent a quantum attack as well as a classical attack. Managing to prevent two kinds of attack and protecting the information from a new prying strategy is the goal. It should be mentioned that improvements can be made to the algorithm by future users in order to strengthen its capability and make it more effectively secure.



---

*Source: 104325-2014-11-24.xml*