Paper 2003/170

HARPS: HAshed Random Preloaded Subset Key Distribution

Mahalingam Ramkumar and Nasir Memon

Abstract

In this paper, we introduce HAshed Random Preloaded Subset (HARPS) key distribution, a scalable key predistribution scheme employing only symmetric crypto primitives. HARPS is ideally suited for resource constrained nodes that need to operate without a trusted authority (TA) for extended periods (as is the case for nodes forming mobile ad hoc networks (MANETs)). The performance of HARPS is compared with that of two other key predistribution schemes. The first, RPS, is a based on random intersection of keys preloaded in nodes. The second, is (a slight modification to) a scheme proposed by Leighton and Micali (LM). HARPS is a generalization of both RPS and LM. All the three schemes, rely on some degree of resistance to hardware tampering, and have probabilistic measures for the ``merit'' of the system. The merit of the schemes is a function of the probability that an attacker who has compromised N nodes (or has access to keys buried in N nodes) can ``eavesdrop'' on a conversation between R nodes (R=2 for unicast communications). We analyze and compare the performance of the three schemes for unicast and multicast communications. We show that HARPS has significant performance advantage over SIMS and LM.