# A Hierarchical Matrix Decomposition-Based Signcryption without Key-Recovery in Large-Scale WSN

Authors: Chi Yuan; Wenping Chen; Deying Li
Journal: Wireless Communications and Mobile Computing
 (2018)

---

## Abstract

The sensors in wireless sensor network (WSN) are vulnerable to malicious attacks due to the transmission nature of wireless media. Secure and authenticated message delivery with low energy consumption is one of the major aims in WSN. The identity-based key authentication scheme is more suitable for the WSN. In this paper, the Hierarchical Matrix Decomposition-based Signcryption (HMDS) algorithm was proposed, which is a kind of identity-based authentication scheme. In HMDS scheme, three-layer architecture, base station (BS), cluster head, and intracluster, is employed to adapt to the common structure of WSN. As the key generation center (KGC), the BS adopts matrix decomposition to generate the identification information and public key for cluster head, which not only reduces the cost of calculation and storage but also avoids the collusion attack. Experiments show that the HMDS algorithm has more advantages over other algorithms and is very suitable for the large-scale WSN.


---

## Body

## 1. Introduction

Wireless sensor network (WSN) combined sensor and network communication technology has real-time sensing and information acquisition functions. It is applied to various fields such as national defense, environment monitoring, transportation management, medical treatment, and public health [1, 2]. The wireless sensor network has the characteristics of large-scale, multihop communication and complex deployment environment, and so forth [3, 4]. At the same time, since the sensor network nodes mostly have small size and are deployed in unattended harsh environment, the sensor node energy as well as the computing capability is greatly limited. Therefore, low energy cost and computation complexity are important requirements for WSN application [5]. In addition, WSN is different from the wired network, the communication channel of wireless network is public, and it is not difficult for an adversary to manipulate the sensors in an unprotected WSN. As a result, the sensors in a WSN are vulnerable to malicious attacks. Thus, the energy efficiency and network security must be considered when designing WSN application [6–9].Cryptography plays a very important role in security [10–12]. The common public key encryption methods can be classified into three categories: Public Key Infrastructure (PKI) based encryption, identity-based encryption (IBE) and the certificate-free encryption [13]. Among them, the identity-based encryption (IBE) method has obvious advantage in both security and calculation complexity. The literature [14] pointed out that the IBE method is the most suitable public key system for wireless sensor networks (WSN). However, there is a flaw in the key escrow scheme of IBE algorithms. Because the Private Key Generator (PKG) holds private keys of all users, it can easily impersonate any node user, decrypt its ciphertext, and forge user signatures.In this paper, the Hierarchical Matrix Decomposition-based Signcryption (HMDS) algorithm was proposed to resolve the above problems. In HMDS algorithm, the clustering management scheme is employed to adapt to the data aggregation architecture in WSN. The matrix decomposition-based method is adopted to generate the keys for cluster head nodes, which makes use of identification information and avoids absolute control of KGC on the private keys. Such mechanism really solves the key escrow problem in IBE algorithm. To evaluate the performance of the HMDS scheme, we compare it with the Hierarchical Identity-Based Signcryption Scheme (HIS) algorithm [15]. The experiment results show that the HMDS algorithm is more suitable for the WSN. Especially in the large-scale WSN, the HMDS algorithm is very stable and has advantage over HIS scheme.


## 2. Related Works

### 2.1. Public Key Authentication

In recent years, many researchers have done a lot of work on the key authentication for WSN. There are three kinds of authentication methods, PKI-based encryption, identity-based encryption, and certificate-free encryption.


#### 2.1.1. PKI-Based Encryption

In a typical PKI-based scheme, the public key certificate is signed by a certificate authority (CA) to achieve the binding between the user’s public key and its identity. The certificate-based key management scheme is the most common authentication scheme. However, the PKI-based key management scheme tends to consume too much storage, calculation, and communication resource, which is unaffordable for the energy-constrained sensor nodes in WSN [16, 17].


#### 2.1.2. Identity-Based Encryption

In 1984, the identity-based encryption algorithm was first proposed by Shamir [18], which enabled any pair of users to communicate securely and verify each other’s signatures without exchanging private or public keys. In 2003, Chen studied the key management protocol in identity-based encryption scheme [19]. In order to simplify the management of the key, the user’s public key was used for directly calculating the user’s identity information, and the private key was credibly generated by PKG (Private Key Generator). Without the public key certificate, such scheme reduced the storage and computing cost for issuance, cancellation, and certification.To reduce the energy consumption of the identity-based authentication node, some identity-based key management protocols for WSN were proposed [20, 21]. The literature [11] pointed out that the identity-based encryption was the most suitable public key scheme for wireless sensor networks (WSN). Neal Koblitz [22] and Victor Miller [23] proposed elliptic curve cryptosystem. Then, the similar algorithm was proposed by Zhang et al. in [24], which presented that the security of ECC was based on the discrete logarithm problem. Compared with other public key systems, this scheme is a promising method with high security, low cost, and high efficiency. However, in most elliptic curves based key management schemes, grouping management mechanism was not introduced. With the increasing of nodes, more communication with BS is needed, which was not suitable for the nodes with limited energy in WSN.In the key-insulated cryptography proposed by Qin Zhiguang et al., the key was divided into two parts: one part was managed by the users and the other part was saved by a physical security helper [12]. When the key was needed, the two parts of the key were spliced into a complete key. But it failed to take advantage of the identity information from each effective node. Chen Yuan et al. [13] proposed an identity-based encryption scheme without bilinear pairings. Both algorithms used the idea of noncertificate; the private key was generated by the node and the Private Key Generator (PKG). Therefore, the two algorithms could not really solve the key escrow problem.Guo Jianghong et al. [16] proposed a new key agreement scheme for WSN. The node established the pairing key through the Diffie-Hellman protocol, and the required key parameters are obtained through broadcast. The scheme still has the advantages of the identity-based encrypted key agreement scheme, but the time and energy consumption for bilinear pairing operation is very high. Guo et al. [25] combined the identity-based RSA mechanism with the lightweight Certificate Authority (CA) to construct an identity-based mixed model, ECC-CA, for sensor network cryptography scheme. But the scheme has relatively huge cost of calculation and communication.


#### 2.1.3. Certificate-Free Encryption

To resolve the certificate problem in the PKI-based scheme and the key escrow problem in the identity-based scheme, the certificate-free encryption method was proposed. In certificate-free encryption algorithm, a credible third-party Key Generation Center (KGC) was still employed to jointly generate the user’s private key. KGC did not directly hold the users’ private keys but only generated a partial private key. The users themselves generated the final private key instead. In such scheme, the public key information could not be directly obtained from the user identity information [26, 27]. At present, these provable security certificate-free construction methods are based on the Waters hash function, which leads to long system parameters and requires more pairing calculations. Thus, these methods are not suitable for WSN with limited storage capacity and calculation capability.


### 2.2. Cluster-Based Authentication for WSNs

Zhang et al. [28] used two cluster heads to realize the system authentication work. They assumed that the cluster head (CH) had limited processing capacity and could not meet the requirements of data calculation. In a cluster, one CH was responsible for intercluster communication and the other CH was responsible for the collection and processing of data in its cluster. Dai et al. [29] also proposed a dual cluster head authentication scheme, whose main principle was similar to the system proposed by Zhang. The main CH and the sub-CH were selected in the larger clusters; the main CH was assisted by the sub-CH. Wang et al. [30] proposed a nonuniform clustering management scheme achieved by establishing clusters with different sizes, which was different from dual cluster head structure. However, it did not consider the fact that the influence of fixed factors on network varies with the number of rounds. Based on the dynamic search strategy, in literature [31], dynamic CH was introduced to collect the interference data of illegal nodes, but it could not realize adaptive switching data collection path. Yu et al. [32] proposed a DEER algorithm to find the optimal path between a CH and the coordinator, but it may lead to unbalanced load among the CHs.Rohbanina et al. [33] proposed a hierarchical WSN for key management, which first constructed the shortest path and uses the elliptic curve-based cryptography scheme for session key distribution. DENG et al. [34] made use of the network differentiation to improve system communication efficiency, which adopted the grouping encryption algorithm. By using the summary information comparison method and the singular point exclusion strategy, the system recoverability was enhanced. Klaoudatou et al. [35] thoroughly evaluated the cluster-based Group Key Agreement (GKA) protocols for WSNs. The authors examined many related literatures to study their performance and energy consumption. They thought that clustering is ideal for large-scale environments and time-critical applications. The use of cluster-based approaches optimizes network bandwidth and service discovery while addressing the needs for scalability at the same time.


## 2.1. Public Key Authentication

In recent years, many researchers have done a lot of work on the key authentication for WSN. There are three kinds of authentication methods, PKI-based encryption, identity-based encryption, and certificate-free encryption.


### 2.1.1. PKI-Based Encryption

In a typical PKI-based scheme, the public key certificate is signed by a certificate authority (CA) to achieve the binding between the user’s public key and its identity. The certificate-based key management scheme is the most common authentication scheme. However, the PKI-based key management scheme tends to consume too much storage, calculation, and communication resource, which is unaffordable for the energy-constrained sensor nodes in WSN [16, 17].


### 2.1.2. Identity-Based Encryption

In 1984, the identity-based encryption algorithm was first proposed by Shamir [18], which enabled any pair of users to communicate securely and verify each other’s signatures without exchanging private or public keys. In 2003, Chen studied the key management protocol in identity-based encryption scheme [19]. In order to simplify the management of the key, the user’s public key was used for directly calculating the user’s identity information, and the private key was credibly generated by PKG (Private Key Generator). Without the public key certificate, such scheme reduced the storage and computing cost for issuance, cancellation, and certification.To reduce the energy consumption of the identity-based authentication node, some identity-based key management protocols for WSN were proposed [20, 21]. The literature [11] pointed out that the identity-based encryption was the most suitable public key scheme for wireless sensor networks (WSN). Neal Koblitz [22] and Victor Miller [23] proposed elliptic curve cryptosystem. Then, the similar algorithm was proposed by Zhang et al. in [24], which presented that the security of ECC was based on the discrete logarithm problem. Compared with other public key systems, this scheme is a promising method with high security, low cost, and high efficiency. However, in most elliptic curves based key management schemes, grouping management mechanism was not introduced. With the increasing of nodes, more communication with BS is needed, which was not suitable for the nodes with limited energy in WSN.In the key-insulated cryptography proposed by Qin Zhiguang et al., the key was divided into two parts: one part was managed by the users and the other part was saved by a physical security helper [12]. When the key was needed, the two parts of the key were spliced into a complete key. But it failed to take advantage of the identity information from each effective node. Chen Yuan et al. [13] proposed an identity-based encryption scheme without bilinear pairings. Both algorithms used the idea of noncertificate; the private key was generated by the node and the Private Key Generator (PKG). Therefore, the two algorithms could not really solve the key escrow problem.Guo Jianghong et al. [16] proposed a new key agreement scheme for WSN. The node established the pairing key through the Diffie-Hellman protocol, and the required key parameters are obtained through broadcast. The scheme still has the advantages of the identity-based encrypted key agreement scheme, but the time and energy consumption for bilinear pairing operation is very high. Guo et al. [25] combined the identity-based RSA mechanism with the lightweight Certificate Authority (CA) to construct an identity-based mixed model, ECC-CA, for sensor network cryptography scheme. But the scheme has relatively huge cost of calculation and communication.


### 2.1.3. Certificate-Free Encryption

To resolve the certificate problem in the PKI-based scheme and the key escrow problem in the identity-based scheme, the certificate-free encryption method was proposed. In certificate-free encryption algorithm, a credible third-party Key Generation Center (KGC) was still employed to jointly generate the user’s private key. KGC did not directly hold the users’ private keys but only generated a partial private key. The users themselves generated the final private key instead. In such scheme, the public key information could not be directly obtained from the user identity information [26, 27]. At present, these provable security certificate-free construction methods are based on the Waters hash function, which leads to long system parameters and requires more pairing calculations. Thus, these methods are not suitable for WSN with limited storage capacity and calculation capability.


## 2.1.1. PKI-Based Encryption

In a typical PKI-based scheme, the public key certificate is signed by a certificate authority (CA) to achieve the binding between the user’s public key and its identity. The certificate-based key management scheme is the most common authentication scheme. However, the PKI-based key management scheme tends to consume too much storage, calculation, and communication resource, which is unaffordable for the energy-constrained sensor nodes in WSN [16, 17].


## 2.1.2. Identity-Based Encryption

In 1984, the identity-based encryption algorithm was first proposed by Shamir [18], which enabled any pair of users to communicate securely and verify each other’s signatures without exchanging private or public keys. In 2003, Chen studied the key management protocol in identity-based encryption scheme [19]. In order to simplify the management of the key, the user’s public key was used for directly calculating the user’s identity information, and the private key was credibly generated by PKG (Private Key Generator). Without the public key certificate, such scheme reduced the storage and computing cost for issuance, cancellation, and certification.To reduce the energy consumption of the identity-based authentication node, some identity-based key management protocols for WSN were proposed [20, 21]. The literature [11] pointed out that the identity-based encryption was the most suitable public key scheme for wireless sensor networks (WSN). Neal Koblitz [22] and Victor Miller [23] proposed elliptic curve cryptosystem. Then, the similar algorithm was proposed by Zhang et al. in [24], which presented that the security of ECC was based on the discrete logarithm problem. Compared with other public key systems, this scheme is a promising method with high security, low cost, and high efficiency. However, in most elliptic curves based key management schemes, grouping management mechanism was not introduced. With the increasing of nodes, more communication with BS is needed, which was not suitable for the nodes with limited energy in WSN.In the key-insulated cryptography proposed by Qin Zhiguang et al., the key was divided into two parts: one part was managed by the users and the other part was saved by a physical security helper [12]. When the key was needed, the two parts of the key were spliced into a complete key. But it failed to take advantage of the identity information from each effective node. Chen Yuan et al. [13] proposed an identity-based encryption scheme without bilinear pairings. Both algorithms used the idea of noncertificate; the private key was generated by the node and the Private Key Generator (PKG). Therefore, the two algorithms could not really solve the key escrow problem.Guo Jianghong et al. [16] proposed a new key agreement scheme for WSN. The node established the pairing key through the Diffie-Hellman protocol, and the required key parameters are obtained through broadcast. The scheme still has the advantages of the identity-based encrypted key agreement scheme, but the time and energy consumption for bilinear pairing operation is very high. Guo et al. [25] combined the identity-based RSA mechanism with the lightweight Certificate Authority (CA) to construct an identity-based mixed model, ECC-CA, for sensor network cryptography scheme. But the scheme has relatively huge cost of calculation and communication.


## 2.1.3. Certificate-Free Encryption

To resolve the certificate problem in the PKI-based scheme and the key escrow problem in the identity-based scheme, the certificate-free encryption method was proposed. In certificate-free encryption algorithm, a credible third-party Key Generation Center (KGC) was still employed to jointly generate the user’s private key. KGC did not directly hold the users’ private keys but only generated a partial private key. The users themselves generated the final private key instead. In such scheme, the public key information could not be directly obtained from the user identity information [26, 27]. At present, these provable security certificate-free construction methods are based on the Waters hash function, which leads to long system parameters and requires more pairing calculations. Thus, these methods are not suitable for WSN with limited storage capacity and calculation capability.


## 2.2. Cluster-Based Authentication for WSNs

Zhang et al. [28] used two cluster heads to realize the system authentication work. They assumed that the cluster head (CH) had limited processing capacity and could not meet the requirements of data calculation. In a cluster, one CH was responsible for intercluster communication and the other CH was responsible for the collection and processing of data in its cluster. Dai et al. [29] also proposed a dual cluster head authentication scheme, whose main principle was similar to the system proposed by Zhang. The main CH and the sub-CH were selected in the larger clusters; the main CH was assisted by the sub-CH. Wang et al. [30] proposed a nonuniform clustering management scheme achieved by establishing clusters with different sizes, which was different from dual cluster head structure. However, it did not consider the fact that the influence of fixed factors on network varies with the number of rounds. Based on the dynamic search strategy, in literature [31], dynamic CH was introduced to collect the interference data of illegal nodes, but it could not realize adaptive switching data collection path. Yu et al. [32] proposed a DEER algorithm to find the optimal path between a CH and the coordinator, but it may lead to unbalanced load among the CHs.Rohbanina et al. [33] proposed a hierarchical WSN for key management, which first constructed the shortest path and uses the elliptic curve-based cryptography scheme for session key distribution. DENG et al. [34] made use of the network differentiation to improve system communication efficiency, which adopted the grouping encryption algorithm. By using the summary information comparison method and the singular point exclusion strategy, the system recoverability was enhanced. Klaoudatou et al. [35] thoroughly evaluated the cluster-based Group Key Agreement (GKA) protocols for WSNs. The authors examined many related literatures to study their performance and energy consumption. They thought that clustering is ideal for large-scale environments and time-critical applications. The use of cluster-based approaches optimizes network bandwidth and service discovery while addressing the needs for scalability at the same time.


## 3. Hierarchical Matrix Decomposition-Based Signcryption (HMDS) Scheme

### 3.1. Overview of HMDS Scheme

In the WSN, cluster-based hierarchical architecture could decrease the communication overhead of data collection and aggregation. Moreover, it is good to extend the lifetime if nodes are assigned to different roles according to their resources. Therefore, we propose a Hierarchical Matrix Decomposition-based Signcryption (HMDS) scheme, which adopts the cluster-based hierarchical architecture illustrated as in Figure1. There are three layers, base station (BS), cluster head layer, and intracluster layer. Usually, the WSN consists of a few clusters and a BS. When a node communicates with other nodes in different cluster, the message must be forwarded by the corresponding CHs.Figure 1
Architecture of HMDS.In the HMDS scheme, the BS is used as KGC. There are three modules for performing the KGC functions, database module, encryption machine module, and key management system module. The BS assigns an identification number and generates the public key for each CH in cluster head layer. MatrixD is stored in the database on BS. Given a symmetric matrixD, it is Doolittle-decomposed into two triangular matricesL andR; thus, the ID of each node can be assigned quickly according to the polynomial function. Furthermore, the authentication and key updating of the node can be realized.The nodes with more storage and computing resource are assigned as CHs. Each CH is responsible for managing a number of ordinary sensor nodes and performing more complex operations. In the cluster head layer, each CH computes the public key for each sensor node in its cluster.Before presenting the detail of the HMDS scheme, it is necessary to introduce some deployed notations as described in Table1.Table 1
Deployed notations.
Notations Guide D (n×n) symmetric matrix L The lower triangular matrix of Doolittle-decomposed for matrix D R The upper triangular matrix of Doolittle-decomposed for matrix D S i / P i Secret key/ Public key of applicantIDi I d i Identification number of cluster head nodei G The base point on the elliptic curve U i The verification parameter of nodei H Hash function


### 3.2. Signcryption for Intercluster Communication

#### 3.2.1. Initialization

The BS, as the KGC, is trustable to generate key for CHs. Before generating keys, the steps of initialization are described as follows.(A) BS selects a (n×n) symmetric matrixD and saves it. Each order principal minor determinant ofD is not equal to 0; the matrixD is represented as follows: (1)D=d11⋱dijdji⋱dn·nwheredij=dji.(B) As the KGC, the BS performs Doolittle decomposition for the matrixD as follows:(2)D=L·R=1l2·11⋯⋯1ln·1ln·2ln·n-11·r1·1r1·2⋯r1·nr2·2⋯r2·n⋱⋮rn·n_=L·R0·R1=1l2·11⋯⋯1ln·1ln·2ln·n-11·r1·1r2·2⋱rn·n·1r1·2r1·1⋯r1·nr1·11⋯r2·nr2·2⋱⋮1_(C) The KGC saves all the information of the matrix R, and according to the diagonal elements of the matrixR, the following one-way polynomial function is used to generate the identification number Idi for each CH nodei.(3)Idi=fx=r11·xn+r22·xn-1+···+rnn·x1mod⁡p,wherex=rii,i∈1,n.(D) KGC broadcasts the matrixL to all the CHs; that is to say, each CH knows all the information of the matrixL.(E) According to the CH numberIdi and matrixL, each CH node only stores the corresponding row elements in matrixL and ignores other elements. For example, if Idi=4, the CH only stores the 4th row elements of theL matrix as follows:(4)1l2·11⋯⋯1ln·1ln·2ln·n-11⇒i=4Id4l4·1_l4·2_⋯_1_.


#### 3.2.2. User Key Generation (Extract)

After initialization, the steps of key generation are described as follows.(A) The applicant nodei,named as CHi, selects a pointP(xi,yi)on the elliptic curve as its own private key, that is, Si=(xi,yi), and then randomly selects a number zi∈Z and calculates the verification shares Vi=ziSi=(Vxi,Vyi).(B)CHi saves the random number zi, which will be used in the signcryption process; then it combines the self verification shares Vi with the identity information Idi and sends it to the KGC. It should be noted that random number zi will not be sent to KGC, which prevents KGC from leaking secrets, and zi is only used for the intercluster communication.(C) After receiving the information, the KGC selects a random numberj. According to the value ofj together with CHi’s numberi, the KGC chooses the element rji in the matrix R and obtains the verification parameter VKgc=rji/rjj of the KGC.(D) The KGC calculates the public keyPi=G·Vi for CHi based on the received verification shares Vi(Vxi,Vyi).(E) The KGC sends the random numberj, the verification parameter VKGC, and the user public key Pi to the applicant CHi.(F) After receiving the information returned by the KGC, according to the received random numberj, CHi selects the jth element lij from the stored ith row vector in matrixL and verifies whether lij= VKGC. If the verification passes, CHi accepts the public key Pi and saves its own private key Si. Then, the KGC announces the user’s public key Pi to other CHs. Otherwise, it returns an error and the application fails (the correctness will be proven in Section 4.1).Thus, the configuration of the public and private keys for each CH has been completed.


#### 3.2.3. Signcryption

WhenCHi needs to send a message to CHj, the following steps will be performed.(A)CHi first takes the random number zi which is saved at the public key application stage; together with the base pointG on the elliptic curve, CHi calculates Ki=zi·G=(kxGi,kyGi). Then, CHi calculates the verification parameter Ui=kxGi·Pj=(uxij,uyij) by kxGi and the public key Pj of CHj. After that, CHi encrypts the messageMsgby using uxijand obtains C=Euxij(Msg).(B)CHi calculates the parameters Mi=H1kxGi∣C,Ni=H0kxGi·MiG,(5)O′=Si-kxGi·Mimod⁡q,O=M+O′(C)CHi generates the ciphertext σi=(K(kxGi,kyGi)C=Euxij(Msg)NiOzi) according to the stored random number zi and all the above parameters.(D)CHi sends the ciphertext to CHj.


#### 3.2.4. Unsigncryption

AfterCHj receives the ciphertext, the following steps will be performed to decrypt the received message.(A)CHj extracts the first half kxGi of Ki and calculates the verification parameters Uj=kxGi·Pj=(uxj,uyj) with its own public key.(B)CHj calculates (6)Mj=H1kxGiCO′′=O-Mj.(C)CHj decrypts the encrypted message by using uxj to obtain Msg=Duxj(C).(D)CHj calculates Pj′=Ni+O′′·G and verifies if zi·Pj= Pi; if they are equal, the common communication key of CHi and CHj is uxij, and uyij is stored as the intercluster shared key after receiving the textMsg; otherwise, the verification fails.Thus, communication between the clusters finished.


### 3.3. Signcryption for Intracluster Communication

#### 3.3.1. Key generation and Unsigncryption

In each cluster,CHi and CHj obtained the shared key uyij between clusteri and clusterj through the above process. The key generation, signcryption, and unsigncryption for the ordinary nodes in a cluster are similar to those for cluster head, as described in Section 3.2, so it is not necessary to repeat them here.


#### 3.3.2. Intracluster Key Updating

In order to ensure security, the BS will periodically inform each CH to perform the intracluster key updating operation. For instance, in the cluster whose cluster head isCHi, the updating steps are as follows:(A)CHi generates a new cluster shared key uyij′.(B)CHi uses its own private key Si for identity signature, and the ordinary nodes authenticate it.(C) The signature and the new cluster shared keyuyij′ together with the original shared key are encrypted to obtain C′=Euxij(Sn(Idi)SiIdiClock(uxij)′) and the information is broadcasted in this cluster.(D) After the ordinary nodes receive the broadcasted information, they decrypt the information by original shared keyuyij and verify it by the public key of the cluster head; if the verification passes, the new cluster shared key (uyij)′ is saved to replace the old one and answersCH; otherwise, discard the data package.


## 3.1. Overview of HMDS Scheme

In the WSN, cluster-based hierarchical architecture could decrease the communication overhead of data collection and aggregation. Moreover, it is good to extend the lifetime if nodes are assigned to different roles according to their resources. Therefore, we propose a Hierarchical Matrix Decomposition-based Signcryption (HMDS) scheme, which adopts the cluster-based hierarchical architecture illustrated as in Figure1. There are three layers, base station (BS), cluster head layer, and intracluster layer. Usually, the WSN consists of a few clusters and a BS. When a node communicates with other nodes in different cluster, the message must be forwarded by the corresponding CHs.Figure 1
Architecture of HMDS.In the HMDS scheme, the BS is used as KGC. There are three modules for performing the KGC functions, database module, encryption machine module, and key management system module. The BS assigns an identification number and generates the public key for each CH in cluster head layer. MatrixD is stored in the database on BS. Given a symmetric matrixD, it is Doolittle-decomposed into two triangular matricesL andR; thus, the ID of each node can be assigned quickly according to the polynomial function. Furthermore, the authentication and key updating of the node can be realized.The nodes with more storage and computing resource are assigned as CHs. Each CH is responsible for managing a number of ordinary sensor nodes and performing more complex operations. In the cluster head layer, each CH computes the public key for each sensor node in its cluster.Before presenting the detail of the HMDS scheme, it is necessary to introduce some deployed notations as described in Table1.Table 1
Deployed notations.
Notations Guide D (n×n) symmetric matrix L The lower triangular matrix of Doolittle-decomposed for matrix D R The upper triangular matrix of Doolittle-decomposed for matrix D S i / P i Secret key/ Public key of applicantIDi I d i Identification number of cluster head nodei G The base point on the elliptic curve U i The verification parameter of nodei H Hash function


## 3.2. Signcryption for Intercluster Communication

### 3.2.1. Initialization

The BS, as the KGC, is trustable to generate key for CHs. Before generating keys, the steps of initialization are described as follows.(A) BS selects a (n×n) symmetric matrixD and saves it. Each order principal minor determinant ofD is not equal to 0; the matrixD is represented as follows: (1)D=d11⋱dijdji⋱dn·nwheredij=dji.(B) As the KGC, the BS performs Doolittle decomposition for the matrixD as follows:(2)D=L·R=1l2·11⋯⋯1ln·1ln·2ln·n-11·r1·1r1·2⋯r1·nr2·2⋯r2·n⋱⋮rn·n_=L·R0·R1=1l2·11⋯⋯1ln·1ln·2ln·n-11·r1·1r2·2⋱rn·n·1r1·2r1·1⋯r1·nr1·11⋯r2·nr2·2⋱⋮1_(C) The KGC saves all the information of the matrix R, and according to the diagonal elements of the matrixR, the following one-way polynomial function is used to generate the identification number Idi for each CH nodei.(3)Idi=fx=r11·xn+r22·xn-1+···+rnn·x1mod⁡p,wherex=rii,i∈1,n.(D) KGC broadcasts the matrixL to all the CHs; that is to say, each CH knows all the information of the matrixL.(E) According to the CH numberIdi and matrixL, each CH node only stores the corresponding row elements in matrixL and ignores other elements. For example, if Idi=4, the CH only stores the 4th row elements of theL matrix as follows:(4)1l2·11⋯⋯1ln·1ln·2ln·n-11⇒i=4Id4l4·1_l4·2_⋯_1_.


### 3.2.2. User Key Generation (Extract)

After initialization, the steps of key generation are described as follows.(A) The applicant nodei,named as CHi, selects a pointP(xi,yi)on the elliptic curve as its own private key, that is, Si=(xi,yi), and then randomly selects a number zi∈Z and calculates the verification shares Vi=ziSi=(Vxi,Vyi).(B)CHi saves the random number zi, which will be used in the signcryption process; then it combines the self verification shares Vi with the identity information Idi and sends it to the KGC. It should be noted that random number zi will not be sent to KGC, which prevents KGC from leaking secrets, and zi is only used for the intercluster communication.(C) After receiving the information, the KGC selects a random numberj. According to the value ofj together with CHi’s numberi, the KGC chooses the element rji in the matrix R and obtains the verification parameter VKgc=rji/rjj of the KGC.(D) The KGC calculates the public keyPi=G·Vi for CHi based on the received verification shares Vi(Vxi,Vyi).(E) The KGC sends the random numberj, the verification parameter VKGC, and the user public key Pi to the applicant CHi.(F) After receiving the information returned by the KGC, according to the received random numberj, CHi selects the jth element lij from the stored ith row vector in matrixL and verifies whether lij= VKGC. If the verification passes, CHi accepts the public key Pi and saves its own private key Si. Then, the KGC announces the user’s public key Pi to other CHs. Otherwise, it returns an error and the application fails (the correctness will be proven in Section 4.1).Thus, the configuration of the public and private keys for each CH has been completed.


### 3.2.3. Signcryption

WhenCHi needs to send a message to CHj, the following steps will be performed.(A)CHi first takes the random number zi which is saved at the public key application stage; together with the base pointG on the elliptic curve, CHi calculates Ki=zi·G=(kxGi,kyGi). Then, CHi calculates the verification parameter Ui=kxGi·Pj=(uxij,uyij) by kxGi and the public key Pj of CHj. After that, CHi encrypts the messageMsgby using uxijand obtains C=Euxij(Msg).(B)CHi calculates the parameters Mi=H1kxGi∣C,Ni=H0kxGi·MiG,(5)O′=Si-kxGi·Mimod⁡q,O=M+O′(C)CHi generates the ciphertext σi=(K(kxGi,kyGi)C=Euxij(Msg)NiOzi) according to the stored random number zi and all the above parameters.(D)CHi sends the ciphertext to CHj.


### 3.2.4. Unsigncryption

AfterCHj receives the ciphertext, the following steps will be performed to decrypt the received message.(A)CHj extracts the first half kxGi of Ki and calculates the verification parameters Uj=kxGi·Pj=(uxj,uyj) with its own public key.(B)CHj calculates (6)Mj=H1kxGiCO′′=O-Mj.(C)CHj decrypts the encrypted message by using uxj to obtain Msg=Duxj(C).(D)CHj calculates Pj′=Ni+O′′·G and verifies if zi·Pj= Pi; if they are equal, the common communication key of CHi and CHj is uxij, and uyij is stored as the intercluster shared key after receiving the textMsg; otherwise, the verification fails.Thus, communication between the clusters finished.


## 3.2.1. Initialization

The BS, as the KGC, is trustable to generate key for CHs. Before generating keys, the steps of initialization are described as follows.(A) BS selects a (n×n) symmetric matrixD and saves it. Each order principal minor determinant ofD is not equal to 0; the matrixD is represented as follows: (1)D=d11⋱dijdji⋱dn·nwheredij=dji.(B) As the KGC, the BS performs Doolittle decomposition for the matrixD as follows:(2)D=L·R=1l2·11⋯⋯1ln·1ln·2ln·n-11·r1·1r1·2⋯r1·nr2·2⋯r2·n⋱⋮rn·n_=L·R0·R1=1l2·11⋯⋯1ln·1ln·2ln·n-11·r1·1r2·2⋱rn·n·1r1·2r1·1⋯r1·nr1·11⋯r2·nr2·2⋱⋮1_(C) The KGC saves all the information of the matrix R, and according to the diagonal elements of the matrixR, the following one-way polynomial function is used to generate the identification number Idi for each CH nodei.(3)Idi=fx=r11·xn+r22·xn-1+···+rnn·x1mod⁡p,wherex=rii,i∈1,n.(D) KGC broadcasts the matrixL to all the CHs; that is to say, each CH knows all the information of the matrixL.(E) According to the CH numberIdi and matrixL, each CH node only stores the corresponding row elements in matrixL and ignores other elements. For example, if Idi=4, the CH only stores the 4th row elements of theL matrix as follows:(4)1l2·11⋯⋯1ln·1ln·2ln·n-11⇒i=4Id4l4·1_l4·2_⋯_1_.


## 3.2.2. User Key Generation (Extract)

After initialization, the steps of key generation are described as follows.(A) The applicant nodei,named as CHi, selects a pointP(xi,yi)on the elliptic curve as its own private key, that is, Si=(xi,yi), and then randomly selects a number zi∈Z and calculates the verification shares Vi=ziSi=(Vxi,Vyi).(B)CHi saves the random number zi, which will be used in the signcryption process; then it combines the self verification shares Vi with the identity information Idi and sends it to the KGC. It should be noted that random number zi will not be sent to KGC, which prevents KGC from leaking secrets, and zi is only used for the intercluster communication.(C) After receiving the information, the KGC selects a random numberj. According to the value ofj together with CHi’s numberi, the KGC chooses the element rji in the matrix R and obtains the verification parameter VKgc=rji/rjj of the KGC.(D) The KGC calculates the public keyPi=G·Vi for CHi based on the received verification shares Vi(Vxi,Vyi).(E) The KGC sends the random numberj, the verification parameter VKGC, and the user public key Pi to the applicant CHi.(F) After receiving the information returned by the KGC, according to the received random numberj, CHi selects the jth element lij from the stored ith row vector in matrixL and verifies whether lij= VKGC. If the verification passes, CHi accepts the public key Pi and saves its own private key Si. Then, the KGC announces the user’s public key Pi to other CHs. Otherwise, it returns an error and the application fails (the correctness will be proven in Section 4.1).Thus, the configuration of the public and private keys for each CH has been completed.


## 3.2.3. Signcryption

WhenCHi needs to send a message to CHj, the following steps will be performed.(A)CHi first takes the random number zi which is saved at the public key application stage; together with the base pointG on the elliptic curve, CHi calculates Ki=zi·G=(kxGi,kyGi). Then, CHi calculates the verification parameter Ui=kxGi·Pj=(uxij,uyij) by kxGi and the public key Pj of CHj. After that, CHi encrypts the messageMsgby using uxijand obtains C=Euxij(Msg).(B)CHi calculates the parameters Mi=H1kxGi∣C,Ni=H0kxGi·MiG,(5)O′=Si-kxGi·Mimod⁡q,O=M+O′(C)CHi generates the ciphertext σi=(K(kxGi,kyGi)C=Euxij(Msg)NiOzi) according to the stored random number zi and all the above parameters.(D)CHi sends the ciphertext to CHj.


## 3.2.4. Unsigncryption

AfterCHj receives the ciphertext, the following steps will be performed to decrypt the received message.(A)CHj extracts the first half kxGi of Ki and calculates the verification parameters Uj=kxGi·Pj=(uxj,uyj) with its own public key.(B)CHj calculates (6)Mj=H1kxGiCO′′=O-Mj.(C)CHj decrypts the encrypted message by using uxj to obtain Msg=Duxj(C).(D)CHj calculates Pj′=Ni+O′′·G and verifies if zi·Pj= Pi; if they are equal, the common communication key of CHi and CHj is uxij, and uyij is stored as the intercluster shared key after receiving the textMsg; otherwise, the verification fails.Thus, communication between the clusters finished.


## 3.3. Signcryption for Intracluster Communication

### 3.3.1. Key generation and Unsigncryption

In each cluster,CHi and CHj obtained the shared key uyij between clusteri and clusterj through the above process. The key generation, signcryption, and unsigncryption for the ordinary nodes in a cluster are similar to those for cluster head, as described in Section 3.2, so it is not necessary to repeat them here.


### 3.3.2. Intracluster Key Updating

In order to ensure security, the BS will periodically inform each CH to perform the intracluster key updating operation. For instance, in the cluster whose cluster head isCHi, the updating steps are as follows:(A)CHi generates a new cluster shared key uyij′.(B)CHi uses its own private key Si for identity signature, and the ordinary nodes authenticate it.(C) The signature and the new cluster shared keyuyij′ together with the original shared key are encrypted to obtain C′=Euxij(Sn(Idi)SiIdiClock(uxij)′) and the information is broadcasted in this cluster.(D) After the ordinary nodes receive the broadcasted information, they decrypt the information by original shared keyuyij and verify it by the public key of the cluster head; if the verification passes, the new cluster shared key (uyij)′ is saved to replace the old one and answersCH; otherwise, discard the data package.


## 3.3.1. Key generation and Unsigncryption

In each cluster,CHi and CHj obtained the shared key uyij between clusteri and clusterj through the above process. The key generation, signcryption, and unsigncryption for the ordinary nodes in a cluster are similar to those for cluster head, as described in Section 3.2, so it is not necessary to repeat them here.


## 3.3.2. Intracluster Key Updating

In order to ensure security, the BS will periodically inform each CH to perform the intracluster key updating operation. For instance, in the cluster whose cluster head isCHi, the updating steps are as follows:(A)CHi generates a new cluster shared key uyij′.(B)CHi uses its own private key Si for identity signature, and the ordinary nodes authenticate it.(C) The signature and the new cluster shared keyuyij′ together with the original shared key are encrypted to obtain C′=Euxij(Sn(Idi)SiIdiClock(uxij)′) and the information is broadcasted in this cluster.(D) After the ordinary nodes receive the broadcasted information, they decrypt the information by original shared keyuyij and verify it by the public key of the cluster head; if the verification passes, the new cluster shared key (uyij)′ is saved to replace the old one and answersCH; otherwise, discard the data package.


## 4. Correctness and Security Analysis

### 4.1. Correctness Analysis

Theorem 1.
In the process of generating public key (described in Section3.2.2) for CH, if lij=VKGC, the public key generation satisfies the correctness requirements.Proof.
Firstly, according to the Doolittle decomposition rules for the symmetric matrix D, combined with the knowledge of Order Principal Minor Determinant, we have(7)D=L·R=1l2·11⋯⋯1ln·1ln·2ln·n-11·r1·1r1·2⋯r1·nr2·2⋯r2·n⋱⋮rn·nbecauseD=L·R=L·R,D≠0,L=1thatisD=1·R=∏i=1nrii≠0⇒rii≠0i∈1,2,···,n_
Furthermore, the matrix R can be decomposed as follows:(8)R=r1·1r1·2⋯r1·nr2·2⋯r2·n⋱⋮rn·n=R0·R1=r1·1r2·2⋱rn·n·1r1·2r1·1⋯r1·nr1·11⋯r2·nr2·2⋱⋮1
Therefore, we have(9)D=L·R=L·R0·R1_becauseD=DT,D=L·R0·R1soD=DT=L·R0·R1T=R0·R1T·LT=R1T·R0T·LT=R1T·R0·LT=L·R0·R1
Based on uniqueness of the Doolittle decomposition, we haveL=R1T; that is,(10)L=1l2·11⋯⋯1ln·1ln·2ln·n-11=RT=1r1·2r1·1⋯r1·nr1·11⋯r2·nr2·2⋱⋮1TVKgc=rjirjj⇓lij=VKgc_
Therefore, the KGC public key generation process satisfies the correctness requirements.Theorem 2.
The recalculation process of the verification parameterPi satisfies the correctness requirements.Proof.
(11) s i n c e  O ′ = S i - H 0 k x G i · M i mod ⁡ q , N i = H 0 k x G i · M i G , O ′ ′ = O - M j t h e n  P j ′ = N i + O ′ ′ · G = H 0 k x G i · M i G + O - M j G = H 0 k x G i G + M i · G + O · G - M i · G b e c a u s e  P i = V i · G , V i  = z i · S i s o  P i = z i · S i · G = z i S i · G = z i · P j ′


### 4.2. Security Analysis

In the HMDS algorithm, the private key of an applicant is managed by the applicant itself, and the KGC only generates the public key for the applicant. The authentication parameters transferred during the communication process are also based on the public keys of the applicant. Therefore, even if a node is compromised, it will not affect the security of other nodes.In the HMDS algorithm, one characteristic is that the monomial function is adopted to generate the identification number for an applicant, which ensures the partial public secret not to leak. From the polynomial,Idi=f(x)=r11·x(n)+r22·x(n-1)+···+rnn·x(1)mod⁡(p); according to Honer’s Rule, we can continuously extract xi as a common factor from the residual polynomial recursively to compute Yi, as illustrated in Table 2. It can be observed that if x, rii, and p are known, it is very easy to compute the value of Yi. Conversely, if Yi and p are known and we try to get the value of xi, it will cost at least n2(log2 P)2 times of multiplication. When n and p are very large, it is very difficult to obtain the value of xi,. Therefore, it is ensured that the identification number of each node is quickly generated, but it is difficult to crack. Another characteristic of the HMDS algorithm is that the information kept by each applicant is very simple, which saves the cost of calculation and storage resource.Table 2
Function y=f(x).
Factor r11 r22 r33 ... r n - 1 n - 1 r n n Y/xi Y1=r11 Y2=xi⋅Y1+r22 Y3=xi⋅Y2+r33 ... Y n - 1=xi⋅Yn-2+rn-1n-1 Y n=xi⋅Yn-1+rnn


## 4.1. Correctness Analysis

Theorem 1.
In the process of generating public key (described in Section3.2.2) for CH, if lij=VKGC, the public key generation satisfies the correctness requirements.Proof.
Firstly, according to the Doolittle decomposition rules for the symmetric matrix D, combined with the knowledge of Order Principal Minor Determinant, we have(7)D=L·R=1l2·11⋯⋯1ln·1ln·2ln·n-11·r1·1r1·2⋯r1·nr2·2⋯r2·n⋱⋮rn·nbecauseD=L·R=L·R,D≠0,L=1thatisD=1·R=∏i=1nrii≠0⇒rii≠0i∈1,2,···,n_
Furthermore, the matrix R can be decomposed as follows:(8)R=r1·1r1·2⋯r1·nr2·2⋯r2·n⋱⋮rn·n=R0·R1=r1·1r2·2⋱rn·n·1r1·2r1·1⋯r1·nr1·11⋯r2·nr2·2⋱⋮1
Therefore, we have(9)D=L·R=L·R0·R1_becauseD=DT,D=L·R0·R1soD=DT=L·R0·R1T=R0·R1T·LT=R1T·R0T·LT=R1T·R0·LT=L·R0·R1
Based on uniqueness of the Doolittle decomposition, we haveL=R1T; that is,(10)L=1l2·11⋯⋯1ln·1ln·2ln·n-11=RT=1r1·2r1·1⋯r1·nr1·11⋯r2·nr2·2⋱⋮1TVKgc=rjirjj⇓lij=VKgc_
Therefore, the KGC public key generation process satisfies the correctness requirements.Theorem 2.
The recalculation process of the verification parameterPi satisfies the correctness requirements.Proof.
(11) s i n c e  O ′ = S i - H 0 k x G i · M i mod ⁡ q , N i = H 0 k x G i · M i G , O ′ ′ = O - M j t h e n  P j ′ = N i + O ′ ′ · G = H 0 k x G i · M i G + O - M j G = H 0 k x G i G + M i · G + O · G - M i · G b e c a u s e  P i = V i · G , V i  = z i · S i s o  P i = z i · S i · G = z i S i · G = z i · P j ′


## 4.2. Security Analysis

In the HMDS algorithm, the private key of an applicant is managed by the applicant itself, and the KGC only generates the public key for the applicant. The authentication parameters transferred during the communication process are also based on the public keys of the applicant. Therefore, even if a node is compromised, it will not affect the security of other nodes.In the HMDS algorithm, one characteristic is that the monomial function is adopted to generate the identification number for an applicant, which ensures the partial public secret not to leak. From the polynomial,Idi=f(x)=r11·x(n)+r22·x(n-1)+···+rnn·x(1)mod⁡(p); according to Honer’s Rule, we can continuously extract xi as a common factor from the residual polynomial recursively to compute Yi, as illustrated in Table 2. It can be observed that if x, rii, and p are known, it is very easy to compute the value of Yi. Conversely, if Yi and p are known and we try to get the value of xi, it will cost at least n2(log2 P)2 times of multiplication. When n and p are very large, it is very difficult to obtain the value of xi,. Therefore, it is ensured that the identification number of each node is quickly generated, but it is difficult to crack. Another characteristic of the HMDS algorithm is that the information kept by each applicant is very simple, which saves the cost of calculation and storage resource.Table 2
Function y=f(x).
Factor r11 r22 r33 ... r n - 1 n - 1 r n n Y/xi Y1=r11 Y2=xi⋅Y1+r22 Y3=xi⋅Y2+r33 ... Y n - 1=xi⋅Yn-2+rn-1n-1 Y n=xi⋅Yn-1+rnn


## 5. Performance Evaluation

### 5.1. Computation Complexity Analysis

We compare the HMDS algorithm with the HIS algorithm; the main operations and complexity of the two algorithms are shown in Table3, which include four steps, system initialization, user key generation (extraction), signcryption, and unsigncryption.Table 3
Complexity of calculation.
Process HMDS HIS Operation cost of calculation Operation cost of calculation Initialization ( A )   S e l e c t  D; (B)Doolittledecomposition: (C)rii→fxIdi; (D)MatrixL→Idi; (E)Idi←SavedRowi(L) ( A )   O 1; (B)nn+1/2 (C)On; (D)On; (E)O(1) ( A )   S e l e c t  q , G q , E G; (B)SelectSymmatrixD; (C)GenetateH0,H1; (D)VandermondeMatrisID; (E)Generatekey; (F)Broadcast; ( A )   O 1; (B)O1; (C)O1; (D)O(n∗n); (E)O1; (F)O(n);  Extraction ( A )   S e l e c t  P i ; G e n e r a t e  V i; (B)Idi→Vi‖IdiKGC; (C)CalculateVKgc; (D)CalculatePi; (E)KGC→jVkgcPiIdi; (F)lij?=VKgc ( A )   O 1; (B)O1; (C)O1; (D)O1; (E)O1; (F)O(n); ( A )   S e l e c t  P i ; G e n e r a t e  V i; (B)Idi→ViIdiKGC; (C)D→y=fxmod(p)D′; (D)CaculateD′∗ID: (E)KGC→KijB1PiIdi; (F)Caculate(B∗ID): ( A )   O 1; (B)O1; (C)O(n∗n); (D)O(n∗n); (E)On; (F)O(n∗n);  Signcryption A   G e n e r a t e   K i , U i , C ; ( B ) M i = H 1 ( k x G i C ) N i = H 0 ( k x G i ⋅ M i ) G O ′ = S i - H 0 ( k x G i ⋅ M i )  m o d  q O = M + O ′ ( C )   I d i → σ i = ( K ( k x G i , k y G i ) C I d j ; ( A )   O 1; (B)O1; (C)O(1); ( A )   I D i : G e n e r a t e  K , U , C = E u m; (B)CalculateM,N; (C)CalculateO′,O=M+O′; (D)Idi→σ=(K=(k1,k2),C,N,O,z)Idj; ( A )   O 1; (B)O1; (C)O1; (D)O(1);  Unsigncryption ( A )   C a l c u l a t e  U j; (B)Mj=H1(kxGiC)O′′=O-Mj (C)Msg=DuxjC (D)Pj′=Ni+O′′⋅Gzi⋅Pj′?≡Pi ( A )   O 1; (B)O1; (C)O1; (D)O(1); ( A )   C a l c u l a t e  U ′ = k 1 P j = u , v; (B)M=H1(k1‖C),O′O-M; (C)m=DuC; (D)Pj′=Ni+O′⋅Gzi⋅P′?≡Pi ( A )   O 1; (B)O1; (C)O1; (D)O(1);  Total O(HMDS)=n∗n O(HIS)=6n∗n


### 5.2. Simulation Experiments

We set up six classical simulation configurations for HMDS and HIS scheme to represent different scenarios, denoted as S1~S6. To evaluate the efficiency of the HMDS scheme, we take the time cost as the metric to compare the HMDS scheme with the HIS scheme. The experiment parameters setting of the 6 scenarios is as shown in Table4, whereNum_CH is the number of clusters andn is the number of nodes.Table 4
Experimental setting.
OS Cpu HZ RAM Developing environment Library files Initial energy of ch (Joule) Energy range Number of cluster layers  Win10 home i5,x64 1.9Ghz 8G Visual studio 2010 <time.h>clock() 20 1.5-3J(random) 2  S1:n=25,Num_CH=2; S2:n=60,Num_CH=3; S3:n=100,Num_CH=4;S4:n=300,Num_CH=10; S5:n=600,Num_CH=20; S6:n=1000,Num_CH=35;Since the key steps of the HMDS scheme are setup (initialization) stage and key generation (extract) stage, the efficiency of the HMDS scheme depends on the two stages. Therefore, besides evaluating the overall efficiency of the HMDS scheme, we specially evaluate the efficiency of the two stages, respectively.


#### 5.2.1. Efficiency of Initialization and Extract Stage

As shown in Figure2, it can be observed that the time consumption of the two algorithms in the three scenarios, S1, S2, and S3, is all within 100ms and the HMDS algorithm has a slight advantage over the HIS algorithm. It is because the number of the nodes is small. With the number of nodes increasing from 100 (in S3) to 1000 (in S6), the time consumption of the two algorithms also has a large increment, and the HMDS algorithm has an obvious advantage over the HIS algorithm. Especially in the scenario S6, the HIS algorithm takes about 850ms, while the HMDS algorithm only takes 300ms, which saves about two-thirds of the time. In general, for the HIS algorithm, the time consumption of the two stages increases steeply when the network sizen increases quickly. In comparison, the HMDS algorithm is relatively stable in time consuming when the network sizen is large. Therefore, the HMDS algorithm is more applicable to the WSN than the HIS algorithm. Especially when the network sizen is very large, the HMDS algorithm has more obvious advantages.Figure 2
Time consumption of the two stages.


#### 5.2.2. Overall Efficiency

We randomly take 20 pairs of nodes to evaluate the overall efficiency; that is to say, we measure the time consumption of the four stages, from initialization to the end of unsigncryption. As shown in Figure3, the overall time consumption for both algorithms increases with the number of nodes increasing, but the HMDS algorithm still takes less time than the HIS algorithm. This trend becomes more and more obvious with the increasing of the network size and is consistent with the results of the above two-stage experiments.Figure 3
Overall time consumption.Therefore, the HMDS algorithm outperforms the HIS algorithm. Furthermore, the HMDS algorithm does not cause rapid increase of time consumption when the network scale grows. So the HMDS algorithm is more suitable for larger-scale WSN.


## 5.1. Computation Complexity Analysis

We compare the HMDS algorithm with the HIS algorithm; the main operations and complexity of the two algorithms are shown in Table3, which include four steps, system initialization, user key generation (extraction), signcryption, and unsigncryption.Table 3
Complexity of calculation.
Process HMDS HIS Operation cost of calculation Operation cost of calculation Initialization ( A )   S e l e c t  D; (B)Doolittledecomposition: (C)rii→fxIdi; (D)MatrixL→Idi; (E)Idi←SavedRowi(L) ( A )   O 1; (B)nn+1/2 (C)On; (D)On; (E)O(1) ( A )   S e l e c t  q , G q , E G; (B)SelectSymmatrixD; (C)GenetateH0,H1; (D)VandermondeMatrisID; (E)Generatekey; (F)Broadcast; ( A )   O 1; (B)O1; (C)O1; (D)O(n∗n); (E)O1; (F)O(n);  Extraction ( A )   S e l e c t  P i ; G e n e r a t e  V i; (B)Idi→Vi‖IdiKGC; (C)CalculateVKgc; (D)CalculatePi; (E)KGC→jVkgcPiIdi; (F)lij?=VKgc ( A )   O 1; (B)O1; (C)O1; (D)O1; (E)O1; (F)O(n); ( A )   S e l e c t  P i ; G e n e r a t e  V i; (B)Idi→ViIdiKGC; (C)D→y=fxmod(p)D′; (D)CaculateD′∗ID: (E)KGC→KijB1PiIdi; (F)Caculate(B∗ID): ( A )   O 1; (B)O1; (C)O(n∗n); (D)O(n∗n); (E)On; (F)O(n∗n);  Signcryption A   G e n e r a t e   K i , U i , C ; ( B ) M i = H 1 ( k x G i C ) N i = H 0 ( k x G i ⋅ M i ) G O ′ = S i - H 0 ( k x G i ⋅ M i )  m o d  q O = M + O ′ ( C )   I d i → σ i = ( K ( k x G i , k y G i ) C I d j ; ( A )   O 1; (B)O1; (C)O(1); ( A )   I D i : G e n e r a t e  K , U , C = E u m; (B)CalculateM,N; (C)CalculateO′,O=M+O′; (D)Idi→σ=(K=(k1,k2),C,N,O,z)Idj; ( A )   O 1; (B)O1; (C)O1; (D)O(1);  Unsigncryption ( A )   C a l c u l a t e  U j; (B)Mj=H1(kxGiC)O′′=O-Mj (C)Msg=DuxjC (D)Pj′=Ni+O′′⋅Gzi⋅Pj′?≡Pi ( A )   O 1; (B)O1; (C)O1; (D)O(1); ( A )   C a l c u l a t e  U ′ = k 1 P j = u , v; (B)M=H1(k1‖C),O′O-M; (C)m=DuC; (D)Pj′=Ni+O′⋅Gzi⋅P′?≡Pi ( A )   O 1; (B)O1; (C)O1; (D)O(1);  Total O(HMDS)=n∗n O(HIS)=6n∗n


## 5.2. Simulation Experiments

We set up six classical simulation configurations for HMDS and HIS scheme to represent different scenarios, denoted as S1~S6. To evaluate the efficiency of the HMDS scheme, we take the time cost as the metric to compare the HMDS scheme with the HIS scheme. The experiment parameters setting of the 6 scenarios is as shown in Table4, whereNum_CH is the number of clusters andn is the number of nodes.Table 4
Experimental setting.
OS Cpu HZ RAM Developing environment Library files Initial energy of ch (Joule) Energy range Number of cluster layers  Win10 home i5,x64 1.9Ghz 8G Visual studio 2010 <time.h>clock() 20 1.5-3J(random) 2  S1:n=25,Num_CH=2; S2:n=60,Num_CH=3; S3:n=100,Num_CH=4;S4:n=300,Num_CH=10; S5:n=600,Num_CH=20; S6:n=1000,Num_CH=35;Since the key steps of the HMDS scheme are setup (initialization) stage and key generation (extract) stage, the efficiency of the HMDS scheme depends on the two stages. Therefore, besides evaluating the overall efficiency of the HMDS scheme, we specially evaluate the efficiency of the two stages, respectively.


### 5.2.1. Efficiency of Initialization and Extract Stage

As shown in Figure2, it can be observed that the time consumption of the two algorithms in the three scenarios, S1, S2, and S3, is all within 100ms and the HMDS algorithm has a slight advantage over the HIS algorithm. It is because the number of the nodes is small. With the number of nodes increasing from 100 (in S3) to 1000 (in S6), the time consumption of the two algorithms also has a large increment, and the HMDS algorithm has an obvious advantage over the HIS algorithm. Especially in the scenario S6, the HIS algorithm takes about 850ms, while the HMDS algorithm only takes 300ms, which saves about two-thirds of the time. In general, for the HIS algorithm, the time consumption of the two stages increases steeply when the network sizen increases quickly. In comparison, the HMDS algorithm is relatively stable in time consuming when the network sizen is large. Therefore, the HMDS algorithm is more applicable to the WSN than the HIS algorithm. Especially when the network sizen is very large, the HMDS algorithm has more obvious advantages.Figure 2
Time consumption of the two stages.


### 5.2.2. Overall Efficiency

We randomly take 20 pairs of nodes to evaluate the overall efficiency; that is to say, we measure the time consumption of the four stages, from initialization to the end of unsigncryption. As shown in Figure3, the overall time consumption for both algorithms increases with the number of nodes increasing, but the HMDS algorithm still takes less time than the HIS algorithm. This trend becomes more and more obvious with the increasing of the network size and is consistent with the results of the above two-stage experiments.Figure 3
Overall time consumption.Therefore, the HMDS algorithm outperforms the HIS algorithm. Furthermore, the HMDS algorithm does not cause rapid increase of time consumption when the network scale grows. So the HMDS algorithm is more suitable for larger-scale WSN.


## 5.2.1. Efficiency of Initialization and Extract Stage

As shown in Figure2, it can be observed that the time consumption of the two algorithms in the three scenarios, S1, S2, and S3, is all within 100ms and the HMDS algorithm has a slight advantage over the HIS algorithm. It is because the number of the nodes is small. With the number of nodes increasing from 100 (in S3) to 1000 (in S6), the time consumption of the two algorithms also has a large increment, and the HMDS algorithm has an obvious advantage over the HIS algorithm. Especially in the scenario S6, the HIS algorithm takes about 850ms, while the HMDS algorithm only takes 300ms, which saves about two-thirds of the time. In general, for the HIS algorithm, the time consumption of the two stages increases steeply when the network sizen increases quickly. In comparison, the HMDS algorithm is relatively stable in time consuming when the network sizen is large. Therefore, the HMDS algorithm is more applicable to the WSN than the HIS algorithm. Especially when the network sizen is very large, the HMDS algorithm has more obvious advantages.Figure 2
Time consumption of the two stages.


## 5.2.2. Overall Efficiency

We randomly take 20 pairs of nodes to evaluate the overall efficiency; that is to say, we measure the time consumption of the four stages, from initialization to the end of unsigncryption. As shown in Figure3, the overall time consumption for both algorithms increases with the number of nodes increasing, but the HMDS algorithm still takes less time than the HIS algorithm. This trend becomes more and more obvious with the increasing of the network size and is consistent with the results of the above two-stage experiments.Figure 3
Overall time consumption.Therefore, the HMDS algorithm outperforms the HIS algorithm. Furthermore, the HMDS algorithm does not cause rapid increase of time consumption when the network scale grows. So the HMDS algorithm is more suitable for larger-scale WSN.


## 6. Conclusion

In this paper, the identity-based HMDS authentication algorithm was proposed. The public key of the applicant is generated by KGC and the private key is computed by the node itself to solve the key escrow problem, which is a disadvantage of the common identity-based authentication algorithm. The HMDS algorithm adopts hierarchical structure to adapt to WSN requirement. By employing matrix decomposition, the cost of calculation and storage is reduced. Through analysis and experimental comparison, the HMDS algorithm can ensure communication security in the WSN environment and has characteristics of low energy consumption and high stability, which is very suitable for WSN. Furthermore, when the network scale is large, the performance of the HMDS algorithm is very stable and has advantages over HIS scheme. In the future, we will improve the existing matrix decomposition-based HDMS algorithm, especially to optimize the authentication method between cluster heads. Meanwhile, we will study the key updating mechanism to improve the authentication efficiency.



---

*Source: 5929828-2018-12-02.xml*