The Private and Public Correlation Cost of Three Random Variables With Collaboration
Eric Chitambar, Min-Hsiu Hsieh, Andreas Winter
In this paper, we consider the problem of generating arbitrary three-party correlations from a combination of public and secret correlations. Two parties-called Alice and Bob-share perfectly correlated bits that are secret from a collaborating third party, Charlie. At the same time, all three parties have access to a separate source of correlated bits, and their goal is to convert these two resources into multiple copies of some given tripartite distribution P(XYZ). We obtain a single-letter characterization of the tradeoff between public and private bits that are needed to achieve this task. The rate of private bits is shown to generalize Wyner's classic notion of common information held between a pair of random variables. The problem we consider can be contrasted fruitfully with the task of secrecy formation, in which P(XYZ) is generated using public communication and local randomness but with Charlie functioning as an adversary instead of a collaborator. We describe in detail the differences between the collaborative and adversarial scenarios.
arXiv:1411.0729•IEEE Transactions on Information Theory•Mar 10, 2016•8 citations