B.5. Random Pairwise Scheme

A pairwise key predistribution scheme offers perfect resilience against node captures, that is, the capture of any number c of nodes does not reveal any information about the secrets used by uncaptured nodes. This corresponds to P_e = 0 irrespective of c. This desirable property of the network is achieved by giving each key to the key rings of only two nodes. Moreover, the sharing of a key k between two unique nodes u and v implies that these nodes can authenticate themselves to one another — no other node possesses k and can prove itself as u to v or as v to u.

Pairwise keys can be distributed to nodes in many ways. Now, we deal with random distribution. Let m denote the size of the key ring of each sensor node. For each node u in the network, the key set-up server randomly selects m other nodes v₁, . . . , v_m and distributes a new random key k_i to each of the pairs (u, v_i) for i = 1, . . . , m. This distribution mechanism should also ensure that two nodes u, v in the network share at most one key. If k is given to u and v, the set-up server also attaches the ID of v to the copy of k in the key ring of u and the ID of u to the copy of k in the key ring of v.

In the direct key establishment phase, each node u broadcasts its own ID. Each physical neighbour v of u, that finds the ID of u stored against a key in the key ring of v, identifies u as its direct neighbour and also the unique key shared by u and v.

The analysis of the random pairwise scheme is a bit tricky. Here, the global connectivity graph G_key is m-regular, that is, each node has degree exactly m and we cannot expect to maintain this degree locally too. On the other hand, it is reasonable to assume under a random deployment model that the fraction of nodes with which a given node shares pairwise keys remains the same both locally and globally. More precisely, we equate p′ with p, that is,

Equation B.5

Here, d denotes the desired local degree of a node. Equation (B.2) gives the formula for d in terms of the global connectivity P_c. For P_c = 0.9999, we have d = 16.11 for n = 1,000, d = 18.42 for n = 10,000, d = 20.72 for n = 100,000, and d = 23.03 for n = 1,000,000. That is, the value of d does not depend heavily on n, as long as n ranges over practical values. In particular, one may fix d = 20 (or d = 25 more conservatively) for all applications.

Equation (B.5) implies

This equation reflects the drawback of the random pairwise scheme. The value m is limited by the memory of a sensor node, whereas n′ is dictated by the density of nodes in the deployment area and d can be taken as a constant, and so the network size n is bounded above by the quantity called the maximum supportable network size. The basic scheme (and its variants) support networks of arbitrarily large sizes, whereas the random pairwise scheme has only limited supports.

Example B.5.

B.5.1. Multi-hop Range Extension

Since m and d are limited by hard constraints, the only way to increase the maximum supportable network size is to increase the effective size n′ of the physical neighbourhood of a node. The multi-hop range extension strategy accomplishes that. In the direct key establishment phase, each node u broadcasts its ID. Each physical neighbour v of u re-broadcasts the ID of u. Each physical neighbour w of v then re-re-broadcasts the ID of u. This process is continued for a predetermined number r of hops. Any node u′ reachable from u in ≤ r hops and sharing a pairwise key with u can now establish a path of secure communication with u. During a future communication between u and u′, the intermediate nodes in the path simply forward a message encrypted by the pairwise key between u and u′. Using r hops thereby increases the effective radius of physical neighbourhood by a factor of r, and consequently the number of effective neighbours of each node gets multiplied by a factor of r². Thus, the maximum supportable network size now becomes

For r = 3 and for the parameters of Example B.5, this size now attains a more decent value of 3375.

Increasing r incurs some cost. First, the communication overhead increases quadratically with r. Second, since intermediate nodes in a multi-hop path simply retransmit messages without authentication, chances of specific active attacks at these nodes increase. Large values of r are, therefore, discouraged.