Identity-Based Key Distribution in Wireless Sensor Networks - Security for Wireless Sensor Networks Using Identity-Based Cryptography - page 117

drawback of this scheme is that the trusted base station represents a single point of
compromise for security information, and may also induce a focused communication
load centered on the base station, which may lead to early battery exhaustion for the
nodes closest to the base station. Another concern is that certain networks do not have a
suitable, highly functional, and tamper-proof device that can be used as a secure KDC.

6.3.3 -Secure n n Key-Establishment Schemes

Blom (1984) and Blundo et al. (1992) addressed the problem of key distribution and
key establishment between all pairs of n principals. Although these schemes were origi-
nally intended for group keying in traditional networks, and not for sensor networks,
they are included here because of their relevance to the development of subsequent
key-distribution schemes for sensor networks. The schemes of both Blom and Blundo
et al. have an important resiliency property—the  -secure property. The coalition of
no more than  -compromised sensor nodes reveals nothing about the pairwise key
between any two noncompromised nodes.
The main advantage of this class of schemes is that they allow a parameterizable
trade-off between security and memory overhead. Whereas the full pairwise scheme
involves the storage of

Ο

keys at each node and is n -secure, this class of schemes
allows the storage of O(  ) keys in return for a  -secure property, and it is perfectly
resilient to node compromise until  +1 nodes have been compromised, at which point
the entire network's communications are compromised.

() n

6.3.4 Random Key-Predistribution Schemes

In this method, keys are predistributed by preloading random keying material on sen-
sor nodes with the intention of establishing a common secret key between the commu-
nicating entities. Upon deployment, these nodes carry out a lookup process to see if a
shared key exists between them. As keys are preloaded in a random manner, certain set
of nodes may not share a common key with each other. In such cases, nodes could make
use of their immediate neighbors who share keys, as bridges between the nodes that do
not share a common key. One of the early, key-sharing algorithms using random graph
theory was proposed by Eschenauer and Gligor (2002).

6.3.4.1 Basic Random Key-Predistribution Scheme

In this scheme, let m denote the number of distinct cr yptographic keys that can be stored
on the key ring of a sensor node. This scheme is divided into three phases as follows:

Phase I: Key Predistribution
In this initialization phase, a random pool (set) of keys Q are picked from the total
possible key space. In addition, for each node, m keys are randomly selected from the