Space-Efficient Keying in Wireless Communication Networks

摘要

We investigate the problem of assigning keys to nodes in a network such that each node is able to communicate with every other node in a secure manner. We propose a key as- signment scheme that assigns at most log n 2 keys to each node, where n is the number of nodes in the network. The key that two nodes should use to securely communicate with each other is derived from at most log n keys and can be computed in O(log n) time. Finally, the collusion resistance of our scheme degrades gracefully as the number of collud- ing nodes increase in contrast to a recently proposed key assignment scheme that has zero collusion resistance (that is, two colluding nodes can eavesdrop on all communica- tion in the network). To our knowledge, the key assignment scheme presented in this paper is the most efficient secure key assignment scheme in terms of space that has been pro- posed so far. Key words: secure communication, key pre-distribution, poly-logarithmic key assignment, complete bipartite graph, complete graph, collusion resistance