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.
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 the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples X1, X2, … and Y1, Y2, … with the pairs (X1, Y1), (X2, Y2), … being drawn independently from some known probability distribution µ. They wish to communicate so as to agree on L bits of randomness. The SKG problem is the restriction of the CRG problem to the case where the key is required to be close to random even to an eavesdropper who can listen to their communication (but does not have access to the inputs of Alice and Bob). In this work, we study the relationship between the amount of communication and the number of rounds of interaction in both the CRG and the SKG problems. Specifically, we construct a family of distributions µ = µr,n,L, parametrized by integers r, n and L, such that for every r there exists a constant b = b(r) for which CRG (respectively SKG) is feasible when (Xi, Yi) ∼ µr,n,L with r + 1 rounds of communication, each consisting of O(log n) bits, but when restricted to r/2 – 2 rounds of interaction, the total communication must exceed Ω(n/ logb(n)) bits. Prior to our work no separations were known for r ≥ 2.
We study the role of interaction in the Common Randomness Generation (CRG) and Secret Key Generation (SKG) problems. In the CRG problem, two players, Alice and Bob, respectively get samples X1,X2,… and Y1,Y2,… with the pairs (X1,Y1), (X2,Y2), … being drawn independently from some known probability distribution μ. They wish to communicate so as to agree on L bits of randomness. The SKG problem is the restriction of the CRG problem to the case where the key is required to be close to random even to an eavesdropper who can listen to their communication (but does not have access to the inputs of Alice and Bob). In this work, we study the relationship between the amount of communication and the number of rounds of interaction in both the CRG and the SKG problems. Specifically, we construct a family of distributions μ=μr,n,L, parametrized by integers r, n and L, such that for every r there exists a constant b=b(r) for which CRG (respectively SKG) is feasible when (Xi,Yi)∼μr,n,L with r+1 rounds of communication, each consisting of O(logn) bits, but when restricted to r/2−3 rounds of interaction, the total communication must exceed Ω(n/logb(n)) bits. Prior to our work no separations were known for r≥2.
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 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 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.
Two legitimate parties, referred to as Alice and Bob, wish to generate secret keys from the wireless channel in the presence of an eavesdropper, referred to as Eve, in order to use such keys for encryption and decryption. In general, the secret key rate highly depends on the coherence time of the channel. In particular, a straightforward method of generating secret keys in static environments results in ultra-low rates. In order to resolve this problem, we introduce a low-complexity method called induced randomness. In this method, Alice and Bob independently generate local randomness to be used together with the uniqueness of the wireless channel coefficients in order to enable high-rate secret key generation. In this work, two scenarios are considered: first, when Alice and Bob share a direct communication channel, and second, when Alice and Bob do not have a direct link and communicate through an untrusted relay. After exchanging the induced randomness, post-processing is done by Alice and Bob to generate highly-correlated samples that are used for the key generation. Such samples are then converted into bits, disparities between the sequences generated by Alice and Bob are mitigated, and the resulting sequences are then hashed to compensate for the information leakage to the eavesdropper and to allow consistency checking of the generated key bit sequences. We utilize semantic security measures and information-theoretic inequalities to upper bound the probability of successful eavesdropping attack in terms of the mutual information measures that can be numerically computed. Given certain reasonable system parameters this bound is numerically evaluated to be 2-31and 2-10.57in the first and the second scenario, respectively.