Message Authentication with a New Quantum Hash Function

Yalan Wang ,Yuling Chen ,Haseeb Ahmad and Zhanhong Wei

Abstract:To ensure the security during the communication,we often adopt different ways to encrypt the messages to resist various attacks.However,with the computing power improving,the existing encryption and authentication schemes are being faced with big challenges.We take the message authentication as an example into a careful consideration.Then,we proposed a new message authentication scheme with the Advanced Encryption Standard as the encryption function and the new quantum Hash function as the authentication function.Firstly,the Advanced Encryption Standard algorithm is used to encrypt the result of the initial message cascading the corresponding Hash values,which ensures that the initial message can resist eavesdropping attack.Secondly,utilizing the new quantum Hash function with quantum walks can be much more secure than traditional classical Hash functions with keeping the common properties,such as one-wayness,resisting different collisions and easy implementation.Based on these two points,the message authentication scheme can be much more secure than previous ones.Finally,it is a new way to design the message authentication scheme,which provides a new thought for other researchers in the future.Our works will contribute to the study on the new encryption and authentication functions and the combination of quantum computing with traditional cryptology in the future.

Keywords:Message authentication,symmetric encryption,quantum Hash function,quantum walk.

1 Introduction

Nowadays,we are absorbed in a world where most information can be obtained on the internet.The point-to-point quantum communication is being changed to the multi-party quantum network communication.A wide range of research meanings are focused on this problem in some network structures [Guo,Zhang and Liu (2017); Pang,Liu,Zhou et al.(2017); Li,Wang,Li et al.(2018); Shen,Song,Li et al.(2018).].Regarding the quantum networks,the feasibility and construction have been fully researched theoretically [Dong,Zhang and Zhang et al.(2014); Jiang,Jiang and Ling (2014)].Therefore,the security of information is paid so much attention during communication.There are many different ways to improve the security of the transmitted messages during communication.In information security,authentication [Needham and Schroeder (1978); Krawczyk,Bellare and Canetti (1997)] is one way of resisting active attacks,which plays an important role in various communication systems.

In general,there are two types of authentication,which are entity authentication [Bellare and Rogaway (1993)] and message authentication [Krawczyk,Bellare and Canetti(1997); Tsudik (1992)].The purpose of entity authentication is to verify the identity of the sender during communication.However,we can also use the message authentication to confirm the information source and integrity of the messages.In this manuscript,we will not give more details about the entity authentication.On the contrary,we will attach our importance to the message authentication.

In the message authentication,we adopt a technology to realize the message authentication,which is called Message Authentication Code (MAC) [Bernstein (2005)].Using this technology,the message can be transformed to a data block with the shared keys between the sender and receiver through the authentication function,the length of which is determinate.Thereafter,we cascade the data block to the message.Based on the feature of the Message Authentication Code,Hash functions are often the first choice to act as the authentication function.In classical cryptography [Vignesh,Sudharssun and Kumar (2009)],hash function [Coron,Dodis,Malinaud et al.(2005)] is an important branch.Arbitrary input can be transformed into the output whose length is fixed through the Hash function.Therefore,Hash function can compress the message which is a oneway function.Nowadays,there are many different concrete algorithms called Hash function,such as MD5 [Rivest (1992)],SHA1 [Eastlake 3rd and Jones (2001)],SHA256[Wolrich,Yap,Guilford et al.(2014)] and SHA512 [Gueron,Johnson and Walker(2011)].These Hash algorithms have some in common that the input is always divided into some blocks at the beginning of the scheme.As the computing power improves,existing Hash algorithms have difficulties in resisting various attacks.

Considering the above problems,we try to introduce quantum Hash functions to work as authentication function to improve security during communication.Due to the Shor’s algorithm and Grover’s search algorithm,quantum information processing develops so fast.In addition,there is a memory-efficient simulation method of this algorithm [Tang,Xu and Duan (2018)].Nowadays,quantum information processing are developing so fast,including quantum network coding [Li,Chen,Xu et al.(2015); Xu,Chen,Li et al.(2015)],quantum key management [Xu,Chen,Duo et al.(2015); Liu,Xu,Yang.et al(2018)],quantum secret sharing [Chen,Tang,Xu et al.(2018)],quantum remote state preparation [Xu,Chen,Dou et al.(2016); Chen,Sun,Xu et al.(2014); Qu,Wu,Wang et al.(2017)],quantum information hiding [Wei,Chen,Niu et al.(2015); Qu,Cheng,Liu et al.(2018);Qu,Chen,Ji et al.(2018)],quantum multi-party computation[Liu,Wang,Yuan et al.(2016)] and quantum relief algorithm[Liu,Gao,Yu et al.(2018)].Quantum Hash function is supposed to have better performance than classical Hash function in execution and security.Recently,many researchers proposed their quantum Hash function schemes.In 2013,Li et al.[Li,Zhang,Guo et al.(2013)] put forward a kind of quantum Hash scheme based on the two-particle interacting quantum walk.This kind of quantum Hash scheme can be executed in classical computer and practical but still need to be improved in some aspects.In 2018,Li et al.[Li,Yang,Bi et al.(2018)] presented a kind of quantum Hash function based on two-particle controlled interacting quantum walks.This quantum Hash function guarantees the security of hash function by infinite possibilities of the initial state and the irreversibility of measurement rather than hard mathematic problems.Therefore,this Hash function has better performance than the Hash scheme in Li et al.[Li,Zhang,Guo et al.(2013)].Lately,Yang et al.[Yang,Bi,Chen et al.(2018)] proposed the latest Hash scheme by introducing alternate single-qubit coin operators into discrete-time quantum walk.In addition,they showed that the implementation of this Hash function is simpler than previous quantum Hash functions.Moreover,this Hash function has a variable output length to meet the needs of various security levels desired among different applications.

As we described,the quantum Hash function has much better performance than previous classical Hash function used in the message authentication.However,if the initial message is cascaded to the hash values without any additional operations,this message authentication will be faced with eavesdropping attacks.In order to settle this problem,the Advanced Encryption Standard (AES) [Zeghid,Machhout,Khriji et al.(2007)]algorithm is naturally introduced into this message authentication scheme.That is to say,we can use the AES algorithm to encrypt the results of the initial messages cascading the hash values.When the receiver receives the ciphertexts,receiver can execute the AES algorithm to get the initial message and corresponding hash values.With the AES algorithm added,the security of the initial message can be guaranteed.

All in all,in our paper,we use the AES algorithm to serve as the encryption function and the latest Hash scheme [Yang,Bi,Chen et al.(2018)] as the authentication function in our message authentication scheme.Firstly,the AES algorithm is used to encrypt the initial message and the hash values of the initial message,which ensures that the initial message can resist eavesdropping attacks.Secondly,utilizing the new quantum Hash function with quantum walks can be much more secure than traditional classical Hash functions with keeping the common properties like one-wayness,resisting different collisions and easy implementation.Based on these two points,the message authentication scheme can be much more secure than previous ones.Finally,the security level of the message authentication will be improved greatly.Our works can offer a new aspect for utilizing quantum hash function to the traditional classical cryptology to improve the security of communication.

The remaining layout of our manuscript is organized as below.Some basic knowledge involved in our scheme will be given in Section 2.We will describe the process of the message authentication in detail in Section 3.Then,some analyses about our scheme will be provided in Section 4.Finally,conclusions will be made in Section 5.

2 Preliminaries

In the message authentication,the encryption function is supposed to be reversible.Only in this way,can the receiver decrypts the ciphertext to get the plaintext after receiving the ciphertext .However,the authentication function must be one-way so that the message can be more secure.

2.1 Symmetric encryption algorithm

In the message authentication,the encryption function should be reversible.Therefore,we take the symmetric encryption scheme into account.We can use the same keys to encrypt and decrypt messages during the communication.Generally speaking,symmetric encryption consists of two types of encryption schemes,e.g.,the block cipher and the sequential cipher (stream cipher).In our scheme,the block cipher will be focused.In block cipher scheme,firstly,the plaintext will be converted into a sequence of binary digits.Then,the sequence of binary digits will be partitioned to some equal-sized data blocks.Finally,every data block is supposed to be encrypted through some calculations with keys.This is the whole process of the block cipher scheme.All in all,when researchers design the block cipher schemes,two principles must be met,that is confusion and diffusion.Based on these two principles,the block cipher can efficiently resist the statistic analysis attacks.In our applications,there are two kinds of block cipher schemes,e.g.,Data Encryption Standard (DES) [Mahajan and Sachdeva (2013)] and AES[Mahajan and Sachdeva (2013)].

Figure1:The process of one round of AES.We take the 10 rounds AES algorithm as an example

Considering the security requirement,we adopt the AES to work as the encryption function in our scheme.There are three types of AES structures according the length of data block and keys,e.g.,the length of the data block is 128 bits and keys can be 128 bits,192 bits or 256 bits,and 10 rounds,12 rounds or 14 rounds for encryption,respectively.We choose the first one.There are four operations in every round,which are substituting bytes,shifting rows,mixing columns and adding round keys.The whole process of the AES is shown in Fig.1.

We can learn about the process of the whole AES in Fig.1.Here,we adopt the scheme of 10 rounds.However,there are some things worth noticing.In the last round,there is no mixing column operation.Additionally,before the first round,the plaintext and initial keys will be encrypted by through adding round keys.

2.2 Discrete-time quantum walk

In our paper,there is a notion involved in the quantum Hash function that is quantum walk.Quantum walk,as the counterpart of the classical random walk,has attracted as much as possible attention since proposed [Aharonov,Davidovich and Zagury (1993)].In general,quantum walk is mainly divided as continuous-time quantum walk [Norio (2005)]and discrete-time quantum walk [Lovett,Cooper,Trevers et al.(2010); Rohde,Schreiber,Štefaňák et al.(2011)].We attach the importance to the discrete-time quantum walk.Walkers are controlled by coin operators in the discrete-time quantum walk.Naturally,at the present,the number of walkers and coins is variable.There are two spaces,which are coin space denoted by Hcand walker space denoted byHw,respectively.Then,the whole space is the Hilbert space H=Hc⊗Hw.The movement of the walker is controlled by the conditional shift operator as follows:

which displays the summation over all possible positions.The whole process is under the control of the coin flipping operator and the conditional shift operatorS.The coin flipping operator is denoted byI⊗C,in whichIis the identity operator controlling the walker andCis the coin flipping operator applied to the coin state.On the circle,when we employ identity operatorI,the walker will walk clockwise.Correspondingly,if the Pauli operatorσxis employed on the circle,then,the walker will walk anticlockwise.The circumstances we describe are demonstrated in Fig.2.In our literature,the one-coin one-walker quantum walk takes place on the circle,the node number of which isN.

Figure2:The possible directions of the walker walks on the circle.(a) The direction is clockwise under the control of the coin operator I .(b) The direction is anticlockwise under the control of the coin operator σx

2.3 Quantum Hash function

After giving simple descriptions about the block cipher schemes,in the following part,one-way Hash function will be described in detail.In choosing the authentication function,we pay our attention to the one-way quantum Hash function.After studying the Yang et al.[Yang,Bi,Chen et al.(2018)],the main properties of a Hash function are onewayness,strong collision resistance and weak collision resistance.The properties of the quantum Hash function in Xu et al.[Xu,Chen,Duo et al.(2015)] are given as follows.

· One-wayness:given a messageM,it is possible to compute the Hash valueh(M)while it is infeasible to deduce the initial messageMwith a given Hash valueh(M)computationally.

· Weak collision resistance:given a messageM,it is infeasible to find another messageM1computationally so thath(M) =h(M1).

· Strong collision resistance:it is infeasible to find arbitrary two different messagesMandM1computationally so thath(M) =h(M1).

These three properties are main principles worth considering when adopting a Hash function.Compared with classical Hash function,quantum Hash function has more advantages,such as easy execution,higher level security.Introducing the quantum Hash function proposed in Yang et al.[Yang,Bi,Chen et al.(2018)],our message authentication scheme will be more secure.The detailed process of the quantum Hash function in Yang et al.[Yang,Bi,Chen et al.(2018)] is depicted as follows.

· Select the parameters(n,θ1,θ2,α)under the constraints:nis an odd number and 0 ＜θ1,θ2,α＜π/2.Hereαis the parameter determining the initial coin stateυ=c osα0 +sinα1.nis the number of nodes on a cycle.Moreover,θ1andθ2are parameters of two coin operators controlling the quantum walk.The two coin operators areC1andC2,

The initial message bit “1” decidesC1and “0” decidesC2.

· Run the one-coin one-walker discrete-time quantum walk on a cycle under the control of the messageMand generate the probability distribution.

· Amplify all values in the resulting probability distribution by10jtimes and keep only their integer part modulo2kto form a binary string as the Hash value,withj≥k.The bit length of the hash value isnk.

This is the process of the latest quantum Hash function scheme,whose security is higher than previous ones.Deservedly,we decide to adopt this quantum Hash function to be the authentication function.

3 The process of message authentication

In previous section,we have discussed the MAC.The DES with Cipher Block Chaining(CBC) model was often adopted into the message authentication in the past,which is defined CBC-MAC.However,recently,the hash function is taken to construct the corresponding MAC,which is called HAMC.One of the reasons is that the hash function can be executed easily and quickly.In this manuscript,we take a new kind of quantum hash function to work as the authentication function.We will give detailed descriptions about the general message authentication scheme and the explicit message authentication scheme we are going to take.

Firstly,we briefly introduce the process of the general message authentication scheme.In a general message authentication scheme,the initial messageMwill be encrypted with keysKusing an encryption algorithm to get the ciphertextsC(K,M).Thereafter,the sender Alice cascades the initial messageMand the ciphertextsC(K,M)to get the resultC(K,M) ||M.Then,Alice sends the resultC(K,M) ||Mto the receiver Bob.After receiving the resultC(K,M) ||M,the receiver Bob uses the same keysKto encrypt the initial messageMto getC′ (K,M).Finally,Bob compares the resultC(K,M)with the resultC′ (K,M).IfC(K,M) =C′(K,M),the messageMis not tampered and truly sent from the sender Alice,or the message authentication is invalid,that is to say,the initial messageMmay be tampered or not truly sent from the sender Alice.Finally,the whole process is shown in Fig.3.

Figure3:The general process of message authentication. M is the initial message which is going to be transferred from the sender to the receiver. C is the authentication function used to encrypt the initial message M .“||” is an operation used to cascade the initial message and the ciphertexts.The rectangular frame is used to stand for the channel during communication. K is the keys used to encrypt the initial message

In Fig.3,we can learn about the general process of message authentication.After learning about the process of the general message authentication scheme,based on these knowledge,we do some adjustments to the general message authentication scheme.In the following parts,we will describe the process of the explicit message authentication scheme in detail.The process of our message authentication scheme is shown in Fig.4.

Figure4:The process of explicit message authentication. M is the initial message which is going to be transferred from the sender to the receiver. Hash is the authentication function used to encrypt the initial message M .“||” is an operation used to cascade the initial message and the ciphertexts.The rectangular frame is used to stand for the channel during communication. K is the keys used to encrypt the initial message and decrypt the ciphertexts. E is the encryption operation. D is the decryption operation

As shown in Fig.4,we can learn about the process of the explicit message authentication scheme in detail.In this process,the parameters of the one-way quantum Hash function aren,θ1,θ2andα.nis the node number of a cycle which is an odd number.These descriptions about parameters are mentioned in Subsection 2.3.Here,we will not give too much descriptions about that.There are some differences between the general message authentication scheme and the explicit message authentication scheme.We choose a new kind of quantum Hash function into the explicit message authentication scheme to work as the authentication function.In addition,before transmitting the result of the initial message cascading the Hash values,we will use the AES algorithm to encrypt the result of the initial message cascading the Hash values,which can ensure the security of the initial message during the transmission.In the following,our message authentication scheme can be given by following steps.

· To begin with,we choose the appropriate values for parameters(n,θ1,θ2,α)and keysKpre-shared between the sender Alice and receiver Bob.The initial messageMdecides the coin operators to control the quantum walk.Then,we can get the possibility distribution to be transformed to quantum hash valueHash(M).

· The sender Alice cascades the initial messageMwith the quantum Hash valueHash(M)to get the resultM| |Hash(M).Considering the security of the initial messageM,the block cipher algorithm AES is utilized to encrypt the resultM| |Hash(M)using keysK(generated by the pseudo-random number generator) to get the ciphertextsE(K,[M| |Hash(M)]).The sender Alice sends the ciphertextsE(K,[M| |Hash(M)])through the channel (Assume that the channel is absolutely secure).

· After receiving the ciphertextsE(K,[M| |Hash(M)]),the receiver Bob firstly uses the same keysKto decrypt the ciphertextsE(K,[M| |Hash(M)])with AES algorithm.Then,Bob adopts pre-shared parameters(n,θ1,θ2,α)to perform quantum Hash operation on the initial messageMto getHash′(M).Finally,Bob compares the values ofHash(M)with that ofHash′(M).IfHash(M) =Hash′(M),it is reasonable to believe that the initial messageMis not forged or tampered and really sent from the sender Alice.However,ifHash(M) ≠Hash′(M),it is reasonable to believe that the messageMis forged or tampered or the messageMis not sent by the sender.

This is the whole process of the explicit message authentication scheme.Note that in this message authentication scheme,on the one hand,AES algorithm works as the encryption function to ensure the security of the initial messageM.In this way,can the scheme resist the passive attacks,such as eavesdropping attacks.On the other hand,we adopt the one-way quantum Hash function to serve as the authentication function to resist active attacks,such as forging or tampering the initial messages.Therefore,this message authentication scheme will be much more secure than the previous ones.After giving our detailed message authentication scheme,in the following parts,analyses for this message authentication scheme will be given.

4 Analyses

In this proposed message authentication scheme,the encryption function and authentication function are two main parts.So we decide to analyze our message authentication scheme from these two aspects in the following parts.

4.1 The encryption function

In this paper,we use the AES algorithm to be the encryption function.In the process of the message authentication scheme,after receiving the ciphertexts,the receiver Bob is going to decrypt the ciphertexts using the same encryption algorithm.Therefore,the encryption function should be reversible.And until now,it is no doubt that the AES algorithm is a better choice no matter from the security or the implementation.Even the length of the block data and keys are 64 bits and 56 bits,respectively,the DES algorithm still cannot meet the security requirements under the present circumstances.Therefore,we choose the AES algorithm to act as the encryption function in our message authentication scheme.

In AES algorithm,there are four important operations which are substituting bytes,shifting rows,mixing columns and adding round keys.Moreover,before the four operations,with the operation extending keys added,the security of AES is greatly improved.We mainly analyze the AES algorithm from four aspects,e.g.,security,performance,space and implementation.

· As for the security of the AES algorithm,S box in the operation substituting bytes is non-linear and the operation mixing columns contributes to the diffusion of the AES algorithm.Additionally,the complexity of all the four operations and the operation extending keys ensure the security of the AES algorithm.

· The performance of the AES algorithm is evaluated by how many attacks the algorithm can resists,encryption,decryption and keys used in the message authentication scheme.Firstly,the AES can resist the energy attack and timing attack.At the same time,the execution is not influenced.Then,the process of the encryption is not same with that of decryption.And the time to execute the encryption and decryption is very close.Finally,the length of the data block and keys can be selective for 128 bits,192 bits and 256 bits.This displays that we can decide the data block and keys flexibly,which improve the security of the message authentication scheme.After these analyses,on the whole,the performance of the AES algorithm is much better than the previous symmetric algorithms.· The steps for encryption are not same with that for decryption,therefore,the AES algorithm is suitable for the limited space and circumstances to execute encryption or decryption operations.

· On one hand,it is very convenient for the AES to be executed on different systems including the 8-bit,64-bit and DSP.The built-in distribution mechanism can make better use of CPU resources.This is the advantages of the AES algorithm in software.On the other hand,in hardware,when adopted 128 bits for the length of data block and keys,time to execute the AES algorithm is extremely less than other symmetric algorithms.However,more rounds are needed if the length of the keys becomes larger.Then,we need more time to execute the AES algorithm,which means that we need more time to execute the message authentication scheme naturally.Honestly,this is a weakness of the AES algorithm.

Through these analyses,it is obvious that the AES algorithm is a relatively better choice to act as the encryption function in the message authentication scheme.

4.2 The authentication function

We have mentioned some advantages in previous sections so that the one-way quantum Hash function has better performance than one-way classical Hash function.In designing classical Hash message authentication code (HMAC),there are some principles to be considered,which are listed in RFC 2104.Though we adopt the quantum Hash function,the analyses are still similar to that of the classical Hash function.

· The quantum Hash function in the message authentication scheme should be easily implemented in corresponding software.In this message authentication scheme,the quantum Hash values are generated by the one-coin one-walker quantum walk.With classical computer,the process of quantum walk can be easily realized to get the corresponding Hash values.Therefore,our quantum Hash function has no difficulties in software implementation.

· It should be convenient and easy to apply the keys and operations involved in the Hash function.The main operation of the quantum Hash function is quantum walk,which can be easily executed in classical computer.As for the keys,parameters of the keys are(n,θ1,θ2,α)andKwhich are determined in the beginning without complex computation.So the keys and operations involved in this quantum Hash function can be realized easily.

· When designing the Hash function in the message authentication scheme,the properties of the Hash function should be kept.The quantum Hash function,proposed in Yang et al.[Yang,Bi,Chen et al.(2018)],still has basic properties.The quantum Hash function has properties of one-wayness,resistance to birthday attack,good avalanche effect and good sensitivity to the initial messageM.In addition,the diffusion and confusion properties are still be kept shown in Yang et al.[Yang,Bi,Chen.et al (2018)].In general,the essential properties of the classical Hash function are still kept in this quantum Hash function.

· If the security of the Hash function can be ensured,the security of the message authentication scheme will be guaranteed too.In a message authentication scheme,the security of the authentication function is greatly fundamental to the whole scheme.First,the initial state is infinite and the modular arithmetic is irreversible involved in the quantum Hash function.Second,on a classical computer,assumingNpossible items of the set for the variables (Nis infinite theoretically),it obviously takesO(N)operations to determine the items.So it is computationally hard to find collision for this quantum Hash function.Finally,when generating the Hash values,we amplify the resulting probability distribution by10jtimes and keep only the integer part modulo2k.This makes the process irreversible because it is a many-to-one relationship.Based on these properties,it is reasonable to believe that the quantum Hash function is very secure.

Based on the above analyses,no matter from the performance or security,the one-way quantum Hash function is very suitable to be adopted in the message authentication scheme.

5 Conclusions

After the above discussions,we will give some conclusions about our message authentication scheme.In traditional message authentication scheme,there are two main functions called encryption function and authentication function,respectively.Generally speaking,the encryption function is reversible,however,the authentication function is irreversible.Based on these principles,considering the security and implementation of the whole message authentication scheme,we take the AES algorithm as the encryption function and a new kind of one-way quantum Hash function as the authentication function.In existing circumstances,the AES algorithm is relatively secure than other symmetric encryption algorithms.More importantly for this paper,we adopt the quantum Hash function to serve as the authentication function for the first time.Due to the improvements to the computing power,existing encryption and authentication algorithms are being faced with big challenges.So it is a trend to try new and more secure encryption and authentication functions.The quantum Hash function based on the quantum walks is a good choice.The quantum Hash function has the common properties with classical Hash functions,such as irreversibility,sensitive to the initial messageMand resisting different collisions.In addition,the quantum Hash function is implemented very easily on classical computer.Last but not least,the quantum Hash function is more secure than classical Hash functions.Because in the process of the one-way quantum Hash function,the initial states are infinite and some operations in the generation of the Hash values are non-linear.In conclusion,the quantum Hash function used in the message authentication scheme makes this message authentication scheme absolutely more secure.

Every coin has two sides.The quantum Hash function maybe has some weakness left to be improved in the future,such as all-round security tests and mature applications.But it is worth believing that the quantum Hash function will be a good choice in wide application sooner or later.