An efficient random key pre-distribution scheme

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.