Affordable Access

Combinatorial design of key distribution mechanisms for wireless sensor networks

Institute of Electrical and Electronics Engineers (IEEE)
Publication Date
  • 010104 Combinatorics And Discrete Mathematics (Excl. Physical Combinatorics)
  • 080402 Data Encryption
  • 100503 Computer Communications Networks
  • 100510 Wireless Communications
  • Wireless Sensor Networks
  • Key Distribution Mechanism
  • Balanced Incomplete Block Designs
  • Generalized Quadrangles
  • Key-Chains
  • Communication
  • Computer Science
  • Design
  • Mathematics


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 prior 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 sizes.

There are no comments yet on this publication. Be the first to share your thoughts.