Appears in collection : 2016 - T1 - WS5 - Secrecy and privacy theme

We show that an old result from Nash-Williams and Tutte on the duality in maximal spanning tree packing in multigraphs carries an information-theoretic significance in the context of largest multiterminal secret key generation from pairwise independent secret keys. This information theoretic interpretation leads to a new form for the dual term in the result of Nash-Williams and Tutte. We then discuss a natural generalization of the multiterminal secret key generation with the presence of a helper. In an interesting case with the ‘‘weak’’ helper, we show that the duality generalizes to maximal Steiner tree packing, which is NP-hard.