PaperlayerView exact revision on arXiv

Source-linked AI summary

The Secrecy Graph and Some of its Properties

Martin Haenggi

arXiv:0804.2249v1cs.ITcs.DMmath.ITmath.PR

TL;DR

To assess how secrecy constraints affect ad hoc-network connectivity, the paper introduces a random geometric secrecy graph whose links permit secure communication. It studies lattice and Poisson models and concludes that, in random networks, relative eavesdropper density 0.15 suffices to make percolation impossible.

  • Problem

    The paper asks how the secrecy constraint affects connectivity in ad hoc networks.

    Source: §I · p. 1

  • Method

    The paper defines a geometric graph retaining links that permit secure communication and studies degree and percolation properties for lattice and Poisson point-process models.

    Source: §I · p. 1, §II · p. 2, B. Poisson model · p. 2

  • Results

    In the random case, relative eavesdropper density 0.15 is sufficient to make percolation impossible.

    Source: §V · p. 5

  • Takeaways & Limitations

    The paper concludes that eavesdroppers are rather harmful to connectivity in random networks.

    Source: §V · p. 5

Abstract

from arXiv · show

A new random geometric graph model, the so-called secrecy graph, is introduced and studied. The graph represents a wireless network and includes only edges over which secure communication in the presence of eavesdroppers is possible. The underlying point process models considered are lattices and Poisson point processes. In the lattice case, analogies to standard bond and site percolation can be exploited to determine percolation thresholds. In the Poisson case, the node degrees are determined and percolation is studied using analytical bounds and simulations. It turns out that a small density of eavesdroppers already has a drastic impact on the connectivity of the secrecy graph.

I. INTRODUCTION

The paper introduces a random geometric secrecy graph that retains links over which secure communication is possible, using a geometric constraint based on eavesdropper locations. It defines directed and undirected versions and studies their degree properties and behavior on stochastic point processes.

II. THE SECRECY GRAPH

  • The directed graph retains x_i→x_j only when no eavesdropper lies within distance δ(x_i,x_j) of transmitter x_i.The paper’s secrecy constraint follows from assuming transmission near the intended receiver’s channel capacity, so a more distant eavesdropper cannot intercept the message.Source: §II · p. 1, §I · p. 1
  • The basic graph keeps links secure in both directions, while the enhanced graph also keeps one-way secure links that can support a reply using a one-time pad.The paper says this use lowers link capacity from 1/2 in each direction to 1/3.Source: §II · p. 1
  • The directed graph’s mean in-degree and out-degree are equal, and the two undirected mean degrees sum to twice either directed mean degree.The relation is N̄ + N̄′ = 2N̄_in = 2N̄_out.Source: §II · p. 1
  • The study examines degree distributions and percolation thresholds for secrecy graphs on lattices and Poisson point processes.The paper treats these as stochastic vertex-location models.Source: §II · p. 2

A. Lattice model

The lattice model uses a square lattice with independently thinned eavesdropper locations, while the Poisson model uses independent point processes for legitimate nodes and eavesdroppers. The Poisson setup also defines an intensity threshold for the absence of percolation at radii above Gilbert’s critical radius.

A. Lattice model

  • The lattice model uses the standard square lattice, with eavesdroppers placed by independently thinning a regular point set with probability p.The corresponding secrecy graphs are denoted by G⃗_p, G_p, and G′_p.Source: A. Lattice model · p. 2

B. Poisson model

  • In the Poisson model, legitimate nodes form a unit-intensity PPP and independent eavesdroppers form a PPP of intensity λ over Gilbert’s disk graph with range r.The underlying disk graph connects nodes at distance at most r.Source: B. Poisson model · p. 2
  • For r > r_G, λ_c(r) is the infimum eavesdropper intensity λ for which θ(λ,r) = 0.Here θ(λ,r) is the probability that the component containing the origin is infinite.Source: B. Poisson model · p. 2

III. PROPERTIES OF THE LATTICE SECRECY GRAPHS

For lattice secrecy graphs, percolation thresholds depend on eavesdropper placement: edge-midpoint placement has threshold p=1/2, while placement on lattice sites has a threshold of about 0.41.

III. PROPERTIES OF THE LATTICE SECRECY GRAPHS

  • p=1/2 is the percolation threshold for G′_p when eavesdroppers occupy edge midpoints, analogous to bond percolation.At this threshold, eavesdropper density equals good-guy density; the graph still percolates when the eavesdropper density is any factor 1−ε below the good-guy density.Source: §III · p. 2
  • When eavesdroppers are placed on lattice sites, the maximum density is about 0.41, based on the estimated site-percolation threshold.The site-percolation critical probability is stated to be about 0.59.Source: §III · p. 2
  • Among regular eavesdropper placements, edge-midpoint placement appears to cause the least damage to secrecy-graph connectivity.This comparison refers to the eavesdropper locations specified in (8).Source: §III · p. 2

A. Isolation probabilities for r = ∞

For r=∞, directed out-isolation occurs when the nearest point in the combined good-node and eavesdropper processes is an eavesdropper. In the basic graph, in-isolation is less probable than out-isolation, and isolation in the enhanced graph is least probable.

A. Isolation probabilities for r = ∞

  • In the directed graph, out-isolation is the event that the nearest point in Φ∪Ψ is an eavesdropper.The combined process has density 1 + λ.Source: A. Isolation probabilities for r = ∞ · p. 2
  • For the basic graph, the nearest good-node distance R has density 2πr exp(−πr²), and its two-disk exclusion area is cπR².Here c = 4/3 + 3/(2π).Source: A. Isolation probabilities for r = ∞ · p. 2
  • In-isolation is less probable than out-isolation, and the enhanced graph has the smallest isolation probability.For in-isolation, every other node must have an eavesdropper in its corresponding exclusion disk; this requires a larger area to be free of eavesdroppers.Source: A. Isolation probabilities for r = ∞ · p. 2

B. Degree distributions

The degree results connect power constraints and eavesdropper density to degree distributions and mean degree. Poisson and geometric distributions arise as limiting cases, while the mean degree changes between power-limited and secrecy-limited regimes.

B. Degree distributions

  • As r→∞, the directed out-degree is geometric with mean 1/λ.The count is n when the first n points in the combined nearest-neighbor sequence are good nodes and the next is an eavesdropper.Source: B. Degree distributions · p. 3
  • For finite r, if no eavesdropper lies within distance r, the degree is Poisson with mean πr²; otherwise it is Poisson with mean πR².R is the distance to the nearest eavesdropper.Source: B. Degree distributions · p. 3
  • For finite r, isolation probability combines the cases of no node within range and a nearest node that is an eavesdropper.As λ→0, it approaches the Poisson isolation probability; as r→∞, it approaches the geometric isolation probability.Source: B. Degree distributions · p. 3
  • The two-parameter degree distribution includes Poisson and geometric distributions as special cases, and Fig. 2 compares it with both limits.The Poisson limit occurs as λ→0; the geometric limit occurs as r→∞.Source: B. Degree distributions · pp. 3–4, Figure 2 · p. 3
  • The mean degree grows approximately as πr² for small r, then is capped at 1/λ by the secrecy constraint.The boundary between power-limited and secrecy-limited regimes is 2πr² = 1/λ, with inflection at rT = (2πλ)^−1/2.Source: Figure 3 · p. 3, B. Degree distributions · p. 4
  • At fixed r, the mean degree decreases monotonically with λ, from πr² to 0, and is upper-bounded by 1/λ.Source: B. Degree distributions · p. 4
  • For r = ∞, the passage introduces the transmission range (power) needed to get within ε of the maximum mean out-degree, but provides no recoverable value.Source: B. Degree distributions · p. 4
  • The mean degree satisfies the bounds a/λ > EN > b/λ; the cited passage also gives EN = 1/(λc) ≈ 0.62/λ.Here b = 1/4.Source: B. Degree distributions · p. 4

C. Secrecy ratios

The secrecy ratios decrease as either range or eavesdropper density increases. In some graphs, more than half of the links are secure in only one direction unless one-time pads are used.

C. Secrecy ratios

  • η(λ, r) decreases in both r and λ.The passage introduces relative edge densities of the enhanced and basic graphs as a related quantity.Source: C. Secrecy ratios · p. 4
  • As λr² grows, the ratio of mean degrees reaches a minimum of (2c − 1)⁻¹, and more than 50% of links can be secure in only one direction.One-time pads are an exception to this directional limitation.Source: C. Secrecy ratios · p. 4

D. Edge lengths

In the unlimited-range graph, edge lengths are close to Rayleigh distributed, while the finite-range, low-eavesdropper limit has a different density.

D. Edge lengths

  • The simulated edge-length distribution in G⃗λ,∞ is very close to Rayleigh, with mean 1/(2λ).Longer edges occur very slightly more often than the Rayleigh distribution predicts.Source: D. Edge lengths · p. 4
  • Nodes whose nearest bad guy is farther away have many long edges, slightly skewing the edge-length distribution toward longer edges.Source: D. Edge lengths · p. 4
  • For finite r as λ → 0, the edge-length pdf converges to 2x/r² for 0 ≤ x ≤ r.Source: D. Edge lengths · p. 4

E. Oriented percolation of⃗Gλ,r

Oriented out-percolation asks whether the origin has a positive probability of an infinite out-component. The critical-density boundary rises with range and approaches a finite limit; simulations estimate that limit at approximately 0.1499.

E. Oriented percolation of⃗Gλ,r

V. CONCLUDING REMARKS

The paper introduces secrecy graphs for secure communication and studies lattice- and Poisson-based networks. Its Poisson analysis finds that a relative eavesdropper density of 0.15 suffices to make percolation impossible.

V. CONCLUDING REMARKS

  • The secrecy graph models secure communication by including only links over which communication is possible in the presence of eavesdroppers.Source: §V · p. 5
  • For lattice models, the analysis uses direct analogies to bond and site percolation; for Poisson networks, it derives mean degrees and, in some cases, degree distributions.A two-parameter distribution found in the analysis includes Poisson and geometric distributions as special cases.Source: §V · p. 5
  • In the random case, a relative eavesdropper density of 0.15 is sufficient to make percolation impossible.The percolation region is bounded and numerically determined.Source: §V · p. 5
Loading 0804.2249v1…