Perfect Secret Key Generation for a class of Hypergraphical Sources
This work addresses secure communication in network information theory by extending secret key generation to hypergraphical models, but it is incremental as it builds on existing graph-based approaches.
The paper tackles the problem of perfect secret key generation for hypergraphical sources, generalizing a prior graph-based model, and achieves capacity-achieving schemes for specific classes of hypergraphs, such as complete t-uniform hypergraphs and certain 3-uniform hypergraphs, with concrete key rates like binom(m-2, t-2) bits per star graph.
Nitinawarat and Narayan proposed a perfect secret key generation scheme for the so-called \emph{pairwise independent network (PIN) model} by exploiting the combinatorial properties of the underlying graph, namely the spanning tree packing rate. This work considers a generalization of the PIN model where the underlying graph is replaced with a hypergraph, and makes progress towards designing similar perfect secret key generation schemes by exploiting the combinatorial properties of the hypergraph. Our contributions are two-fold. We first provide a capacity achieving scheme for a complete $t$-uniform hypergraph on $m$ vertices by leveraging a packing of the complete $t$-uniform hypergraphs by what we refer to as star hypergraphs, and designing a scheme that gives $\binom{m-2}{t-2}$ bits of perfect secret key per star graph. Our second contribution is a 2-bit perfect secret key generation scheme for 3-uniform star hypergraphs whose projections are cycles. This scheme is then extended to a perfect secret key generation scheme for generic 3-uniform hypergraphs by exploiting star graph packing of 3-uniform hypergraphs and Hamiltonian packings of graphs. The scheme is then shown to be capacity achieving for certain classes of hypergraphs.