A random perturbation-based scheme for pairwise key establishment in sensor networks

A prerequisite for secure communications between two sensor nodes is that these nodes exclusively share a pairwise key. Although numerous pairwise key establishment (PKE) schemes have been proposed in recent years, most of them have no guarantee for direct key establishment, no resilience to a large number of node compromises, no resilience to dynamic network topology, or high overhead. To address these limitations, we propose a novel random perturbation-based (RPB) scheme in this paper. The scheme guarantees that any two nodes can directly establish a pairwise key without exposing any secret to other nodes. Even after a large number of nodes have been compromised, the pairwise keys shared by non-compromised nodes remain highly secure. Moreover, the scheme adapts to changes in network topology and incurs low computation and communication overhead. To the best of our knowledge, the RPB scheme is the only one that provides all these salient features without relying on public key cryptography. Through prototype-based evaluation, we show that the RPB scheme is highly efficient and practical for current generation of sensor nodes. In particular, to support a sensor network with up to 2¹⁶ nodes, establishing a pairwise key of 80 bits between any two 8-bit, 7.37-MHz MICA2 motes only requires about 0.13 second of CPU time, 0.33 KB RAM space, and 15 KB ROM space per node.