dorsal/arxiv
View SchemaPerfect Secret Key Generation for a class of Hypergraphical Sources
| Authors | Manuj Mukherjee, Sagnik Chatterjee, Alhad Sethi |
|---|---|
| Categories | |
| ArXiv ID | 2601.10697vv1 |
| URL | https://arxiv.org/abs/2601.10697 |
| License | http://creativecommons.org/licenses/by/4.0/ |
Abstract
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.
{
"annotation_id": "d7ef0fc4-6a72-4413-8a05-5f9c8c934df7",
"date_created": "2026-02-17T05:53:26.420000Z",
"date_modified": "2026-02-17T05:53:26.420000Z",
"file_hash": "c5e5ef231f9a9fb724dbea40c8a607b4d4a36a365d80160dcd04b8c2136469c3",
"private": false,
"record": {
"abstract": "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.\n 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.",
"arxiv_id": "2601.10697",
"authors": [
"Manuj Mukherjee",
"Sagnik Chatterjee",
"Alhad Sethi"
],
"categories": [
"cs.IT",
"math.IT"
],
"license": "http://creativecommons.org/licenses/by/4.0/",
"title": "Perfect Secret Key Generation for a class of Hypergraphical Sources",
"url": "https://arxiv.org/abs/2601.10697",
"version": "v1"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "21b0e331-164f-48ec-bc24-e9c542c46a6a",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}