Trust - Peer-to-Peer Computing: Applications, Architecture, Protocols, and Challenges - page 150

vide a cost-effective key infrastructure to secure the sensor network. However,
their design requires a centralized key server and the re-keying 1 process sug-
gested is ine cient due to the large amount of message exchanges (i.e., a large
overhead).
Based on a trusted intermediary node and the underlying routing protocol,
Chan and Perrig [Chan and Perrig, 2005] introduced a class of key establish-
ment protocols, called Peer Intermediaries for Key Establishment (PIKE). By
assuming the existence of routing information, PIKE uses a third node C lo-
cated somewhere in the network to act as a trusted intermediary between two
nodes A and B. The trusted entity shares a common key with both node A
and node B so that the key establishment protocols can be securely routed
through node C to perform connection establishment. The objectives of PIKE
are to provide a uniform communication pattern for key establishment and
reduce the communication and memory overheads when the network size in-
creases. However, the dependence on the underlying routing protocol makes
this scheme less attractive and it is hard to adapt to topology changes. It is
noted that PIKE is considered as a deterministic key pre-distribution scheme
because any two nodes are guaranteed to be able to set up a key.

6.10.1.2 Probabilistic Key Pre-Distribution Schemes

Eschenauer and Gligor [Eschenauer and Gligor, 2002] proposed a random
key pre-distribution scheme (referred to as basic scheme in this chapter) in
2002. Based on random graph theory [Erdos and Renyi, 1960], the basic scheme
relies on probabilistic key sharing among nodes and uses a simple shared
key discovery protocol and path key establishment for the connection setup
process. This scheme assumes that the sensor network forms a random graph
and keys are installed in nodes prior to deployment. Each sensor node installs
a random set of keys from the key pool. Any two neighbors are connected if
they are able to find a common key.
The principle of key pre-distribution is widely adopted in many key man-
agement schemes in WSNs. One of the major reasons is that it can provide
an acceptable level of security on the resource-constrained sensor nodes. After
the pioneering work of the random key pre-distribution scheme proposed by
Eschenauer and Gligor [Eschenauer and Gligor, 2002], many enhancements
on the basic scheme have been proposed. In the following, we briefly discuss
several typical trust establishment schemes which enhance the basic scheme
in different ways.
Chan et al. [Chan et al., 2003] proposed a q-composite key pre-distribution
scheme in which q common keys (q > 1) are required to establish a single se-
cure link between two neighboring nodes. This scheme achieves better security
under small scale attack (when the fraction of compromised nodes is less than
0.5%) while increasing the vulnerability when the number of compromised
nodes increases. They also proposed a random pairwise scheme which can

1 Re-keying refers to the process of replacing an old key with a new one.