MKPS: a multivariate polynomial scheme for symmetric key-establishment in distributed sensor networks

ABSTRACT

Privacy is a critical service in node-to-node communications when sensor networks are deployed in adversarial environments. However, providing this service is a nontrivial task because of the lack of infrastructure and node limitations. Existing techniques distribute secret keys to the network users through a trusted third party or using computationally-complex public-key methods. An alternative approach is pre-distributing keying material to the nodes prior to the network deployment. Exploiting the mathematical properties of symmetric polynomials, we propose a multivariate key pre-distribution scheme (MKPS) in this paper. In this scheme, using uniquely assigned IDs, shares of d-variate polynomials are stored into the memory of every sensor. After the network deployment, every two neighbor nodes at the unit Hamming distance of each other establish exactly d-1 common keys without any interaction with a third party in the network. The final secret key used by these nodes is a symmetric combination of all the common keys. We will show that this feature significantly improves the security of the MKPS over previous schemes. The proposed method is in the category of threshold schemes, i.e., it remains perfectly secure up to the capture of a certain fraction of sensor nodes. We also propose a location-aware MKPS in which, by taking advantage of the location information, perfect connectivity is achieved. The new location-aware scheme is a cell-based method in which nodes are randomly deployed within hexagonal cells. Nodes are unaware of their exact locations. Nevertheless, they know the coordinates of their residing cells. One MKPS is used to secure communications within every cell and one to secure communications between cells. This location-based scheme significantly improves the resiliency of the network against the node capture.

REFERENCES

• 1: T. Arampatzis, J. Lygeros, and S. Manesis. A survey of applications of wireless sensors and wireless sensor networks. In Proc. IEEE Int. Symp. Intelligent Control, volume 1, pages 719--724, Limassol, Cyprus, June 2005. IEEE.
• 2: R. Blom. Non-public key distribution. In D. Chaum, R. L. Rivest, , and A. T. Sherman, editors, Proc. Adv. Cryptol. - CRYPTO'82, pages 231--236, NY, 1982. Plenum Publishing.
• 3: 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
• 4: 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
• 5: W. Du, J. Deng, Y. S. Han, S. Chen, and P. K. Varshney. A key management scheme for wireless sensor networks using deployment knowledge. In Proc. IEEE Conf. Comput. Commun. - INFOCOM'04, volume 1, pages 586--597, NJ, 2004. IEEE.
• 6: 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]
• 7: 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]
• 8: Dijiang Huang , Manish Mehta , Deep Medhi , Lein Harn, Location-aware key management scheme for 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.1029110]
• 9: Joengmin Hwang , Yongdae Kim, Revisiting random key pre-distribution schemes for 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.1029111]
• 10: Donggang Liu , Peng Ning, Location-based pairwise key establishments for static sensor networks, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia [doi>10.1145/986858.986869]
• 11: Donggang Liu , Peng Ning , Rongfang Li, Establishing pairwise keys in distributed sensor networks, ACM Transactions on Information and System Security (TISSEC), v.8 n.1, p.41-77, February 2005 [doi>10.1145/1053283.1053287]
• 12: Roberto Di Pietro , Luigi V. Mancini , Alessandro Mei, Random key-assignment for secure Wireless Sensor Networks, Proceedings of the 1st ACM workshop on Security of ad hoc and sensor networks, October 31, 2003, Fairfax, Virginia [doi>10.1145/986858.986868]
• 13: H. Pishro-Nik, K. Chan, and F. Fekri. On connectivity properties of large-scale wireless sensor networks. In Proc. First Ann. IEEE Commun. Society Conf. on Sensor Commun. and Net., Santa Clara, CA, 4-7 October 2004. CD-ROM.
• 14: Gordon L. Stüber, Principles of mobile communication (2nd ed.), Kluwer Academic Publishers, Norwell, MA, 2001

INDEX TERMS

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

General Terms:
Security

Keywords:
key pre-distribution, location-aware, multivariate polynomial, wireless sensor network