On the Public Communication Needed to Achieve SK Capacity in the Multiterminal Source Model

Abstract

The focus of this paper is on the public communication required for generating a maximal-rate secret key (SK) within the multiterminal source model of Csisz{á}r and Narayan. Building on the prior work of Tyagi for the two-terminal scenario, we derive a lower bound on the communication complexity, $R_{\text{SK}}$, defined to be the minimum rate of public communication needed to generate a maximal-rate SK. It is well known that the minimum rate of communication for omniscience, denoted by $R_{\text{CO}}$, is an upper bound on $R_{\text{SK}}$. For the class of pairwise independent network (PIN) models defined on uniform hypergraphs, we show that a certain "Type $\mathcal{S}$" condition, which is verifiable in polynomial time, guarantees that our lower bound on $R_{\text{SK}}$ meets the $R_{\text{CO}}$ upper bound. Thus, PIN models satisfying our condition are $R_{\text{SK}}$-maximal, meaning that the upper bound $R_{\text{SK}}\le R_{\text{CO}}$ holds with equality. This allows us to explicitly evaluate $R_{\text{SK}}$ for such PIN models. We also give several examples of PIN models that satisfy our Type $\mathcal{S}$ condition. Finally, we prove that for an arbitrary multiterminal source model, a stricter version of our Type $\mathcal{S}$ condition implies that communication from \emph{all} terminals ("omnivocality") is needed for establishing a SK of maximum rate. For three-terminal source models, the converse is also true: omnivocality is needed for generating a maximal-rate SK only if the strict Type $\mathcal{S}$ condition is satisfied. Counterexamples exist that show that the converse is not true in general for source models with four or more terminals.

Submitted to the IEEE Transactions on Information Theory. arXiv admin note: text overlap with arXiv:1504.00629

References in corpus (3)

• Wyner's Common Information: Generalizations and A New Lossy Source Coding Interpretation
• Achieving SK Capacity in the Source Model: When Must All Terminals Talk?
• The communication complexity of achieving SK capacity in a class of PIN models

Cited by in corpus (16)

• Bounds on the Communication Rate Needed to Achieve SK Capacity in the Hypergraphical Source Model
• Interactive Secure Function Computation
• Info-Clustering: A Mathematical Theory for Data Clustering
• Coordination Through Shared Randomness
• Secret Key Agreement under Discussion Rate Constraints
• Secret key agreement for hypergraphical sources with limited total discussion
• Incremental and Decremental Secret Key Agreement
• Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation
• Part I: Improving Computational Efficiency of Communication for Omniscience
• Compressed Secret Key Agreement: Maximizing Multivariate Mutual Information Per Bit
• Wiretap Secret Key Agreement Via Secure Omniscience
• On the Optimality of Secret Key Agreement via Omniscience
• Upper Bounds via Lamination on the Constrained Secrecy Capacity of Hypergraphical Sources
• One-Shot Perfect Secret Key Agreement for Finite Linear Sources
• Secret Key Generation for Minimally Connected Hypergraphical Sources
• Multiterminal Secret Key Agreement at Asymptotically Zero Discussion Rate