Assisted Common Information With an Application to Secure Two-Party Sampling

作者：Prabhakaran Vinod M^*; Prabhakaran Manoj M

来源：IEEE Transactions on Information Theory, 2014, 60(6): 3413-3434.

DOI：10.1109/TIT.2014.2316011

• Common information
• secure multiparty computation
• Wyner-Ziv coding
• oblivious transfer

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 Gacs-Korner common information, called the assisted common information, which takes into account almost common information ignored by Gacs-Korner 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).

• 出版日期2014-6