4th International ICST Conference on Security and Privacy in Communication Networks

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},
        keywords={Wireless sensor network random pre-distribution of keys security.},
  • Alessandro Mei
    Alessandro Panconesi
    Jaikumar Radhakrishnan
    Year: 2008
    Unassailable Sensor Networks
    DOI: 10.1145/1460877.1460911
Alessandro Mei1,*, Alessandro Panconesi1,*, Jaikumar Radhakrishnan2,*
  • 1: Dept of Computer Science Sapienza University of Rome
  • 2: School of Technology and Computer Science TIFR, Mumbai, India
*Contact email: mei@di.uniroma1.it, ale@di.uniroma1.it, jaikumar@tifr.res.in


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.