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

the n -1 possible unique keys that this node could share with the other n nodes in the
network. Using the same reasoning as the random key-predistribution scheme, as long
as these m keys provide some sufficient probability p of enabling any two neighboring
nodes to establish a secure link, the resultant graph of initial secure links will have a
high probability of being connected. The remaining links are then established using
this initial graph exactly as in the random key-predistribution scheme.
Chan et al. (2003) present a preliminary initial distributed-node-revocation scheme
that makes use of the fact that possessing unique pairwise keys allows nodes to perform
node-to-node identity authentication.
In their scheme, each of the m nodes that shares a unique pairwise key with the tar-
get node (i.e., the node's participants) carries a preloaded vote that it can use to signify a
message that the target is compromised. These m votes form a Merk le hash tree with m
leaves (Merkle 1980). To vote against the target node, a node performs a network-wide
broadcast of its vote (i.e., its leaf in the Merkle hash tree) along with the log m internal
hash values, which will allow the other participants of the target to verify that this leaf
value is part of the Merkle hash tree. Once at least t participants of a given target have
voted, and the votes have been verified by the other m participants using the Merkle
hash tree, all m nodes will erase any pairwise keys shared with the target, thus revoking
it from the network.
The random pairwise key scheme inherits both strengths and weaknesses from
the full pairwise keys scheme and the random key-distribution scheme. Under the
random pairwise keys scheme, nodes captured do not reveal information to the rest
of the network, and central revocation can be accomplished by just unicasting to each
of the nodes that share keys with the revoked node. It also involves a much lower
memory overhead than the full pairwise keys scheme. Unfortunately, like the random
key-predistribution schemes, it is probabilistic and cannot be guaranteed to work in
nonuniform or sparse deployments.
6.3.7 Multispace Key Schemes
This class of schemes is a hybrid between random key predistribution and the  -secure
n × n key-establishment schemes. These schemes were first proposed by Du et al.
(2003). Recall that in random key predistribution, a key pool is first selected from the
universe of possible keys. Each sensor node is then preloaded with a set of keys from
the key pool such that any two nodes possess some chosen probability p of sharing
enough keys to form a secure link. Multispace key schemes use the same basic notion
of random key predistribution but use key spaces, where individual keys are used in
random key predistribution. Hence, the key pool is replaced by a pool of key spaces
and each node randomly selects a subset of key spaces from the pool of key spaces,
such that any two nodes will have some common key space with probability p . Each
key space represents a unique instance of a different  -secure n×n key-establishment
scheme [e.g., Blom's scheme (1984)]. If two nodes possess the same key space, they can
then perform the relevant  -secure n × n key-establishment scheme to generate a secure
session key.