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

IEEE Transactions on Information Theory

Common randomness in information theory and cryptography. II. CR capacity

Rudolf Ahlswede, Imre Csiszár

Published Jan 1, 1998• 256 citations
Publisher

Abstract

For pt.I see ibid., vol.39, p.1121, 1993. The common randomness (CR) capacity of a two-terminal model is defined as the maximum rate of common randomness that the terminals can generate using resources specified by the given model. We determine CR capacity for several models, including those whose statistics depend on unknown parameters. The CR capacity is shown to be achievable robustly, by common randomness of nearly uniform distribution no matter what the unknown parameters are. Our CR capacity results are relevant for the problem of identification capacity, and also yield a new result on the regular (transmission) capacity of arbitrarily varying channels with feedback.

DOI
10.1109/18.651026

Related papers

Common Randomness Generation and Identification over Gaussian Channels

Rami Ezzine, Wafa Labidi, Holger Boche +1 more

Common randomness (CR), as a resource, is not commonly used in existing practical communication systems. In the common randomness framework, both sender and receiver, often described as terminals, aim to generate a common random variable observable to both, perhaps with low error probability. The knowledge of this CR allows to implement correlated random protocols that could lead to faster and more efficient algorithms. We characterize CR over Gaussian channels for their practical relevance in many communication situations by deriving the CR capacity for both Gaussian Single-Input Single-Output (SISO) and Multiple-Input Multiple-Output (MIMO) cases. Furthermore, CR plays a key role in the identification scheme. In many new applications such as several machine-to-machine and human-to-machine systems and the tactile internet, which demand ultra-reliable low latency, the identification or also called post-Shannon scheme is proved to be more efficient than the classical transmission. It has been proved that through CR generation, the post-Shannon communication task allows to achieve an enormous performance gain. We consider a correlation-assisted secure identification scheme over Gaussian wiretap channels (GWC) and develop a lower bound on the corresponding secure identification capacity.

Globecom•Dec 1, 2020•27 citations

Common Randomness Generation from Finite Compound Sources

Rami Ezzine, Moritz Wiese, Christian Deppe +1 more

We investigate the problem of generating common randomness (CR) from finite compound sources aided by unidirectional communication over rate-limited perfect channels. The two communicating parties, often referred to as terminals, observe independent and identically distributed (i.i.d.) samples of a finite compound source and aim to agree on a common random variable with a high probability for every possible realization of the source state. Both parties know the set of source states as well as their statistics. However, they are unaware of the actual realization of the source state. We establish a single-letter lower and upper bound on the compound CR capacity for the specified model. Furthermore, we present two special scenarios where the established bounds coincide.

arXiv:2401.14323•IEEE International Symposium on Information Theory (ISIT)•Jul 7, 2024•3 citations

Common randomness and secret key generation with a helper

I.A CSISZAR, P. Narayan

Ahlswede-Csiszar (1993) and Csiszar (see Problemy Peredacii Informatsii, 1996) have addressed problems of determining the common randomness (CR) capacity and the secret key (SK) capacity for a variety of models as they arise in information theory and cryptography. We study problems of common randomness and secret key generation by a pair of terminals called the "users" with help from a third terminal, called the "helper". Noiseless one-way communication from the helper to the users as also from one user to the other, subject to rate constraints, is permitted over public channels. A situation involving a wiretapper is also considered.

IEEE International Symposium on Information Theory (ISIT)•Nov 22, 2002•12 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•7 citations

Common Randomness: A Key Enabler of Trustworthy 6G Communication Systems

Rami Ezzine, Moritz Wiese, Wafa Labidi +2 more

Common randomness (CR) is a valuable resource for enhancing the trustworthiness of 6G communication systems. This article highlights the role of CR in improving scalability, security, and resilience in distributed 6G architectures. It provides an overview of information-theoretic two-source models for CR generation and summarizes known capacity results, together with their implications for practical systems under different communication settings, including one-way, two-way, helper-assisted, and interactive scenarios. Furthermore, the article explores CR-assisted secure identification over Gaussian channels as an application and highlights selected open research problems in CR generation for next-generation wireless systems. The article targets researchers and practitioners interested in bridging information-theoretic tools with emerging 6G communication systems.

arXiv:2609.18574•IEEE BITS the Information Theory Magazine•Jan 1, 2026•0 citations

Common Randomness Generation from Sources with Infinite Polish Alphabet

Wafa Labidi, Rami Ezzine, Moritz Wiese +2 more

We investigate the problem of common randomness (CR) generation in the basic two-party communication setting in which a sender and a receiver aim to agree on a common random variable with high probability. The terminals observe independent and identically distributed (i.i.d.) samples of sources with an arbitrary distribution defined on a Polish alphabet and are allowed to communicate as little as possible over a noisy, memoryless channel. We establish single-letter upper and lower bounds on the CR capacity for the specified model. The derived bounds hold with equality except for at most countably many points where discontinuity issues might arise.

arXiv:2405.01948•May 3, 2024•0 citations
For pt.I see ibid., vol.39, p.1121, 1993. The common randomness (CR) capacity of a two-terminal model is defined as the maximum rate of common randomness that the terminals can generate using resources specified by the given model. We determine CR capacity for several models, including those whose statistics depend on unknown parameters. The CR capacity is shown to be achievable robustly, by common randomness of nearly uniform distribution no matter what the unknown parameters are. Our CR capacity results are relevant for the problem of identification capacity, and also yield a new result on the regular (transmission) capacity of arbitrarily varying channels with feedback.
Common randomness (CR), as a resource, is not commonly used in existing practical communication systems. In the common randomness framework, both sender and receiver, often described as terminals, aim to generate a common random variable observable to both, perhaps with low error probability. The knowledge of this CR allows to implement correlated random protocols that could lead to faster and more efficient algorithms. We characterize CR over Gaussian channels for their practical relevance in many communication situations by deriving the CR capacity for both Gaussian Single-Input Single-Output (SISO) and Multiple-Input Multiple-Output (MIMO) cases. Furthermore, CR plays a key role in the identification scheme. In many new applications such as several machine-to-machine and human-to-machine systems and the tactile internet, which demand ultra-reliable low latency, the identification or also called post-Shannon scheme is proved to be more efficient than the classical transmission. It has been proved that through CR generation, the post-Shannon communication task allows to achieve an enormous performance gain. We consider a correlation-assisted secure identification scheme over Gaussian wiretap channels (GWC) and develop a lower bound on the corresponding secure identification capacity.
We investigate the problem of generating common randomness (CR) from finite compound sources aided by unidirectional communication over rate-limited perfect channels. The two communicating parties, often referred to as terminals, observe independent and identically distributed (i.i.d.) samples of a finite compound source and aim to agree on a common random variable with a high probability for every possible realization of the source state. Both parties know the set of source states as well as their statistics. However, they are unaware of the actual realization of the source state. We establish a single-letter lower and upper bound on the compound CR capacity for the specified model. Furthermore, we present two special scenarios where the established bounds coincide.
Ahlswede-Csiszar (1993) and Csiszar (see Problemy Peredacii Informatsii, 1996) have addressed problems of determining the common randomness (CR) capacity and the secret key (SK) capacity for a variety of models as they arise in information theory and cryptography. We study problems of common randomness and secret key generation by a pair of terminals called the "users" with help from a third terminal, called the "helper". Noiseless one-way communication from the helper to the users as also from one user to the other, subject to rate constraints, is permitted over public channels. A situation involving a wiretapper is also considered.
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.
Common randomness (CR) is a valuable resource for enhancing the trustworthiness of 6G communication systems. This article highlights the role of CR in improving scalability, security, and resilience in distributed 6G architectures. It provides an overview of information-theoretic two-source models for CR generation and summarizes known capacity results, together with their implications for practical systems under different communication settings, including one-way, two-way, helper-assisted, and interactive scenarios. Furthermore, the article explores CR-assisted secure identification over Gaussian channels as an application and highlights selected open research problems in CR generation for next-generation wireless systems. The article targets researchers and practitioners interested in bridging information-theoretic tools with emerging 6G communication systems.
We investigate the problem of common randomness (CR) generation in the basic two-party communication setting in which a sender and a receiver aim to agree on a common random variable with high probability. The terminals observe independent and identically distributed (i.i.d.) samples of sources with an arbitrary distribution defined on a Polish alphabet and are allowed to communicate as little as possible over a noisy, memoryless channel. We establish single-letter upper and lower bounds on the CR capacity for the specified model. The derived bounds hold with equality except for at most countably many points where discontinuity issues might arise.