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

be regarded as a randomized version of the pairwise scheme. In the pairwise
scheme, each sensor node has n−1 keys which are privately shared with
another node in the network. To reduce the memory storage, the random
pairwise scheme only picks a subset of keys from those n−1 keys. Thus, the
memory usage of the sensor node is reduced but the network connectivity is
also decreased. The random pairwise scheme provides full resilience against
node capture attack as even when some nodes are compromised, the remain-
der of the network remains fully secure. However, due to the limited memory
storage of sensors, each node can only hold a limited amount of unique keys.
The number of keys stored cannot scale well with the increasing network size.
As a result, the maximum network size supported is smaller than that of the
basic scheme.
Based on the known attack probabilities 2 in different regions, Chan et
al.'s scheme [Chan et al., 2005b] targets at enhancing the overall network re-
silience 3 . Their scheme adjusts the number of distinct keys stored in a sensor
node depending on the attack probability of the region they are going to be
deployed. If a node is going to be deployed in a region with a higher attack
probability, fewer keys will be assigned to it and vice versa. In this case, the
adversaries have a higher probability to attack a node with fewer keys stored,
and therefore the number of keys exposed to the adversaries after each attack
is smaller. It is clear that there are two drawbacks in this approach. Firstly,
a certain extent of connectivity is sacrificed. Secondly, additional informa-
tion on a known and fixed attack probability is required to be known before
deployment. Nevertheless, the authors showed that there is a substantial im-
provement in network resilience.
Du et al. [Du et al., 2005] proposed a random key pre-distribution method
built on the Blom key pre-distribution scheme [Blom, 1984] to improve net-
work resilience. Blom's original scheme uses a single key space to allow any
pair of nodes to compute a secret key. Each node is required to store λ+ 1 keys
and the scheme guarantees that as long as no more than λ nodes are compro-
mised, all the links between non-compromised nodes remain secure. Du et al.
extended this idea to multiple key spaces instead of a single one. Two nodes
share a pairwise key only if they hold a common key space. Their scheme keeps
the λ-secure property but relaxes the memory requirement. Consequently, the
network formed results in a connected graph with a probability instead of a
guaranteed complete graph by Blom's scheme. Later, Du et al. [Du et al., 2004]
tried to reduce the memory usage using the deployment knowledge (e.g., lo-
cation) while achieving the same level of connectivity. However, such a piece
of knowledge is not always available, especially in a hostile area and dynamic
network environment. Specifically, o ine estimation of the node distribution
2 Attack probability refers to the probability that a node within a certain region will be
captured.
3 Network resilience generally refers to the ability of a network to resist being affected by
some attacks.