Redoubtable Sensor Networks

ABSTRACT

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 predistribution 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 adversary 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 predistribution 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. We also show in a mathematically rigorous way that the network enjoys another strong security property. The adversary cannot partition the network into two linear size components, compromising all the links between them, unless it captures linearly many nodes. This implies that the network is also fault tolerant with respect to node failures. Our theoretical results are complemented by extensive simulations that reinforce our main conclusions.

REFERENCES

• 1: I. F. Akyildiz , W. Su , Y. Sankarasubramaniam , E. Cayirci, Wireless sensor networks: a survey, Computer Networks: The International Journal of Computer and Telecommunications Networking, v.38 n.4, p.393-422, 15 March 2002 [doi>10.1016/S1389-1286(01)00302-4 ]
• 2: Christian Bettstetter, On the minimum node degree and connectivity of a wireless multihop network, Proceedings of the 3rd ACM international symposium on Mobile ad hoc networking & computing, June 09-11, 2002, Lausanne, Switzerland [doi>10.1145/513800.513811]
• 3: R Blom, An optimal class of symmetric key generation systems, Proc. of the EUROCRYPT 84 workshop on Advances in cryptology: theory and application of cryptographic techniques, p.335-338, December 1985, Paris, France
• 4: Carlo Blundo , Alfredo De Santis , Amir Herzberg , Shay Kutten , Ugo Vaccaro , Moti Yung, Perfectly-Secure Key Distribution for Dynamic Conferences, Proceedings of the 12th Annual International Cryptology Conference on Advances in Cryptology, p.471-486, August 16-20, 1992
• 5: Bollobas, B. 1998. Modern Graph Theory. Springer.
• 6: Haowen Chan , Adrian Perrig , Dawn Song, Random Key Predistribution Schemes for Sensor Networks, Proceedings of the 2003 IEEE Symposium on Security and Privacy, p.197, May 11-14, 2003
• 7: Conti, M., Di Pietro, R., and Mancini, L. V. 2007. Ecce: Enhanced cooperative channel establishment for secure pairwise communication in wireless sensor networks. Ad Hoc Netw. 5, 1, 49--62.
• 8: Roberto Di Pietro , Luigi V. Mancini , Alessandro Mei, Energy efficient node-to-node authentication and communication confidentiality in wireless sensor networks, Wireless Networks, v.12 n.6, p.709-721, November 2006 [doi>10.1007/s11276-006-6530-5]
• 9: Roberto Di Pietro , Luigi V. Mancini , Alessandro Mei , Alessandro Panconesi , Jaikumar Radhakrishnan, Connectivity properties of secure wireless sensor networks, Proceedings of the 2nd ACM workshop on Security of ad hoc and sensor networks, October 25-25, 2004, Washington DC, USA [doi>10.1145/1029102.1029112]
• 10: Wenliang Du , Jing Deng , Yunghsiang S. Han , Pramod K. Varshney, A pairwise key pre-distribution scheme for wireless sensor networks, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948118]
• 11: Erdös, P. and Rényi, A. 1960. On the evolution of random graphs. Publ. Math. Inst. Hungar. Acad. Sci. 5, 17--61.
• 12: Laurent Eschenauer , Virgil D. Gligor, A key-management scheme for distributed sensor networks, Proceedings of the 9th ACM conference on Computer and communications security, November 18-22, 2002, Washington, DC, USA [doi>10.1145/586110.586117]
• 13: James Allen Fill , Edward R. Scheinerman , Karen B. Singer-Cohen, Random intersection graphs when m= w(n): an equivalence theorem relating the evolution of the G(n, m, p) and G(n,P<>/italic>) models, Random Structures & Algorithms, v.16 n.2, p.156-176, March 2000 [doi>10.1002/(SICI)1098-2418(200003)16:2<156::AID-RSA3>3.0.CO;2-H ]
• 14: Michał Karoński , Edward R. Scheinerman , Karen B. Singer-Cohen, On Random Intersection Graphs: The Subgraph Problem, Combinatorics, Probability and Computing, v.8 n.1-2, p.131-159, January 1999
• 15: Donggang Liu , Peng Ning, Establishing pairwise keys in distributed sensor networks, Proceedings of the 10th ACM conference on Computer and communications security, October 27-30, 2003, Washington D.C., USA [doi>10.1145/948109.948119]
• 16: Newman, M. E. J. 2003. The structure and function of complex networks. SIAM Rev. 45, 167--256.
• 17: Mathew D. Penrose, On k-connectivity for a geometric random graph, Random Structures & Algorithms, v.15 n.2, p.145-164, Sept.1999 [doi>10.1002/(SICI)1098-2418(199909)15:2<145::AID-RSA2>3.0.CO;2-G ]
• 18: Adrian Perrig , Robert Szewczyk , Victor Wen , David Culler , J. D. Tygar, SPINS: security protocols for sensor networks, Proceedings of the 7th annual international conference on Mobile computing and networking, p.189-199, July 2001, Rome, Italy [doi>10.1145/381677.381696]
• 19: Singer-Cohen, K. B. 1995. Random intersection graphs. Ph.D. thesis, Department of Mathematical Sciences, The Johns Hopkins University.
• 20: Dudley Stark, The vertex degree distribution of random intersection graphs, Random Structures & Algorithms, v.24 n.3, p.249-258, May 2004 [doi>10.1002/rsa.v24:3]
• 21: Watts, D. J., and Strogatz, S. H. 1998. Collective dynamics of “small world” networks. Nature 393, 440--442.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.0 General
          Subjects: Security and protection (e.g., firewalls)

Additional Classification:
  C. Computer Systems Organization
  C.2 COMPUTER-COMMUNICATION NETWORKS
      C.2.1 Network Architecture and Design
          Subjects: Wireless communication
      C.2.4 Distributed Systems

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.6 Security and Protection
          Subjects: Cryptographic controls

  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks

  K. Computing Milieux
  K.6 MANAGEMENT OF COMPUTING AND INFORMATION SYSTEMS
      K.6.5 Security and Protection (D.4.6, K.4.2)

General Terms:
Design, Security

Keywords:
Wireless sensor network, connectivity, probabilistic key sharing, random graphs