Source-linked AI summary
Random-Priority Frontier Routing: Tight $Θ(n^c)$ Bounds Against $c$-Node Cartels
Krišjānis Petručena
TL;DR
Compromised intermediate relays can observe relayed material in trusted-node networks, motivating routing that reduces dependence on any one relay. The paper introduces random-priority frontier routing, which repeatedly expands the highest-priority vertex on the global frontier under topology-oblivious access. For fixed cartel size c and target success probability q, Θ(n^c) independent executions suffice in the worst case, with a matching lower bound; the guarantee concerns cartel avoidance, not secret-key generation.
Problem
Trusted-node QKD can expose relayed material to compromised intermediate nodes, creating a need for path diversification with graph-independent cartel-avoidance guarantees.
Method
The paper assigns independent random priorities and repeatedly expands the highest-priority unvisited vertex on the global frontier of the explored connected region without prior topology knowledge.
Results
Θ(n^c) independent executions are sufficient in the worst case for fixed c and q, and matching constructions make this threshold tight.
Takeaways & Limitations
rpfr provides a tight topology-oblivious cartel-avoidance guarantee for admissible static cartels, while its guarantee does not establish that an avoided route yields secret key.
Takeaways & Limitations
Where a trusted, current topology map is available, disjoint-path selection can provide a stronger avoidance probability than rpfr.
Abstract
from arXiv · showhide
We study path diversification in trusted-node networks, where sensitive material is relayed through intermediate nodes, some of which may be compromised. Our randomized routing rule assigns each vertex an independent random priority and repeatedly expands the highest-priority vertex on the global frontier of the explored region. Let $G$ have $n$ vertices, let $s,t$ be honest endpoints, and let $C$ be a set of $c$ compromised intermediate vertices, called a cartel, whose deletion leaves $s$ and $t$ connected. For every fixed $c$ and every fixed target probability $q\in(0,1)$, we prove that $Θ(n^c)$ independent executions are sufficient in the worst case for some route to avoid $C$ with probability at least $q$.
1 Introduction
The paper introduces random-priority frontier routing, which replaces local random-walk choices with global highest-priority frontier expansion. It establishes a tight worst-case Θ(n^c) execution threshold for avoiding a fixed c-node cartel.
- Trusted-node QKD networks remain exposed when compromised relays observe relayed key material, motivating path diversification and privacy amplification.
- The preceding highestscore-neighbor rule hs was evaluated empirically and can have exponentially small cartel-avoidance probability.
- Global-frontier routing selects the highest-ranked unvisited vertex adjacent to the connected explored region, rather than making a local neighbor choice.
- The resulting procedure, random-priority frontier routing (rpfr), applies global extremal-frontier growth to an adversarial routing objective with a designated target.
- For fixed c, Θ(n^c) independent executions are sufficient in the worst case for a constant-probability cartel-free route, and a matching graph establishes tightness.
2 Model
The model uses a static admissible cartel and topology-oblivious exploration driven by fresh random vertex priorities. rpfr expands the highest-priority global frontier vertex until it reaches the target, preserving connectivity of the visited region.
- 2 Model: An admissible cartel is a set of c intermediate vertices whose deletion leaves an s–t path; separating cartels are excluded because avoidance is impossible.
- 2 Model: The cartel is static, and relayed material is intercepted exactly when the route visits a cartel vertex before first visiting t.
- 2 Model: The topology-oblivious procedure reveals adjacency only from visited vertices, while authenticated identifiers and trusted control-plane data prevent cartel manipulation of priorities or frontier discovery.
- 2.1 Random-priority frontier routing: Each vertex other than s receives an independent continuous random score, whose relative order is uniformly random.
- 2.1 Random-priority frontier routing: Algorithm 1 maintains scores and revealed graph access, moves through paths in the visited subgraph, and returns the exploration trace.
- 2.1 Random-priority frontier routing: Each selected frontier vertex neighbors the visited set, so the induced visited subgraph stays connected and relocation within it remains possible.
- 2.1 Random-priority frontier routing: The target is selected only when it has maximal score on the whole frontier, and fresh seeds can derive scores on demand without knowing the full vertex set.
3 Tight cartel-avoidance bound
The paper proves a universal cartel-avoidance bound for random-priority frontier routing and constructs instances attaining it. Consequently, independent reruns require Θ(n^c) executions for fixed cartel size and target success probability, within the stated routing model.
- The avoidance probability is at least the probability that all cartel vertices occupy the bottom c positions in the random ordering.The proof uses this sufficient event to ensure every honest frontier vertex outranks every cartel vertex until t is reached.
- The sufficient event may be stronger than necessary on individual graphs, but the tightness construction shows no larger graph-independent guarantee is possible.The construction uses an honest path from s to t and connects every cartel vertex to both s and the first honest path vertex.
- The tight instance has an honest path s = v0, v1, …, vq = t with q = n−c−1, while each cartel vertex is adjacent to s and v1.Deleting the cartel leaves the honest path, so the cartel remains admissible.
- 3.1 Independent executions: With a fixed cartel and independent fresh rankings, the worst-case number of executions needed for constant success is Θ(n^c) for fixed c.The threshold follows by solving the independent-failure expression and using the product formula’s Θ(n^c) growth.
4 Comparisons and cost
The comparison contrasts local highest-score routing with rpfr on a counterexample, then situates rpfr against topology-aware routing and implementation costs.
- Local routing comparison: 2^-Ω(n) avoidance occurs for local hs on a biconnected graph with one universally adjacent cartel vertex.The construction has n = 2m+2 vertices and uses a single cartel vertex w.
- Local routing comparison: At each internal path vertex, choosing its leaf forces the next step into the cartel, so survival requires an honest successor to outrank both the leaf and w.Conditioned on R(w) = z, each survival event has probability (1 − z^2)/2, with m −1 conditionally independent events.
- Local routing comparison: rpfr guarantees at least (n −1)^−1 avoidance on the same graph, versus 2^-Ω(n) for local hs.The difference arises because a high-scored honest vertex elsewhere on the global frontier cannot protect against a local trap under hs.
- Topology-aware baseline: Topology-aware uniform selection among internally vertex-disjoint paths achieves at least 1 − c/κ avoidance when κ > c.This baseline assumes a trusted controller has a current topology map and can enumerate those paths.
- Topology-aware baseline: rpfr targets topology-oblivious settings: it discovers adjacency during execution and needs no connectivity input, unlike disjoint-path selection.Its token-based implementation can keep relays stateless, with token size O(n + |E|) and one-execution time O(|E| + n log n).