Percolation on the Information-Theoretically Secure Signal to Interference Ratio Graph

Rahul Vaze, Srikanth K. Iyer

TL;DR

This paper establishes the mathematical conditions for global, secure connectivity in wireless networks plagued by both mutual interference and eavesdroppers. By modeling the network as a "Secure SINR Graph," the authors prove that a "giant component" of secure links will emerge (percolate) provided the density of legitimate users is high enough and interference is sufficiently suppressed.

What Problem Does This Paper Address?

In wireless communication, two major hurdles prevent reliable and private data transfer: interference (signals from other legitimate users clashing) and eavesdropping (unauthorized parties intercepting the signal).

Historically, researchers studied these issues in isolation:

  1. SINR Graphs: Focused on how interference affects connectivity but ignored security.
  2. Secrecy Graphs: Focused on eavesdroppers but assumed users didn't interfere with each other (e.g., they used different frequencies).

The real world is messier. Legitimate users often transmit simultaneously, creating a background of interference that affects both the intended receiver and the eavesdropper. This paper tackles the Secure SINR Graph (SSG), where a link is only "secure" if the signal-to-interference-plus-noise ratio (SINR) at the intended receiver is strictly better than the SINR at any potential eavesdropper. The challenge is that this connection threshold is no longer a fixed number; it’s a complex random variable that depends on the locations of every node in the network.

Methods

The authors use stochastic geometry and continuum percolation theory to analyze the network. They model legitimate nodes and eavesdroppers as two independent Poisson Point Processes (PPPs) in a 2D plane.

Key technical approaches include:

  • Lattice Mapping: To prove that the network can connect over long distances (the super-critical regime), the authors tile the 2D plane into a square lattice. They define an edge in this lattice as "open" if a specific set of local conditions are met (e.g., at least one legitimate node exists, no eavesdroppers are nearby, and interference is low). By showing this discrete lattice percolates, they prove the underlying continuous wireless network does too.
  • Dual Graph Blocking: To prove the "sub-critical" regime (where the network fails to connect), they define a "blocking" graph formed by eavesdropper connections. If this eavesdropper-based graph forms an infinite structure, it geometrically "strangles" the legitimate network, preventing any infinite connected components from forming.
  • Interference Suppression ($\gamma$): They incorporate a parameter $\gamma$ representing the "processing gain." Legitimate receivers can use coding to suppress interference, but eavesdroppers (who don't know the code) cannot. This mathematical asymmetry is what allows secure communication to exist even in noisy environments.

Datasets

Not discussed in the paper. As a theoretical work in probability and information theory, the results are derived through formal proofs rather than empirical data or simulations.

Key Insights and Ideas

  • The "Security Edge": The most critical insight is that legitimate users have an advantage because they can coordinate. By using interference suppression ($\gamma$), legitimate nodes can "clean up" their received signal in a way that an eavesdropper cannot. This creates a "window" of SINR where a link is viable for a friend but useless for a foe.
  • Random Thresholds: Unlike standard connectivity models where you just need a signal above a certain decibel level, security here requires being "better than the best eavesdropper." This makes the connectivity of one link dependent on the global state of the network.
  • Phase Transitions: The paper proves that wireless security isn't a linear scale; it’s a binary state at scale. There is a "critical density" ($\lambda_c$). If your user density is below this, the network is a collection of isolated islands. Once you cross it, a massive, interconnected, secure backbone suddenly emerges.

Key Results

  • Theorem 1.1 (Connectivity is Possible): For any finite density of eavesdroppers, there exists a high enough density of legitimate nodes and a small enough interference parameter $\gamma$ such that the network will form an infinite secure component.
  • Theorem 1.2 (The Lower Bound): Conversely, if the density of legitimate nodes is too low, the network will never percolate, regardless of how well you suppress interference.
  • Universal Lower Bound: The authors show that the case with zero interference ($\gamma = 0$) provides a "universal lower bound." If the network can't connect without interference, it certainly won't connect with it.

Limitations and Future Work

  • Static Nodes: The model assumes nodes are stationary. In reality, mobile users and eavesdroppers would change the topology dynamically.
  • One-Way Security: The paper focuses on "out-components"—the ability of a node to send a secure message. It does not deeply explore bi-directional secure connectivity (where both parties can talk back and forth securely), though it notes this is a logical next step.
  • Simplified Path-Loss: The results depend on the signal attenuation function $\ell(x)$. While the proofs cover a wide class of functions, extremely complex environments (like urban canyons with heavy shadowing) might require more nuanced models.
  • Infinite vs. Finite: Percolation theory deals with infinite planes. While this provides excellent insights for large networks, the behavior of small, edge-constrained networks (like a single office building) might differ.

Summary updated

Abstract

We consider a continuum percolation model consisting of two types of nodes, namely legitimate and eavesdropper nodes, distributed according to independent Poisson point processes in R2 of intensities λ and λE, respectively. A directed edge from one legitimate node A to another legitimate node B exists provided that the strength of the signal transmitted from node A that is received at node B is higher than that received at any eavesdropper node. The strength of the signal received at a node from a legitimate node depends not only on the distance between these nodes, but also on the location of the other legitimate nodes and an interference suppression parameter γ. The graph is said to percolate when there exists an infinitely connected component. We show that for any finite intensity λE of eavesdropper nodes, there exists a critical intensity λc < ∞ such that for all λ > λc the graph percolates for sufficiently small values of the interference parameter. Furthermore, for the subcritical regime, we show that there exists a λ0 such that for all λ < λ0 ≤ λc a suitable graph defined over eavesdropper node connections percolates that precludes percolation in the graphs formed by the legitimate nodes.
BibTeX
@article{vaze2014percolation,
  author = {Rahul Vaze and Srikanth K. Iyer},
  title = {{Percolation on the Information-Theoretically Secure Signal to Interference Ratio Graph}},
  journal = {J. Appl. Probab.},
  year = {2014},
  url = {https://openreview.net/forum?id=ZRylrDLMGd},
}

Loading related content...

Figure