Researches on Scheme of Pairwise Key Establishment  for DistributedSensor Networks  Wang Lei  Fujian University Technology  Fuzhou,Funjian, PR.China  (+)86-591-8755-9001, 350014  wanglei_hn@hn165.com  Chen Zhi-ping  Fujian University Technology  Fuzhou,Funjian, PR.China  (+)86-591-8755-9001, 350014  jt_zpchen@hnu.cn  Jiang Xin-hua  Fujian University Technology  Fuzhou,Funjian, PR.China  (+)86-591-8755-9001, 350014  xhj@csu.edu.cn  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 new kind of cluster deployed sensor networks  distribution model is presented, and based on which, an  innovative Hierarchical Hypercube model - H(k,u,m,v,n) and the  mapping relationship between cluster deployed sensor networks  and the H(k,u,m,v,n) are proposed. By utilizing nice properties of  H(k,u,m,v,n) model, a new general framework for pairwise key  predistribution and a new pairwise key establishment algorithm  are designed, which combines the idea of KDC(Key Distribution  Center) and polynomial pool schemes. Furthermore, the working  performance of the newly proposed pairwise key establishment  algorithm is seriously inspected. Theoretic analysis and  experimental figures show that the new algorithm has better  performance and provides higher possibilities for sensor to  establish pairwise key, compared with previous related works.  Categories and Subject Descriptors  C.2.4 [Computer-Communication-Networks]: Distributed  Systems-Distributed applications.    1. INTRODUCTION  Security communication is an important requirement in many  sensor network applications, so shared secret keys are used  between communicating nodes to encrypt data. As one of the  most fundamental security services, pairwise key establishment  enables the sensor nodes to communicate securely with each other  using cryptographic techniques. However, due to the sensor  nodes' limited computational capabilities, battery energy, and  available memory, it is not feasible for them to use traditional  pairwise key establishment techniques such as public key  cryptography and key distribution center (KDC). Several  alternative approaches have been developed recently to perform  pairwise key establishment on resource-constrained sensor  networks without involving the use of traditional cryptography   [14].  Eschenauer and Gligor proposed a basic probabilistic key   predistribution scheme for pairwise key establishment [1]. In the  scheme, each sensor node randomly picks a set of keys from a key  pool before the deployment so that any two of the sensor nodes  have a certain probability to share at least one common key. Chan  et al. further extended this idea and presented two key   predistribution schemes: a q-composite key pre-distribution scheme  and a random pairwise keys scheme. The q-composite scheme  requires any two sensors share at least q pre-distributed keys. The  random scheme randomly picks pair of sensors and assigns each  pair a unique random key [2]. Inspired by the studies above and  the polynomial-based key pre-distribution protocol [3], Liu et al.  further developed the idea addressed in the previous works and  proposed a general framework of polynomial pool-based key   predistribution [4]. The basic idea can be considered as the  combination of the polynomial-based key pre-distribution and the  key pool idea used in [1]] and [2]. Based on such a framework,  they presented two pairwise key pre-distribution schemes: a  random subset assignment scheme and a grid-based scheme. A  polynomial pool is used in those schemes, instead of using a key  pool in the previous techniques. The random subset assignment  scheme assigns each sensor node the secrets generated from a  random subset of polynomials in the polynomial pool. The   gridbased scheme associates polynomials with the rows and the  columns of an artificial grid, assigns each sensor node to a unique  coordinate in the grid, and gives the node the secrets generated  from the corresponding row and column polynomials. Based on  this grid, each sensor node can then identify whether it can  directly establish a pairwise key with another node, and if not,  what intermediate nodes it can contact to indirectly establish the  pairwise key.  A similar approach to those schemes described by Liu et al was  independently developed by Du et a. [5]. Rather than on Blundo's  scheme their approach is based on Blom's scheme [6]. In some  cases, it is essentially equivalent to the one in [4]. All of those  schemes above improve the security over the basic probabilistic  key pre-distribution scheme. However, the pairwise key  establishment problem in sensor networks is still not well solved.  For the basic probabilistic and the q-composite key   predistribution schemes, as the number of compromised nodes  increases, the fraction of affected pairwise keys increases quickly.  As a result, a small number of compromised nodes may affect a  large fraction of pairwise keys [3]. Though the random pairwise  keys scheme doses not suffer from the above security problem, it  incurs a high memory overhead, which increases linearly with the  number of nodes in the network if the level of security is kept  constant [2][4]. For the random subset assignment scheme, it  suffers higher communication and computation overheads.  In 2004, Liu proposed a new hypercube-based pairwise key  predistribution scheme [7], which extends the grid-based scheme  from a two dimensional grid to a multi-dimensional hypercube.  The analysis shows that hypercube-based scheme keeps some  attractive properties of the grid-based scheme, including the  guarantee of establishing pairwise keys and the resilience to node  compromises. Also, when perfect security against node  compromise is required, the hypercube-based scheme can support  a larger network by adding more dimensions instead of increasing  the storage overhead on sensor nodes. Though hypercube-based  scheme (we consider the grid-based scheme is a special case of  hypercube-based scheme) has many attractive properties, it  requires any two nodes in sensor networks can communication  directly with each other. This strong assumption is impractical in  most of the actual applications of the sensor networks.  In this paper, we present a kind of new cluster-based distribution  model of sensor networks, and for which, we propose a new  pairwise key pre-distribution scheme. The main contributions of  this paper are as follows:  Combining the deployment knowledge of sensor networks and the  polynomial pool-based key pre-distribution, we setup a   clusterbased topology that is practical with the real deployment of sensor  networks. Based on the topology, we propose a novel cluster  distribution based hierarchical hypercube model to establish the  pairwise key. The key contribution is that our scheme dose not  require the assumption of all nodes can directly communicate  with each other as the previous schemes do, and it still maintains  high probability of key establishment, low memory overhead and  good security performance. We develop a kind of new pairwise  key establishment algorithm with our hierarchical hypercube  model.  The structure of this paper is arranged as follows: In section 3, a  new distribution model of cluster deployed sensor networks is  presented. In section 4, a new Hierarchical Hypercube model is  proposed. In section 5, the mapping relationship between the  clusters deployed sensor network and Hierarchical Hypercube  model is discussed. In section 6 and section 7, new pairwise key  establishment algorithm are designed based on the Hierarchical  Hypercube model and detailed analyses are described. Finally,  section 8 presents a conclusion.  2. PRELIMINARY  Definition 1 (Key Predistribution): The procedure, which is used  to encode the corresponding encryption and decryption algorithms  in sensor nodes before distribution, is called Key Predistribution.  Definition 2 (Pairwise Key): For any two nodes A and B, if they  have a common key E, then the key E is called a pairwise key  between them.  Definition 3 (Key Path): For any two nodes A0 and Ak, when there  has not a pairwise key between them, if there exists a path  A0,A1,A2,……,Ak-1,Ak, and there exists at least one pairwise key  between the nodes Ai and Aj for 0≤i≤k-1 and 1≤j≤k, then the path  consisted of A0,A1,A2,……,Ak-1,Ak is called a Key Path between A0  and Ak.  Definition 4 (n-dimensional Hypercube): An n-dimensional  Hypercube (or n−cube) H(v,n) is a topology with the following  properties: (1) It is consisted of n·vn-1  edges, (2) Each node can be  coded as a string with n positions such as b1b2…bn, where  0≤b1,b2,…,bn≤v-1, (3) Any two nodes are called neighbors, which  means that there is an edge between them, iff there is just one  position different between their node codes.  3. MODEL OF CLUSTERS DEPLOYED  SENSOR NETWORKS  In some actual applications of sensor networks, sensors can be  deployed through airplanes. Supposing that the deployment  rounds of sensors are k, and the communication radius of any  sensors is r, then the sensors deployed in the same round can be  regarded as belonging to a same Cluster. We assign a unique  cluster number l (1 ≤ l ≤ k) for each cluster. Supposing that the  sensors form a connected graph in any cluster after deployment  through airplanes, and then the Fig.1 presents an actual model of  clusters deployed sensor networks.  Figure.1 An actual model of clusters deployed sensor  networks.  From Figure.1, it is easy to know that, for a given node A, there  exist lots of nodes in the same cluster of A, which can be  communicated directly with A, since the nodes are deployed  densely in a cluster. But there exist much less nodes in a cluster  neighboring to the cluster of A, which can be communicated  directly with A. since the two clusters are not deployed at the  same time.  4. HIERARCHICAL HYPERCUBE MODEL  Definition 5 (k-levels Hierarchical Hypercube): Let there are N  nodes totally, then a k-levels Hierarchical Hypercube named  H(k,u,m,v,n) can be constructed as follows:  1) The N nodes are divided into k clusters averagely, and  the [N/k] nodes in any cluster are connected into an n-dimensional  Hypercube: In the n-dimensional Hypercube, any node is encoded  55  as i1i2…in, which are called In-Cluster-Hypercube-Node-Codes,  where 0 ≤ i1,i2,…in ≤ v-1,v=[ n  kN / ],[j] equals to an integer not  less than j. So we can obtain k such kind of different hypercubes.  2) The k different hypercubes obtained above are encoded  as j1j2…jm, which are called Out-Cluster-Hypercube-Node-Codes,  where 0 ≤ j1,j2,…jm ≤ u-1,u=[ m  k ]. And the nodes in the k  different hypercubes are connected into m-dimensional  hypercubes according to the following rules: The nodes with same  In-Cluster-Hypercube-Node-Codes and different   Out-ClusterHypercube-Node-Codes are connected into an m-dimensional  hypercube.  (The graph constructed through above steps is called a k-levels  Hierarchical Hypercube abbreviated as H(k,u,m,v,n).)  3) Any node A in H(k,u,m,v,n) can be encoded as (i, j),  where i(i=i1i2…in, 0 ≤ i1,i2,…in ≤ v-1) is the   In-Cluster-HypercubeNode-Code of node A, and j(j=j1j2…jm, 0 ≤ j1,j2,…jm ≤ u-1) is the  Out-Cluster-Hypercube-Node-Code of node A.  Obviously, the H(k,u,m,v,n) model has the following good  properties:  Property 1: The diameter of H(k,u,m,v,n) model is m+n.  Proof: Since the diameter of n-dimensional hypercube is n,  and the diameter of m-dimensional hypercube is m, so it is easy to  know that the diameter of H(k,u,m,v,n) model is m+n from the  definition 5.  Property 2: The distance between any two nodes A(i1, j1) and B(i2,  j2) in H(k,u,m,v,n) model is d(A,B)= dh(i1, i2)+dh(j1, j2), where dh  represents the Hamming distance.  Proof: Since the distance between any two nodes in  hypercube equals to the Hamming distance between them, so it is  obvious that the theorem 2"s conclusion stands from definition 5.  5. MAPPING CLUSTERS DEPLOYED  SENSOR NETWORKS TO H(K,U,M,V,N)  Obviously, from the description in section 3 and 4, we can know  that the clusters deployed sensor network can be mapped into a   klevels- hierarchical hypercube model as follows:  At first, the k clusters in the sensor network can be mapped into k  different levels (or hypercubes) in the k-levels- hierarchical  hypercube model. Then, the sensor nodes in each cluster can be  encoded with the In-Cluster-Hypercube-Node-Codes, and the  sensor nodes in the k different clusters with the same   In-ClusterHypercube-Node-Codes can be encoded with the   Out-ClusterHypercube-Node-Codes according to the definition 5 respectively.  Consequently, the whole sensor network has been mapped into a  k-levels- hierarchical hypercube model.  6. H(K,U,M,V,N) MODEL-BASED  PAIRWISE KEY PREDISTRIBUTION  ALGORITHM FOR SENSOR NETWORKS  In order to overcome the drawbacks of polynomial-based and  polynomial pool-based key predistribution algorithms, this paper  proposed an innovative H(k,u,m,v,n) model-based key  predistribution scheme and pairwise key establishment algorithm,  which combines the advantages of polynomial-based and key  pool-based encryption schemes, and is based on the KDC and  polynomials pool-based key predistribution models.  The new H(k,u,m,v,n) model-based pairwise key establishment  algorithm includes three main steps: (1) Generation of the  polynomials pool and key predistribution, (2) Direct pairwise key  discovery, (3) Path key discovery.  6.1 Generation of Polynomials Pool and Key  Predistribution  Supposing that, the sensor network includes N nodes, and is  deployed through k different rounds. Then we can predistribute  keys for each sensor node on the basis of the H(k,u,m,v,n) model  as follows:  Step 1: Key setup server randomly generates a bivariate  polynomials pool such as the following: F={ f i  iiil n >< −121 ,...,,, (x,y),  f j  jjjinii m >< −121  ,...,,,,...,2,1  (x,y) | 0 ≤ iii n 121 ... −≤≤≤ ≤ v-1, 1 ≤ i ≤ n,  1 ≤ l ≤ k; 0 ≤ jjj m 121 ... −≤≤≤ ≤ u-1 , 1 ≤ j ≤ m} with vn  *m*um-1  +[N/vn  ]*n*vn-1  different t-degree bivariate polynomials over a finite  field Fq, and then assigns a unique polynomial ID to each  bivariate polynomial in F.  Step 2: In each round, key setup server assigns a unique node  ID: (i1i2…in,j1j2…jm) to each sensor node from small to big, where  0 ≤ i1,i2,…in ≤ v-1, 0 ≤ j1,j2,…jm ≤ u-1.  Step 3: key setup server assigns a unique cluster ID: l to all  the sensor nodes deployed in the same round, where 1 ≤ l ≤ k.  Step 4: key setup server predistributes m+n bivariate  polynomials { f iiil n  1  ,...,,, 32 >< (i1,y),…, f n  iiil n >< −121 ,...,,, (in,y);  f jjinii m  1  ,...,,,...,2,1 2  >< ( j1,y),…, f m  jjinii m >< −11  ,...,,,...,2,1  ( jm,y) } and the  corresponding polynomial IDs to the sensor node deployed in the  lth round and with ID (i1i2…in, j1j2…jm).  6.2 Direct Pairwise Key Discovery  If the node A(i1i2…in,j1j2…jm) in the sensor network wants to  establish pairwise key with a node B (i'1i'2…i'n,j'1j'2…j'm), then  node A can establish pairwise key with the node B trough the  following methods.  Firstly, node A computes out the distance between itself and node  B: d= d1+ d2, where d1=dh(i1i2…in, i'1i'2…i'n) and d2=dh(j1j2…jm,  j'1j'2…j'm). If d=1, then node A obtains the direct pairwise key  between itself and node B according to the following theorem 1:  Theorem 1: For any two sensor nodes A(i1i2…in,j1j2…jm) and B  (i'1i'2…i'n,j'1j'2…j'm) in the sensor network, supposing that the  56  distance between nodes A and B is d= d1+ d2, where d1=dh(i1i2…in,  i'1i'2…i'n) and d2=dh(j1j2…jm, j'1j'2…j'm). If d=1, then there exists a  direct pairwise key between nodes A and B.  Poof: Since d=1, then there is d1=1, d2=0, or d1=0, d2=1.  1) If d1=1, d2=0: From d2=0, there is nodes A, B belong to the  same cluster. Supposing that nodes A, B belong to the same  cluster l, then from d1=1 ⇒ There is only one position different  between i1i2…in and i"1i"2…i"n. Let it=i"t, when 1 ≤ t ≤ n-1, and  in ≠ i"n ⇒ f n  iiil n >< −121 ,...,,, (in,i"n)= f n  iiil n >′′′< −121 ,...,,, (i"n,in). So, there  exists a direct pairwise key f n  iiil n >< −121 ,...,,, (in,i"n) between nodes A  and B.  2) If d1=0, d2=1: From d2=1 ⇒ There is only one position  different between j1j2…jm and j"1j"2…j"m. Let jt=j"t, when 1 ≤ t ≤   m1, and jm ≠ j"m. Since d1=0 ⇒ i1i2…in equals to  i"1i"2…i"n ⇒ f m  jjjinii m >< −121  ,...,,,,...,2,1  (jm, j"m)=  f m  jjji nii m >′′′′′′< −121  ,...,,,,...,2,1  (j"m,jm). So, there exists a direct pairwise  key f m  jjjinii m >< −121  ,...,,,,...,2,1  (jm, j"m) between nodes A and B.  According to theorem 1, we present the detailed description of the  direct pairwise key discovery algorithm as follows:  Step 1: Obtain the node IDs and cluster IDs of the source  node A and destination node B;  Step 2: Compute out the distance between nodes A and B: d=  d1+ d2;  Step 3: If d1=1, d2=0, then select out a common polynomial  share of nodes A and B from { f iiil n  1  ,...,,, 32 >< ,..., f n  iiil n >< −121 ,...,,, } to  establish direct pairwise key;  Step 4: If d1=0, d2=1, then select out a common polynomial  share of nodes A and B from  { f jjinii m  1  ,...,,,...,2,1 2  >< ,..., f m  jjjinii m >< −121  ,...,,,,...,2,1  } to establish direct  pairwise key;  Step 5: Otherwise, there exists no direct pairwise key  between nodes A and B. And then turn to the following path key  discovery process.  6.3 Path Key Discovery  If d>1, then node A can establish path key with node B according  to the following theorem 2:  Theorem 2: For any two sensor nodes A(i1i2…in,j1j2…jm) and B  (i'1i'2…i'n,j'1j'2…j'm) in the sensor network, supposing that the  distance between nodes A and B is d= d1+ d2, where d1=dh(i1i2…in,  i'1i'2…i'n) and d2=dh(j1j2…jm, j'1j'2…j'm). If d>1, then there exists a  path key between nodes A and B.  Proof: Let d1=a, d2=b, then we can think that it ≠ i't, when  1 ≤ t ≤ a; but it=i't, when t>a; and jt ≠ j't, when 1 ≤ t ≤ b; but jt=j't,  when t>b. Obviously, nodes A(i1i2…in, j1j2…jm) ,(i'1i2 i3…in,  j1j2…jm),(i'1i'2 i3…in, j1j2…jm),…,(i'1i'2…i'n, j1j2…jm) belong to the  same cluster. So, according to the supposing condition of The  nodes in the same cluster form a connected graph, there is a  route among those nodes. In addition, in those nodes, the distance  between any two neighboring nodes is 1, so from theorem 1, it is  easy to know that there exists direct pairwise key between any  two neighboring nodes among those nodes.  For nodes (i'1i'2…i'n,j1j2…jm), (i'1i'2…i'n,j'1 j2 j3…jm),  (i'1i'2…i'n,j'1j'2 j3…jm-1 jm),…, (i'1i'2…i'n,j'1j'2…j'm-1jm), since they  have the same Out-Cluster-Hypercube-Node-Codes with the node  B(i'1i'2…i'n,j'1j'2…j'm), so nodes (i'1i'2…i'n,j1j2…jm), (i'1i'2…i'n,j'1 j2  j3…jm), (i'1i'2…i'n,j'1j'2 j3…jm-1 jm),…, (i'1i'2…i'n,j'1j'2…j'm-1 jm) and  node B belong to a same logical hypercube. Obviously, from the  supposing condition of The whole sensor network forms a  connected graph, there is a route among those nodes. In addition,  in those nodes, the distance between any two neighboring nodes is  1, so from theorem 1, it is easy to know that there exists direct  pairwise key between any two neighboring nodes among those  nodes.  So, it is obvious that there exists a path key between nodes A  and B.  According to theorem 2, we present the detailed description of the  path key discovery algorithm as follows:  Step 1: Compute out the intermediate nodes (i'1i2  i3…in,j1j2…jm), (i'1i'2 i3…in,j1j2…jm),…,(i'1i'2…i'n, j1j2…jm) and  (i'1i'2…i'n,j1'j2 j3…jm), (i'1i'2…i'n,j'1j'2 j3…j'm-1  jm),…,(i'1i'2…i'n,j'1j'2…j'm-1 jm) from the source node  A(i1i2…in,j1j2…jm) and the destination node B (i'1i'2…i'n,j'1j'2…j'm).  Step 2: In those nodes series A(i1i2…in,j1j2…jm), (i'1i2  i3…in,j1j2…jm), (i'1i'2 i3…in,j1j2…jm),…,(i'1i'2…i'n,j1j2…jm) and  (i'1i'2…i'n,j1'j2 j3…jm), (i'1i'2…i'n,j'1j'2 j3…j'm-1 jm),…, (i'1i'2…i'n,  j'1j'2…j'm-1 jm), B (i'1i'2…i'n,j'1j'2…j'm), the neighboring nodes select  their common polynomial share to establish direct pairwise key.  From theorem 2, it is easy to know that any source node A  can compute out a key path P to the destination node B according  to the above algorithm, when there are no compromised nodes in  the sensor network. Once the key path P is computed out, then  node A can send messages to B along the path P to establish  indirect pairwise key with node B. Fig.2 presents a example of  key path establishment.  Figure.2 Key path establishment example.  For example: In the above Figure.2, node A((012),(1234)) can  establish pairwise key with node B((121),(2334)) through the  following key path: A((012),(1234)) → C((112),(1234)) →  D((122),(1234)) → E((121),(1234)) → F((121),(2234)) →  B((121),(2334)), where node F shall route through nodes G, H, I,  J to establish direct pairwise key with node B.  57  According to the properties of H(k,u,m,v,n) model, we can prove  that the following theorem by combing the proof of theorem 2:  Theorem 3: Supposing that there exist no compromised nodes in  the sensor network, and the distance between node A and B, then  there exists a shortest key path with k distance between node A  and B logically. That is to say, node A can establish indirect  pairwise key with node B through t-1 intermediate nodes.  Proof: Supposing that the distance between node A(i1i2…in,  j1j2…jm) and B (i'1i'2…i'n, j'1j'2…j'm) is d=d1+ d2, where  d1=dh(i1i2…in, i'1i'2…i'n), d2=dh(j1j2…jm, j'1j'2…j'm). Since d=t,  according to the construction properties of H(k,u,m,v,n), it is easy  to know that there exist t-1 intermediate nodes I1,…,It-1, in the  logical space H(k,u,m,v,n), which satisfy that the distance  between any two neighboring nodes in the nodes series A,   I1,…,It1, B equals to 1. So according to the theorem 1, we can know that  nodes A, I1,…,It-1, B form a correct key path between node A and  B. If any two neighboring nodes in the nodes series A, I1,…,It-1, B  can communicate directly, then node A can establish indirect  pairwise key with node B through those t-1 intermediate nodes.  6.4 Dynamic Path Key Discovery  The path key discovery algorithm proposed in the above section  can establish a key path correctly, only when there exist no  compromised nodes in the whole sensor network, since the key  path is computed out beforehand. And the proposed algorithm  cannot find an alternative key path when there exist some  compromised nodes or some intermediate nodes not in the  communication radius, even that there exists other alternative key  paths in the sensor network. From the following example we can  know that there are many parallel paths in the H(k,u,m,v,n) model  for any two given source and destination nodes, since the  H(k,u,m,v,n) model is high fault-tolerant[9,10]  .  Figure.3 Alternative key path establishment example.  For example: Considering the key path establishment example  given in the above section based on Figure.2:  A((012),(1234)) → C((112),(1234)) → D((122),(1234)) →  E((121),(1234)) → F((121),(2234)) → B((121),(2334)),  supposing that node F((121),(2234)) has compromised, then from  Figure.3, we can know that there exists another alternative key  path as A((012),(1234)) → C((112),(1234)) → D((122),(1234))  →E((121),(1234)) → M((121),(1334)) → B((121),(2334)), which  can be used to establish the indirect pairwise key between node A  and B, where node E shall route through nodes D and K to  establish direct pairwise key with node M, and node M shall route  through nodes N, O, G, H, I, J to establish direct pairwise key  with node B.  Since the sensors are source limited, so they are easy to die or out  of the communication radius, therefore the algorithm proposed in  the above section cannot guarantee to establish correct key path  efficiently. In this section, we will propose a dynamic path key  discovery algorithm as follows, which can improve the  probability of key path effectively:  Algorithm I: Dynamic key path establishment algorithm based on  H(k,u,m,v,n) model for cluster deployed sensor networks.  Input: Sub-sensor network H(k,u,m,v,n), which has some  compromised /fault sensors and fault links, And two reachable  nodes A(a1…an,a"1…a"m) and B(b1…bn,b"1…b"m) in H(k,u,m,v,n),  where a"t ≠ b"t, t∈[1,s], a"t=b"t, t >s.  Output: A correct key path from node A to B in H(k,u,m,v,n).  Step 1: Obtain the code strings of node A and B: A ←  (a1…an,a"1…a"m), B ← (b1…bn,b"1…b"m), where aj, bj [0,∈ u-1],  a"j, b"j [0,∈ v-1].  Step 2: If a"1…a"m = b"1…b"m, then node A can find a route  to B according to the routing algorithms of hypercube [9-10].  Step 3: Otherwise, node A can find a route to C(b1…bn,  a"1…a"m) according to the Algorithm I or Algorithm II. Then let  I0=C(b1…bn,a"1…a"m), I1=(b1…bn,b"1 a"2…a"m),…,  Is=B(b1…bn,b"1 b"2…b"s a"s+1…a"m), and each node It in the above  nodes series find a route to its neighboring node It+1 on the basis  of the location information (Detailed routing algorithms based on  location information can see the references[11-14]).  Step 4: Algorithm exits. If such kind of a correct key path  exists, then through which node A can establish an indirect  pairwise key with node B. Otherwise, node A fails to establish an  indirect pairwise key with node B. And node A will tries again to  establish an indirect pairwise key with node B some time later.  7. ALGORITHM ANALYSES  7.1 Practical Analyses  According to the former description and analyses, it is easy to  know that the above newly proposed algorithm has the following  properties:  Property 3: When there exist no fault and compromised nodes, by  using new pairwise key predistribution scheme based on  H(k,u,m,v,n) model, the probability of direct pairwise key  establishment between any two nodes can be estimated as  P=(m(u-1)+n(v-1))/(N-1), where N is the total number of nodes in  the sensor network, and N=um  * vn  .  Proof: Since the predistributed pairwise keys for any node FA  ={ f iiil n  1  ,...,,, 32 >< (i1,y),…, f n  iiil n >< −121 ,...,,, (in,y); f jjinii m  1  ,...,,,...,2,1 2  >< (j1  ,y),…, f m  jjinii m >< −11  ,...,,,...,2,1  ( jm,y) } in the newly proposed  algorithm. Obviously, in the logical hypercube formed by the  nodes in the same cluster of node A, there are n(v-1) nodes, which  58  have direct pairwise key with node A. And in the logical  hypercube formed by the nodes in different clusters from that of  node A, there are m(u-1) nodes, which have direct pairwise key  with node A. Therefore, there are totally m(u-1)+n(v-1) nodes,  which have direct pairwise key with node A. So, the probability of  pairwise key establishment between any two nodes can be  estimated as P=(m(u-1)+n(v-1))/(N-1), since the whole sensor  network has N sensor nodes in all.  Figure.4 presents the comparision between the probability of  direct pairwise key establishment between any two nodes and the  dimension n, when the sensor network has different total nodes,  and use the new pairwise key predistribution scheme based on  H(8,2,3,v,n) model.  2 3 4 5 6 7 8 9 10  0  0.002  0.004  0.006  0.008  0.01  Number of Dimension  ProbabilitytoEstablishDirectKey  N = 8000  N=10000  N=20000  N=30000  Figure.4 Comparision between the probability of direct  pairwise key establishment between any two nodes and the  dimension n, when the sensor network has different total  nodes, and use the new pairwise key predistribution scheme  based on H(8,2,3,v,n) model.  From Figure.4, it is easy to know that by using new pairwise key  predistribution scheme based on H(k,u,m,v,n) model, the  probability of direct pairwise key establishment between any two  nodes decreases with the increasing of the scale of the sensor  networks, and in addition, the probability of direct pairwise key  establishment between any two nodes decreases with the  increasing of the dimension n, when the scale of the sensor  network is fixed.  Theorem 4: Supposing that the total sensors is N in the sensor  network, then when u ≥ v2  , the probability of direct pairwise key  establishment between any two nodes, when using the key  distribution scheme based on the hypercube model H(v,p), is  smaller than that when using the key distribution scheme based on  the H(k,u,m,v,n) model.  Proof: Since u ≥ v, then we can let u=vt  , where t ≥ 2. Since  the total number of nodes in H(v,p) is vp  =N, the total number of  nodes in H(k,u,m,v,n) is um  * vn  =N. Let p=x+n, then there is  um  *vn  = vx  * vn  ⇒ um  =vx  ⇒ x=tm.  From the property 3, it is easy to know that the probability of  direct pairwise key establishment between any two nodes can be  estimated as P=(m(u-1)+n(v-1))/(N-1). According to the  description in [7], it is well know that the probability of direct  pairwise key establishment between any two nodes can be  estimated as P"= p(v-1)/(N-1)= (x(v-1)+n(v-1))/(N-1).  Next, we will prove that m(u-1) ≥ x(v-1):  m(u-1)= m(vt  -1), x(v-1)= tm(v-1). Construct a function as  f(t)= vt  -1- t(v-1), where t ≥ 2. When t=2, it is obvious that there is  f(t)= vt  -2v+1=( v-1)2  ≥ 0 and f"(t)=t vt-1  - v+1 ≥ 2v- v+1= v+1>0.  So, there is f(t) ≥ 0 ⇒ vt  -1 ≥ t(v-1) ⇒ m(vt  -1) ≥ tm(v-1) ⇒   m(u1) ≥ x(v-1).  Therefore, the conclusion of the theorem stands.  As for the conclusion of theorem 4, we give an example to  illustrate.  Supposing that the total number of nodes in the sensor network is  N=214  , and H(k,u,m,v,n)=H(16,4,2,2,10), H(v,p)= H(10,14), then  the probability of direct pairwise key establishment between any  two nodes based on the H(k,u,m,v,n) model is P=   (m(u-1)+n(v1))/(N-1)= (2(4-1)+10(2-1))/(214  -1)=16/(214  -1), but the probability  of direct pairwise key establishment between any two nodes based  on the H(v,p) model is P"= p(v-1)/(N-1)=14(2-1)/(214  -1)= 14/(214    1).  Supposing that the total number of nodes in the sensor network is  N, Figure.5 illustrates the comparison between the probability of  direct pairwise key establishment between any two nodes based  on the H(k,u,m,v,n) model and the probability of direct pairwise  key establishment between any two nodes based on the H(v,p)  model, when u=4 and v=2.  1 2 3 4 5 6 7 8 9 10  0  0.5  1  1.5  x 10  -3  scaleofthesensornetwork  ProbabilitytoEstablishDirectKey  H(k,u,m,v,n)model-based  H(v,p)model-based  Figure.5 Comparison between the probability of direct  pairwise key establishment between H(v,n) and H(k,u,m,v,n)  models.  From Figure.5, it is easy to know that the theorem 5 stands.  Theorem 5: Supposing that the total sensors is N in the sensor  network, then the pairwise key distribution scheme based on the  hypercube model H(v,p), is only a special case of the pairwise key  distribution scheme based on the H(k,u,m,v,n) model.  Proof: As for the pairwise key distribution scheme based on the  H(k,u,m,v,n) model, let k=1 (u=1, m=0), which means that the  total sensor network includes only one cluster. Then obviously,  the H(k,u,m,v,n) model will degrade into the H(v,n) model.  According to the former anayses in this paper and the definition  of the pairwise key distribution scheme based on the hypercube  model H(v,p) in [7], it is easy to know that the conclusion of the  theorem stands.  59  7.2 Security Analyses  By using the pairwise key establishment algorithm based on the  H(k,u,m,v,n) model, the intruders can launch two kinds of attacks:  1) The attackers may target the pairwise key between two  particular sensor node, in order to compromise the pairwise key  between them, or prevent them to establish pairwise key. 2) The  attackers may attack against the whole sensor network, inorder to  decrease the probability of the pairwise key establishment, or  increase the cost of the pairwise key establishment.  Attacks against a Pair of sensor nodes  1. Supposing that the intruders want to attack two particular sensor  nodes u,v, where u,v are all not compromised nodes, but the  intruders want to compromise the pairwise key between them.  1) If u,v can establish direct pairwise key, then the only way to  compromise the key is to compromise the common bivariate  polynomial f(x,y) between u,v. Since the degree of the bivariate  polynomial f(x,y) is t, so the intruders need to compromise at least  t+1 sensor nodes that have a share of the bivariate polynomial f(x,y).  2) If u,v can establish indirect pairwise key through intermediate  nodes, then the intruders need to compromise at least one  intermediate node, or compromise the common bivariate  polynomial f(x,y) between two neighboring intermediate nodes. But  even if the intruders succeed to do that, node u and v can still   reestablish indirect pairwise key through alternative intermediate  nodes.  2. Supposing that the intruders want to attack two particular sensor  nodes u,v, where u,v are all not compromised nodes, but the  intruders want to prevent them to establish the pairwise key.  Then, the intruders need to compromise all of the m+n bivariate  polynomials of node u or v. Since the degree of the bivariate  polynomial f(x,y) is t, so for bivariate polynomial, the intruders need  to compromise at least t+1 sensor nodes that have a share of the  given bivariate polynomial. Therefore, the intruders need to  compromise (m+n)(t+1) sensor nodes altogether to prevent u,v to  establish the pairwise key.  Attacks against the sensor network  Supposing that the Attackers know the distribution of the  polynomials over sensor nodes, it may systematically attack the  network by compromising the polynomials in F one by one in order  to compromise the entire network. Assume the fraction of the  compromised polynomials is pc, then there are up to  N"=pc × { vn  v  N  umv n  n  mn ××+×× ][ }= pc ××N (m+n)  Sensor nodes that have at least one compromised polynomial share.  Among all of the remaining N- N" sensor nodes, none of them  includes a compromised polynomial share. So, the remaining N- N"  sensor nodes can establish direct pairwise key by using any one of  their polynomial shares. However, the indirect pairwise keys in the  remaining N- N" sensor nodes may be affected. And they may need  to re-establish a new indirect pairwise key between them by select  alternative intermediate nodes that do not belong to the N"  compromised nodes.  Supposing that the scale of the sensor network is N=10000, Figure.6  presents the comparison between pc and the number of sensor nodes  with at least one compromised polynomial share in sensor networks  based on different H(k,u,m,v,n) distribution models.  From Figure.6, it is easy to know that, when the scale of the sensor  network is fixed, the number of the affected sensor nodes in the  sensor network increases with the increasing of the number of  compromised nodes.  0 0.02 0.04 0.06 0.08 0.1 0.12 0.14 0.16  0  1000  2000  3000  4000  5000  6000  7000  8000  F rac tion of C om prom is ed B ivariate P oly nom ialsSensorNodeswithatleastoneCompromisedPolynomialShare  H (1,0,0,100,2)  H (2,2,1,71,2)  H (4,2,2,50,2)  H (8,2,3,36,2)  Figure.6 the comparison between pc and the number of sensor  nodes with at least one compromised polynomial share in sensor  networks based on different H(k,u,m,v,n) distribution models.  Theorem 6: Supposing that the total sensors is N in the sensor  network, and the fraction of compromised nodes is pc, then when  u>v, the number of affected nodes of the H(v,p) model based key  predistribution scheme, is bigger than that of the H(k,u,m,v,n) model  based key predistribution scheme.  Proof: Since the number of affected nodes of the H(k,u,m,v,n)  model based key predistribution scheme is pc ××N (m+n), and it is  proved in [7] that the number of affected nodes of the H(v,p) model  based key predistribution scheme is pc ××N p. Let p=x+n, then  there is um  * vn  = vx  * vn  ⇒ um  =vx  . Since u>v ⇒ x>m ⇒  pc ××N (m+n)< pc ××N (x+n)= pc ××N p.  Supposing that the scale of the sensor network is N=10000, Figure.7  presents the comparison between pc and the number of sensor nodes  with at least one compromised polynomial share in sensor networks  based on H(9,3,2,2,n) and H(2,p) distribution models.  From Figure.7, it is easy to know that the conclusion of theorem 9 is  correct, and the number of the affected sensor nodes in the sensor  network increases with the increasing of the number of  compromised nodes, when the scale of the sensor network is fixed.  60  0.01 0.02 0.03 0.04 0.05 0.06 0.07 0.08 0.09 0.1 0.11  0  1000  2000  3000  4000  5000  6000  7000  8000  9000  10000  Fraction of Compromised Bivariate Polynomials  SensorNodeswithatleastoneCompromisedPolynomialShare  H(9,3,2,34,2)  H(16,4,2,25,2)  H(225,15,2,7,2)  H(1296,36,2,3,2)  H(2,14)  Figure.7 the comparison between pc and the number of sensor  nodes with at least one compromised polynomial share in  sensor networks based on H(9,3,2,2,n) and H(2,p) distribution  models.  8. CONCLUSION  A new hierarchical hypercube model named H(k,u,m,v,n) is  proposed, which can be used for pairwise key predistribution for  cluster deployed sensor networks. And Based on the H(k,u,m,v,n)  model, an innovative pairwise key predistribution scheme and  algorithm are designed respectively, by combing the good  properties of the Polynomial Key and Key Pool encryption  schemes.  The new algorithm uses the good characteristics of node codes  and high fault-tolerance of H(k,u,m,v,n) model to route and  predistribute pairwise keys, in which nodes are not needed to be  able to communicate with each other directly such as that the  algorithms proposed by [7] shall need. So, the traditional pairwise  key predistribution algorithm based on hypercube model [7] is  only a special case of the new algorithm proposed in this paper.  Theoretical and experimental analyses show that the newly  proposed algorithm is an efficient pairwise key establishment  algorithm that is suitable for the cluster deployed sensor networks.  9. ACKNOWLEDGMENTS  Our thanks to ACM SIGCHI for allowing us to modify templates  they had developed, and to nature science fund of Fujian province  of PR.China under grant No.A0510024.  10. REFERENCES  [1] L. Eschenauer and V. Gligor. A key-management scheme for  distribute sensor networks. In Proceedings of the 9th ACM  Conference on Computer and Communication Security.  ACM Press, Washington DC, USA, 2002, 41-47.  [2] H. Chan, A. Perrig, and D. Song. Random key  predistribution schemes for sensor networks. In IEEE  Symposium on Security and Privacy. IEEE Computer  Society, California, USA, 2003, 197-213.  [3] C. Blundo, A. D. Santis, A. Herzberg, S. Kutten, U. Vaccaro,  and M. Yung. Perfectly-secure key distribution for dynamic  conferences. Lecture Notes in Computer Science. 1993, 740,  471-486.  [4] D. Liu and P. Ning. Establishing pairwise keys in distributed  sensor networks. In Proceedings of the 10th ACM  Conference on Computer and Communications Security.  ACM Press, Washingtion, DC, USA, 2003, 52-61.  [5] W. Du, J. Deng, Y. Han, and P. Varshney. A pairwise key  pre-distribution scheme for wireless sensor networks. In  Proceedings of the Tenth ACM Conference on Computer and  Communications Security. Washingtion, DC, USA,2003,   4251.  [6] R. Blom. An optimal class of symmetric key generation  systems. Advances in Cryptology: Proceedings of  EUROCRYPT 84. Lecture Notes in Computer Science. 1985,  209, :335-338.  [7] Donggang Liu, Peng Ning, Rongfang Li, Establishing  Pairwise Keys in Distributed Sensor Networks. ACM Journal  Name, 2004, 20, 1-35.  [8] L. Fang, W. Du, and N. Peng. A Beacon-Less Location  Discovery Scheme for Wireless Sensor Networks,  INFOCOM 2005.  [9] Wang Lei, Lin Ya-ping, Maximum safety path matrix based  fault-tolerant routing algorithm for hypercube  interconnection network. Journal of software. 2004,15(7),  994-1004.  [10] Wang Lei, Lin Ya-ping, Maximum safety path vector based  fault-tolerant routing algorithm for hypercube  interconnection network. Journal of China Institute of  Communications. 2004, 16(4), 130-137.  [11] Lin Ya-ping, Wang Lei, Location information based  hierarchical data congregation routing algorithm for sensor  networks. Chinese Journal of electronics. 2004, 32(11),  1801-1805.  [12] W. Heinzelman, J. Kulik, and H. Balakrishnan, Negotiation  Based Protocols for Disseminating Information in Wireless  Sensor Networks. ACM Wireless Networks. 2002, 8,   169185.  [13] Manjeshwar,A.; Agrawal,D.P. TEEN: a routing protocol for  enhanced efficiency in wireless sensor networks]. In  Proceedings of 15th Parallel and Distributed Processing  Symposium]. IEEE Computer Society, San Francisco, USA,  2001, 2009-2015.  [14] B. Krishnamachari, D. Estrin, and S. Wicker. Modelling  Data-Centric Routing in Wireless Sensor Networks. In  Proceedings of IEEE Infocom, 2002.  61