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

Common Randomness and Key Generation with Limited Interaction.

Jingbo Liu, Paul Cuff, Sergio Verdú

Published Jan 5, 2016• 7 citations
OpenAlex

Abstract

The basic two-terminal common randomness (CR) and key generation models are considered, where the communication between the terminals may be limited, and in particular may not be enough to achieve the maximum CR/key rate. We introduce general notions of $XY$-absolutely continuity and $XY$-concave function, and characterize the first order CR/key-communication tradeoff in terms of the evaluation of the $XY$-concave envelope of a functional defined on a set of distributions, which is simpler than the multi-letter characterization. Two extreme cases are given special attention. First, in the regime of very small communication rates, the CR bits per interaction bit (CRBIB) and key bits per interaction bit (KBIB) are expressed with a new symmetrical strong data processing constant, defined as the minimum of a parameter such that a certain information-theoretic functional touches its $XY$-concave envelope at a given source distribution. We also provide a computationally friendly strong converse bound for CRBIB and a similar (but not necessarily strong) one for KBIB in terms of the supremum of the maximal correlation coefficient over a set of distributions. The proof uses hypercontractivity and properties of the R\'enyi divergence. A criterion the tightness of the bound is given with applications to binary symmetric sources. Second, a new characterization of the minimum interaction rate needed for achieving the maximum key rate (MIMK) is given, and we resolve a conjecture by Tyagi and Narayan \cite{tyagi2013common} regarding the MIMK for binary sources. We also propose a new conjecture for binary symmetric sources.

Related papers

Key generation with limited interaction

Jingbo Liu, Paul Cuff, Sergio Verdú

The basic two-terminal key generation model is considered, where the communication between the terminals is limited. We introduce a preorder relation on the set of joint distributions called XY-absolute continuity, and we reduce the multi-letter characterization of the key-communication tradeoff to the evaluation of the XY-concave envelope of a functional. For small communication rates, the key bits per interaction bit is expressed with a “symmetrical strong data processing constant”. Using hypercontractivity and Rényi divergence, we also prove a computationally friendly strong converse bound for the common randomness bits per interaction bit in terms of the supremum of the maximal correlation coefficient over a set of distributions, which is tight for binary symmetric sources. Regarding the other extreme case, a new characterization of the minimum interaction for achieving the maximum key rate (MIMK) is given, and is used to resolve a conjecture by Tyagi [1] about the MIMK for binary sources.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2016•3 citations

Secret Key Generation With Limited Interaction

Jingbo Liu, Paul Cuff, Sergio Verdú

A basic two-terminal secret key generation model is considered, where the interactive communication rate between the terminals may be limited, and in particular may not be enough to achieve the maximum key rate. We first prove a multi-letter characterization of the key-communication rate region (where the number of auxiliary random variables depends on the number of rounds of the communication), and then provide an equivalent but simpler characterization in terms of concave envelopes in the case of unlimited number of rounds. Two extreme cases are given special attention. First, in the regime of very low communication rates, the key bits per interaction bit (KBIB) is expressed with a new “symmetric strong data processing constant”, which has a concave envelope characterization analogous to that of the conventional strong data processing constant. The symmetric strong data processing constant can be upper bounded by the supremum of the maximal correlation coefficient over a set of distributions, which allows us to determine the KBIB for binary symmetric sources, and conclude, in particular, that the interactive scheme is not more efficient than the one-way scheme at least in the low communication-rate regime. Second, a new characterization of the minimum interaction rate needed for achieving the maximum key rate (MIMK) is given, and we resolve a conjecture by Tyagi regarding the MIMK for (possibly nonsymmetric) binary sources. We also propose a new conjecture for binary symmetric sources that the interactive scheme is not more efficient than the one-way scheme at any communication rate.

arXiv:1601.00899•IEEE Transactions on Information Theory•Aug 28, 2017•32 citations

Common Information and Secret Key Capacity

Himanshu Tyagi

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 communication 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.

arXiv:1304.2444•IEEE Transactions on Information Theory•May 20, 2013•70 citations

Secret Key Generation in the Multiterminal Source Model : Communication and Other Aspects

Manuj Mukherjee

This dissertation is primarily concerned with the communication required to achieve secret key (SK) capacity in a multiterminal source model. The multiterminal source model introduced by Csiszar and Narayan consists of a group of remotely located terminals with access to correlated sources and a noiseless public channel. The terminals wish to secure their communication by agreeing upon a group secret key. The key agreement protocol involves communicating over the public channel, and agreeing upon an SK secured from eavesdroppers listening to the public communication. The SK capacity, i.e., the maximum rate of an SK that can be agreed upon by the terminals, has been characterized by Csiszar and Narayan. Their capacity-achieving key generation protocol involved terminals communicating to attain omniscience, i.e., every terminal gets to recover the sources of the other terminals. While this is a very general protocol, it often requires larger rates of public communication than is necessary to achieve SK capacity. The primary focus of this dissertation is to characterize the communication complexity, i.e., the minimum rate of public discussion needed to achieve SK capacity. A lower bound to communication complexity is derived for a general multiterminal source, although it turns out to be loose in general. While the minimum rate of communication for omniscience is always an upper bound to the communication complexity, we derive tighter upper bounds to communication complexity for a special class of multiterminal sources, namely, the hypergraphical sources. This upper bound yield a complete characterization of hypergraphical sources where communication for omniscience is a rate-optimal protocol for SK generation, i.e., the communication complexity equals the minimum rate of communication for omniscience. Another aspect of the public communication touched upon by this dissertation is the necessity of omnivocality, i.e., all terminals communicating, to achieve the SK capacity. It is well known that in two-terminal sources, only one terminal communicating success to generate a maximum rate secret key. However, we are able to show that for three or more terminals, omnivocality is indeed required to achieve SK capacity if a certain condition is met. For the specific case of three terminals, we show that this condition is also necessary to ensure omnivocality is essential in generating a SK of maximal rate. However, this condition is no longer necessary when there are four or more terminals. A certain notion of common information, namely, the Wyner common information, plays a central role in the communication complexity problem. This dissertation thus includes a study of multiparty versions of the two widely used notions of common information, namely, Wyner common information and Gacs-Korner (GK) common information. While evaluating these quantities is difficult in general, we are able to derive explicit expressions for both types of common information in the case of hypergraphical sources. We also study fault-tolerant SK…

•Jan 1, 2017•0 citations

Resource-Efficient Common Randomness and Secret-Key Schemes

Badih Ghazi, T. S. Jayram

We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space.

arXiv:1707.08086•Society for Industrial and Applied Mathematics eBooks•Jan 1, 2018•14 citations

Common randomness and secret key generation with a helper

Imre Csiszár, Prakash Narayan

We consider the generation of common randomness (CR), secret or not secret, by two user terminals with aid from a "helper" terminal. Each terminal observes a different component of a discrete memoryless multiple source. The helper aids the users by transmitting information to them over a noiseless public channel subject to a rate constraint. Furthermore, one of the users is allowed to transmit to the other user over a public channel under a similar rate constraint. We study the maximum rate of CR which can be thus generated, including under additional secrecy conditions when it must be concealed from a wiretapper. Lower bounds for the corresponding capacities are provided, and single-letter capacity formulas are obtained for several special cases of interest.

IEEE Transactions on Information Theory•Mar 1, 2000•302 citations
The basic two-terminal common randomness (CR) and key generation models are considered, where the communication between the terminals may be limited, and in particular may not be enough to achieve the maximum CR/key rate. We introduce general notions of XYXYXY-absolutely continuity and XYXYXY-concave function, and characterize the first order CR/key-communication tradeoff in terms of the evaluation of the XYXYXY-concave envelope of a functional defined on a set of distributions, which is simpler than the multi-letter characterization. Two extreme cases are given special attention. First, in the regime of very small communication rates, the CR bits per interaction bit (CRBIB) and key bits per interaction bit (KBIB) are expressed with a new symmetrical strong data processing constant, defined as the minimum of a parameter such that a certain information-theoretic functional touches its XYXYXY-concave envelope at a given source distribution. We also provide a computationally friendly strong converse bound for CRBIB and a similar (but not necessarily strong) one for KBIB in terms of the supremum of the maximal correlation coefficient over a set of distributions. The proof uses hypercontractivity and properties of the R'enyi divergence. A criterion the tightness of the bound is given with applications to binary symmetric sources. Second, a new characterization of the minimum interaction rate needed for achieving the maximum key rate (MIMK) is given, and we resolve a conjecture by Tyagi and Narayan \cite{tyagi2013common} regarding the MIMK for binary sources. We also propose a new conjecture for binary symmetric sources.
The basic two-terminal key generation model is considered, where the communication between the terminals is limited. We introduce a preorder relation on the set of joint distributions called XY-absolute continuity, and we reduce the multi-letter characterization of the key-communication tradeoff to the evaluation of the XY-concave envelope of a functional. For small communication rates, the key bits per interaction bit is expressed with a “symmetrical strong data processing constant”. Using hypercontractivity and Rényi divergence, we also prove a computationally friendly strong converse bound for the common randomness bits per interaction bit in terms of the supremum of the maximal correlation coefficient over a set of distributions, which is tight for binary symmetric sources. Regarding the other extreme case, a new characterization of the minimum interaction for achieving the maximum key rate (MIMK) is given, and is used to resolve a conjecture by Tyagi [1] about the MIMK for binary sources.
A basic two-terminal secret key generation model is considered, where the interactive communication rate between the terminals may be limited, and in particular may not be enough to achieve the maximum key rate. We first prove a multi-letter characterization of the key-communication rate region (where the number of auxiliary random variables depends on the number of rounds of the communication), and then provide an equivalent but simpler characterization in terms of concave envelopes in the case of unlimited number of rounds. Two extreme cases are given special attention. First, in the regime of very low communication rates, the key bits per interaction bit (KBIB) is expressed with a new “symmetric strong data processing constant”, which has a concave envelope characterization analogous to that of the conventional strong data processing constant. The symmetric strong data processing constant can be upper bounded by the supremum of the maximal correlation coefficient over a set of distributions, which allows us to determine the KBIB for binary symmetric sources, and conclude, in particular, that the interactive scheme is not more efficient than the one-way scheme at least in the low communication-rate regime. Second, a new characterization of the minimum interaction rate needed for achieving the maximum key rate (MIMK) is given, and we resolve a conjecture by Tyagi regarding the MIMK for (possibly nonsymmetric) binary sources. We also propose a new conjecture for binary symmetric sources that the interactive scheme is not more efficient than the one-way scheme at any communication rate.
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 communication 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.
This dissertation is primarily concerned with the communication required to achieve secret key (SK) capacity in a multiterminal source model. The multiterminal source model introduced by Csiszar and Narayan consists of a group of remotely located terminals with access to correlated sources and a noiseless public channel. The terminals wish to secure their communication by agreeing upon a group secret key. The key agreement protocol involves communicating over the public channel, and agreeing upon an SK secured from eavesdroppers listening to the public communication. The SK capacity, i.e., the maximum rate of an SK that can be agreed upon by the terminals, has been characterized by Csiszar and Narayan. Their capacity-achieving key generation protocol involved terminals communicating to attain omniscience, i.e., every terminal gets to recover the sources of the other terminals. While this is a very general protocol, it often requires larger rates of public communication than is necessary to achieve SK capacity. The primary focus of this dissertation is to characterize the communication complexity, i.e., the minimum rate of public discussion needed to achieve SK capacity. A lower bound to communication complexity is derived for a general multiterminal source, although it turns out to be loose in general. While the minimum rate of communication for omniscience is always an upper bound to the communication complexity, we derive tighter upper bounds to communication complexity for a special class of multiterminal sources, namely, the hypergraphical sources. This upper bound yield a complete characterization of hypergraphical sources where communication for omniscience is a rate-optimal protocol for SK generation, i.e., the communication complexity equals the minimum rate of communication for omniscience. Another aspect of the public communication touched upon by this dissertation is the necessity of omnivocality, i.e., all terminals communicating, to achieve the SK capacity. It is well known that in two-terminal sources, only one terminal communicating success to generate a maximum rate secret key. However, we are able to show that for three or more terminals, omnivocality is indeed required to achieve SK capacity if a certain condition is met. For the specific case of three terminals, we show that this condition is also necessary to ensure omnivocality is essential in generating a SK of maximal rate. However, this condition is no longer necessary when there are four or more terminals. A certain notion of common information, namely, the Wyner common information, plays a central role in the communication complexity problem. This dissertation thus includes a study of multiparty versions of the two widely used notions of common information, namely, Wyner common information and Gacs-Korner (GK) common information. While evaluating these quantities is difficult in general, we are able to derive explicit expressions for both types of common information in the case of hypergraphical sources. We also study fault-tolerant SK…
We study common randomness where two parties have access to i.i.d. samples from a known random source, and wish to generate a shared random key using limited (or no) communication with the largest possible probability of agreement. This problem is at the core of secret key generation in cryptography, with connections to communication under uncertainty and locality sensitive hashing. We take the approach of treating correlated sources as a critical resource, and ask whether common randomness can be generated resource-efficiently. We consider two notable sources in this setup arising from correlated bits and correlated Gaussians. We design the first explicit schemes that use only a polynomial number of samples (in the key length) so that the players can generate shared keys that agree with constant probability using optimal communication. The best previously known schemes were both non-constructive and used an exponential number of samples. In the amortized setting, we characterize the largest achievable ratio of key length to communication in terms of the external and internal information costs, two well-studied quantities in theoretical computer science. In the relaxed setting where the two parties merely wish to improve the correlation between the generated keys of length k, we show that there are no interactive protocols using o(k) bits of communication having agreement probability even as small as 2–o(k). For the related communication problem where the players wish to compute a joint function f of their inputs using i.i.d samples from a known source, we give a simultaneous message passing protocol using 2O(c) bits where c is the interactive randomized public-coin communication complexity of f. This matches the lower bound shown previously while the best previously known upper bound was doubly exponential in c. Our schemes reveal a new connection between common randomness and unbiased error-correcting codes, e.g., dual-BCH codes and their analogues in Euclidean space.
We consider the generation of common randomness (CR), secret or not secret, by two user terminals with aid from a "helper" terminal. Each terminal observes a different component of a discrete memoryless multiple source. The helper aids the users by transmitting information to them over a noiseless public channel subject to a rate constraint. Furthermore, one of the users is allowed to transmit to the other user over a public channel under a similar rate constraint. We study the maximum rate of CR which can be thus generated, including under additional secrecy conditions when it must be concealed from a wiretapper. Lower bounds for the corresponding capacities are provided, and single-letter capacity formulas are obtained for several special cases of interest.