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:1601.00899 · IEEE Transactions on Information Theory

Secret Key Generation With Limited Interaction

Jingbo Liu, Paul Cuff, Sergio Verdú

Published Aug 28, 2017• 34 citations
arXivHTMLPDF

Abstract

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.

DOI
10.1109/tit.2017.2746104

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

Common Randomness and Key Generation with Limited Interaction.

Jingbo Liu, Paul Cuff, Sergio Verdú

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.

•Jan 5, 2016•8 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

On the communication complexity of secret key generation in the multiterminal source model

Manuj Mukherjee, Navin Kashyap

Communication complexity refers to the minimum rate of public communication required for generating a maximal-rate secret key (SK) in the multiterminal source model of Csiszár and Narayan. Tyagi recently characterized this communication complexity for a two-terminal system. We extend the ideas in Tyagi's work to derive a lower bound on communication complexity in the general multiterminal setting. In the important special case of the complete graph pairwise independent network (PIN) model, our bound allows us to determine the exact linear communication complexity, i.e., the communication complexity when the communication and SK are restricted to be linear functions of the randomness available at the terminals.

arXiv:1401.1117•IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2014•8 citations

Communication-Constrained Secret Key Generation: Second-Order Bounds

Henri Hentilä, Yanina Y. Shkel, Visa Koivunen

We study communication-constrained secret key generation, where two legitimate parties would like to generate a secret key using communication subject to a rate constraint. The problem is studied in the finite-blocklength regime. In this regime, the use of auxiliary random variables subject to Markov chain conditions in the corresponding asymptotic bounds has proven to make most existing proof techniques insufficient. However, two recently proposed proof techniques – one for the achievability side based on Poisson matching, and another for the converse side based on reverse hypercontractivity – allow us to overcome these issues to some extent. Based on these techniques, novel one-shot and second-order achievability and converse bounds are derived for the problem. While the second-order bounds do not coincide, leaving a precise second-order characterization of the problem an open issue, they improve upon the previously known tightest bounds. The second-order bounds are demonstrated for two simple sources: the binary symmetric source and the Gaussian symmetric source. For the binary source, we find that the gap between the two bounds is mainly due to an unwanted constant in the converse bound, and the non-convexity of the achievability bound.

IEEE Transactions on Information Theory•Sep 13, 2024•4 citations

Minimal public communication for maximum rate secret key generation

Himanshu Tyagi

Secret key generation is considered for a pair of terminals that observe correlated sources and communicate interactively over a public channel. It is argued that optimum rate secret key generation is linked inherently to the Wyner's notion of common information between two dependent random variables. The minimum rate of interactive public communication required to generate an optimum rate secret key is characterized in terms of a variant of this notion of common information.

IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•1 citation
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.
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.
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.
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.
Communication complexity refers to the minimum rate of public communication required for generating a maximal-rate secret key (SK) in the multiterminal source model of Csiszár and Narayan. Tyagi recently characterized this communication complexity for a two-terminal system. We extend the ideas in Tyagi's work to derive a lower bound on communication complexity in the general multiterminal setting. In the important special case of the complete graph pairwise independent network (PIN) model, our bound allows us to determine the exact linear communication complexity, i.e., the communication complexity when the communication and SK are restricted to be linear functions of the randomness available at the terminals.
We study communication-constrained secret key generation, where two legitimate parties would like to generate a secret key using communication subject to a rate constraint. The problem is studied in the finite-blocklength regime. In this regime, the use of auxiliary random variables subject to Markov chain conditions in the corresponding asymptotic bounds has proven to make most existing proof techniques insufficient. However, two recently proposed proof techniques – one for the achievability side based on Poisson matching, and another for the converse side based on reverse hypercontractivity – allow us to overcome these issues to some extent. Based on these techniques, novel one-shot and second-order achievability and converse bounds are derived for the problem. While the second-order bounds do not coincide, leaving a precise second-order characterization of the problem an open issue, they improve upon the previously known tightest bounds. The second-order bounds are demonstrated for two simple sources: the binary symmetric source and the Gaussian symmetric source. For the binary source, we find that the gap between the two bounds is mainly due to an unwanted constant in the converse bound, and the non-convexity of the achievability bound.