On Improving Key Pre-distribution Schemes for Sensor Networks

ID
TR-2009-18
Authors
Majid Khabbazian, Ian Blake, Vijay Bhargava and Hosna Jabbari
Publishing date
July 24, 2009
Length
9 pages
Abstract
In this work, we show how to improve the resilience or computational cost of two primary key pre-distribution schemes.First, we consider the primary key pre-distribution scheme proposed by Eschenauer and Gligor and its extension by Chan, Perrig and Song. We propose a modified version of their schemes and prove that it provides significantly higher resilience than the original schemes at almost no extra cost. The second part of this work deals with the primary key pre-distribution scheme proposed by Blom and its extension by Du, Deng Han and Varshney. The key pre-distribution scheme by Blom and its extension offer much higher resilience than random key pre-distribution schemes at the cost of higher computational cost. We show that the computational cost of the Blom scheme can be significantly reduced at the cost of slight reduction in resilience or a small increase in memory requirement. It is expected that aspects of the techniques introduced here, suitably adapted, can be applied to other key distribution schemes to improve efficiency.