Mixing in Random Digraphs with Application to the Forward-Secure Key Evolution in Wireless Sensor Networks
Open Access
- 18 December 2014
- journal article
- research article
- Published by Association for Computing Machinery (ACM) in ACM Transactions on Sensor Networks
- Vol. 11 (2) , 1-27
Abstract
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.Keywords
Funding Information
- Narodowe Centrum Nauki (DEC-2011/01/B/ST1/03943)
This publication has 10 references indexed in Scilit:
- From key predistribution to key redistributionTheoretical Computer Science, 2012
- Stationary distribution and cover time of random walks on random digraphsJournal of Combinatorial Theory, Series B, 2012
- The simple random walk and max‐degree walk on a directed graphRandom Structures & Algorithms, 2008
- Diverging Keys in Wireless Sensor Networks2006
- Key infection: smart trust for smart dust2004
- A key-management scheme for distributed sensor networks2002
- The Probabilistic Method2000
- Random Graphs2000
- Random oracles are practical1993
- Authentication and authenticated key exchangesDesigns, Codes and Cryptography, 1992