# Hierarchical Key Management Scheme with Probabilistic Security in a Wireless Sensor Network (WSN)

Authors: Ashwag Albakri; Lein Harn; Sejun Song
Journal: Security and Communication Networks
 (2019)

---

## Abstract

Securing data transferred over a WSN is required to protect data from being compromised by attackers. Sensors in the WSN must share keys that are utilized to protect data transmitted between sensor nodes. There are several approaches introduced in the literature for key establishment in WSNs. Designing a key distribution/establishment scheme in WSNs is a challenging task due to the limited resources of sensor nodes. Polynomial-based key distribution schemes have been proposed in WSNs to provide a lightweight solution for resource-constraint devices. More importantly, polynomial-based schemes guarantee that a pairwise key exists between two sensors in the WSNs. However, one problem associated with all polynomial-based approaches in WSNs is that they are vulnerable to sensor capture attacks. Specifically, the attacker can compromise the security of the entire network by capturing a fixed number of sensors. In this paper, we propose a novel polynomial-based scheme with a probabilistic security feature that effectively reduces the security risk of sensor-captured attacks and requires minimal memory and computation overhead. Furthermore, our design can be extended to provide hierarchical key management to support data aggregation in WSNs.


---

## Body

## 1. Introduction

Wireless sensor networks (WSNs) have been deployed in various settings that aim at data acquisition. For instance, WSNs are deployed to observe road traffic or patients’ medical conditions in civilian environments and to track specific targets or monitor battlegrounds in military domains [1, 2]. A WSN consists of sensor nodes that are usually deployed in unattended environments to sense events or specific phenomena and relay such data to other sensors. WSNs can be classified into two types:flat andhierarchical. In flat WSNs, all sensors have the same capabilities to collect data and forward them to other sensors in the network. In hierarchical WSNs, devices are organized into a hierarchy based on their capabilities: sensor nodes with their limited capabilities (i.e., limited storage, processing power, and battery life) are located in the bottom of the hierarchy;cluster heads (CHs) are located in the middle of the hierarchyand have more capabilities than those of sensor nodes; and a mobile sink (or a base station) has the largest capabilities and is located at the top of the hierarchy. In the hierarchical structure, sensor nodes are responsible for forwarding data to the CHs, which process the data and send them to the base station, where further analysis on the collected data can take place [1].Due to the sensitivity of data transmitted in WSNs, security services such as data confidentiality and data authentication are needed to protect data from various attacks, such aseavesdropping attacks, in which an attacker tries to compromise the transmitted data, andnode capture attacks, in which an attacker tries to compromise the stored keys used to protect the data. In order to provide data confidentiality and authentication, source and destination nodes must share a secret key before exchanging any data. Establishing secret keys between sensors is called thekey distribution/establishment in WSNs. Since sensor nodes are limited in their memory, as well their processing and battery power, adding security services is a challenging task. Incorporating key distribution protocols in WSNs must accommodate the sensors’ physical limitations.Utilizing asymmetric cryptographic schemes [3–5] is considered impractical as they require extensive computation and large storage that are not suitable for implementation in sensors due to their inherit characteristics (i.e., limited memory, processing, and battery power). There are several approaches to designing secure key distribution schemes in WSNs. One approach is to preload all sensors with one master key. This approach provides high network connectivity, low storage requirements, and no communication/computation overhead. However, the network becomes vulnerable to node capture attacks as capturing one sensor compromises the security of the entire network. Another approach is to preload each sensor with a pairwise key that is shared between two sensors. In this approach, each sensor needs to share a pairwise key with every other sensor in the network. This approach can resist node capture attack, but the storage requirement is linearly proportional to the network size. Thus, this approach is impractical to be implemented in a large network.In most key distribution schemes in WSNs, there are some objectives that need to be satisfied, such as low memory requirements, low computational and communication overhead, and high connectivity and robustness against node capture attacks. In this paper, we propose the first polynomial-based key distribution scheme with probabilistic security. Our proposed scheme follows thehierarchical key management structure in which sensors in a WSN are classified into multiple clusters and keys are generated based on the hierarchical structure. In summary, the proposed scheme has the following features:(i)
It is the first polynomial-based key distribution scheme with probabilistic security.(ii)
It guarantees a shared key between two sensors.(iii)
If the degree of the chosen polynomial ist-1, then capturing t or more than t sensors has a very low probability of compromising the security of the WSN.(iv)
It provides keys to support three types of communication: sensor-to-sensor communication, sensor-to-cluster head (CH) communication, and CH-to-sink communication.(v)
It provides a revocation mechanism to ensure the confidentiality of data transferred in the network.(vi)
It has a hierarchical key management structure, which means it minimizes the storage requirements of each sensor, CH, and the sink.This paper is organized as follows: Section2 demonstrates the network model. Section 3 discusses the related work. Section 4 explains our contribution. Section 5 introduces the model of our proposed scheme and Section 6 introduces the proposed key management scheme. Security analysis is included in Section 7. Section 8 demonstrates the performance analysis, and finally conclusions are drawn in Section 9.


### 1.1. Motivation

Data transmitted in the WSN need to be protected; otherwise the data collected in the network are also available to attackers. To secure data transmitted between sensors in the WSN, sensors must share keys with other sensors before transmitting any data. These keys are utilized to protect the data from attackers. Polynomial-based schemes have been adopted to establish and distribute keys to sensors in WSNs.The motivation of our work is based on two reasons:First, our approach of using a polynomial-based key generation scheme to generate tokens (i.e., keying materials) for sensors is to simplify key establishment tasks in wireless sensor communication. Since sensors are constrained devices, we aim at reducing the amount of information that needs to be transmitted and stored by sensors as well as reducing the computational processing overhead. Tokens preloaded into sensors facilitate establishing pairwise shared keys between any two sensors noninteractively. In addition, a hierarchical key management model is used to enable us to generate tokens according to network traffic flow. With such a feature, the tokens’ sizes (i.e., polynomial’s coefficients) decrease when they move from the top of the hierarchy, which has the more capable devices (i.e., base station, cluster heads) to the bottom of the hierarchy, which consists of limited-resource devices (i.e., sensors).Second, our work is motivated by the fact that all polynomial-based predistribution schemes are inherently deterministic security schemes that are vulnerable to sensor-captured attacks. Thus, if an attacker captures a specific number of sensors, the attacker can reconstruct the polynomial used to generate keying materials (i.e., tokens) in the network and that leads to compromising the security of the whole network. In this work, we aim at designing a polynomial-based scheme that resists sensor-captured attacks. In this paper, we propose a polynomial-based scheme with probabilistic security that reduces sensor capture attacks. More specifically, capturing a specific number of sensors has a very low probability for an attacker to reconstruct the polynomial and compromise the WSNs. We can adjust the system’s parameters to lower this probability, as explained in Section6.


## 1.1. Motivation

Data transmitted in the WSN need to be protected; otherwise the data collected in the network are also available to attackers. To secure data transmitted between sensors in the WSN, sensors must share keys with other sensors before transmitting any data. These keys are utilized to protect the data from attackers. Polynomial-based schemes have been adopted to establish and distribute keys to sensors in WSNs.The motivation of our work is based on two reasons:First, our approach of using a polynomial-based key generation scheme to generate tokens (i.e., keying materials) for sensors is to simplify key establishment tasks in wireless sensor communication. Since sensors are constrained devices, we aim at reducing the amount of information that needs to be transmitted and stored by sensors as well as reducing the computational processing overhead. Tokens preloaded into sensors facilitate establishing pairwise shared keys between any two sensors noninteractively. In addition, a hierarchical key management model is used to enable us to generate tokens according to network traffic flow. With such a feature, the tokens’ sizes (i.e., polynomial’s coefficients) decrease when they move from the top of the hierarchy, which has the more capable devices (i.e., base station, cluster heads) to the bottom of the hierarchy, which consists of limited-resource devices (i.e., sensors).Second, our work is motivated by the fact that all polynomial-based predistribution schemes are inherently deterministic security schemes that are vulnerable to sensor-captured attacks. Thus, if an attacker captures a specific number of sensors, the attacker can reconstruct the polynomial used to generate keying materials (i.e., tokens) in the network and that leads to compromising the security of the whole network. In this work, we aim at designing a polynomial-based scheme that resists sensor-captured attacks. In this paper, we propose a polynomial-based scheme with probabilistic security that reduces sensor capture attacks. More specifically, capturing a specific number of sensors has a very low probability for an attacker to reconstruct the polynomial and compromise the WSNs. We can adjust the system’s parameters to lower this probability, as explained in Section6.


## 2. Network Model

Schemes in WSNs can be divided into two broad categories,flat WSNs andhierarchical WSNs. In a flat scheme, all sensor nodes have the same processing, communication, and battery power. On the other hand, there are three different devices in the hierarchal WSNs and they are organized, in a hierarchy based on their capabilities, into a base station (BS) or a mobile sink (MS), cluster heads (CHs), and sensor nodes. The base station is at the top of the hierarchy with the largest capabilities. CHs are on the next level under the base station and retain higher storage, better communication, and more computation power than that of sensor nodes, which are at the lowest level of the hierarchy. According to [6], hierarchal WSNs perform better than flat networks in terms of communication overhead and scalability in large networks. Therefore, we follow the hierarchical WSNs in designing our proposed scheme.In a hierarchal scheme, the WSN is partitioned into several clusters, depending on the network’s application. In each cluster, there is a CH that serves all sensor nodes in its cluster. To transmit data, each sensor node sends data to its local CH. Next, the CH processes the data, aggregates it, and then forwards it to the base station. The hierarchal model with different types of sensors has been utilized in various environments. For example, in a military environment, different types of sensors are utilized to collect data (e.g., images, sounds, and motions) for different purposes such as intrusion detection, chemical and biological threat detection, and object presence detection [7, 8]. The sensors can also be classified based on their physical properties such as motion sensors, thermal sensors, pressure sensors, and chemical sensors [9]. The model of our proposed hierarchical key management scheme is shown in Figure 1.Figure 1
The network model of the proposed hierarchal key management scheme.In the network model, there is a key generation center (KGC), which is responsible for generating keying materials (i.e., tokens) for all nodes in the network. The KGC is located at the base station level and takes a top-down approach in generating tokens, starting from base station, then CHs, and finally sensor nodes. The detailed discussion is included in Section5.


## 3. Related Work

The literature is rich with papers focusing on establishing secure key distribution schemes in WSNs. Most of the proposed schemes are implemented in aflat structure. These schemes are based on several common approaches such as random-key predistribution schemes [13], polynomial-based predistribution schemes [14], and grid-based predistribution schemes [15]. Eschenaueret al. [13] proposed the first random-key scheme, in which each sensor was preloaded with a subset of keys drawn randomly from a pool of keys called akey pool. The collection of preloaded keys is called thekey ring. If two sensors want to communicate with each other, they need to find at least one common key in their key rings; otherwise, they need to find a neighbor that shares common keys with each of the sensors. The random-key scheme is aprobabilistic key distribution scheme withprobabilistic security. Concisely, this scheme does not guarantee a shared pairwise key between two sensors. Also, capturing the sensors reveals only partial keys in the key pool. In order to increase the probability of establishing keys between sensors, the size of the key ring of each sensor needs to increase. However, increasing the size of the key ring will also increase the probability of a sensor capture attack since capturing each sensor will reveal more keys from the key pool. Thus, there is always a trade-off between the probability of network connectivity and the resiliency to a node capture attack. In the polynomial-based approach, it is adeterministic key establishment withdeterministic security. A deterministic key establishment guarantees a shared key between any two sensors, while deterministic security, also calleddeterministic t-secure, means if the degree of the polynomial used to generate keys for sensors ist-1, then capturing t or more than t sensors can compromise the security of the entire network. Increasing the degree of the polynomial can improve the security against a sensor capture attack; however, this will increase the storage and computational requirements of the sensors. Designing a deterministic key distribution scheme with probabilistic security is the motivation of our paper.In large-scale networks, researchers observed that hierarchal WSNs perform better than flat networks in terms of communication overhead and scalability [6]. This is in part due to the ability of aggregating data from large numbers of sensor nodes onto relay nodes and then forwarding them to destination nodes in fewer hops [6, 16–18]. Shenet al. [1] proposed a key distribution scheme in hierarchal WSNs based on a symmetric bivariate polynomial. Although their scheme is scalable, secure, and lightweight, it shows high communication and computational overhead. On the other hand, Kumaret al. [19] proposed a symmetric/asymmetric key predistribution scheme based on a hardware chip, called a Trusted Platform Module (TPM) that is added to the CHs and sensors in the hierarchal WSNs. This chip-based scheme resists physical attacks such as node capture attacks, node injection attacks, and node impersonation attacks. However, the security of this scheme depends on the TPM chip in devices (CHs and sensor nodes). The TPM chip embedded in every sensor increases the whole network cost, and that is not a practical solution to be considered in a large WSN [20]. In [10], Mahmoodet al. proposed a polynomial subset-based multiparty key management system for limited-resource devices such as WSNs and the Internet of Things (IoT). In the polynomial generation phase, their proposed scheme uses an XOR operation instead of the expensive multiplication operations to reduce the computation overhead. Although the scheme shows a reduction in the storage and computation overhead, it has a high communication overhead and requires regenerating a new polynomial when a sensor node joins or leaves the network. In [11], the authors proposed a multivariate polynomial-based key management scheme in which a base station creates a pool of random symmetric trivariate polynomials; then each CH chooses a trivariate polynomial and generates shares for all sensors in its cluster, which are bivariate polynomials. The CH hashes the shares before sending them to the sensors to ensure their integrity. If node i and node j want to communicate, they use their shares to create the pairwise keys, fi,j=f(j,i). Thus, each sensor stores a bivariate polynomial’s coefficients, which requires a large storage space. In [21], Bahramiet al. proposed a hierarchical key predistribution scheme in a fog network to provide secure communication between end-devices (i.e., constrained devices) in a fog cluster, and between end-devices and fog nodes (i.e., CHs), which is simulating the hierarchical WSN’s schemes. Their proposed scheme, which is based on a residual design, shows less memory requirements and enhances the scalability of the network. However, their key predistribution scheme follows the probabilistic schemes in which a shared pairwise key between end-devices in a fog cluster is not guaranteed; so, in case there is no shared key between two end-devices, they will start a path-key discovery phase in which they need to find an intermediary node that shares a key with both of them, this way introducing a communication overhead. In [22], Albakriet al. proposed a hierarchical polynomial-based key management scheme in fog computing. Although their proposed scheme exhibits a good performance in terms of communication, computation, and storage space for IoT devices (i.e., constrained devices), it does not consider communication links between IoT devices. Hamsha and Nagaraja in [12] proposed a lightweight threshold key management scheme in WSNs. The proposed scheme is based on Shamir’s secret key sharing scheme to generate shares for all nodes in the network. They divided the network into multiple levels, and at each level the base station is responsible for selecting a polynomial, secret keys, generating shares, and updating thresholds. In addition, all sensors are preloaded with a network key that is utilized for secure data transmission between sensor nodes. Although the scheme seems lightweight in terms of storage, it is vulnerable to sensor capture attacks. Capturing one sensor enables an attacker to obtain the network key and that leads to compromising the security of the WSN. In [23], Kumaret al. proposed a key predistribution scheme in WSNs based on combinatorial design. Their scheme improves the overall network resiliency and ensures network connectivity in case cluster heads or sensor nodes are compromised by an attacker. Also, they adopted a symmetric design to reduce the storage requirements of cluster heads. On the other hand, their proposed scheme exhibits high communication and computation overhead at the shared key discover phase. In our proposed scheme, we preloaded all network nodes (i.e., cluster heads, sensors) with tokens that enable each node to establish shared keys independently without requiring additional information to be transferred to establish the keys.As sensor nodes are deployed in hostile and unattended environments, they are exposed to various attacks. To secure WSNs and ensure the confidentiality of data transmitted in the network, it is crucial to implement a revocation mechanism to exclude the compromised nodes from participating in network activities or revealing the content of secure messages. In [24], Geet al. classified the revocation schemes into two categories: centralized and distributed schemes. In the distributed revocation schemes, sensor nodes collaborate with each other to exclude compromised nodes using voting techniques. On the other hand, the centralized approach transfers the revocation process into a central authority (i.e., base station) that becomes responsible for detecting the compromised nodes and removing compromised keys in the sensor nodes. Although the centralized approach exhibits a single point of failure, since all revocations are handled by the central authority, it shows a better performance (i.e., storage, communication, and computation overhead) than distributed revocation mechanisms [24, 25]. In our proposed scheme, we adopt the centralized approach for key revocation. However, the detection mechanism is not in the scope of this paper. We assume that the CH, which monitors the node activities, can identify the misbehaving node and is able to revoke the compromised node from the network.


## 4. Our Contribution

The main contribution of this paper is to propose, for the first time, a polynomial-based scheme with probabilistic security. With a probabilistic security feature, there is a low probability for sensor capture attacks to successfully reconstruct the polynomials that are used to generate tokens for all nodes in the network. We aim at reducing sensor-captured attacks as much as possible. We also show that we can adjust a system’s parameters to lower such attacks and enhance the security of the network.One of the unique properties of our proposed scheme, which is a polynomial-based design, is that all pairwise shared keys between two sensors can be computed noninteractively. The communication overhead of our scheme must be much shorter than most nonpolynomial-based designs. This is because nonpolynomial-based schemes need to exchange information interactively in order to establish pairwise keys that result in high communication overhead. More details are discussed in the performance analysis section.


## 5. Model of Proposed Scheme

Instead of adopting a flat key management [13–19, 26], our proposed scheme uses the hierarchical key management model [27, 28]. In such models, sensors are distributed into different clusters. Each cluster has a cluster head (CH). All CHs are connected to a sink. Collected information by each sensor node can be transmitted to its neighbor sensor node and to its CH. Finally, all collected data are sent to the sink by the CH. Arranging data in a WSN in such a hierarchical structure has several advantages [29]. First, in a hierarchical network, the CHs and the sink manage most communication traffic of the network. Sensors are woken up only when they are needed for data transmission or data collection. This can reduce energy consumption. Furthermore, the CH is able to conclude the local information since all collected information passes through it. Finally, the CH transmits most data, so more communication channels can host more sensors in the network. Consequently, the hierarchical WSN has better scalability and is more efficient than the flat WSN.In our proposed hierarchical key management structure, tokens are generated from top to bottom. The key generation center (KGC) first selects a trivariate polynomial,F(x,y,z), and uses it to generate all tokens in the WSN. The token of the sink is the trivariate polynomial. Then, the KGC uses the trivariate polynomial to generate tokens, which are bivariate polynomials for all cluster heads. Similarly, the KGC uses the bivariate polynomial of each CH to generate tokens, which are univariate polynomials for all sensor nodes in the cluster. In our proposed structure, each upper level device in a WSN is able to access tokens of the lower level devices. For example, the sink knows the tokens of all CHs and each CH knows all the tokens of its sensor nodes.In data aggregation, a sensor node aggregates the reported values from its children and forwards the aggregated value to its parent. The hierarchical key management of our proposed scheme can provide keys to support three types of secret communications in a WSN: (1)unicast communication in which a node sends data to a single node or its cluster head, (2)local broadcast in which the cluster head sends data to all the nodes in the cluster, and (3)global broadcast in which the sink sends data to all the nodes in the network.


## 6. Proposed Scheme

We propose a polynomial-based key distribution scheme with probabilistic security. The three main steps in our predistributed key management scheme are the token generation, key establishment, and key revocation. The following subsections explain each step in detail.


### 6.1. Token Generation

A key generation center (KGC) initially selects a prime modulus,p, and a trivariate polynomial, F(x,y,z), to generate sensors’ tokens in a WSN, where p has the same size of keys needed in secret communication. We assume that the degree of x isk-1, the degree of y ist-1, and the degree of z ish-1, where these parameters (i.e.,k-1, t-1, andh-1) are the thresholds of the polynomials used to generate tokens. In addition, these parameters determine the strength to resist the sensor capture attack. The trivariate polynomial is retained by the sink of the network. We assume each device in the WSN (e.g., the sink, CH, and sensors) has a unique ID.Each CH with a cluster identity,IDC, has a token that is a bivariate polynomial, FIDC,y,zmod⁡p. Each unique bivariate polynomial is kept by each CH. Note that the properties of this type of asymmetric bivariate polynomial can be found in [30]. Moreover, tokens of sensor nodes in the same cluster are generated by a bivariate polynomial. For example, the token of a sensor node with the identity idj∈IDC is FIDC,idj,zmod⁡p and FIDC,y,idjmod⁡p, which are two univariate polynomials. Each sensor node needs to store the coefficients of two univariate polynomials.


### 6.2. Key Establishment

Our proposed scheme provides two types of keys: unicast and broadcast communication keys. The unicast keys are used to support sensor-to-sensor, sensor-to-CH, and CH-to-sink communications. The broadcast keys are either local keys used by the CHs to send messages to the sensors in their cluster, or global keys used by the sink to broadcast a message to all sensors in the network. The following subsections demonstrate the key establishment process.(a) Unicast Communication Keys (1)
Key between two sensor nodes. According to [30], any two sensor nodes in the same cluster can share a pairwise key. For example, two sensor nodes with the following identities and tokens, idj∈IDC, FIDC,y,idjmod⁡p, FIDC,idj,zmod⁡p, and idk∈IDC,FIDC,y,idkmod⁡p, FIDC,idk,zmod⁡p, respectively, can share a key FIDC,idk,idjmod⁡p if idj>idk or FIDC,idj,idkmod⁡p if idj<idk, as seen in Figure 2. Thus, any node can send data secretly to any other node in the same cluster. (2)
Key between a sensor node and its CH. Any CH can use its bivariate polynomial to share a pairwise key with any sensor node in its cluster. For example, the CH with cluster identity IDC and its bivariate polynomial FIDC,y,zmod⁡p can share the key KC,idj=FIDC,IDC,idjmod⁡p, with a sensor node with the consequent identity and tokens, idj∈IDC, FIDC,y,idjmod⁡p, FIDC,idj,zmod⁡p. (3)
Key between a sink and each CH. The sink can use its trivariate polynomial to share a pairwise key with any CH in a WSN. For example, the sink with the trivariate polynomial Fx,y,zmod⁡p can share the key KS,C=FIDC,IDC,IDCmod⁡p with a CH with identity IDC and token FIDC,y,zmod⁡p.Figure 2
Key establishment between sensor withidk and sensor with idj (idk<idj).(b) Local Broadcast Key. A local broadcast key, KLB, can be determined and sent to each sensor node separately as EKC,idj(KLB) by their CH; the broadcast key, KLB, is encrypted under the shared key, KC,idj, with each sensor node.(c) Global Broadcast Key. A global broadcast key, KGB, can be determined and sent to each cluster head separately as EkS,C(KGB) by the sink. Thus, the broadcast key, KGB, is encrypted under the shared key, KS,C, with each cluster head. After receiving the global broadcast key, each CH forwards it to each sensor node separately as EKC,idj(KGB), which means that the global broadcast key, KGB, is encrypted under the shared key, KC,idj, with each sensor node.


### 6.3. Key Revocation

If an attacker compromises a sensor node, he can get the token used to generate pairwise keys as well as the unicast and broadcast keys. Thus, it is important to utilize a key revocation scheme.The sink creates a node revocation list (NRL) that includes the IDs of all revoked nodes. The NRL is initially empty and is populated whenever a compromised node gets detected. This list is stored on each device in the WSN. The NRL is checked for any messages exchanged in the network to ensure that all current members of the network are valid/noncompromised nodes. We adopt the node revocation list from the scheme of Wanget al. [31] since it is an efficient and simple way to allow nodes (i.e., the sink, CH, and sensors) to identify the compromised nodes and exclude them from the network [24, 25].Our revocation mechanism works as follows. The CH is responsible for monitoring the sensors’ activities and detecting misbehaved sensors. If a malicious sensor is detected, the CH will add that sensor’s ID into its NRL. Since the broadcast keys stored in the compromised sensor are revealed by the attacker, the CH must update the local broadcast key,KLB, and sends it to a noncompromised sensor (not in the NRL) in its cluster separately and encrypted by the shared pairwise key between a sensor and its CH as EKC,idjKLB. Then, the CH must send the updated NRL encrypted by the local broadcast key, EKLBNRL, to all sensors in the cluster. Thus, each noncompromised sensor can decrypt the message using the local broadcast key, which authenticates the CH, and then updates its NRL. After that, the CH sends a request to the sink to update the global broadest key, KGB. It also sends the updated NRL to the sink, encrypted by the pairwise key as EkS,CNRL, where KS,C is the pairwise key between the CH and the sink. The sink will authenticate the message sent by the CH, update its NRL, create a new global broadcast key, KGB, and send it to each CH in the network encrypted by the pairwise key between CH and the sink as EkS,C(KGB). Once each CH receives the message from the sink, it authenticates the message using the pairwise key, KS,C, updates the global broadcast key, KGB, and sends a local broadcast message to all nodes in its cluster to update the global broadcast key as EKLB(KGB). This way, only the sensor nodes that have the updated local broadcast key can decrypt the message and store the updated global broadcast key.Our proposed key establishment scheme is a polynomial-based scheme. Thus, we do not need to adopt a sophisticated revocation mechanism since nodes do not store pairwise keys. Instead, they store the polynomial’s coefficients that are used along with the node ID to create the pairwise key. Before that, a sensor’s ID is checked to make sure that it is not listed in the NRL; otherwise, this communication is terminated. Threshold is the intrinsic part of the polynomial-based scheme, so if the number of compromised nodes approaches the threshold value, new tokens must be generated.


## 6.1. Token Generation

A key generation center (KGC) initially selects a prime modulus,p, and a trivariate polynomial, F(x,y,z), to generate sensors’ tokens in a WSN, where p has the same size of keys needed in secret communication. We assume that the degree of x isk-1, the degree of y ist-1, and the degree of z ish-1, where these parameters (i.e.,k-1, t-1, andh-1) are the thresholds of the polynomials used to generate tokens. In addition, these parameters determine the strength to resist the sensor capture attack. The trivariate polynomial is retained by the sink of the network. We assume each device in the WSN (e.g., the sink, CH, and sensors) has a unique ID.Each CH with a cluster identity,IDC, has a token that is a bivariate polynomial, FIDC,y,zmod⁡p. Each unique bivariate polynomial is kept by each CH. Note that the properties of this type of asymmetric bivariate polynomial can be found in [30]. Moreover, tokens of sensor nodes in the same cluster are generated by a bivariate polynomial. For example, the token of a sensor node with the identity idj∈IDC is FIDC,idj,zmod⁡p and FIDC,y,idjmod⁡p, which are two univariate polynomials. Each sensor node needs to store the coefficients of two univariate polynomials.


## 6.2. Key Establishment

Our proposed scheme provides two types of keys: unicast and broadcast communication keys. The unicast keys are used to support sensor-to-sensor, sensor-to-CH, and CH-to-sink communications. The broadcast keys are either local keys used by the CHs to send messages to the sensors in their cluster, or global keys used by the sink to broadcast a message to all sensors in the network. The following subsections demonstrate the key establishment process.(a) Unicast Communication Keys (1)
Key between two sensor nodes. According to [30], any two sensor nodes in the same cluster can share a pairwise key. For example, two sensor nodes with the following identities and tokens, idj∈IDC, FIDC,y,idjmod⁡p, FIDC,idj,zmod⁡p, and idk∈IDC,FIDC,y,idkmod⁡p, FIDC,idk,zmod⁡p, respectively, can share a key FIDC,idk,idjmod⁡p if idj>idk or FIDC,idj,idkmod⁡p if idj<idk, as seen in Figure 2. Thus, any node can send data secretly to any other node in the same cluster. (2)
Key between a sensor node and its CH. Any CH can use its bivariate polynomial to share a pairwise key with any sensor node in its cluster. For example, the CH with cluster identity IDC and its bivariate polynomial FIDC,y,zmod⁡p can share the key KC,idj=FIDC,IDC,idjmod⁡p, with a sensor node with the consequent identity and tokens, idj∈IDC, FIDC,y,idjmod⁡p, FIDC,idj,zmod⁡p. (3)
Key between a sink and each CH. The sink can use its trivariate polynomial to share a pairwise key with any CH in a WSN. For example, the sink with the trivariate polynomial Fx,y,zmod⁡p can share the key KS,C=FIDC,IDC,IDCmod⁡p with a CH with identity IDC and token FIDC,y,zmod⁡p.Figure 2
Key establishment between sensor withidk and sensor with idj (idk<idj).(b) Local Broadcast Key. A local broadcast key, KLB, can be determined and sent to each sensor node separately as EKC,idj(KLB) by their CH; the broadcast key, KLB, is encrypted under the shared key, KC,idj, with each sensor node.(c) Global Broadcast Key. A global broadcast key, KGB, can be determined and sent to each cluster head separately as EkS,C(KGB) by the sink. Thus, the broadcast key, KGB, is encrypted under the shared key, KS,C, with each cluster head. After receiving the global broadcast key, each CH forwards it to each sensor node separately as EKC,idj(KGB), which means that the global broadcast key, KGB, is encrypted under the shared key, KC,idj, with each sensor node.


## 6.3. Key Revocation

If an attacker compromises a sensor node, he can get the token used to generate pairwise keys as well as the unicast and broadcast keys. Thus, it is important to utilize a key revocation scheme.The sink creates a node revocation list (NRL) that includes the IDs of all revoked nodes. The NRL is initially empty and is populated whenever a compromised node gets detected. This list is stored on each device in the WSN. The NRL is checked for any messages exchanged in the network to ensure that all current members of the network are valid/noncompromised nodes. We adopt the node revocation list from the scheme of Wanget al. [31] since it is an efficient and simple way to allow nodes (i.e., the sink, CH, and sensors) to identify the compromised nodes and exclude them from the network [24, 25].Our revocation mechanism works as follows. The CH is responsible for monitoring the sensors’ activities and detecting misbehaved sensors. If a malicious sensor is detected, the CH will add that sensor’s ID into its NRL. Since the broadcast keys stored in the compromised sensor are revealed by the attacker, the CH must update the local broadcast key,KLB, and sends it to a noncompromised sensor (not in the NRL) in its cluster separately and encrypted by the shared pairwise key between a sensor and its CH as EKC,idjKLB. Then, the CH must send the updated NRL encrypted by the local broadcast key, EKLBNRL, to all sensors in the cluster. Thus, each noncompromised sensor can decrypt the message using the local broadcast key, which authenticates the CH, and then updates its NRL. After that, the CH sends a request to the sink to update the global broadest key, KGB. It also sends the updated NRL to the sink, encrypted by the pairwise key as EkS,CNRL, where KS,C is the pairwise key between the CH and the sink. The sink will authenticate the message sent by the CH, update its NRL, create a new global broadcast key, KGB, and send it to each CH in the network encrypted by the pairwise key between CH and the sink as EkS,C(KGB). Once each CH receives the message from the sink, it authenticates the message using the pairwise key, KS,C, updates the global broadcast key, KGB, and sends a local broadcast message to all nodes in its cluster to update the global broadcast key as EKLB(KGB). This way, only the sensor nodes that have the updated local broadcast key can decrypt the message and store the updated global broadcast key.Our proposed key establishment scheme is a polynomial-based scheme. Thus, we do not need to adopt a sophisticated revocation mechanism since nodes do not store pairwise keys. Instead, they store the polynomial’s coefficients that are used along with the node ID to create the pairwise key. Before that, a sensor’s ID is checked to make sure that it is not listed in the NRL; otherwise, this communication is terminated. Threshold is the intrinsic part of the polynomial-based scheme, so if the number of compromised nodes approaches the threshold value, new tokens must be generated.


## 7. Security Analysis

In our hierarchical key management structure, there are three types of devices in a WSN. These are the sensor nodes, cluster heads (CHs), and a sink. Each WSN hosts a large number of sensor nodes, which are located at the lowest level of the structure. Each sensor node has stored unique secret tokens that can be used to support secure communications with the CH or any other sensor node in the cluster. In every network, there exists multiple CHs where each CH manages communications occurring within the cluster. Each cluster has stored a unique secret token that can be used to support secure communications between any sensor node in the cluster and the sink. There is only one sink (i.e., also called “base station”). The sink is located at the highest level of the hierarchical structure and holds a unique token that can be used to support secure communications with any cluster head.


### 7.1. The Attack Model

The attack model of the proposed scheme is divided into two categories: sensor capture attacks and common network attacks.


#### 7.1.1. Sensor Capture Attacks

Due to the vulnerable and open environment where sensor nodes are deployed, it becomes easy to physically capture the sensors. In addition, sensor nodes are not equipped with tamper-proof hardware, and that enables attackers to obtain tokens stored in the captured sensors, which leads to serious security issues. Thus, we aim at decreasing these attacks as much as we can.If an attacker compromises the token of the sink, the security of our proposed scheme breaks completely. Thus, the sink needs to be well protected. Since there is only one sink, we can adopt a sophisticated mechanism such as a hardware-based tamper-proof technology to strengthen its security.If an attack compromises the token of each CH, all tokens of the sensor nodes within the cluster will be compromised. However, the tokens of sensor nodes located in other clusters will be intact. The following theorem discusses the security if the attack compromises multiple CH tokens.Theorem 1.
If the attacker captures k CH tokens, the attacker can recover the trivariate polynomial used to generate all secret tokens.Proof.
The trivariate polynomial used to generate all tokens isFx,y,z where the degree of x isk-1, the degree of y ist-1, and the degree of z ish-1. The token of each cluster head with cluster identity, IDC, is a bivariate polynomial, FIDC,y,zmod⁡p. Assume that k tokens of CHs with their identities, IDC,i,i=1,2,…,k, have been compromised by an attack. Then, following the Lagrange interpolation formula, the attacker can obtain ∑i=1kF(IDC,i,y,z)∏j=1,j≠ikx-IDC,j/IDC,i-IDC,jmod⁡p=Fx,y,z. However, fewer than k tokens of CHs cannot obtain the trivariate polynomial.Note. If we limit the number of CHs to be fewer than k, the above attack can never occur.In the following discussion, we divide sensor capture attacks into two types, the situation when (a) all capturing sensors belong to the same cluster and when (b) not all capturing sensors belong to the same cluster.Theorem 2 (sensor capture attack I).
If the attacker has captured t sensor nodes belonging to the same cluster, it can recover the bivariate polynomial used to generate tokens of sensor nodes in the cluster.Proof.
The polynomial used to generate tokens of sensor nodes belonging to the same cluster is a bivariate polynomial,FIDC,y,z with degreet-1 in y andh-1 in z. Knowing t sensors’ token values, FIDC,idj,z,j=1,2,…,t, from the Lagrange interpolating formula, the attacker can recover the bivariate polynomial used to generate tokens in this cluster as ∑j=1tF(IDC,idj,z)∏i=1,i≠jty-idi/idj-idimod⁡p=FIDC,y,z. However, acquiring less than t tokens does not grant the recovery of the bivariate polynomial.Note. This sensor capture attack can only be applied if all captured sensor nodes are in the same cluster. This condition decreases the possibility of a sensor capture attack occurring since captured sensor nodes randomly belong to different clusters in WSNs. In summary, our proposed scheme effectively reduces the risk of a sensor capture attack since this attack only works if two conditions are satisfied simultaneously, (a) having captured t or more sensor nodes and (b) having at least t sensor nodes belonging to the same cluster in all captured nodes. Furthermore, if we limit the number of sensor nodes in each cluster to be less than t, then this attack can never occur.Theorem 3 (sensor capture attack II).
If the attacker has captured m sensors (i.e.,m>tk) among which at most t sensors belong to the same cluster, he can recover the trivariate polynomial used to generate sensor tokens.Proof.
The trivariate polynomial used to generate all tokens isFx,y,z, where the degree of x isk-1, the degree of y ist-1, and the degree of z ish-1. Recall that the polynomial used to generate the tokens of sensors is a bivariate polynomial, FIDC,y,z with degreet-1 in y andh-1 in z. According to [28], from each captured sensor with tokens, FIDC,idj,zmod⁡p and FIDC,y,idjmod⁡p, we can establish at most t+h linearly independent equations in terms of the coefficients of the trivariate polynomial, Fx,y,z. Thus, there are at most t(t+h) linearly independent equations that can be established from the t captured sensors belonging to the same cluster. We assume that there are m captured sensors among which (at most)t sensors belonging to the same cluster exist. If the number of coefficients of the trivariate polynomial, Fx,y,z, is larger than the number of equations available to the attacker, that is, thk>m(t+h), then these m captured sensors cannot recover Fx,y,z. On the other hand, if m>thk/t+h, it can solve the trivariate polynomial used to generate the tokens of the sensors. Furthermore, from [30], since tt+h>th, we have m>tk. In other words, this attack needs to capture far more sensors than the previous attack to compromise the bivariate polynomial used to generate tokens for each class.Note. This sensor capture attack is much harder than the previous attack since (a) it needs to capture far more sensors than the previous one, and (b) among these captured sensors, there are at most t sensors belonging to the same cluster.


#### 7.1.2. Common Network Attacks

This section describes several common network attacks we consider when designing our proposed scheme.(1) Impersonation Attack. It is an attack in which the adversary assumes the identity of a legitimate entity in the wireless sensor network. The proposed scheme allows sensors to exchange their identities over the network to establish the pairwise keys independently. If an attacker tries to send a fake identity and pretend to be a legitimate sensor, the attacker will not obtain any information from sensors nodes because the data adversary sent does not come from the same mathematical structure (i.e., the polynomial used by KGC to generate tokens). As a result, its message will be dropped and legitimate sensors will terminate the communication. Because the attacker does not possess any valid token, the attacker will never be able to establish a pairwise key and send valid data that sensors can decrypt with their pairwise keys.(1) Replay Attack. It is an attacker who captures a message and tries to replay it to sender to confuse sender and obtain information. The proposed scheme preloaded sensors with tokens that enable sensors to compute pairwise keys independently. No additional information is required to establish the keys other than the sensors’ identities. Utilizing nonce for sensors communications eliminates the replay attack [32].(1) Key Exposure Attack. Exchanging keys over the network could lead to key exposer attacks [32]. Since our proposed scheme is predistribution scheme in which sensors are preloaded with tokens before deployed into the WSNs, there are no keys transferred over the network. Our aim is to reduce the amount of information that need to be exchanged between sensors to establish the keys. Thus, our proposed scheme resists such attacks.


## 7.1. The Attack Model

The attack model of the proposed scheme is divided into two categories: sensor capture attacks and common network attacks.


### 7.1.1. Sensor Capture Attacks

Due to the vulnerable and open environment where sensor nodes are deployed, it becomes easy to physically capture the sensors. In addition, sensor nodes are not equipped with tamper-proof hardware, and that enables attackers to obtain tokens stored in the captured sensors, which leads to serious security issues. Thus, we aim at decreasing these attacks as much as we can.If an attacker compromises the token of the sink, the security of our proposed scheme breaks completely. Thus, the sink needs to be well protected. Since there is only one sink, we can adopt a sophisticated mechanism such as a hardware-based tamper-proof technology to strengthen its security.If an attack compromises the token of each CH, all tokens of the sensor nodes within the cluster will be compromised. However, the tokens of sensor nodes located in other clusters will be intact. The following theorem discusses the security if the attack compromises multiple CH tokens.Theorem 1.
If the attacker captures k CH tokens, the attacker can recover the trivariate polynomial used to generate all secret tokens.Proof.
The trivariate polynomial used to generate all tokens isFx,y,z where the degree of x isk-1, the degree of y ist-1, and the degree of z ish-1. The token of each cluster head with cluster identity, IDC, is a bivariate polynomial, FIDC,y,zmod⁡p. Assume that k tokens of CHs with their identities, IDC,i,i=1,2,…,k, have been compromised by an attack. Then, following the Lagrange interpolation formula, the attacker can obtain ∑i=1kF(IDC,i,y,z)∏j=1,j≠ikx-IDC,j/IDC,i-IDC,jmod⁡p=Fx,y,z. However, fewer than k tokens of CHs cannot obtain the trivariate polynomial.Note. If we limit the number of CHs to be fewer than k, the above attack can never occur.In the following discussion, we divide sensor capture attacks into two types, the situation when (a) all capturing sensors belong to the same cluster and when (b) not all capturing sensors belong to the same cluster.Theorem 2 (sensor capture attack I).
If the attacker has captured t sensor nodes belonging to the same cluster, it can recover the bivariate polynomial used to generate tokens of sensor nodes in the cluster.Proof.
The polynomial used to generate tokens of sensor nodes belonging to the same cluster is a bivariate polynomial,FIDC,y,z with degreet-1 in y andh-1 in z. Knowing t sensors’ token values, FIDC,idj,z,j=1,2,…,t, from the Lagrange interpolating formula, the attacker can recover the bivariate polynomial used to generate tokens in this cluster as ∑j=1tF(IDC,idj,z)∏i=1,i≠jty-idi/idj-idimod⁡p=FIDC,y,z. However, acquiring less than t tokens does not grant the recovery of the bivariate polynomial.Note. This sensor capture attack can only be applied if all captured sensor nodes are in the same cluster. This condition decreases the possibility of a sensor capture attack occurring since captured sensor nodes randomly belong to different clusters in WSNs. In summary, our proposed scheme effectively reduces the risk of a sensor capture attack since this attack only works if two conditions are satisfied simultaneously, (a) having captured t or more sensor nodes and (b) having at least t sensor nodes belonging to the same cluster in all captured nodes. Furthermore, if we limit the number of sensor nodes in each cluster to be less than t, then this attack can never occur.Theorem 3 (sensor capture attack II).
If the attacker has captured m sensors (i.e.,m>tk) among which at most t sensors belong to the same cluster, he can recover the trivariate polynomial used to generate sensor tokens.Proof.
The trivariate polynomial used to generate all tokens isFx,y,z, where the degree of x isk-1, the degree of y ist-1, and the degree of z ish-1. Recall that the polynomial used to generate the tokens of sensors is a bivariate polynomial, FIDC,y,z with degreet-1 in y andh-1 in z. According to [28], from each captured sensor with tokens, FIDC,idj,zmod⁡p and FIDC,y,idjmod⁡p, we can establish at most t+h linearly independent equations in terms of the coefficients of the trivariate polynomial, Fx,y,z. Thus, there are at most t(t+h) linearly independent equations that can be established from the t captured sensors belonging to the same cluster. We assume that there are m captured sensors among which (at most)t sensors belonging to the same cluster exist. If the number of coefficients of the trivariate polynomial, Fx,y,z, is larger than the number of equations available to the attacker, that is, thk>m(t+h), then these m captured sensors cannot recover Fx,y,z. On the other hand, if m>thk/t+h, it can solve the trivariate polynomial used to generate the tokens of the sensors. Furthermore, from [30], since tt+h>th, we have m>tk. In other words, this attack needs to capture far more sensors than the previous attack to compromise the bivariate polynomial used to generate tokens for each class.Note. This sensor capture attack is much harder than the previous attack since (a) it needs to capture far more sensors than the previous one, and (b) among these captured sensors, there are at most t sensors belonging to the same cluster.


### 7.1.2. Common Network Attacks

This section describes several common network attacks we consider when designing our proposed scheme.(1) Impersonation Attack. It is an attack in which the adversary assumes the identity of a legitimate entity in the wireless sensor network. The proposed scheme allows sensors to exchange their identities over the network to establish the pairwise keys independently. If an attacker tries to send a fake identity and pretend to be a legitimate sensor, the attacker will not obtain any information from sensors nodes because the data adversary sent does not come from the same mathematical structure (i.e., the polynomial used by KGC to generate tokens). As a result, its message will be dropped and legitimate sensors will terminate the communication. Because the attacker does not possess any valid token, the attacker will never be able to establish a pairwise key and send valid data that sensors can decrypt with their pairwise keys.(1) Replay Attack. It is an attacker who captures a message and tries to replay it to sender to confuse sender and obtain information. The proposed scheme preloaded sensors with tokens that enable sensors to compute pairwise keys independently. No additional information is required to establish the keys other than the sensors’ identities. Utilizing nonce for sensors communications eliminates the replay attack [32].(1) Key Exposure Attack. Exchanging keys over the network could lead to key exposer attacks [32]. Since our proposed scheme is predistribution scheme in which sensors are preloaded with tokens before deployed into the WSNs, there are no keys transferred over the network. Our aim is to reduce the amount of information that need to be exchanged between sensors to establish the keys. Thus, our proposed scheme resists such attacks.


## 7.1.1. Sensor Capture Attacks

Due to the vulnerable and open environment where sensor nodes are deployed, it becomes easy to physically capture the sensors. In addition, sensor nodes are not equipped with tamper-proof hardware, and that enables attackers to obtain tokens stored in the captured sensors, which leads to serious security issues. Thus, we aim at decreasing these attacks as much as we can.If an attacker compromises the token of the sink, the security of our proposed scheme breaks completely. Thus, the sink needs to be well protected. Since there is only one sink, we can adopt a sophisticated mechanism such as a hardware-based tamper-proof technology to strengthen its security.If an attack compromises the token of each CH, all tokens of the sensor nodes within the cluster will be compromised. However, the tokens of sensor nodes located in other clusters will be intact. The following theorem discusses the security if the attack compromises multiple CH tokens.Theorem 1.
If the attacker captures k CH tokens, the attacker can recover the trivariate polynomial used to generate all secret tokens.Proof.
The trivariate polynomial used to generate all tokens isFx,y,z where the degree of x isk-1, the degree of y ist-1, and the degree of z ish-1. The token of each cluster head with cluster identity, IDC, is a bivariate polynomial, FIDC,y,zmod⁡p. Assume that k tokens of CHs with their identities, IDC,i,i=1,2,…,k, have been compromised by an attack. Then, following the Lagrange interpolation formula, the attacker can obtain ∑i=1kF(IDC,i,y,z)∏j=1,j≠ikx-IDC,j/IDC,i-IDC,jmod⁡p=Fx,y,z. However, fewer than k tokens of CHs cannot obtain the trivariate polynomial.Note. If we limit the number of CHs to be fewer than k, the above attack can never occur.In the following discussion, we divide sensor capture attacks into two types, the situation when (a) all capturing sensors belong to the same cluster and when (b) not all capturing sensors belong to the same cluster.Theorem 2 (sensor capture attack I).
If the attacker has captured t sensor nodes belonging to the same cluster, it can recover the bivariate polynomial used to generate tokens of sensor nodes in the cluster.Proof.
The polynomial used to generate tokens of sensor nodes belonging to the same cluster is a bivariate polynomial,FIDC,y,z with degreet-1 in y andh-1 in z. Knowing t sensors’ token values, FIDC,idj,z,j=1,2,…,t, from the Lagrange interpolating formula, the attacker can recover the bivariate polynomial used to generate tokens in this cluster as ∑j=1tF(IDC,idj,z)∏i=1,i≠jty-idi/idj-idimod⁡p=FIDC,y,z. However, acquiring less than t tokens does not grant the recovery of the bivariate polynomial.Note. This sensor capture attack can only be applied if all captured sensor nodes are in the same cluster. This condition decreases the possibility of a sensor capture attack occurring since captured sensor nodes randomly belong to different clusters in WSNs. In summary, our proposed scheme effectively reduces the risk of a sensor capture attack since this attack only works if two conditions are satisfied simultaneously, (a) having captured t or more sensor nodes and (b) having at least t sensor nodes belonging to the same cluster in all captured nodes. Furthermore, if we limit the number of sensor nodes in each cluster to be less than t, then this attack can never occur.Theorem 3 (sensor capture attack II).
If the attacker has captured m sensors (i.e.,m>tk) among which at most t sensors belong to the same cluster, he can recover the trivariate polynomial used to generate sensor tokens.Proof.
The trivariate polynomial used to generate all tokens isFx,y,z, where the degree of x isk-1, the degree of y ist-1, and the degree of z ish-1. Recall that the polynomial used to generate the tokens of sensors is a bivariate polynomial, FIDC,y,z with degreet-1 in y andh-1 in z. According to [28], from each captured sensor with tokens, FIDC,idj,zmod⁡p and FIDC,y,idjmod⁡p, we can establish at most t+h linearly independent equations in terms of the coefficients of the trivariate polynomial, Fx,y,z. Thus, there are at most t(t+h) linearly independent equations that can be established from the t captured sensors belonging to the same cluster. We assume that there are m captured sensors among which (at most)t sensors belonging to the same cluster exist. If the number of coefficients of the trivariate polynomial, Fx,y,z, is larger than the number of equations available to the attacker, that is, thk>m(t+h), then these m captured sensors cannot recover Fx,y,z. On the other hand, if m>thk/t+h, it can solve the trivariate polynomial used to generate the tokens of the sensors. Furthermore, from [30], since tt+h>th, we have m>tk. In other words, this attack needs to capture far more sensors than the previous attack to compromise the bivariate polynomial used to generate tokens for each class.Note. This sensor capture attack is much harder than the previous attack since (a) it needs to capture far more sensors than the previous one, and (b) among these captured sensors, there are at most t sensors belonging to the same cluster.


## 7.1.2. Common Network Attacks

This section describes several common network attacks we consider when designing our proposed scheme.(1) Impersonation Attack. It is an attack in which the adversary assumes the identity of a legitimate entity in the wireless sensor network. The proposed scheme allows sensors to exchange their identities over the network to establish the pairwise keys independently. If an attacker tries to send a fake identity and pretend to be a legitimate sensor, the attacker will not obtain any information from sensors nodes because the data adversary sent does not come from the same mathematical structure (i.e., the polynomial used by KGC to generate tokens). As a result, its message will be dropped and legitimate sensors will terminate the communication. Because the attacker does not possess any valid token, the attacker will never be able to establish a pairwise key and send valid data that sensors can decrypt with their pairwise keys.(1) Replay Attack. It is an attacker who captures a message and tries to replay it to sender to confuse sender and obtain information. The proposed scheme preloaded sensors with tokens that enable sensors to compute pairwise keys independently. No additional information is required to establish the keys other than the sensors’ identities. Utilizing nonce for sensors communications eliminates the replay attack [32].(1) Key Exposure Attack. Exchanging keys over the network could lead to key exposer attacks [32]. Since our proposed scheme is predistribution scheme in which sensors are preloaded with tokens before deployed into the WSNs, there are no keys transferred over the network. Our aim is to reduce the amount of information that need to be exchanged between sensors to establish the keys. Thus, our proposed scheme resists such attacks.


## 8. Performance

In this section, we evaluate the performance of the proposed scheme, theoretically, in terms of storage, computation, and communication overhead. In addition, the probabilistic property of the proposed scheme is explained.


### 8.1. Storage Requirement

In our proposed scheme, only the sink needs to store a trivariate polynomial,Fx,y,z, where the degree of x isk-1, the degree of y ist-1, and the degree of z ish-1. In other words, the storage of the sink iskth coefficients inGF(p). Each CH with cluster identity, IDC, needs to store a bivariate polynomial, FIDC,y,zmod⁡p. The storage requirement of each cluster head isth coefficients inGF(p). Each sensor node with identity, idj∈IDC, needs to store two univariate polynomials, FIDC,y,idjmod⁡p and FIDC,idj,zmod⁡p. The storage requirement of each sensor node is t+h coefficients inGF(p). In summary, in our proposed hierarchical key management scheme, each sensor node located at the lowest level only needs to store a minimal number of coefficients, but the sink located at the highest level needs to store the most coefficients.


### 8.2. Computational Requirement

In the following discussion, we evaluate the computational requirements of various communication keys. Horner’s rule [33] can be used to reduce the computational cost in the polynomial evaluation. According to Horner’s rule, evaluating a univariate polynomial of degreeh-1 needsh-1 multiplications and h additions.(1)
Key between two sensor nodes. Two sensor nodes with their identities idj and idk in the same cluster can share a pairwise key FIDC,idk,idj if idj>idk or FIDC,idj,idk if idj<idk. For example, if idj>idk, sensor node with identity idj can use its token FIDC,y,idj which is a univariate polynomial iny having degreet-1 to obtain the shared key FIDC,idk,idj. It needst-1 multiplications andt additions. Similarly, sensor node with identity idk  can use its token FIDC,idk,z, which is a univariate polynomial inz having degreeh-1, to obtain the shared key. It needsh-1 multiplications andh additions.(2)
Key between sensor node and cluster head.Any cluster head with identity IDC  can use its bivariate polynomial FIDC,y,z to share a pairwise key, KC,idj=FIDC,IDC,idj, with any sensor node with identity idj, in the same cluster. The bivariate polynomial FIDC,y,z hast-1 degree in y andh-1 degree in z. The cluster needsth multiplications andth+t-1 additions.(3)
Key between sink and each cluster head. The sink can use its trivariate polynomial Fx,y,z to share a pairwise key, KS,C=FIDC,IDC,IDC, with any cluster head with identity IDC. The trivariate polynomial Fx,y,z hask-1 degree inx, t-1 degree in y, andh-1 degree in z. The sink needsk(th+1) multiplications andkth+kt-1 additions.


### 8.3. Communication Overhead

The proposed scheme has a low communication overhead for key establishment. After deployment, no information needs to be transmitted to establish the shared pairwise keys except the sensors’ IDs and that is a crucial step for self-organization protocols in WSN. Thus, there is no such overhead in key distribution schemes [1]. On the other hand, updating broadcast keys, which involves sending new broadcast keys to each sensor using the pairwise keys, may introduce some communication overhead.


### 8.4. Probabilistic Security

Our proposed scheme is the first polynomial-based key distribution scheme with probabilistic security. Unlike all polynomial-based schemes, in which capturingt or more than t sensors can recover the polynomial of degreet-1, which led to compromising the whole network security, the random deployment of sensors loaded with different polynomial structures makes it difficult to guarantee that t captured sensors belong to the same class. The proposed scheme allows sensors from the same cluster to communicate with each other since their tokens/shares are generated from the same polynomial structure. Thus, sensors from different categories cannot communicate with each other because they are preloaded with shares that are created from different polynomials. In order to reveal the polynomial used to generate the shares for sensors, the attacker needs to collect at least t sensors that all belong to the same cluster. In that way, the probability of finding such sensors is very low, which increases the difficulty of sensor capture attacks. This increased difficulty leads to the enhancement of the security of the WSN. We show the statistical analysis of the probabilistic security of the proposed scheme.In a WSN, ifn is the number of sensor nodes and l is the number of clusters, then r is the number of sensor nodes in each cluster (i.e., r=n/l). The probability of capturing t sensor nodes belonging to the same cluster is Pt=l.Ctr/Ctn. Figure 3 shows the probability of capturing t sensor nodes belonging to the same cluster for different threshold values. We can observe that this probability drops to zero very quickly after increasing the threshold value. Figure 4 shows this probability for a different number of clusters. Again, we observe that this probability drops to zero after increasing the number of clusters. Results show that our proposed scheme has probabilistic security and the probability of sensor capture attacks can be effectively reduced to be almost nonexistent by increasing the thresholdt (t≥3) or the number of clusters l (i.e., l≥4).Figure 3
The probability of capturingt sensors belonging to the same cluster with various thresholds (forl=4, n=40, r=10).Figure 4
The probability of capturingt sensors belonging to the same cluster with various numbers of clusters (forn=30, t=3).


### 8.5. Comparison

Table1 compares our proposed scheme with other polynomial-based schemes in [10–12]. Our proposed scheme stores two polynomial shares in each sensor. The degrees of the polynomials areh-1 andt-1; thus each sensor stores (t+h) coefficients. Compared to [10], each sensor node stores a master key and a univariate polynomial of degreeR, which means that each sensor storesR+1 coefficients. In [11], CHs generate shares to each sensor in its cluster, which are bivariate polynomials. In addition, each sensor is preloaded with a secret key. In [12], each sensor stores three keys: a network key that is used to secure communication between sensors; a cluster key that is used to secure communication between a sensor and its cluster head; and a share of a secret that is assumed to be utilized for group communication. Each of the keys and the share is of size p, which is the modulus size in the scheme, requiring a storage space of three p-bit keys. For computation overhead, our proposed scheme only needs to do a polynomial evolution, whereas in [10, 11], each sensor requires decrypting the message, computing a hash, and doing a polynomial evaluation. In [12], sensors are preloaded with the required keys and they do not need to do any computation to establish the keys. Our proposed scheme has low communication overhead since each sensor is preloaded with the shares and there is no need to transmit any data other than the sensor’s ID, which does not produce an overhead. On the other hand, the key establishment schemes in [10, 11] require many messages to be exchanged to authenticate sensor nodes and distribute polynomials used for generating the shared key, which shows a high communication overhead. In [12], the scheme shows high communication overhead due to the dynamic change of thresholds by the BS changes, which leads to reconstructing new shares for sensors nodes.Table 1
Comparing the proposed scheme with other schemes.
Comparison Criteria Proposed scheme [10] [11] [12] Storage overhead Two univariate polynomials(t+h) A univariate polynomial(R+1) Bivariate polynomial+Secret key 3p-bit keys  Computation overhead Polynomial evaluation Polynomial evaluation+Encryption/Decryption+Hash function Polynomial evaluation+Hash function -  Communication overhead Low High High High  Security against sensor-captured attack Probabilistic Deterministic Deterministic DeterministicThe problem with all deterministic key establishment schemes, including [10–12], is that their security is deterministic, so an attacker can successfully reconstruct the polynomial used to generate tokens after capturing t sensors and that compromises the security of the whole network. However, our proposed scheme is the first to provide probabilistic security for deterministic polynomial-based key establishment schemes, in which capturing more than t sensor nodes belonging to the same cluster has a very low probability, as explained in the security analysis section. In [12], if an attacker compromises a sensor, the attacker can obtain not only the network key that leads to compromising all data transmitted between sensors but also the cluster key that allows for the capture of all data transmitted between the compromised sensor and its cluster head. Thus, capturing one sensor leads to compromising the security of the whole WSN.


## 8.1. Storage Requirement

In our proposed scheme, only the sink needs to store a trivariate polynomial,Fx,y,z, where the degree of x isk-1, the degree of y ist-1, and the degree of z ish-1. In other words, the storage of the sink iskth coefficients inGF(p). Each CH with cluster identity, IDC, needs to store a bivariate polynomial, FIDC,y,zmod⁡p. The storage requirement of each cluster head isth coefficients inGF(p). Each sensor node with identity, idj∈IDC, needs to store two univariate polynomials, FIDC,y,idjmod⁡p and FIDC,idj,zmod⁡p. The storage requirement of each sensor node is t+h coefficients inGF(p). In summary, in our proposed hierarchical key management scheme, each sensor node located at the lowest level only needs to store a minimal number of coefficients, but the sink located at the highest level needs to store the most coefficients.


## 8.2. Computational Requirement

In the following discussion, we evaluate the computational requirements of various communication keys. Horner’s rule [33] can be used to reduce the computational cost in the polynomial evaluation. According to Horner’s rule, evaluating a univariate polynomial of degreeh-1 needsh-1 multiplications and h additions.(1)
Key between two sensor nodes. Two sensor nodes with their identities idj and idk in the same cluster can share a pairwise key FIDC,idk,idj if idj>idk or FIDC,idj,idk if idj<idk. For example, if idj>idk, sensor node with identity idj can use its token FIDC,y,idj which is a univariate polynomial iny having degreet-1 to obtain the shared key FIDC,idk,idj. It needst-1 multiplications andt additions. Similarly, sensor node with identity idk  can use its token FIDC,idk,z, which is a univariate polynomial inz having degreeh-1, to obtain the shared key. It needsh-1 multiplications andh additions.(2)
Key between sensor node and cluster head.Any cluster head with identity IDC  can use its bivariate polynomial FIDC,y,z to share a pairwise key, KC,idj=FIDC,IDC,idj, with any sensor node with identity idj, in the same cluster. The bivariate polynomial FIDC,y,z hast-1 degree in y andh-1 degree in z. The cluster needsth multiplications andth+t-1 additions.(3)
Key between sink and each cluster head. The sink can use its trivariate polynomial Fx,y,z to share a pairwise key, KS,C=FIDC,IDC,IDC, with any cluster head with identity IDC. The trivariate polynomial Fx,y,z hask-1 degree inx, t-1 degree in y, andh-1 degree in z. The sink needsk(th+1) multiplications andkth+kt-1 additions.


## 8.3. Communication Overhead

The proposed scheme has a low communication overhead for key establishment. After deployment, no information needs to be transmitted to establish the shared pairwise keys except the sensors’ IDs and that is a crucial step for self-organization protocols in WSN. Thus, there is no such overhead in key distribution schemes [1]. On the other hand, updating broadcast keys, which involves sending new broadcast keys to each sensor using the pairwise keys, may introduce some communication overhead.


## 8.4. Probabilistic Security

Our proposed scheme is the first polynomial-based key distribution scheme with probabilistic security. Unlike all polynomial-based schemes, in which capturingt or more than t sensors can recover the polynomial of degreet-1, which led to compromising the whole network security, the random deployment of sensors loaded with different polynomial structures makes it difficult to guarantee that t captured sensors belong to the same class. The proposed scheme allows sensors from the same cluster to communicate with each other since their tokens/shares are generated from the same polynomial structure. Thus, sensors from different categories cannot communicate with each other because they are preloaded with shares that are created from different polynomials. In order to reveal the polynomial used to generate the shares for sensors, the attacker needs to collect at least t sensors that all belong to the same cluster. In that way, the probability of finding such sensors is very low, which increases the difficulty of sensor capture attacks. This increased difficulty leads to the enhancement of the security of the WSN. We show the statistical analysis of the probabilistic security of the proposed scheme.In a WSN, ifn is the number of sensor nodes and l is the number of clusters, then r is the number of sensor nodes in each cluster (i.e., r=n/l). The probability of capturing t sensor nodes belonging to the same cluster is Pt=l.Ctr/Ctn. Figure 3 shows the probability of capturing t sensor nodes belonging to the same cluster for different threshold values. We can observe that this probability drops to zero very quickly after increasing the threshold value. Figure 4 shows this probability for a different number of clusters. Again, we observe that this probability drops to zero after increasing the number of clusters. Results show that our proposed scheme has probabilistic security and the probability of sensor capture attacks can be effectively reduced to be almost nonexistent by increasing the thresholdt (t≥3) or the number of clusters l (i.e., l≥4).Figure 3
The probability of capturingt sensors belonging to the same cluster with various thresholds (forl=4, n=40, r=10).Figure 4
The probability of capturingt sensors belonging to the same cluster with various numbers of clusters (forn=30, t=3).


## 8.5. Comparison

Table1 compares our proposed scheme with other polynomial-based schemes in [10–12]. Our proposed scheme stores two polynomial shares in each sensor. The degrees of the polynomials areh-1 andt-1; thus each sensor stores (t+h) coefficients. Compared to [10], each sensor node stores a master key and a univariate polynomial of degreeR, which means that each sensor storesR+1 coefficients. In [11], CHs generate shares to each sensor in its cluster, which are bivariate polynomials. In addition, each sensor is preloaded with a secret key. In [12], each sensor stores three keys: a network key that is used to secure communication between sensors; a cluster key that is used to secure communication between a sensor and its cluster head; and a share of a secret that is assumed to be utilized for group communication. Each of the keys and the share is of size p, which is the modulus size in the scheme, requiring a storage space of three p-bit keys. For computation overhead, our proposed scheme only needs to do a polynomial evolution, whereas in [10, 11], each sensor requires decrypting the message, computing a hash, and doing a polynomial evaluation. In [12], sensors are preloaded with the required keys and they do not need to do any computation to establish the keys. Our proposed scheme has low communication overhead since each sensor is preloaded with the shares and there is no need to transmit any data other than the sensor’s ID, which does not produce an overhead. On the other hand, the key establishment schemes in [10, 11] require many messages to be exchanged to authenticate sensor nodes and distribute polynomials used for generating the shared key, which shows a high communication overhead. In [12], the scheme shows high communication overhead due to the dynamic change of thresholds by the BS changes, which leads to reconstructing new shares for sensors nodes.Table 1
Comparing the proposed scheme with other schemes.
Comparison Criteria Proposed scheme [10] [11] [12] Storage overhead Two univariate polynomials(t+h) A univariate polynomial(R+1) Bivariate polynomial+Secret key 3p-bit keys  Computation overhead Polynomial evaluation Polynomial evaluation+Encryption/Decryption+Hash function Polynomial evaluation+Hash function -  Communication overhead Low High High High  Security against sensor-captured attack Probabilistic Deterministic Deterministic DeterministicThe problem with all deterministic key establishment schemes, including [10–12], is that their security is deterministic, so an attacker can successfully reconstruct the polynomial used to generate tokens after capturing t sensors and that compromises the security of the whole network. However, our proposed scheme is the first to provide probabilistic security for deterministic polynomial-based key establishment schemes, in which capturing more than t sensor nodes belonging to the same cluster has a very low probability, as explained in the security analysis section. In [12], if an attacker compromises a sensor, the attacker can obtain not only the network key that leads to compromising all data transmitted between sensors but also the cluster key that allows for the capture of all data transmitted between the compromised sensor and its cluster head. Thus, capturing one sensor leads to compromising the security of the whole WSN.


## 9. Conclusion

In this paper, we proposed a hierarchical key management and key distribution scheme. Our scheme is a deterministic key distribution scheme since it guarantees that a pairwise key is shared between any two arbitrary sensor nodes in a cluster, between a sensor node and its CH, and between the sink and each CH. Furthermore, our scheme has a probabilistic security feature that shows robustness against sensor capture attacks. Finally, our scheme requires sensor nodes of minimal memory, communication, and computational overhead.



---

*Source: 3950129-2019-07-14.xml*