Toronto Networking Seminar 2006

Combinatorial Key Distribution Algorithms for Sensor Networks

Bulent Yener
Rensselaer Polytechnic Institute

Date:  March  24,  3pm
Location: BA1210 (Bahen Center)


Key distribution is one of the most challenging security issues in distributed wireless sensor networks where sensor nodes are randomly scattered over a hostile territory. In such a sensor deployment scenario, there is no prior knowledge of post deployment configuration. For security solutions requiring pairwise keys, it is impossible to decide how to distribute key pairs to sensor nodes before the deployment. Existing approaches to this problem are to assign more than one key, namely a key-chain, to each node. Key-chains are randomly drawn from a key-pool. Either two neighboring nodes have a key in common in their key-chains, or there is a path, called key-path, among these two nodes where each pair of neighboring nodes on this path has a key in common. Problem in such a solution is to decide on the key-chain size and key-pool size so that every pair of nodes can establish a session key directly or through a path with high probability. The length of the key-path is the key factor for the efficiency of the design. In this talk we present "deterministic" and "hybrid" approaches, based on Combinatorial Design Theory, for key distribution and discuss their performance.


Bulent Yener is an Associate Professor in the Department of Computer Science and Co-Director of Pervasive Computing and Networking Center at Rensselaer Polytechnic Institute in Troy, New York, where he is also a member of the Griffiss Institute. He  received the MS. and Ph.D. degrees in Computer Science, both from Columbia University , in 1987 and 1994, respectively.  Before joining to RPI, I was a Member of Technical Staff at the Bell Laboratories in Murray Hill, New Jersey. He is an associate editor of ACM/Kluwer Winet journal and the IEEE Network Magazine, and serves as Chair of the Technical Committee on Computer Communications in the IEEE Communications Society.