dorsal/arxiv
View SchemaPerfect Secret Key Generation for a class of Hypergraphical Sources
| Authors | Manuj Mukherjee, Sagnik Chatterjee, Alhad Sethi |
|---|---|
| Categories | |
| ArXiv ID | 2601.10697vv2 |
| 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": "a7b88f9d-696e-4c8d-ae81-acc8c37a78e6",
"date_created": "2026-02-17T05:53:26.422000Z",
"date_modified": "2026-02-17T05:53:26.422000Z",
"file_hash": "eff94ccded2b1e25283421607830fea1029d261eb45d209bd67e677b8c3a60c4",
"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": "v2"
},
"schema_id": "dorsal/arxiv",
"source": {
"execution_id": "7c7cf67a-2870-4d7b-8713-a1b1ea52b888",
"id": "arXiv Dataset",
"type": "Model",
"variant": "snapshot-2026-01-17",
"version": "0.1.0"
},
"user_id": 1000002
}