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 Information Theory Workshop (ITW)

Common randomness amplification: A constructive view

Grégory Demay, Ueli M. Maurer

Published Sep 1, 2012• 1 citation
Publisher

Abstract

Common randomness is an important resource in many areas such as game theory and cryptography. We discuss the general problem of common randomness amplification between two distrustful parties connected by a communication channel and sharing some initial randomness. In this setting, both parties wish to agree on a common value distributed according to a target distribution by using their initial amount of common randomness and exchanging messages. Our results show that no protocol which is secure in a composable sense can significantly amplify the entropy initially shared by the parties.

DOI
10.1109/itw.2012.6404693

Related papers

On the impossibility of information-theoretic composable coin toss extension

Gregor Seiler, Ueli M. Maurer

Shared randomness is an important resource in cryptography. It is well-known that in the information-theoretic setting there is no protocol that allows two parties who do not trust each other to obtain a uniformly distributed shared bit string solely by exchanging messages such that a dishonest party can not influence the result. On the other hand, in the situation where the two parties already share a random bit string and want to use it in order to construct a longer random bit string, it is only known to be impossible when the protocols are restricted in the number of messages to be exchanged. In this paper we prove that it is also impossible when arbitrarily many messages are allowed.

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

The Role of Interaction in Common Randomness and Secret Key Generation

Noah Golowich

In this work we study the problems of common randomness generation (CRG) and secret key generation (SKG). In the CRG problem, two parties, Alice and Bob, receive samples X and Y, respectively, from some joint source distribution μ. The two parties wish to agree on a key consisting of many bits of randomness, by exchanging messages that depend on each party’s respective input and the previous messages. The SKG problem is the same as CRG, except that an eavesdropper who observes the messages must not be able to determine much information about the key. We study the tradeoff between the minimum total length of all messages for a protocol generating a given number of bits of randomness and the minimum possible number of rounds in such a protocol. We construct a source distribution parametrized by positive integers r, n, and l, achieving such a tradeoff in a strong sense: when Alice and Bob can use r + 2 rounds of communication and l ≥ n, they can agree on l bits of entropy by communicating only O(log n) bits, but when they are restricted to r rounds of communication, they require communication of Ω(n^(1/2) / poly log(n)) bits to agree on l bits of entropy. We also prove an analogous result for the setting in which Alice and Bob can amortize, meaning that they receive N i.i.d. samples of (X, Y) from μ, and the communication and key length, respectively, are measured by the ratio of the actual number of bits communicated and the actual key length, respectively, to N.

•Aug 23, 2019•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•15 citations

Round Complexity of Common Randomness Generation: The Amortized Setting

Noah Golowich, Madhu Sudan

In this work we study the effect of rounds of interaction on the common randomness generation (CRG) problem. In the CRG problem, two parties, Alice and Bob, receive samples Xi and Yi, respectively, where (Xi, Yi) are drawn jointly from a source distribution μ. The two parties wish to agree on a common random key consisting of many bits of randomness, by exchanging messages that depend on each party's respective input and the previous messages. In this work we study the amortized version of the problem, i.e., the number of bits of communication needed per random bit output by Alice and Bob, in the limit as the number of bits generated tends to infinity. The amortized version of the CRG problem has been extensively studied in the information theory literature, though very little was known about the effect of interaction on this problem. Recently Bafna et al. (SODA 2019) considered the non-amortized version of the problem (so here the goal of the interaction is to generate a fixed number of random bits): they gave a family of sources μr,n parameterized by r,n ϵ ℕ, such that with r + 2 rounds of communication one can generate n bits of common randomness with this source with O(r log n) communication, whereas with roughly r/2 rounds the communication complexity is Ω(n/ poly log n). Note in particular that their source is designed with the target number of bits in mind and hence the result does not apply to the amortized setting. In this work we strengthen the work of Bafna et al. in two ways: First we show that the results extend to the classical amortized setting. We also reduce the gap between the round complexity in the upper and lower bounds to an additive constant. Specifically we show that for every pair r, n ϵ ℕ the (amortized) communication complexity to generate Ω(n) bits of common randomness from the source μr,n using r + 2 rounds of communication is O(r log n) whereas the amortized communication required to generate the same amount of randomness from r rounds is . Our techniques exploit known connections between information complexity and CRG, and the main novelty is our ability to analyze the information complexity of protocols getting inputs from the source μr,n.

arXiv:1909.00323•Society for Industrial and Applied Mathematics eBooks•Dec 23, 2019•5 citations

On the Problem of Local Randomness in Privacy Amplification with an Active Adversary

Xin Li

We study the problem of privacy amplification with an active adversary in the information theoretic setting. In this setting, two parties Alice and Bob start out with a shared $n$-bit weak random string $W$, and try to agree on a secret random key $R$ over a public channel fully controlled by an active and unbounded adversary. Typical assumptions are that these two parties have access to local private uniform random bits. In this paper we seek to minimize the requirements on the local randomness used by the two parties. We make two improvements over previous results. First, we reduce the number of random bits needed for each party to $Θ(\ell+\log n)$, where $\ell$ is the security parameter, as long as $W$ has min-entropy $n^{Ω(1)}$. Previously, the best known result needs to use $Θ((\ell+\log n)\log n)$ bits. Our result is also asymptotically optimal. Second, we generalize the problem to the case where the two parties only have local weak random sources instead of truly uniform random bits. We show that when each party has a local weak random source with min-entropy $> n/2$, there is an efficient privacy amplification protocol that works nearly as good as if the two parties have access to local uniform random bits. Next, in the case where each party only has a weak random source with arbitrarily linear min-entropy, we give an efficient privacy amplification protocol where we can achieve security parameter up to $Ω(\log k)$. Our results give the first protocols that achieve privacy amplification when each party only has access to a local weak random source.

arXiv:1011.2551•Nov 11, 2010•1 citation

Common Randomness Generation from Sources with Infinite Polish Alphabets

Wafa Labidi, Rami Ezzine, Moritz Wiese +2 more

We study the problem of common randomness (CR) generation in a fundamental two-party communication scenario, where a sender and a receiver seek to agree-with high probability-on a shared random variable. Both parties observe independent and identically distributed (i.i.d.) samples from sources defined over a Polish alphabet with an arbitrary joint distribution. Communication is restricted to a unidirectional, minimally interactive exchange over a noisy, memoryless channel. For this setting, we establish single-letter lower and upper bounds on the CR capacity. These bounds coincide except possibly at a countable set of points where discontinuities may arise.

IEEE International Symposium on Information Theory (ISIT)•Jun 22, 2025•0 citations
Common randomness is an important resource in many areas such as game theory and cryptography. We discuss the general problem of common randomness amplification between two distrustful parties connected by a communication channel and sharing some initial randomness. In this setting, both parties wish to agree on a common value distributed according to a target distribution by using their initial amount of common randomness and exchanging messages. Our results show that no protocol which is secure in a composable sense can significantly amplify the entropy initially shared by the parties.
Shared randomness is an important resource in cryptography. It is well-known that in the information-theoretic setting there is no protocol that allows two parties who do not trust each other to obtain a uniformly distributed shared bit string solely by exchanging messages such that a dishonest party can not influence the result. On the other hand, in the situation where the two parties already share a random bit string and want to use it in order to construct a longer random bit string, it is only known to be impossible when the protocols are restricted in the number of messages to be exchanged. In this paper we prove that it is also impossible when arbitrarily many messages are allowed.
In this work we study the problems of common randomness generation (CRG) and secret key generation (SKG). In the CRG problem, two parties, Alice and Bob, receive samples X and Y, respectively, from some joint source distribution μ. The two parties wish to agree on a key consisting of many bits of randomness, by exchanging messages that depend on each party’s respective input and the previous messages. The SKG problem is the same as CRG, except that an eavesdropper who observes the messages must not be able to determine much information about the key. We study the tradeoff between the minimum total length of all messages for a protocol generating a given number of bits of randomness and the minimum possible number of rounds in such a protocol. We construct a source distribution parametrized by positive integers r, n, and l, achieving such a tradeoff in a strong sense: when Alice and Bob can use r + 2 rounds of communication and l ≥ n, they can agree on l bits of entropy by communicating only O(log n) bits, but when they are restricted to r rounds of communication, they require communication of Ω(n^(1/2) / poly log(n)) bits to agree on l bits of entropy. We also prove an analogous result for the setting in which Alice and Bob can amortize, meaning that they receive N i.i.d. samples of (X, Y) from μ, and the communication and key length, respectively, are measured by the ratio of the actual number of bits communicated and the actual key length, respectively, to N.
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.
In this work we study the effect of rounds of interaction on the common randomness generation (CRG) problem. In the CRG problem, two parties, Alice and Bob, receive samples Xi and Yi, respectively, where (Xi, Yi) are drawn jointly from a source distribution μ. The two parties wish to agree on a common random key consisting of many bits of randomness, by exchanging messages that depend on each party's respective input and the previous messages. In this work we study the amortized version of the problem, i.e., the number of bits of communication needed per random bit output by Alice and Bob, in the limit as the number of bits generated tends to infinity. The amortized version of the CRG problem has been extensively studied in the information theory literature, though very little was known about the effect of interaction on this problem. Recently Bafna et al. (SODA 2019) considered the non-amortized version of the problem (so here the goal of the interaction is to generate a fixed number of random bits): they gave a family of sources μr,n parameterized by r,n ϵ ℕ, such that with r + 2 rounds of communication one can generate n bits of common randomness with this source with O(r log n) communication, whereas with roughly r/2 rounds the communication complexity is Ω(n/ poly log n). Note in particular that their source is designed with the target number of bits in mind and hence the result does not apply to the amortized setting. In this work we strengthen the work of Bafna et al. in two ways: First we show that the results extend to the classical amortized setting. We also reduce the gap between the round complexity in the upper and lower bounds to an additive constant. Specifically we show that for every pair r, n ϵ ℕ the (amortized) communication complexity to generate Ω(n) bits of common randomness from the source μr,n using r + 2 rounds of communication is O(r log n) whereas the amortized communication required to generate the same amount of randomness from r rounds is . Our techniques exploit known connections between information complexity and CRG, and the main novelty is our ability to analyze the information complexity of protocols getting inputs from the source μr,n.
We study the problem of privacy amplification with an active adversary in the information theoretic setting. In this setting, two parties Alice and Bob start out with a shared nnn-bit weak random string WWW, and try to agree on a secret random key RRR over a public channel fully controlled by an active and unbounded adversary. Typical assumptions are that these two parties have access to local private uniform random bits. In this paper we seek to minimize the requirements on the local randomness used by the two parties. We make two improvements over previous results. First, we reduce the number of random bits needed for each party to Θ(ℓ+log⁡n)Θ(\ell+\log n)Θ(ℓ+logn), where ℓ\ellℓ is the security parameter, as long as WWW has min-entropy nΩ(1)n^{Ω(1)}nΩ(1). Previously, the best known result needs to use Θ((ℓ+log⁡n)log⁡n)Θ((\ell+\log n)\log n)Θ((ℓ+logn)logn) bits. Our result is also asymptotically optimal. Second, we generalize the problem to the case where the two parties only have local weak random sources instead of truly uniform random bits. We show that when each party has a local weak random source with min-entropy >n/2> n/2>n/2, there is an efficient privacy amplification protocol that works nearly as good as if the two parties have access to local uniform random bits. Next, in the case where each party only has a weak random source with arbitrarily linear min-entropy, we give an efficient privacy amplification protocol where we can achieve security parameter up to Ω(log⁡k)Ω(\log k)Ω(logk). Our results give the first protocols that achieve privacy amplification when each party only has access to a local weak random source.
We study the problem of common randomness (CR) generation in a fundamental two-party communication scenario, where a sender and a receiver seek to agree-with high probability-on a shared random variable. Both parties observe independent and identically distributed (i.i.d.) samples from sources defined over a Polish alphabet with an arbitrary joint distribution. Communication is restricted to a unidirectional, minimally interactive exchange over a noisy, memoryless channel. For this setting, we establish single-letter lower and upper bounds on the CR capacity. These bounds coincide except possibly at a countable set of points where discontinuities may arise.