Multi-terminal secrecy in a linear non-coherent packetized networks

Mahdi Jafari Siavoshani, Christina Fragouli

TL;DR

This paper explores how a group of trusted nodes can generate a shared secret key over a randomized, non-coherent network while a passive eavesdropper (Eve) listens in. The authors provide a complete characterization of the "secrecy capacity" for two terminals and establish tight upper and lower bounds for multi-terminal scenarios in the large field size regime.

What Problem Does This Paper Address?

In modern network coding, routers don't just forward packets; they mix them. In "non-coherent" networks, these mixing coefficients are often randomized and unknown to the senders and receivers beforehand. While this makes networks robust, it creates a security challenge: how do you establish a private key when an eavesdropper like "Eve" can observe the same randomized transmissions?

Existing research often assumes Eve cannot access the broadcast channel or that the network structure is fixed (coherent). This paper tackles the more realistic and difficult scenario where:

  1. Eve overhears everything: She sees the broadcast transmissions and the subsequent public discussions between honest nodes.
  2. The network is a "black box": The channel is modeled as a multiplicative matrix channel over a finite field, representing randomized network coding.
  3. Multi-terminal setup: Alice needs to share a key not just with Bob, but potentially with a whole group of trusted terminals.

Methods

The authors employ Information Theory and Subspace Coding to find the limits of secret key generation.

  • Channel Modeling: They model the network as a non-coherent broadcast channel where Alice injects packets, and each receiver (including Eve) receives a random linear combination of those packets.
  • Upper Bounds: By leveraging and extending the work of Csiszár and Narayan on multiterminal secrecy, the authors derive an outer limit on how much secret information can possibly be extracted from this specific matrix channel.
  • Achievability Scheme (Lower Bound): They propose a scheme where Alice broadcasts random linear combinations. Legitimate nodes then use a "public discussion" channel to reveal their channel transfer matrices. Because these matrices are independent, Alice can identify specific mathematical subspaces that are "orthogonal" to what Eve has seen but are still reachable by the honest nodes.
  • Optimization: For the multi-terminal case ($m \ge 2$), they formulate the key rate as a convex optimization problem, essentially trying to "pack" as many private subspace dimensions as possible into the transmission.

Datasets

As a theoretical paper in information theory, no empirical datasets were used. The authors validated their findings through mathematical proofs and numerical simulations of their derived bounds (illustrated in Figure 2 of the paper), comparing the proposed lower bounds against the theoretical upper bounds across different network parameters.

Key Insights and Ideas

  • The Power of Feedback: The paper highlights that a public channel (even one Eve can hear) is incredibly powerful. It allows honest nodes to reconcile their observations of the network's inherent randomness to "distill" a key that Eve cannot reconstruct.
  • Subspace Orthogonality: The "aha moment" is that in a high-dimensional vector space (large field size $q$), there is almost always a "direction" (subspace) that Alice and Bob share which is completely invisible to Eve, provided Eve hasn't captured the entire space.
  • Two-Terminal Optimality: For the case of just Alice and Bob ($m=1$), the authors prove that their upper and lower bounds match exactly. This provides a closed-form expression for the secrecy capacity in large-scale randomized networks.
  • The "Eve is too powerful" threshold: The results quantify exactly when secrecy becomes impossible. For instance, if Eve's "rank" (the number of independent packets she intercepts) equals Alice's injection rate, the secrecy capacity drops to zero.

Key Results

  • Secrecy Capacity for $m=1$: The paper provides a definitive formula for the two-user case. The rate is proportional to $(\min[n_A, n_B + n_E] - n_E)$, where $n_A, n_B, n_E$ are the dimensions of the spaces seen by Alice, Bob, and Eve respectively.
  • Asymptotic Tightness: The proposed schemes are shown to be optimal as the finite field size $q$ becomes very large.
  • Multi-terminal Bounds: For three or more terminals, the authors provide a linear programming approach to find the best achievable rate. While not always matching the upper bound perfectly for $m \ge 2$, the gap is shown to be small in practical symmetric scenarios.

Limitations and Future Work

  • Large Field Assumption: The results rely on the field size $q$ being "sufficiently large." In practical systems with small fields (like $GF(2)$ or $GF(256)$), the probability of subspaces overlapping increases, which might degrade the actual achievable rate.
  • Passive vs. Active: The model assumes Eve is passive (only listening). It does not account for an active adversary who might inject malicious packets or jam the public channel.
  • Computational Complexity: While the optimization for the multi-terminal case is convex, implementing the subspace reconciliation in real-time for very high-speed networks remains a challenge for future engineering.

Summary updated

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 F <sub xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">q</sub> ) 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.
BibTeX
@inproceedings{siavoshani2012multi,
  author = {Mahdi Jafari Siavoshani and Christina Fragouli},
  title = {{Multi-terminal secrecy in a linear non-coherent packetized networks}},
  booktitle = {NetCod},
  year = {2012},
  url = {https://openreview.net/forum?id=yoX028EFJmn},
}

Loading related content...

Figure