We present a new proof of a celebrated result of Gács and Körner that the common information is far less than the mutual information. Consider two sequences
α1,…αnand
β1,…,βnof random variables, where pairs
(α1,β1),…,(αn,βn)are independent and identically distributed. Gács and Körner proved that it is not possible to extract “common information” from these two sequences unless the joint distribution matrix of random variables
(αi,βi)is a block matrix.
An important subclass of secure multiparty computation is secure sampling: two parties output samples of a pair of jointly distributed random variables such that neither party learns more about the other party's output than what its own output reveals. The parties make use of a setup - correlated random variables with a different distribution - as well as unlimited noiseless communication. An upperbound on the rate of producing samples of a desired distribution from a given setup is presented. The region of tension developed in this paper measures how well the dependence between a pair of random variables can be resolved by a piece of common information. The bounds on rate are a consequence of a monotonicity property; a protocol between two parties can only lower the tension between their views. Connections are drawn between the region of tension and the notion of common information. A generalization of the Gács-Körner common information, called the assisted common information, which takes into account almost common information ignored by Gács-Körner common information is defined. The region of tension is shown to be related to the rate regions of both the assisted common information and the Gray-Wyner systems (and, a fortiori, Wyner's common information).
We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Unand Vnrespectively, drawn from a joint distribution
pUV⊗n, and wish to locally generate sequences Xnand Ynrespectively with a joint distribution that is close (in KL divergence) to
pXY⊗n. We provide a single-letter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the Gàcs-Körner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains
X−U−V−Y can be simulated otherwise. Motivated by this conjecture, we further examine the case where both pUVand pXYare doubly symmetric binary sources with parameters
p,q≤1/2 respectively. While it is trivial that in this case
p≤q is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.
A Santha--Vazirani (SV) source is a sequence of random bits where the conditional distribution of each bit, given the previous bits, can be partially controlled by an adversary. Santha and Vazirani show that deterministic randomness extraction from these sources is impossible. In this paper, we study the generalization of SV sources for nonbinary sequences. We show that unlike the binary setup of Santha and Vazirani, deterministic randomness extraction in the generalized case is sometimes possible. In particular, if the adversary has access to
s “nondegenerate” dice that are
c-sided and can choose one die to throw based on the previous realizations of the dice, then deterministic randomness extraction is possible if
s<c. We present a necessary condition and a sufficient condition for the possibility of deterministic randomness extraction. These two conditions complement each other in the nondegenerate cases. Next, we turn to a distributed setting. In this setting the SV source consists of a random sequence of pairs
(a1,b1),(a2,b2),… distributed between two parties, where the first party receives
ai's and the second one receives
bi's. The goal of the two parties is to extract common randomness without communication. Using the notion of maximal correlation, we prove a necessary condition and a sufficient condition for the possibility of common randomness extraction from these sources. Based on these two conditions, the problem of common randomness extraction essentially reduces to the problem of randomness extraction from (nondistributed) SV sources. This result generalizes results of Gács and Körner, and Witsenhausen about common randomness extraction from independently and identically distributed sources to adversarial sources.