Common Information and Secret Key Capacity

Abstract

We study the generation of a secret key of maximum rate by a pair of terminals observing correlated sources and with the means to communicate over a noiseless public com- munication channel. Our main result establishes a structural equivalence between the generation of a maximum rate secret key and the generation of a common randomness that renders the observations of the two terminals conditionally independent. The minimum rate of such common randomness, termed interactive common information, is related to Wyner's notion of common information, and serves to characterize the minimum rate of interactive public communication required to generate an optimum rate secret key. This characterization yields a single-letter expression for the aforementioned communication rate when the number of rounds of interaction are bounded. An application of our results shows that interaction does not reduce this rate for binary symmetric sources. Further, we provide an example for which interaction does reduce the minimum rate of communication. Also, certain invariance properties of common information quantities are established that may be of independent interest.

Accepted for publication in the IEEE Transactions on Information Theory

Cited by in corpus (24)

• On the Public Communication Needed to Achieve SK Capacity in the Multiterminal Source Model
• Coding for Positive Rate in the Source Model Key Agreement Problem
• Achieving SK Capacity in the Source Model: When Must All Terminals Talk?
• The future of secure communications: device independence in quantum key distribution
• Bounds on the Communication Rate Needed to Achieve SK Capacity in the Hypergraphical Source Model
• Wiretap Secret Key Capacity of Tree-PIN
• Interactive Secure Function Computation
• Converses for Secret Key Agreement and Secure Computing
• Coordination Through Shared Randomness
• Optimal Communication Rates and Combinatorial Properties for Common Randomness Generation
• Secret Key Agreement under Discussion Rate Constraints
• Secret key agreement for hypergraphical sources with limited total discussion
• Shared Information for a Markov Chain on a Tree
• Multiterminal Secret Key Agreement with Nearly No Discussion
• Compressed Secret Key Agreement: Maximizing Multivariate Mutual Information Per Bit
• Secret Key Generation with Limited Interaction
• On the Optimality of Secret Key Agreement via Omniscience
• Secret Key Generation from Vector Gaussian Sources with Public and Private Communications
• Effects of Quantization on the Multiple-Round Secret-Key Capacity
• Upper Bounds via Lamination on the Constrained Secrecy Capacity of Hypergraphical Sources
• Secret Key Generation for Minimally Connected Hypergraphical Sources
• Multiterminal Secret Key Agreement at Asymptotically Zero Discussion Rate
• One-Shot Perfect Secret Key Agreement for Finite Linear Sources
• Notes on Information-Theoretic Privacy