Abstract
We consider a group of $m+1$ trusted nodes that aim to create a shared secret key $K$ over a network in the presence of a passive eavesdropper, Eve. We assume a linear non-coherent network coding broadcast channel (over a finite field $\mathbb{F}_q$) from one of the honest nodes (i.e., Alice) to the rest of them including Eve. All of the trusted nodes can also discuss over a cost-free public channel which is also overheard by Eve. For this setup, we propose upper and lower bounds for the secret key generation capacity assuming that the field size $q$ is very large. For the case of two trusted terminals ($m = 1$) our upper and lower bounds match and we have complete characterization for the secrecy capacity in the large field size regime.
Introduction
In modern network coding, routers do not merely forward packets; they combine them. In "non-coherent" networks, these mixing coefficients are often randomized and unknown to the senders and receivers beforehand. While this enhances network robustness, it introduces a significant security challenge: establishing a private key when an eavesdropper, "Eve," can observe the same randomized transmissions.
This research addresses the realistic and complex scenario where Eve overhears all broadcast transmissions and subsequent public discussions between honest nodes. The network is modeled as a "black box" multiplicative matrix channel over a finite field, representing randomized network coding. The goal is to enable Alice to share a secret key not just with one peer, but with a multi-terminal group of trusted nodes.
Methodology
The study employs information theory and subspace coding to determine the limits of secret key generation. The network is modeled as a non-coherent broadcast channel where Alice injects packets, and each receiver (including Eve) receives a random linear combination of those packets.
To derive upper bounds, the authors extend the work of Csiszár and Narayan on multi-terminal secrecy to this specific matrix channel. For the achievability scheme (lower bound), Alice broadcasts random linear combinations, and legitimate nodes use a public discussion channel to reveal their channel transfer matrices. Since these matrices are independent, Alice can identify specific mathematical subspaces that are "orthogonal" to Eve's observations but reachable by honest nodes. For multi-terminal cases ($m \ge 2$), the key rate is formulated as a convex optimization problem to maximize the "packing" of private subspace dimensions.
Key Insights and Ideas
A central finding is the power of feedback. A public channel, even if overheard by Eve, allows honest nodes to reconcile their observations of the network's inherent randomness to distill a key that Eve cannot reconstruct. In a high-dimensional vector space (large field size $q$), there is almost always a "direction" or subspace shared by Alice and Bob that is invisible to Eve, provided Eve has not captured the entire space.
The research also identifies a threshold where secrecy becomes impossible. Specifically, if Eve's "rank" (the number of independent packets she intercepts) equals Alice's injection rate, the secrecy capacity drops to zero.
Key Results
The authors provide a definitive formula for the secrecy capacity in the two-user case ($m=1$). The rate is proportional to $(\min[n_A, n_B + n_E] - n_E)$, where $n_A, n_B, n_E$ represent the dimensions of the spaces observed by Alice, Bob, and Eve, respectively.
The proposed schemes are shown to be asymptotically optimal as the finite field size $q$ becomes very large. For three or more terminals, a linear programming approach is used to find the best achievable rate. While the upper and lower bounds do not always match perfectly for $m \ge 2$, the gap is shown to be small in practical symmetric scenarios, as illustrated in the numerical simulations.
Conclusion
While this work provides a robust theoretical framework, it relies on the assumption of a "sufficiently large" field size $q$. In practical systems with small fields, the probability of subspace overlap increases, potentially degrading the achievable rate. Furthermore, the model assumes a passive eavesdropper and does not account for active adversaries who might inject malicious packets. Future work will need to address these practical constraints and the computational complexity of implementing subspace reconciliation in real-time high-speed networks.
Summary updated