An efficient random key pre-distribution scheme

Mahalingam Ramkumar, Nasir Memon

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Any key pre-distribution (KPD) scheme is inherently a trade-off between complexity and security. By sacrificing some security (KPD schemes need some assurance of the ability to limit sizes of attacker coalitions), KPD schemes gain many advantages. We argue that random KPD schemes, in general, perform an "advantageous" trade-off which renders them more suitable for practical large scale deployments of resource constrained nodes. We introduce a novel random KPD scheme, HAshed Random Preloaded Subsets (HARPS), which turns out to be a generalization of two other random KPD schemes - random preloaded subsets (RPS), and a scheme proposed by Leighton and Micali (LM). All three schemes have probabilistic measures for the "merit" of the system. We analyze and compare the performance of the three schemes. We show that HARPS has significant advantages over other KPD schemes, and in particular, over RPS and LM.

Original languageEnglish (US)
Title of host publicationGLOBECOM'04 - IEEE Global Telecommunications Conference
Number of pages6
StatePublished - 2004
EventGLOBECOM'04 - IEEE Global Telecommunications Conference - Dallas, TX, United States
Duration: Nov 29 2004Dec 3 2004


OtherGLOBECOM'04 - IEEE Global Telecommunications Conference
Country/TerritoryUnited States
CityDallas, TX

ASJC Scopus subject areas

  • General Engineering


Dive into the research topics of 'An efficient random key pre-distribution scheme'. Together they form a unique fingerprint.

Cite this