2nd International ICST Conference on Security and Privacy in Comunication Networks

Research Article

Sensor Networks that Are Provably Resilient

  • @INPROCEEDINGS{10.1109/SECCOMW.2006.359569,
        author={Roberto  Di Pietro and Luigi V. Mancini and Alessandro Mei and Jaikumar  Radhakrishnan},
        title={Sensor Networks that Are Provably Resilient},
        proceedings={2nd International ICST Conference on Security and Privacy in Comunication Networks},
  • Roberto Di Pietro
    Luigi V. Mancini
    Alessandro Mei
    Jaikumar Radhakrishnan
    Year: 2007
    Sensor Networks that Are Provably Resilient
    DOI: 10.1109/SECCOMW.2006.359569
Roberto Di Pietro1,*, Luigi V. Mancini2,*, Alessandro Mei2,*, Jaikumar Radhakrishnan3,*
  • 1: Dipartimento di Matematica, Universita di Roma Tre, Italy
  • 2: Alessandro Panconesi, Dipartimento di Informatica, Universita di Roma “La Sapienza”, Italy
  • 3: School of Technology and CS, Tata Institute of Fundamental, Research, Bombay, India
*Contact email: dipietro@mat.uniroma3.it, mancini@di.uniroma1.it, mei.ale@di.uniroma1.it, jaikumar@tifr.res.in


We give, for the first time, a precise mathematical analysis of the connectivity and security properties of sensor networks that make use of the random pre-distribution of keys. We also show how to set the parameters - pool and key-ring size - in such a way that the network is not only connected with high probability via secure links, but also provably resilient, in the following sense: we formally show that any attacker that captures sensors at random with the aim of compromising a constant fraction of the secure links, must capture at least a constant fraction of the nodes of the network. In the context of wireless sensor networks where random pre-distribution of keys is employed, we are the first to provide a mathematically precise proof, with a clear indication of parameter choice, that two crucial properties connectivity via secure links and resilience against malicious attacks - can be obtained simultaneously. Our theoretical results are complemented by extensive simulations that reinforce our main conclusions