Combinatorial Design of Key Distribution Mechanisms for Wireless Sensor Networks
Authors:
- 16 April 2007
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE/ACM Transactions on Networking
- Vol. 15 (2) , 346-358
Abstract
Secure communications in wireless sensor networks operating under adversarial conditions require providing pairwise (symmetric) keys to sensor nodes. In large scale deployment scenarios, there is no priory knowledge of post deployment network configuration since nodes may be randomly scattered over a hostile territory. Thus, shared keys must be distributed before deployment to provide each node a key-chain. For large sensor networks it is infeasible to store a unique key for all other nodes in the key-chain of a sensor node. Consequently, for secure communication either two nodes have a key in common in their key-chains and they have a wireless link between them, or there is a path, called key-path, among these two nodes where each pair of neighboring nodes on this path have a key in common. Length of the key-path is the key factor for efficiency of the design. This paper presents novel deterministic and hybrid approaches based on Combinatorial Design for deciding how many and which keys to assign to each key-chain before the sensor network deployment. In particular, Balanced Incomplete Block Designs (BIBD) and Generalized Quadrangles (GQ) are mapped to obtain efficient key distribution schemes. Performance and security properties of the proposed schemes are studied both analytically and computationally. Comparison to related work shows that the combinatorial approach produces better connectivity with smaller key-chain sizesKeywords
This publication has 13 references indexed in Scilit:
- Expander Graph based Key Distribution Mechanisms in Wireless Sensor Networks2006
- A combinatorial approach to key predistribution for distributed sensor networks2005
- Efficient self-healing group key distribution with revocation capability2003
- A pairwise key pre-distribution scheme for wireless sensor networks2003
- On communication security in wireless ad-hoc sensor networks2003
- Combinatorial design of multi-ring networks with combined routing and flow controlComputer Networks, 2002
- Some New Results on Key Distribution Patterns and Broadcast EncryptionDesigns, Codes and Cryptography, 1998
- Combinatorial design of congestion-free networksIEEE/ACM Transactions on Networking, 1997
- Combinatorial characterizations of authentication codesDesigns, Codes and Cryptography, 1992
- A Combinatorial Approach to Threshold SchemesSIAM Journal on Discrete Mathematics, 1988