** Int'l J. of Communications, Network and System Sciences** Vol.2 No.2(2009), Article ID:427,13 pages DOI:10.4236/ijcns.2009.22016

Hierarchical Hypercube Based Pairwise Key Establishment Scheme for Sensor Networks

^{1}College of Software, Hunan University, Changsha, Hunan, China

^{2}Department of Computer Science, Lakehead University, Thunder Bay, Canada

Email: wanglei@hnu.cn

Received November 27, 2008; revised January 17, 2009; accepted February 12, 2009

**Keywords:** Pairwise Key, Sensor Networks, Key Pool, Key Predistribution, H2 Framework

Abstract

Security schemes of pairwise key establishment, which enable sensors to communicate with each other securely, play a fundamental role in research on security issue in wireless sensor networks. A general framework for key predistribution is presented, based on the idea of KDC (Key Distribution Center) and polynomial pool schemes. By utilizing nice properties of H2 (Hierarchical Hypercube) model, a new security mechanism for key predistribution based on such model is also proposed. Furthermore, the working performance of tolerance resistance is seriously inspected in this paper. Theoretic analysis and experimental figures show that the algorithm addressed in this paper has better performance and provides higher possibilities for sensor to establish pairwise key, compared with previous related works.

1. Introduction

The security issue in wireless sensor networks has become research focus because of their tremendous application available in military as well as civilian areas. However, constrained conditions existent in such networks, such as hardware resources and energy consumption, have made security research more challenging compared with that in traditional networks.

Current research focus on such security schemes as authentication and key management issues, which are essential to provide basic secure service on sensor communications. Pairwise key establishment enables any two sensors to communicate secretly with each other. However, due to the characteristics of sensor nodes, it is not feasible to utilize traditional pairwise key establishment schemes.

Eeschnaure et al. [1] presented a probablitic key predistribution scheme for pairwise key establishment. This scheme picks a random pool (set) of keys S out of the total possible key space. For each node, m keys are randomly selected from the key pool S and stored into the node’s memory so that any two sensors have a certain probability of sharing at least one common key. Chan [2] presented two key predistribution techniques: q-composite key predistribution and random pairwise keys scheme. The q-composite scheme extended the performance provided by [1], which requires at least q predistributed keys any two sensor should share. The random scheme randomly pickes pair of sensors and assigns each pair a unique random keys. Liu et al. [3] developed the idea addressed in previous works and proposed a general framework of polynomial pool-based key predistribution. Based on such a framework, they presented random subset assignment and hypercube-based assignment for key predistribution.

However, it still requires further research on key predistribution because of deficiencies existent in those previous works. Since sensor networks may have dramatic varieties of network scale, the q-composite scheme would fail to secure communications as a small number of nodes are compromised. The random scheme may requires each sensor to store a large number of keys, which would be contradicted with hardware constraints of sensor nodes. The random subset assignment would not ensure any two nodes to establish a key path if they do not share a common key. Though the hypercubebased assignment can make sure that there actually exist a key path, however, the possibilities of direct pairwise key establishment are not perfect, leading to large communication overhead.

In order to improve possibilities of direct pairwise key establishment, and depress communication overhead on indirect key establishment, we propose a H2 (Hierarchical Hypercube) framework, combined with a new key predistribution scheme. Moreover two new fault tolerance model and corresponding indirect pairwise key establishment schemes are also proposed, by applying nice properties on tolerance resistance H2 model has provided. The schemes has better working performance on probabilities of pairwise key establishment between any two sensors.

2. Preliminaries

2.1. Notations and Definitions

Definition1(key predistribution): Cryptographic algorithms are pre-loaded in sensors before node deployment phase.

Definition2 (pairwise key): When any two nods share a common key denoted as E, we call that the two nodes share a pairwise key E.

Definition 3 (key path): Given two nodes A_{0} and A_{k}, which do not share a pairwise key, if there exists a path in sequence described as A_{0}, A_{1}, A_{2},……, A_{k}_{-1}, A_{k} and any two nodes A_{i}, A_{j} (0≤i≤k-1,1≤j≤k) share at least one pairwise key, we call that path as a key path.

Definition 4 (n-dimensional hypercube interconnection network): n-dimensional hypercube interconnection network H_{n} (abbreviation as n-cube) is a kind of network topology that has the following characteristics: 1) It is consisted with 2^{n}^{ }nodes and n·2^{n-}^{1} links; 2) Each node can be coded with a different binary string with n bits such as b_{1}b_{2}…b_{n}; 3) For any pair of nodes, there is a link between them if there is just one bit different between their corresponding binary strings.

Figure 1 illustrates the topology of a 4-dimensional hypercube interconnection network, which is consisted with 2^{4}=16 nodes and 4·2^{4}^{-}^{1}=32 links. And the nodes are coded from 0000 to 1111.

2.2. Related Works [1-3]

2.2.1. Polynomial-based Key Predistribution

In the scheme of polynomial-based key predistribution, the key setup server randomly generates a t-degree bivariate polynomial f(x,y)= over a

Figure 1. A 4-dimensional hypercube interconnection network.

finite field F_{q}, Notes that q is fairly large prime number and for any variables x and y, f(x,y)= f(y,x) is always held. Then the key server computes a share of f(x,y), denoted as f(i,y) for each node, where i is assumed to be a unique ID for any sensor node. Every node is pre-loaded with its own share before node-deployment phase. Thus for any two nodes i and j, node i can compute the common key f(i,j) by evaluating f(i,y) at point j, and vice visa.

To predistribute pairwise key with such a scheme as addressed above, node i's storage overhead includes two parts: One is (t+1)log q storage space for storing a tdegree polynomial f(i,y), the other is the storage space for its own ID information. [4] shows that this scheme has ability of t-collusion resistant. That is, if there exists no more than t compromised nodes in the network, the scheme can ensure the pairwise key is secure between any two normal nodes.

2.2.2. Polynomial Pool-based Key Predistribution

Pairwise key establishment in this scheme is processed in the following three phase: polynomial pool generation and key predistribution, direct key establishment, and path key establishment.

1) polynomial pool generation and key predistribution: This phase is mainly concerned with t-degree bivariate polynomial pool (F) generation over a finite field F_{q}. Then a subset F_{i}F is selected and the shares of all of the polynomials in this subset are assigned to the node i.

2) direct key establishment: Assume that node i and j wants to establish pairwise key, if they have a common share on a same polynomial, they can establish pairwise key by utilizing the polynomial-based scheme. This phase is performed as follows: node i may broadcast an encryption list, , , v=1,2,…, |F_{i}|, where K_{v} is the share of the vth polynomial at point j. If node j can decrypts any one of these correctly, that means there exists a common share between the two nodes.

3) path key establishment: If there no pairwise key existent between node i and j, it’s necessary to find a key path defined in Definition3. Then the two nodes transmits secret information for pairwise key generation on this path.

2.2.3. Random Subset Assignment and Hypercube-Based Assignment

1) Random Subset Assignment: Different from polynomial scheme, the main idea of this assignment is to pick a random subset of polynomial pool, denoted as F_{i}F, and assign the share of this subset to node i.

2) Hypercube-based Assignment: Based on the concept of random subset, this assignment generates polynomial pool by utilizing hypercube model, and assign subsets to nodes according to node’s ID.

3. H2 (Hierarchical Hypercube) Model

Definition 5 (H2 diagram): Assume that there exist 2^{n} nodes, the construction algorithm of n-dimension H2(n) is illustrated as follows:

1) Each nodes are connected as a dimensional hypercube, in which nodes are coded from -, and such kind of node code is called Inner-Hypercube-Node-Code. As a result, different such kind of dimensional hypercubes can be formed, where represents the upper integer operation, and means the lower integer operation.

2) The obtained different such kind of dimensional hypercubes are codes from -, and such kind of node code is called Outer-Hypercube-Node-Code. And then, the nodes in the different such kind of dimensional hypercubes with the same Inner-Hypercube-Node-Code are connected as a dimensional hypercube, so we can obtain different such kind of dimensional hypercubes.

3) The graph constructed through the above two steps is called a H2 graph. And it is obvious that each node in the H2 graph is coded as (r,h), where r (≤r≤) is the node’s Inner-Hypercube-Node-Code, and h (≤h≤) is the node’s OuterHypercubeNode-Code.

Theorem 1: There exist 2^{n} in H2(n) diagram.

Proof: The conclusion is naturally held as 2^{n}= *.

Theorem 2: The diameter of H2 (n) is n.

Proof: As the diameter of dimension hypercube is, and it is naturally held for the case of dimension hypercube. Thus the diameter of H2(n) is +=n according to definition5.

Theorem 3: The distance of any two nodes A(r_{1},h_{1}) and B(r_{2},h_{2}) in H2(n) is expressed as d (A,B)= d_{h}(r_{1}, r_{2})+d_{h}(h_{1}, h_{2})+1 where d_{h} is Hamming distance.

Proof: Since the distance of any two nodes is the Hamming distance of their corresponding codes, it is held according to definition5.

4. Pairwise Key Establishment Scheme Based on H2 Model

As addressed above, polynomial-based and polynomoial-based schemes have some limitations. In this section we propose a new pairwise key establishment and predistribution scheme based on H2 model. The new algorithm is composed of three phases: polynomial pool generation and key predistribution, direct key establishment, and path key establishment.

4.1. Polynomial Pool Generation and Key Predistribution

Assume that there are N nodes in a wireless sensor network, where 2^{n}^{-1}< N 2^{n}. A n-dimension H2(n) is then generated and we construct a polynomial pool with the following method:

1) The key setup server randomly generates n*2^{n} bivariate t-degree polynomial pool over a finite fields F_{q} ,denoted as F={ (x,y), (x,y)| 01,1i, 01,1j}.

2) The bivariate polynomials, denoted as { (x,y)| 01}, where 1j, are assigned to the jth dimension of the th hypercube in H2(n).

3) The bivariate polynomials, denoted as{ (x,y)| 01} where1 i, are assigned to the ith dimension of the th hypercube in H2(n).

4) For any nodes (,) in H2(n), the polynomial shares, denoted as { (x,y), (x,y),…, (x,y)} { (x,y), (x,y),…, (x,y)}, are assigned and pre-loaded before deployment phase.

5) The server assigns a unique ID, denoted as (, , to every node in sequence, where 01, 0 1.

4.2. Direct Key Establishment

If any two nodes A(,) and B(,) want to establish pairwise key, the node A can achieve the pairwise key with B by processing the following procedures:

Node A first computes the Hamming distance between B and itself, as d_{1}=d_{h}(,), d_{2}=d_{h}(,). If d_{1}=1 or d_{2}=1, the node can establish the pairwise with the peer according to the conclusion of the Theorem 4.

Theorem 4: For any two nodes A(,) and B(,), If the Hamming distance d_{h}(,)=1, or d_{h}(,) =1, then there exists certainly pairwise key between A and B.

Proof: 1) d_{h}(,)=1: Assume that i_{t}=, where 1t-1. Since (,) = (,). So, There exists a pairwise key (,) between A and B.

2) d_{h}(,)=1: Imitating the step 1), it is easy to prove that there exists a pairwise key between A and B.

4.3. Indirect Key Establishment

If d_{h}(,)>1 and d_{h }(,) >1 then node A establish indirect pairwise key with B according to Theorem 5. In order to make it clear, we will provide a lemma before the illustration of Theorem 5.

Lemma1: For any two nodes A(,) and B(,), assume that d_{h}=k, then there exists a k-distance path denoted as I_{0}(=A), I_{1},…,I_{k}_{-1}, I_{k}(=B), where d_{h} (I_{i},I_{j})=1.

Proof: According to Theorem 3, d_{h} can be expressed as d_{h}(,)+d_{h}(,)=k. Assume that d_{h}(,)=h, then d_{h}(,)=k-h. According to definition5, node C(,) and A are located in a -dimensional hypercube H, and node C and B are located in a -dimensional hypercube. According to the properties of hypercube [5,6], there exist a path described as I_{0}(=A), I_{1},…, I_{h}_{-1}, I_{h}(=C) in H, where d_{h}(I_{i}, I_{j})=1. Similarly, another path with the same property is existed in, denoted as I_{h}(=A), I_{h}_{+1}, …, I_{k}_{-1}, I_{k}(=B), where d_{h} (I_{i},I_{j})=1.

Thus there exist a integrated path in H2 diagram from node A to B, described as I_{0}(=A), I_{1},…,I_{k}_{-1}, I_{k}(=B) where d_{h} (I_{i}, I_{j})=1.

Theorem 5: Assume that any two nodes can communicate directly in a wireless sensor networks, and there is no compromised node in the networks, then there exist a key path for any node A(,) and node B (,).

Proof: According to Lemma1, there exist a path for any two nodes where d_{h}=k in H2 diagram. Thus the conclusion is held.

We propose the algorithm for indirect key establishment as follows. Assume the two nodes A(,) and node B(,) want to establish indirect pairwise key in the network, we propose the algorithm for indirect key establishment illustrated as follows.

Indirect_Key_Establishing_Algorithm(){

1) Node A computes a set L which records the dimensions in which node A and B have different sub-indexes. The set can be expressed as L={(d_{1},d_{2},…,d_{k}),(g_{1},g_{2},…,g_{w})} where d_{1}< d_{2}< …< d_{k}, g_{1}< g_{2}< …< g_{w}.

2) Node A maintains a path set P with initial vale of P={A}.

3) Assume that U(,) =A; s=1.

4) Node A computes intermediate nodes expressed as V=(,). And P=P{V}.

5) Assume that U =V.

6) If s< k, then s=s+1, and repeats the step 4, otherwise turns to step7).

7) Node A computes intermediate nodes V= (,), and let P=P{V}.

8) Let U =V.

9) If s< w, then s=s+1, and repeats step7); otherwise go on step10).

10) Let P=P{B}.

}

According to Theorem 5, any node can compute a key path to it destination when there is no compromised node in the network. Once the path P is achieved, the two nodes can exchange secret information to generate pairwise key between themselves.

For example, the node A((001), (0101)) and the node B((100), (1100)) can establish pairwise key along the following key path: A((001), (0101)) ((101), (0101)) ((100), (0101)) ((100), (1101)) B((100), (1100)).

According to the algorithm described above, the following conclusion is naturally held.

Theorem 6: Assume that any two nodes can communicate with each other directly, and there is no compromised node in a network. If the distance between the two nodes is k, then there exists a key path with distance of k. That is, the two nodes can establish pairwise key through k-1 intermediate nodes.

4.4. Dynamic Key Path Establishment

The Indirect_Key_Establishing_Algorithm() illustrated in Subsection 4.3 can only deal with the situation that there is no compromised node in the network. However, in case of some existent compromised nodes, the algorithm would fail to find fungible intermediate node to help establish pairwise key.

We further analyze the example addressed in Subsection 4.3. When the node ((101),(0101)) is compromised, the node A and B can utilize the following path to establish pairwise key: A((001), (0101)) ((000),(0101)) ((100), (0101)) ((100), (1101)) B((100), (1100)).

When the node ((100),(1101)) is compromised, the two nodes can use the path: A((001), (0101)) ((101), (0101)) ((100), (0101)) ((100), (0100)) B((100), (1100)).

In case that the nodes ((101),(0101)),((100),(1101)) are compromised, there still exists a key path denoted as A((001),(0101)) ((000),(0101)) ((100),(0101)) ((100),(0100)) B((100),(1100)).

4.4.1. Relative Definitions of Local Weak Connectivity

Definition 6: The nodes A and B in a n-dimensional hypercube H_{n} are called neighbors, if that there exists only one different bit in their binary strings.

Definition 7: The node A in an m-dimensional hypercube/sub-hypercube H_{m} is m-disconnected, iif that all links between A and every faultless node in H_{m} are fault. The node A in an m-dimensional hypercube/subhypercube H_{m} is reachable, iif that A is faultless and not m-disconnected.

Definition 8 (k-dimensional local-weak-connectivity): A n-dimensional hypercube H_{n }is k-dimensional local-weak-connected, if all reachable nodes in each k-dimensional sub-hypercube H_{k }(k1) of H_{n }forms a connected graph, and the number of reachable nodes in H_{k} _{ }is bigger than.

Definition 9 (general local-weak-connectivity): An ndimensional hypercube H_{n }is general local-weakconnected, if there exists a h-dimensional sub-hypercube H_{h }(hk), which is local-weak-connected and includes H_{k}, as for each k-dimensional sub-hypercube H_{k }(k1) of H_{n}.

Figure 2 presents a 3-dimensional hypercube H_{3} with two fault nodes and a 3-disconnected node. According to the above two kinds of local-weak-connectivity concepts, it is easy to prove that all reachable nodes in H_{3 }is global connected.

4.4.2. Global Connectivity of Local-Weak-Connected Hypercube

An n-dimensional hypercube H_{n} has nodes, in which each node can be represented by a binary string and has n different links. So H_{n} has n different links totally.

Definition 10: Any binary string…with given length n-k corresponds a k-dimensional sub-hypercube H_{k} with nodes, and the nodes in H_{k} can be represented by such binary strings as…*…*, where * can be 0 or 1.

From the construction algorithm of H_{k}, it is easy to know that all k-dimensional sub-hypercubes_{ }are isomor

Figure 2. A 3-dimensional hypercube H3 with fault nodes and links. In which, the black dots represent fault nodes, the white dots represent faultless nodes, the lines with tokens represent fault links, and the lines without tokens represent faultless links.

phic, and H_{n }includes all of the k-dimensional sub-hypercubes that is isomorphic with H_{k}. And it is easy to prove that H_{n }includes -1 k-dimensional subhypercubes that is isomorphic with H_{k} and has no common nodes with H_{k} also.

Lemma 2: All of the reachable nodes in any two neighboring k-dimensional sub-hypercubes_{ }of the LocalWeak-Connected n-dimensional Hypercube H_{n }form a connected graph.

Proof: Let that H_{k }and are two neighboring k-dimensional sub-hypercubes, according to definition 10, we can utilize binary strings…*…* to represent the nodes in H_{k}, where * can be 0 or 1. Since H_{k }and are neighboring, so there exists at least one common node between H_{k }and the nodes in can be represented as…*…*…**…* and……*…**…*H_{k}.……*…**…*H_{k}. Considering that the number of reachable nodes in is bigger than there exists at least one node A in those nodes represented by……*… **…* is reachable. Since AH_{n}Node A and all of the reachable nodes in form a connected graph. And in addition, since A Node A and all of the reachable nodes in form a connected graph also. So, all of the reachable nodes in H_{k }and form a connected graph.

Theorem 7: All of the reachable nodes in n-dimensional Hypercube H_{n}, which satisfies the conditions of k-dimensional local-weak-connectivity, form a connected graph.

Proof: From Theorem 2, it is easy to prove that the conclusion stands.

From Theorem 7, we can obtain the following deduces easily.

Deduce 1: If n-dimensional Hypercube H_{n} satisfies the conditions of k-dimensional local-weak-connectivity, then all of the reachable nodes in any h-dimensional sub-hypercube H_{h}(hk) form a connected graph.

Deduce 2: If n-dimensional Hypercube H_{n} satisfies the conditions of k-dimensional local-weak-connectivity, then there exists at least a pair of connected reachable nodes…0……and…1……between any pair of k-dimensional sub-hypercubes of…0…*…* and…1…*…*.

Proof: From deduce 1, if n-dimensional Hypercube H_{n} satisfies the conditions of k-dimensional local-weak-connectivityAll of the reachable nodes in any h-dimensional sub-hypercube H_{h}(hk) form a connected graph All of the reachable nodes in any (k+1)-dimensional sub-hypercube…*…*…* form a connected graph. And since the numbers of unreachable nodes in k-dimensional sub-hypercubes…0…*…* and…1…*…* are less than a half of the number of total nodes respectively. So, there exists reachable node…0……in…0…*…*, and there exists reachable node…1……in…1…*…* certainly. And in addition, those two nodes…0……and…1……is connected.

Theorem 8: All of the reachable nodes in n-dimensional Hypercube H_{n}, which satisfies the conditions of general local-weak-connectivity, form a connected graph.

Proof: Since n-dimensional Hypercube H_{n} is localweak-connected, and there exists no other sub-hypercubes that include itself in H_{n}. So, from definition 9, it is easy to know that H_{n} is n-dimensional local-weak-connected. And in addition, from definition 8, we can know that all of the reachable nodes in H_{n }form a connected graph.

Theorem 7 and Theorem 8 show that the hypercubes, that satisfy the conditions of the proposed two kinds of local-weak-connectivity, must be global connected.

4.4.3. K-Dimensional Local-Weak-Connectivity Based Dynamic Key Path Establishment Algorithm

KLWC-based Dynamic_Key_Path_Establishing_Algorithm(){

Input: Sensor network H_{n} with fault nodes and fault links (The links, whose length are bigger than the transmitting radius). And two reachable nodes A(,) and B(,) in H_{n}.

Output: A correct key path P from A to B in H_{n}.

1) Compute and determine the node T= (,) in;

2) P=Dynamic_Key_Path_Establishment_1 (A,T);

3) P=P Dynamic_Key_Path_Establishment_2 (T, B);

4) If P is a correct key path from A to B, then exit, otherwise turn to step 5);

5) Compute and determine the node T=(,) in;

6) P=Dynamic_Key_Path_Establishment_2 (A,T);

7) P=P Dynamic_Key_Path_Establishment_1 (T, B);

8) If P is a correct key path from A to B, then exit, otherwise turn to step 9);

9) Report A, failure to establish a key path from A to B.

}

Algorithm Dynamic_Key_Path_Establishment_1(A,T):

1) Obtain the codes of nodes A and T: A (,), T (,);

/* From definition 10, we can suppose that the k-dimensional sub-hypercube that includes T is ((…*…*),).*/

2) Initialize Path P: PA;

3) Initialize temporary binary string C: C=(,)A;

4) FOR(j=1; j; j++){

IF(){

①According to lemma2 and deduce 1, a pair of connected reachable nodes C and D can be found through discovering in neighboring k-dimensional subhypercubes:

C=(,)D=(,), where = (t [1, j]);

②Join the path from (,) to node D into P;

③CD;

}

}

/* After the above steps, a correct key path from node A(,) to the reachable node ((……),) will be constructed. */

5) Join the path from node ((…),) to node T in the k-dimensional sub-hypercube ((…**),) into P. And then exit. So, a correct key path from node A to node T is discovered.

Algorithm Dynamic_Key_Path_Establishment_2(T, B):

1) Obtain the codes of nodes B and T: T (,); B (,);

/* From definition 10, we can suppose that the k-dimensional sub-hypercube that includes B is (,(…*…*)).*/

2) Initialize Path P: PT;

3) Initialize temporary binary string C: C=(,) T;

4) FOR(l=1; l; l++){

IF(){

① According to lemma2 and deduce 1, a pair of connected reachable nodes C and D can be found through discovering in neighboring k-dimensional sub-hypercubes:

C=(,);

D=(,), where = (t [1, l]).

②Join the path from (,) to node D into P;

③ CD;

}

}

/* After the above steps, a correct key path from node T(,) to the reachable node (, (……)) will be constructed. */

5) Join the path from node (, (……)) to node B in the k-dimensional sub-hypercube (, (…**)) into P. And then exit. So, a correct key path from node T to node B is discovered.

From the above description, we can know that the time complexity of algorithm Dynamic_Key_Path_ Establishment_1 is

+=, and the time complexity of algorithm Dynamic_Key_Path_Establishment_2 is +=, so the total time complexity of the k-Dimensional LocalWeak-Connectivity based Dynamic Key Path Establishment Algorithm is.

Considering the percentage of the fault nodes in sensor networks, when applying the k-Dimensional Local-Weak-Connectivity based Dynamic Key Path Establishment Algorithm actually, we can set k=1,2,3. Then the total time complexity of the k-Dimensional Local-Weak-Connectivity based Dynamic Key Path Establishment Algorithm will be only. Figure 3 illustrates the relationship of dimension n and the scale of the sensor networks.

4.4.4. General Local-Weak-Connectivity Based Dynamic Key Path Establishment Algorithm

GLWC-based Dynamic_Key_Path_Establishing_Algorithm(){

Input: Sensor network H_{n} with fault nodes and fault links (The links, whose length are bigger than the transmitting radius). And two reachable nodes A(,) and B(,) in H_{n}.

Output: A correct key path P from A to B in H_{n}.

1) Compute and determine the node T=(,) in;

2)P=Dynamic_Key_Path_Establishment_3(A, T);

3)P=P Dynamic_Key_Path_Establishment_4(T, B);

4)If P is a correct key path from A to B, then exit, otherwise turn to step 5);

5)Compute and determine the node T=(,) in;

6)P=Dynamic_Key_Path_Establishment_4(A, T);

7)P=P Dynamic_Key_Path_Establishment_3(T, B);

8)If P is a correct key path from A to B, then exit, otherwise turn to step 9);

9)Report A, failure to establish a key path from A to B.

}

Algorithm Dynamic_Key_Path_Establishment_3(A, T):

1)Obtain the codes of nodes A and T: A (,), T (,);

/* From definition 10, we can suppose that the k-dimensional sub-hypercube that includes T is ((…*…*),).*/

2)Initialize Path P: PA;

3)Initialize temporary binary string C: C=(,)A;

4)FOR(j=1; jn; j++){

IF(){

FOR(k=1; kn-j; k++){

IF(According to Theorem 8, a pair of connected reachable nodes C and D can be found through discovering in neighboring k-dimensional sub-hypercubes:

C=(,)D=(,), where = (t [1,j]);

①Join the path from

(,) to node (,) into P;

②C (,

);

③Break;

}

}

IF(k >n-j){

WHILE(kn){

IF(In the k-dimensional hypercube

(,), there exists no faultless key path from node C to node T) k++;

}

}

IF( k > n) exit. Then is not general local-weak-connected, and we cannot find a correct key path from node A to T.

ELSE Join the path from C to T in the k-dimensional hypercube (,) into P;

}

}

5) Exit. And a correct key path from A to T is discovered.

Algorithm Dynamic_Key_Path_Establishment_4(T, B):

1) Obtain the codes of nodes T and B: T (,) and B (,);

/* From definition 10, we can suppose that the k-dimensional sub-hypercube that includes B is (,(…*…*)).*/

2) Initialize Path P: PT;

3) Initialize temporary binary string C: C=(,) T;

4) FOR(l=1; ln; l++){

IF(){

FOR(k=1; kn-j; k++){

IF(According to Theorem 8, a pair of connected reachable nodes C and D can be found through discovering in neighboring k-dimensional sub-hypercubes:

C=(,)D=(,)where = (t [1,j]);

①Join the path from (,) to node (,) into P;

②C (,

);

③Break;

}

}

IF(k >n-j){

WHILE(kn){

IF(In the k-dimensional hypercube (,), there exists no faultless key path from node C to node B) k++;

}

}

IF(k > n) exit. Then is not general local-weak-connected, and we cannot find a correct key path from node T to B.

ELSE Join the path from C to B in the k-dimensional hypercube (,) into P;

}

}

5) Exit. And a correct key path from T to B is discovered.

From the above description, we can know that the time complexity of algorithm Dynamic_Key_Path_ Establishment_3 is +=, where is the smallest integer that satisfies the condition of k-dimensional local-weak-connectivity. And the time complexity of algorithm Dynamic_Key_Path_Establishment_4 is +=, so the total time complexity of the general Local-WeakConnectivity based Dynamic Key Path Establishment Algorithm is.

Considering the percentage of the fault nodes in sensor networks, when applying the general LocalWeakConnectivity based Dynamic Key Path Establishment Algorithm actually, we can set k=1,2,3. Then the total time complexity of the General Local-WeakConnectivity based Dynamic Key Path Establishment Algorithm will be only.

5. Analysis

5.1. Feasibilities of the Algorithm

Theorem 9: In our algorithm, the possibility of direct key establishment for any two nodes can be expressed as P_{H}_{2} ()/(N-1).

Proof: As the algorithm has assigned any node, denoted as (,), shares of polynomials expressed as F_{A }= { (j_{1},y), (j_{2},y),…, (,y)} { (i_{1},y), (i_{2},y),…, (,y)}. It’s clear that there are nodes which can establish direct pairwise key with the node A. Thus P_{H}_{2} ()/(N-1) as the network scale is within the area 2^{n}^{-1}< N 2^{n}.

Suppose that a sensor network has N=10000 sensor nodes, then n=14. The possibility of direct key establish is about P_{H}_{2}2.56% according to the conclusion drawn by Theorem 6. However, the possibility decreases to P_{H}0.14% if the algorithm addressed in [3] is used.

Theroem10: Assume that the possibility of direct key establishment in H2-based scheme is defined as P_{H}_{2}, while the possibility in hypercube is denoted as P_{H}, then P_{H}_{2}>>P_{H}.

Proof: Suppose the number of a network is within the area of 2^{n}^{-1}< N 2^{n}, and P_{H} as addressed in [3]. Thus ==0.

5.2. Overhead AnalysisNode’s Storage Overhead

1) Any node is required to store t-degree bivariate polynomials whose number is n over the finite fields q, which occupies n(t+1)log q bits.

2) In order to keep the security of the Keys, for any bivariate polynomial f(x,y), node A is required to store the ID information of the compromised nodes that can establish direct key with A by using f(x,y). Since the degree of f(x,y) is t, then f(x,y) will be divulged when there are more than t nodes are compromised. So, for any bivariate polynomial f(x,y), node A needs only to store the ID information of n compromised nodes that can establish direct key with A by using f(x,y). In addition, since the node’s ID is a vector of n bits, and from Theorem 4, we can know that node A needs only to store one bit for each compromised node to determine the whole ID information of the compromised node. So, the total storage cost is nt bits.

3) Also the node’s own ID information occupies about n bits storage space, as it is expressed as (,).

All of the storage overhead address above sum up to n(t+1)log q+nt+n= n(t+1)log 2q bits.

Theorem 11: The H2-based and the hypercube-based schemes have the same storage overhead.

Proof: According to the analysis on storage overhead addressed in Subsection 5.4 in [3], the result is certainly held.

Communication Overhead

In a sensor network, sending a unicast message between two arbitrary nodes may involve the overhead of establishing a route. In case of no compromised node existent in the network, any one node can communicate with the others directly. Assume that the overhead for a hop is defined as 1, then for two arbitrary nodes whose Hamming distance is L, the minimum communication overhead is L. We further inspect average communication overhead on H2-based path key establishment.

Suppose there are two nodes A(,) and B(,) In the formal part of node’s code, the probability of =, e{1,…, } is 1/2; Similarly, the probability of =, e{1,…, } is also 1/2 in the latter code part. Thus the probability for the two nodes to have i different sub-index in the formal part is expressed as P[i different sub-indexs in former part]=. In the latter part, we also have:

P[j different sub-indexs in later part]=.

Thus the average communication overhead can be summarized as:

L=+.

Theroem12: The average communication overhead in the H2-based scheme is less than that in the hypercube-based scheme.

Proof: According to the analysis on communication overhead addressed in Subsection 5.4 in [3], the result is certainly held.

Figure 5 shows that the comparison on communication overhead between the H2-based scheme and the hypercube-based scheme.

5.3. Security Analysis

Here we put focus on two types of attacks against H2-based scheme: 1) An adversary may compromise pairwise key between any two nodes or prevent them to establish a pairwise key. 2) The adversary may focus its power to attack against the whole network, for purpose of lowering the probability of pairwise key establishment, or in creasing communication cost.

5.3.1. Attacks against Pairwise Key between Two Nodes

Figure 3. The relationship of dimension n and the scale of the sensor networks.

Figure 4. The comparison of probability to establish direct key between H2-based and Hypercube-based algorithms.

Figure 5. The comparison on average communication overhead between the H2-based and the Hypercube-based schemes.

1) Suppose an adversary launches an attack against two particular nodes, in order to filch their pairwise key. In case that those two nodes are not compromised:

① If the node u and v can establish direct pairwise key, the only means to compromise the key is to resolve the polynomial f(x,y), which is shared by the two nodes. As the degree of this polynomial is adversary t, the adversary is required to compromise at least t+1 compromised nodes with the same share of f(x,y).

② If the node u and v need to establish indirect pairwise key, the adversary is required to compromise an intermediate node, or filch the common share of the bivariate polynomial f(x,y) between the two nodes. However, even if the adversary succeeds to achieve the pairwirse key, the nodes u and v can also select alternatives to re-establish key path.

2) Suppose the adversary launch attacks to prevent pairwise key establishment against two particular nodes, denoted as u and v, which are assumed are not compromised. Then the adversary is required to compromise n bivariate polynomials of the node u or v. Notes that to those polynomials are t-degree, which means that if such attacks succeeded, at least n(t+1) nodes should have been compromised.

As addressed above and analysis presented in Subsection 5.5.1 in [3], if an adversary launches attacks against nodes, the security of the H2-based scheme if equivalent with that of the hypercube-based scheme. That is, we have the following theorem.

Theorem 13: The security of the H2-based scheme if equivalent with that of the hypercube-based scheme.

5.3.2. Attacks against the Whole Network

Suppose that an adversary has known the distribution state of polynomials for each node, he would launch attacks against the whole network systematically by compromising polynomials one by one. Assume that the adversary has compromised l bivariate polynomials, which means that at most nodes have been pre-loaded one of those compromised polynomials. However, the rest of the regular nodes, denoted as N- do not contain compromised polynomial shares. That means N- nodes can still work properly. Notice that those regular nodes should avoid to use compromised shares to establish pairwise key.

Clearly, the number of nodes influenced by adversaries in the H2-based scheme is more than that in the hypercube-based scheme. However, on the condition that the adversary fails to compromise all of the polynomials, the effected nodes can select other regular nodes to establish pairwise key with others.

In addition, it has proved that the probability of direct key establishment in the H2-based scheme is much higher than that in the hypercube-based scheme. Thus in the process of direct key establishment among noncompromised nodes, the degree of the influence cause by adversaries on the H2-based scheme is less than that on the hypercube-based scheme. That means the the H2-based scheme has ability to secure communications among nodes effectively in sensor networks.

5.3.3. Security Performance

Based on the nice properties of fault tolerance in H2-baed scheme, a source node can re-establish pairwise key with the destination by selecting alternative key path.

As addressed in Subsection 4.1, the polynomial pool has n*2^{n} bivariate t-degree polynomials, that is, |F|=n*2^{n}; As every node contains n different polynomial shares, given a particular share of a bivariate polynomial f, the probability for each node to contain such a share is n/|F|. Assume that the number of nodes in a network is 2^{n}^{-1}< N 2^{n}, and the number of supposed compromised node is, the probability for those compromised nodes to contain i shares of f is P_{i}=

As the adversary needs to compromise at least t+1 nodes to filch f, the probability of being compromised for f is P_{c}=1-.

According to Theorem 6, the compromised probability of direct key establishment for any two non-compromised nodes is expressed as P_{link}= P_{c}P_{H}_{2}, in case that a particular polynomial f is compromised.

Figure 6 shows the fraction of compromised direct keys between non-comrpomised nodes as a function of the number of compromised keys for H2 and hypercube-based schemes where N=30000 and t=2.

Figure 6 shows that based on the assumption of same network scale and the proportion of compromised nodes, H2-based scheme provides higher probability than hypercube-based scheme for direct key establishment between any two non-compromised nodes. H2-based scheme would not fail to establish direct key until the proportion increases to 40%, while for Hypercube-based scheme, accepted proportion is about 30%.

We further inspect the probability of compromised indirect key. As addressed in Theorem 6, the probability of direct key establishment for any two nodes is P_{H}_{2 }()/(N-1), the probability of indirect key establishment can be expressed as 1-P_{H}_{. }Thus the probability of compromised indirect key is estimated as (1-P_{H}_{2}) [1-(1-) (1-P_{c})^{2}].

Figure 7 shows that the probability of compromised indirect key between any two non-compromised nodes is a function of the fraction of compromised nodes where N=30000 and t =2.

Figure 7 shows that based on the same conditions of network scale and fraction of compromised nodes, H2-based scheme has better performance than hypercube-based scheme on indirect key establishment. The figure also shows that H2-based scheme would not fail to establish indirect key until the fraction of compromised nodes rises up to 60%. However, the fraction is only about 40% for Hypercube-based scheme.

Here we consider overall security performance of the two schemes. We define the probability of compromised pairwise key ( direct or indirect key) is P_{key}=P_{H}_{2}P_{c}+(1-P_{H}_{2})[1-(1-)].

Figure 8 shows that the probability of compromised pairwise key is a function of the fraction of compromised nodes where N=30000 and t=2 for the two schemes.

From Figure 8, we can know that the probability of the pairwise key between any two non-compromised nodes when the H2-based scheme is applied, is lower than that when the Hypercube-based scheme is applied, supposing that the scale and percentage of compromised nodes of the sensor networks are the same.

So, from the above description, it is obvious that the security performance of the H2-based scheme is better than that of Hypercube-based scheme.

The Probability of Pairwise Key Re-estab-lishment

A source node has to re-establish key path to the destination once some intermediate nodes have been compromised. According to the previous presented two kinds of dynamic key path establishing algorithms, it is easy to know that the algorithms can find a new alternative key path certainly, when k =1,2 or 3, as long as the distribution of the compromised nodes in the whole sensor network satisfy the conditions of 1,2 or 3- dimensional local-weak-connectivity. Next, lets analyze the probability of pairwise key reestablishment when the distrivution of the compromised node do not satisfy the conditions of 1,2 and 3-dimensional localweakconnectivities.

According to the pairwise key establishment scheme addressed above, each node in a network is able to communicate nodes to establish direct pairwise key. Assume that the fraction of compromised nodes is p, then the number of non-compromised nodes among is (1-p)* (). On the condition that a key path is available among those non-compromised nodes, it’s certainly possible for a source node and the destination to establish indirect pairwise key. So, when the distrivution of the compromised node do not satisfy the conditions of 1,2 and 3-dimensional local-weak

Figure 6. The relation between the fraction of compromised direct keys and the number of compromised nodes in H2- based scheme and Hypercube-based scheme.

Figure 7. The comparison on the fraction of compromised indirect keys-number of compromised nodes relation between the H2-based scheme and the Hypercube-based scheme.

Figure 8. The comparison on the fraction of compromised keysnumber of compromised nodes relation between the H2-based scheme and the Hypercube-based scheme.

Figure 9. The relation between the probability of reestablished keys and the number of compromised nodes in the H2-based and Hypercube-based schemes.

connectivities, the probability of pairwise key re-establishment can be estimated as:

P_{re}=1-

Assume that N=30000 and t=2, Figure 9 shows that the probability of pairwise key re-establishment is a function of number of compromised nodes in H2 and hypercube-based schemes. It also shows that the probability of pairwise key re-establishment in H2 scheme is higher than that in hypercube-based scheme for any two non-compromised nodes.

6. Conclusions

An H2-based key predistribution scheme is proposed. Compared with polynomial pool-based scheme, it can improve working performance on probability of direct key establishment without additional storage requirement.

Moreover, experimental figures show that our algorithm has lower communication cost and more secure than previous related works.

7. Acknowledgment

This work was supported in part by the China Scholarship Council (CSC) in form of a scholarship that funds the author, Lei Wang, studying at Lakehead University as a visiting researcher in Canada.

8. References

[1] L. Eeschnaure and V. D. Gligor, “A key-management scheme for distributed sensor networks,” in proceedings of the 9th ACM Conference on Computer and Communication Security, pp. 41-47, 2002.

[2] H. Chan, A. Oerrig, and D. Song, “Random key predistribution schemes for sensor networks,” in IEEE Syposium on Research in Security and Privacy, pp. 197-213, 2003.

[3] D. G. Liu, P. Ning, and R. F. Li, “Establishing pairwise keys in distributed sensor networks,” ACM Journal Name, Vol. 20, pp. 1-35, 2004.

[4] C. Blundo, A. Desantis, S. Kutten, et al., “Perfectly secure key distribution for dynamic conferences,” in Advances in Cryptology-CRYPTO’92, LNCS, 740, pp. 471-486, 1993.

[5] L. Wang and Y. P. Lin, “Maximum safety-path matrices based fault-tolerant routing for hypercube multi-computers,” Journal of Software, Vol. 15, No. 7, pp. 994-1004, 2004.

[6] L. Wang and Y. P. Lin, “A fault-tolerant routing strategy based on maximum safety-path vectors for hypercube multi-computers,” Journal of China Institute of Communications, Vol. 16, No. 4, pp. 130-137, 2004.