Technical Reports

The ICICS/CS Reading Room

UBC CS TR-2009-18 Summary

On Improving Key Pre-distribution Schemes for Sensor Networks, July 24, 2009 Majid "Khabbazian, Ian Blake, Vijay Bhargava and Hosna" Jabbari, 9 pages

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.

If you have any questions or comments regarding this page please send mail to