Unassailable sensor networks

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 un-splittable 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. Copyright 2008 ACM.