Assisted Common Information With an Application to Secure Two-Party Sampling
Authors:
- 7 April 2014
- journal article
- Published by Institute of Electrical and Electronics Engineers (IEEE) in IEEE Transactions on Information Theory
- Vol. 60 (6) , 3413-3434
Abstract
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).Keywords
All Related Versions
Funding Information
- Department of Science and Technology, Government of India, for Ramanujan Fellowship
- National Science Foundation (NSF) CAREER (07-47027)
- NSF (12-28856)
This publication has 21 references indexed in Scilit:
- Efficient Oblivious Transfer Protocols Achieving a Non-zero Rate from Any Non-trivial Noisy CorrelationLecture Notes in Computer Science, 2009
- New Monotones and Lower Bounds in Unconditional Two-Party ComputationIEEE Transactions on Information Theory, 2008
- Efficient Protocols Achieving the Commitment Capacity of Noisy Correlations2006
- On the Oblivious Transfer Capacity of the Erasure Channel2006
- Rates for bit commitment and coin tossing from noisy correlation2004
- To code, or not to code: lossy source-channel communication revisitedIEEE Transactions on Information Theory, 2003
- Coding theorems for Shannon's cipher system with correlated source outputs, and common informationIEEE Transactions on Information Theory, 1994
- The rate-distortion function for source coding with side information at the decoderIEEE Transactions on Information Theory, 1976
- The common information of two dependent random variablesIEEE Transactions on Information Theory, 1975
- Source Coding for a Simple NetworkBell System Technical Journal, 1974