CIF: Small: Random key predistribution in wireless sensor networks -- The impact of partial visibility

University Of Maryland, College Park, College Park MD

Investigators

Abstract

With wireless sensor networks deployed in hostile environments, there is a need for cryptographic protection to enable secure communications services. Unfortunately, many approaches developed for general networking environments do not take into account the unique features of such wireless networks. Starting with the original scheme of Eschenauer and Gligor, random key predistribution schemes have been proposed to address this challenge. Much of the work on these schemes has been carried out under the full visibility assumption whereby sensor nodes are all within communication range of each other. However, the question remains whether randomized key predistribution schemes can indeed deliver the needed security guarantees under wireless communication constraints. To explore how this partial visibility affects two basic issues, namely secure connectivity and resiliency, we study random graph models which are obtained by intersecting two random graphs, namely a communication graph (to model the communications constraints of the wireless medium) and a cryptographic graph (to capture the given predistribution scheme). Our goal is to better understand performance trade-offs and to develop guidelines for dimensioning available cryptographic, communication and computing resources. Intersecting two (or more) random graphs constitutes a modular approach for building graph models of greater complexity. Generally speaking, the structural properties of the random graph obtained by such intersection operations are determined by those of the intersecting random graphs. Since some of the component random graphs have been studied in the literature, existing results can be leveraged, and this makes the modeling paradigm quite appealing for dealing with the multi-dimensional applications encountered in wireless networking (and other areas). Technically, many of the questions of interest are asymptotic in nature (with the numbers of nodes becoming large). The project aims to make contributions on three fronts: (i) Advance the study of random graphs in new directions through probabilistic techniques; (ii) Develop a better understanding of new classes of random graphs which thus far seem to have received little attention in the literature; and (iii) Enhance one's understanding of security issues in some large-scale wireless networking environments. Such issues are inherent to the many critical infrastructures which are monitored by wireless sensor networks, and random key predistribution techniques have a role to play in making these environments more secure. Some of these ideas are likely to be of use in less challenged wireless environments as well.