An efficient key predistribution scheme for ad hoc network security

We introduce hashed random preloaded subsets (HARPS), a highly scalable key predistribution (KPD) scheme employing only symmetric cryptographic primitives. HARPS is ideally suited for resource constrained nodes that need to operate for extended periods without active involvement of a trusted authority (TA), as is usually the case for nodes forming ad hoc networks (AHNs). HARPS, a probabilistic KPD scheme, is a generalization of two other probabilistic KPDs. The first, random preloaded subsets (RPSs), is based on random intersection of keys preloaded in nodes. The second, proposed by Leighton and Micali (LM) is a scheme employing repeated applications of a cryptographic hash function. We investigate many desired properties of HARPS like scalability, computational and storage efficiency, flexibility in deployment modes, renewability, ease of extension to multicast scenarios, ability to cater for broadcast authentication, broadcast encryption, etc., to support its candidacy as an enabler for ad hoc network security. We analyze and compare the performance of the three schemes and show that HARPS has significant advantages over other KPDs, and in particular, over RPS and LM.