Mixing in Random Digraphs with Application to the Forward-Secure Key Evolution in Wireless Sensor Networks

• Published in: ACM transactions on sensor networks 2015-03, Vol.11 (2), p.1-27
• Main Authors: Klonowski, Marek, Kutyłowski, Mirosław, Ren, Michał, Rybarczyk, Katarzyna
• Format: Article
• Language: English
• ISSN: 1550-4859; 1550-4867
• DOI: 10.1145/2637482

A key distribution scheme for wireless sensor networks based on a system of dynamic, pairwise keys is considered. In the scheme, each pair of communicating nodes shares pairwise symmetric keys and changes them at every transmission using a set of hashing functions. This article examines security aspects of the protocol. The most important issue is to ensure that it is infeasible for an adversary to restrict exhaustive key search to a subset of the keyspace. This desirable property holds if, after a small number of random key transitions, the distribution of keys among the nodes is close to uniform. The article provides a rigorous mathematical analysis of the distribution of keys and supplements it with experimental results. The problem is reduced to the question of determining mixing time and the stationary distribution of a random walk on a random digraph. It is shown that with probability close to 1, the mixing time is of small order and the fluctuations of the distribution are limited. This ensures the ongoing security of the protocol by making the communications forward secure and protecting against node compromise.