Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1605.01861 · IEEE International Symposium on Information Theory (ISIT)

Incremental and decremental secret key agreement

Chung Chan, Ali Al-Bashabsheh, Qiaoqiao Zhou

Published Jul 1, 2016• 11 citations
arXivHTMLPDF

Abstract

We study the rate of change of the multivariate mutual information among a set of random variables when some common randomness is added to or removed from a subset. This is formulated more precisely as two new multiterminal secret key agreement problems which ask how one can increase the secrecy capacity efficiently by adding common randomness to a small subset of users, and how one can simplify the source model by removing redundant common randomness that does not contribute to the secrecy capacity. The combinatorial structure has been clarified along with some meaningful open problems.

DOI
10.1109/isit.2016.7541752

Related papers

Change of Multivariate Mutual Information: From Local to Global

Chung Chan, Ali Al-Bashabsheh, Qiaoqiao Zhou

We study the change of multivariate mutual information among a set of random variables when some common randomness is added to or removed from a subset of the random variables. This is formulated more precisely as two new multiterminal secret key agreement problems that, respectively, ask how one can increase the secrecy capacity efficiently by adding common randomness to a small subset of users, and how one can simplify the source model by removing redundant common randomness that does not contribute to the secrecy capacity. Characterizations and strongly polynomial-time computations are derived for the rates of change, maximum usable increment, and redundancy. These results can be applied to study the communication complexity for secret key agreement.

IEEE Transactions on Information Theory•Sep 7, 2017•7 citations

Compressed Secret Key Agreement:Maximizing Multivariate Mutual Information per Bit

Chung Chan

The multiterminal secret key agreement problem by public discussion is formulated with an additional source compression step where, prior to the public discussion phase, users independently compress their private sources to filter out strongly correlated components in order to generate a common secret key. The objective is to maximize the achievable key rate as a function of the joint entropy of the compressed sources. Since the maximum achievable key rate captures the total amount of information mutual to the compressed sources, an optimal compression scheme essentially maximizes the multivariate mutual information per bit of randomness of the private sources, and can therefore be viewed more generally as a dimension reduction technique. Single-letter lower and upper bounds on the maximum achievable key rate are derived for the general source model, and an explicit polynomial-time computable formula is obtained for the pairwise independent network model. In particular, the converse results and the upper bounds are obtained from those of the related secret key agreement problem with rate-limited discussion. A precise duality is shown for the two-user case with one-way discussion, and such duality is extended to obtain the desired converse results in the multi-user case. In addition to posing new challenges in information processing and dimension reduction, the compressed secret key agreement problem helps shed new light on resolving the difficult problem of secret key agreement with rate-limited discussion by offering a more structured achieving scheme and some simpler conjectures to prove.

arXiv:1706.04295•Entropy•Oct 14, 2017•5 citations

Multivariate Mutual Information Inspired by Secret-Key Agreement

Chung Chan, Ali Al-Bashabsheh, Javad B. Ebrahimi +2 more

The capacity for multiterminal secret-key agreement inspires a natural generalization of Shannon's mutual information from two random variables to multiple random variables. Under a general source model without helpers, the capacity is shown to be equal to the normalized divergence from the joint distribution of the random sources to the product of marginal distributions minimized over partitions of the random sources. The mathematical underpinnings are the works on co-intersecting submodular functions and the principle lattices of partitions of the Dilworth truncation. We clarify the connection to these works and enrich them with information-theoretic interpretations and properties that are useful in solving other related problems in information theory as well as machine learning.

Proceedings of the IEEE•Sep 16, 2015•74 citations

Multiterminal Secret Key Agreement at Asymptotically Zero Discussion Rate

Chung Chan, Manuj Mukherjee, Navin Kashyap +1 more

In the multiterminal secret key agreement problem, a set of users want to discuss with each other until they share a common secret key independent of their discussion. We want to characterize the maximum secret key rate, called the secrecy capacity, asymptotically when the total discussion rate goes to zero. In the case of only two users, the capacity is equal to the Gács-Körner common information. However, when there are more than two users, the capacity is unknown. It is plausible that a multivariate extension of the Gács-Kömer common information is the capacity, however, proving the converse is challenging. We resolved this for the hypergraphical sources and finite linear sources, and provide efficiently computable characterizations. We also give some ideas of extending the techniques to more general source models.

arXiv:1802.04955•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2018•12 citations

Multiterminal Secrecy by Public Discussion

Prakash Narayan, Himanshu Tyagi

This monograph describes principles of information theoretic secrecy generation by legitimate parties with public discussion in the presence of an eavesdropper. The parties are guaranteed secrecy in the form of independence from the eavesdropper’s observation of the communication. Part I develops basic technical tools for secrecy generation, many of which are potentially of independent interest beyond secrecy settings. Various information theoretic and cryptographic notions of secrecy are compared. Emphasis is placed on central themes of interactive communication and common randomness as well as on core methods of balanced coloring and leftover hash for extracting secret uniform randomness. Achievability and converse results are shown to emerge from “single shot” incarnations that serve to explain essential structure. Part II applies the methods of Part I to secrecy generation in two settings: a multiterminal source model and a multiterminal channel model, in both of which the legitimate parties are afforded privileged access to correlated observations of which the eavesdropper has only partial knowledge. Characterizations of secret key capacity bring out inherent connections to the data compression concept of omniscience and, for a specialized source model, to a combinatorial problem of maximal spanning tree packing in a multigraph. Interactive common information is seen to govern the minimum rate of communication needed to achieve secret key capacity in the two-terminal source model. Furthermore, necessary and sufficient conditions are analyzed for the secure computation of a given function in the multiterminal source model. Based largely on known recent results, this self-contained monograph also includes new formulations with associated new proofs. Supplementing each chapter in Part II are descriptions of several open problems.

Foundations and Trends® in Communications and Information Theory•Sep 28, 2016•37 citations

When is omniscience a rate-optimal strategy for achieving secret key capacity?

Chung Chan, Manuj Mukherjee, Navin Kashyap +1 more

For the multiterminal secret key agreement problem under a private source model, it is known that the communication complexity required to achieve the capacity can be strictly smaller than the minimum rate of communication for omniscience, but a single-letter characterization is not known. We obtain a single-letter lower bound on the communication complexity as well as some conditions for the communication complexity to be maximal (equal to the smallest rate of communication for omniscience). The results are are stated and derived using a meaningful multivariate mutual information measure. They are stronger than existing ones because 1) they apply to a general discrete memoryless multiple source rather than a special source model, 2) the problem formulation allows private randomization by individual users, 3) the bound is single-letter and the condition can be checked easily, and so 4) more scenarios in which the communication complexity is maximal are discovered. We conjecture that the lower bound can be further improved by giving a concrete example.

IEEE Information Theory Workshop (ITW)•Sep 1, 2016•14 citations
We study the rate of change of the multivariate mutual information among a set of random variables when some common randomness is added to or removed from a subset. This is formulated more precisely as two new multiterminal secret key agreement problems which ask how one can increase the secrecy capacity efficiently by adding common randomness to a small subset of users, and how one can simplify the source model by removing redundant common randomness that does not contribute to the secrecy capacity. The combinatorial structure has been clarified along with some meaningful open problems.
We study the change of multivariate mutual information among a set of random variables when some common randomness is added to or removed from a subset of the random variables. This is formulated more precisely as two new multiterminal secret key agreement problems that, respectively, ask how one can increase the secrecy capacity efficiently by adding common randomness to a small subset of users, and how one can simplify the source model by removing redundant common randomness that does not contribute to the secrecy capacity. Characterizations and strongly polynomial-time computations are derived for the rates of change, maximum usable increment, and redundancy. These results can be applied to study the communication complexity for secret key agreement.
The multiterminal secret key agreement problem by public discussion is formulated with an additional source compression step where, prior to the public discussion phase, users independently compress their private sources to filter out strongly correlated components in order to generate a common secret key. The objective is to maximize the achievable key rate as a function of the joint entropy of the compressed sources. Since the maximum achievable key rate captures the total amount of information mutual to the compressed sources, an optimal compression scheme essentially maximizes the multivariate mutual information per bit of randomness of the private sources, and can therefore be viewed more generally as a dimension reduction technique. Single-letter lower and upper bounds on the maximum achievable key rate are derived for the general source model, and an explicit polynomial-time computable formula is obtained for the pairwise independent network model. In particular, the converse results and the upper bounds are obtained from those of the related secret key agreement problem with rate-limited discussion. A precise duality is shown for the two-user case with one-way discussion, and such duality is extended to obtain the desired converse results in the multi-user case. In addition to posing new challenges in information processing and dimension reduction, the compressed secret key agreement problem helps shed new light on resolving the difficult problem of secret key agreement with rate-limited discussion by offering a more structured achieving scheme and some simpler conjectures to prove.
The capacity for multiterminal secret-key agreement inspires a natural generalization of Shannon's mutual information from two random variables to multiple random variables. Under a general source model without helpers, the capacity is shown to be equal to the normalized divergence from the joint distribution of the random sources to the product of marginal distributions minimized over partitions of the random sources. The mathematical underpinnings are the works on co-intersecting submodular functions and the principle lattices of partitions of the Dilworth truncation. We clarify the connection to these works and enrich them with information-theoretic interpretations and properties that are useful in solving other related problems in information theory as well as machine learning.
In the multiterminal secret key agreement problem, a set of users want to discuss with each other until they share a common secret key independent of their discussion. We want to characterize the maximum secret key rate, called the secrecy capacity, asymptotically when the total discussion rate goes to zero. In the case of only two users, the capacity is equal to the Gács-Körner common information. However, when there are more than two users, the capacity is unknown. It is plausible that a multivariate extension of the Gács-Kömer common information is the capacity, however, proving the converse is challenging. We resolved this for the hypergraphical sources and finite linear sources, and provide efficiently computable characterizations. We also give some ideas of extending the techniques to more general source models.
This monograph describes principles of information theoretic secrecy generation by legitimate parties with public discussion in the presence of an eavesdropper. The parties are guaranteed secrecy in the form of independence from the eavesdropper’s observation of the communication. Part I develops basic technical tools for secrecy generation, many of which are potentially of independent interest beyond secrecy settings. Various information theoretic and cryptographic notions of secrecy are compared. Emphasis is placed on central themes of interactive communication and common randomness as well as on core methods of balanced coloring and leftover hash for extracting secret uniform randomness. Achievability and converse results are shown to emerge from “single shot” incarnations that serve to explain essential structure. Part II applies the methods of Part I to secrecy generation in two settings: a multiterminal source model and a multiterminal channel model, in both of which the legitimate parties are afforded privileged access to correlated observations of which the eavesdropper has only partial knowledge. Characterizations of secret key capacity bring out inherent connections to the data compression concept of omniscience and, for a specialized source model, to a combinatorial problem of maximal spanning tree packing in a multigraph. Interactive common information is seen to govern the minimum rate of communication needed to achieve secret key capacity in the two-terminal source model. Furthermore, necessary and sufficient conditions are analyzed for the secure computation of a given function in the multiterminal source model. Based largely on known recent results, this self-contained monograph also includes new formulations with associated new proofs. Supplementing each chapter in Part II are descriptions of several open problems.
For the multiterminal secret key agreement problem under a private source model, it is known that the communication complexity required to achieve the capacity can be strictly smaller than the minimum rate of communication for omniscience, but a single-letter characterization is not known. We obtain a single-letter lower bound on the communication complexity as well as some conditions for the communication complexity to be maximal (equal to the smallest rate of communication for omniscience). The results are are stated and derived using a meaningful multivariate mutual information measure. They are stronger than existing ones because 1) they apply to a general discrete memoryless multiple source rather than a special source model, 2) the problem formulation allows private randomization by individual users, 3) the bound is single-letter and the condition can be checked easily, and so 4) more scenarios in which the communication complexity is maximal are discovered. We conjecture that the lower bound can be further improved by giving a concrete example.