Performance of the Eschenauer-Gligor key distribution scheme under an ON/OFF channel

Osman Yagan

Abstract

We investigate the secure connectivity of wireless sensor networks (WSNs) under the random key distribution scheme of Eschenauer and Gligor (EG). Unlike previous research conducted under the assumption of full visibility, this study assumes a communication model where unreliable wireless links are represented as ON/OFF channels. We present scaling conditions for model parameters to ensure that the network has no isolated nodes and is securely connected with high probability as the number of nodes becomes large. These results are presented as full zero-one laws, providing the first complete analysis of the EG scheme under non-full visibility. Simulations demonstrate that these laws remain valid under the more realistic disk model, supporting conjectures regarding the connectivity of geometric random graphs with randomly deleted edges.

Introduction

Wireless Sensor Networks (WSNs) are frequently deployed in hostile or inaccessible environments, necessitating robust encrypted communications. However, the severe memory and power constraints of sensor nodes preclude the use of traditional public-key cryptography. The Eschenauer-Gligor (EG) scheme addresses this by assigning each node a random subset of keys (a "key ring") from a large global pool. Secure communication between two nodes is possible only if they are within physical transmission range and share at least one common key.

Historically, mathematical analyses of the EG scheme assumed "full visibility," where every node is within range of every other node. In practice, wireless links are limited by distance and environmental factors. If network parameters are dimensioned based on full-visibility assumptions, the resulting network may suffer from significant connectivity gaps. This paper bridges this gap by analyzing the EG scheme under an ON/OFF channel model, where physical links exist probabilistically, providing a more realistic baseline for network design.

Theoretical Framework

The network is modeled as the intersection of two distinct random graphs:

  1. The Random Key Graph: Represents the EG scheme, where an edge exists if two nodes share at least one key.
  2. The Erdős-Rényi (ER) Graph: Represents the ON/OFF physical channel, where an edge exists independently between any two nodes with a probability $\alpha$.

Using the method of first and second moments from random graph theory, the study establishes asymptotic zero-one laws. These laws identify sharp phase transitions where the probability of a network property (such as being fully connected) jumps from 0 to 1 as the number of nodes $n$ increases. A critical insight is that the threshold for full connectivity coincides with the threshold for the absence of isolated nodes, meaning that preventing isolation is the primary bottleneck for global connectivity.

Results and Validation

The research establishes a precise scaling law: if the product of the physical link probability $\alpha_n$ and the key-sharing probability $\beta_n$ scales as $\alpha_n \beta_n = c \frac{\log n}{n}$, the network is securely connected with probability 1 if $c > 1$, and disconnected with probability 0 if $c < 1$. This provides a sharp dimensioning guideline ($c=1$) for network engineers, avoiding the over-provisioning of keys which can compromise overall security.

Probability of connectivity under the ON/OFF model as a function of key ring size K for various link probabilities α.

As shown in Figure 1, simulations with $n=500$ nodes and a key pool of $P=10,000$ validate these asymptotic results. The empirical probability of connectivity exhibits a sharp jump exactly at the predicted theoretical thresholds for various values of $\alpha$.

Discussion: The ON/OFF Model as a Proxy

While the ON/OFF model assumes independent link failures, real-world wireless networks are spatial, often modeled by "disk models" where nodes connect if they are within a specific radius $\rho$. A significant finding of this work is that the connectivity behavior of the mathematically tractable ON/OFF model is asymptotically equivalent to the more complex disk model, provided the average number of physical neighbors is matched.

Probability of connectivity under the disk model, demonstrating the same phase transition behavior as the ON/OFF model.

Figure 2 illustrates that the disk model follows the same sharp transition patterns as the ON/OFF model. This empirical evidence supports the long-standing Gupta and Kumar conjecture regarding the connectivity of geometric random graphs with random edge deletions. Future work will focus on providing rigorous mathematical proofs for these zero-one laws specifically within geometric settings.

Summary updated

Abstract

We investigate the secure connectivity of wireless sensor networks under the random key distribution scheme of Eschenauer and Gligor. Unlike recent work which was carried out under the assumption of full visibility, here we assume a (simplified) communication model where unreliable wireless links are represented as on/off channels. We present conditions on how to scale the model parameters so that the network i) has no secure node which is isolated and ii) is securely connected, both with high probability when the number of sensor nodes becomes large. The results are given in the form of full zero-one laws, and constitute the first complete analysis of the EG scheme under non-full visibility. Through simulations these zero-one laws are shown to be valid also under a more realistic communication model, i.e., the disk model. The relations to the Gupta and Kumar's conjecture on the connectivity of geometric random graphs with randomly deleted edges are also discussed.
BibTeX
@article{yagan2012performance,
  author = {Osman Yagan},
  title = {{Performance of the Eschenauer-Gligor key distribution scheme under an ON/OFF channel}},
  journal = {IEEE Trans. Information Theory},
  year = {2012},
  url = {https://openreview.net/forum?id=1efmKLJ78T9},
}
Figure