The best keying protocol for sensor networks

Many sensor networks (especially networks of mobile sensors or networks that are deployed to monitor crisis situations) are deployed in an arbitrary and unplanned fashion. Thus, any sensor in such a network can end up being adjacent to any other sensor in the network. To secure the communications between every pair of adjacent sensors in such a network, each sensor xx in the network needs to store n−1n−1 symmetric keys that sensor xx shares with all the other sensors, where nn is an upper bound on the number of sensors in the network. This storage requirement of the keying protocol is rather severe, especially when nn is large and the available storage in each sensor is modest. Earlier efforts to redesign this keying protocol and reduce the number of keys to be stored in each sensor have produced protocols that are vulnerable to impersonation, eavesdropping, and collusion attacks. In this paper, we present a fully secure keying protocol where each sensor needs to store (n+1)/2(n+1)/2 keys, which is much less than the n−1n−1 keys that need to be stored in each sensor in the original keying protocol. We also show that in any fully secure keying protocol, each sensor needs to store at least (n−1)/2(n−1)/2 keys.