Secret key agreement for hypergraphical sources with limited total\n discussion

This work considers the problem of multiterminal secret key agreement by\nlimited total public discussion under the hypergraphical source model. The\nsecrecy capacity as a function of the total discussion rate is completely\ncharacterized by a polynomial-time computable linear program. Compared to the\nexisting solution for a particular hypergraphical source model called the\npairwise independent network (PIN) model, the current result is a non-trivial\nextension as it applies to a strictly larger class of sources and a more\ngeneral scenario involving helpers and wiretapper's side information. In\nparticular, while the existing solution by tree-packing can be strictly\nsuboptimal for the PIN model with helpers and the hypergraphical source model\nin general, we can show that decremental secret key agreement and linear\nnetwork coding is optimal, resolving a previous conjecture in the affirmative.\nThe converse is established by a single-letter upper bound on the secrecy\ncapacity for discrete memoryless multiple sources and individual discussion\nrate constraints. The minimax optimization involved in the bound can be relaxed\nto give the best existing upper bounds on secrecy capacities such as the\nlamination bounds for hypergraphical sources, helper-set bound for general\nsources, the bound at asymptotically zero discussion rate via the multivariate\nG\\'ac--K\\"orner common information, and the lower bound on communication\ncomplexity via a multivariate extension of the Wyner common information. These\nreductions unify existing bounding techniques and reveal surprising connections\nbetween seemingly different information-theoretic notions. Further challenges\nare posed in this work along with a simple example of finite linear source\nwhere the current converse techniques fail even though the proposed achieving\nscheme remains optimal.\n