Research Article
Unassailable Sensor Networks
@INPROCEEDINGS{10.1145/1460877.1460911, author={Alessandro Mei and Alessandro Panconesi and Jaikumar Radhakrishnan}, title={Unassailable Sensor Networks}, proceedings={4th International ICST Conference on Security and Privacy in Communication Networks}, publisher={ACM}, proceedings_a={SECURECOMM}, year={2008}, month={9}, keywords={Wireless sensor network random pre-distribution of keys security.}, doi={10.1145/1460877.1460911} }- Alessandro Mei
Alessandro Panconesi
Jaikumar Radhakrishnan
Year: 2008
Unassailable Sensor Networks
SECURECOMM
ACM
DOI: 10.1145/1460877.1460911
Abstract
We show that massive attacks against sensor networks that use random key pre-distribution schemes cannot be cheap, provided that the parameters are set in the right way. By choosing them appropriately, any adversary whose aim is to compromise a large fraction of the communication links is forced, with overwhelming probability, to capture a large fraction of the nodes. This holds regardless of the information available to the adversary to select the nodes. We consider two important security properties: We say that the network is unassailable if the adversary cannot compromise a linear fraction of the communication links by compromising a sub-linear fraction of the nodes, and that the network is unsplittable if the adversary cannot partition the network into two (or more) linear size fragments. We show how to set the relevant parameters of random key pre-distribution---pool and key ring size---in such a way that the network is not only connected, but also provably unassailable and unsplittable with high probability. Moreover, we also show how to set the parameters in such a way to form a giant component in the network, a connected subgraph including, say, 99\% of the sensors. Giant components emerge by using much smaller key rings, are sparse, and, quite remarkably, are provably unassailable and unsplittable as well. All these results are supported by experiments.