Performance of the Eschenauer-Gligor Key Distribution Scheme Under an ON/OFF Channel

Osman Yagan

TL;DR

This paper analyzes the secure connectivity of Wireless Sensor Networks (WSNs) using the Eschenauer-Gligor (EG) random key distribution scheme under a realistic, unreliable communication environment. By modeling the network as the intersection of a random key graph and an Erdős-Rényi graph (an ON/OFF channel), the author establishes exact mathematical "zero-one laws" that dictate precisely how to scale network parameters to guarantee secure, network-wide connectivity.

What Problem Does This Paper Address?

Wireless Sensor Networks (WSNs) are often deployed in hostile environments, requiring encrypted communications. However, sensors have severe memory and power constraints, making traditional public-key cryptography impossible. The Eschenauer-Gligor (EG) scheme solves this by giving each node a random subset of keys (a "key ring") from a massive global pool. Two nodes can communicate securely if they are in physical range and share at least one key.

Historically, mathematical analyses of the EG scheme assumed "full visibility"—meaning every node was assumed to be within physical transmission range of every other node. In the real world, wireless links are unreliable and limited by distance. If network engineers dimension their sensor memory based on "full visibility" assumptions, the deployed network will likely suffer from disconnected, isolated nodes. This paper tackles this gap by analyzing the EG scheme under an "ON/OFF" channel model, where physical wireless links exist only probabilistically, providing a much more realistic baseline for network design.

Methods

The author approaches the problem using random graph theory. The overall network is modeled as the intersection of two different random graphs:

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

To find the critical thresholds for connectivity, the author uses the method of first and second moments. This rigorous probabilistic technique is used to prove asymptotic zero-one laws—sharp phase transitions where the probability of a network property (like being fully connected) jumps abruptly from 0 to 1 as the number of nodes $n$ approaches infinity. The author specifically proves bounds for the absence of isolated nodes and then shows this condition is sufficient to guarantee full graph connectivity.

Datasets

Not discussed in the paper. The research relies on mathematical proofs and synthetic Monte Carlo simulations (generated in MATLAB) rather than empirical datasets.

Key Insights and Ideas

  • Isolation is the Only Bottleneck: The critical threshold for the entire network being securely connected coincides exactly with the threshold for the absence of isolated nodes. If you provision just enough keys and transmission power to ensure no single node is left completely alone, the entire network will naturally form a single, connected component.
  • Sharp Dimensioning Guidelines: Previous attempts to model this problem resulted in loose bounds (e.g., requiring a scaling factor $c > 8$ to guarantee connectivity). This paper nails down the exact sharp threshold ($c=1$). This is a massive win for practical WSN design: over-provisioning keys wastes precious sensor memory and actually degrades overall network security (by making it easier for captured nodes to compromise the network).
  • A Proxy for Spatial Models: While the ON/OFF model assumes link failures are independent, real wireless networks are spatial (modeled by "disk models" where nodes connect if they are within a radius $\rho$). The author's simulations reveal a surprising insight: the connectivity behavior of the mathematically tractable ON/OFF model is asymptotically equivalent to the highly complex spatial disk model, provided the average number of physical neighbors is matched.

Key Results

  • The Zero-One Law: Let $\alpha_n$ be the probability of a physical link existing, and $\beta_n$ be the probability of two nodes sharing a key. If the combined probability scales as $\alpha_n \beta_n = c \frac{\log n}{n}$, the network is securely connected with a probability approaching 1 if $c > 1$, and disconnected with a probability approaching 0 if $c < 1$.
  • Finite-Node Validation: Through simulations of $n=500$ nodes and a key pool of $P=10,000$, the author showed that the theoretical asymptotic thresholds hold up perfectly for finite, practical network sizes. The empirical probability of connectivity jumps exactly at the predicted theoretical threshold.

Limitations and Future Work

  • Simplistic Channel Model: The ON/OFF channel model assumes that all wireless links fail independently. In reality, wireless links are spatially correlated (e.g., if node A is close to B, and B is close to C, A is highly likely to be close to C).
  • Future Work: The author notes that proving these zero-one laws for the more realistic spatial "disk model" (formally, a random geometric graph with random edge deletions) remains an open mathematical conjecture (originally posed by Gupta and Kumar). The empirical results in this paper strongly suggest the conjecture is true, paving the way for future rigorous proofs in 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: 1) has no secure node which is isolated and 2) 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},
}

Loading related content...

Figure