Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1002.1916 · IEEE Transactions on Information Theory

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

Vinod M. Prabhakaran, Manoj Prabhakaran

Published Apr 7, 2014• 48 citations
arXivHTMLPDF

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).

DOI
10.1109/tit.2014.2316011

Related papers

Assisted common information

Vinod M. Prabhakaran, Manoj Prabhakaran

Secure multi-party computation is a central problem in modern cryptography. An important sub-class of this are problems of the following form: Alice and Bob desire to produce sample(s) of a pair of jointly distributed random variables. Each party must learn nothing more about the other party's output than what its own output reveals. To aid in this, they have available a set up - correlated random variables whose distribution is different from the desired distribution - as well as unlimited noiseless communication. In this paper we present an upperbound on how efficiently a given set up can be used to produce samples from a desired distribution. The key tool we develop is a generalization of the concept of common information of two dependent random variables [Gács-Körner, 1973]. Our generalization - a three-dimensional region - remedies some of the limitations of the original definition which captured only a limited form of dependence. It also includes as a special case Wyner's common information [Wyner, 1975]. To derive the cryptographic bounds, we rely on a monotonicity property of this region: the region of the “views” of Alice and Bob engaged in any protocol can only monotonically expand and not shrink. Thus, by comparing the regions for the target random variables and the given random variables, we obtain our upperbound.

IEEE International Symposium on Information Theory (ISIT)•Jun 1, 2010•8 citations

Assisted common information: Further results

Vinod M. Prabhakaran, Manoj M. Prabhakaran

We presented assisted common information as a generalization of Gacs-Korner (GK) common information at last year's ISIT. The motivation for our formulation was to improve upperbounds on the efficiency of protocols for secure two-party sampling (which is a form of secure multi-party computation). Our upperbound was based on a monotonicity property of a rate region (called the assisted residual information region) associated with the assisted common information formulation. In this note we present further results. We explore the connection of assisted common information with the Gray-Wyner system. We show that the assisted residual information region and the Gray-Wyner region are connected by a simple relationship: the assisted residual information region is the increasing hull of the Gray-Wyner region under an affine map. Several known relationships between GK common information and Gray-Wyner system fall out as consequences of this. Quantities which arise in other source coding contexts acquire new interpretations. In previous work we showed that assisted common information can be used to derive upperbounds on the rate at which a pair of parties can securely sample correlated random variables, given correlated random variables from another distribution. Here we present an example where the bound derived using assisted common information is much better than previously known bounds, and in fact is tight. This example considers correlated random variables defined in terms of standard variants of oblivious transfer, and is interesting on its own as it answers a natural question about these cryptographic primitives.

arXiv:1105.6163•IEEE International Symposium on Information Theory (ISIT)•Jul 1, 2011•7 citations

Multipartite monotones for secure sampling by public discussion from noisy correlations

Pradeep Kr. Banerjee

We address the problem of quantifying the cryptographic content of probability distributions, in relation to an application to secure multi-party sampling against a passive t-adversary. We generalize a recently introduced notion of assisted common information of a pair of correlated sources to that of K sources and define a family of monotone rate regions indexed by K. This allows for a simple characterization of all t-private distributions that can be statistically securely sampled without any auxiliary setup of pre-shared noisy correlations. We also give a new monotone called the residual total correlation that admits a simple operational interpretation. Interestingly, for sampling with non-trivial setups (K > 2) in the public discussion model, our definition of a monotone region differs from the one by Prabhakaran and Prabhakaran (ITW 2012).

arXiv:1502.05773•Iran Workshop on Communication and Information Theory (IWCIT)•May 1, 2015•0 citations

Generalized Common Informations: Measuring Commonness by the Conditional Maximal Correlation

Lei Yu, Houqiang Li, Chang Wen Chen

In literature, different common informations were defined by Gács and Körner, by Wyner, and by Kumar, Li, and Gamal, respectively. In this paper, we define two generalized versions of common informations, named approximate and exact information-correlation functions, by exploiting the conditional maximal correlation as a commonness or privacy measure. These two generalized common informations encompass the notions of Gács-Körner's, Wyner's, and Kumar-Li-Gamal's common informations as special cases. Furthermore, to give operational characterizations of these two generalized common informations, we also study the problems of private sources synthesis and common information extraction, and show that the information-correlation functions are equal to the minimum rates of commonness needed to ensure that some conditional maximal correlation constraints are satisfied for the centralized setting versions of these problems. As a byproduct, the conditional maximal correlation has been studied as well.

arXiv:1610.09289•Oct 28, 2016•19 citations

Secure Two-Party Sampling Primitives are either Useless or Complete.

Ye Wang, Prakash Sharma Ishwar, Shantanu D. Rane

In the secure two-party sampling problem, two parties wish to generate outputs with a desired joint distribution via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own output. For semi-honest parties and information-theoretic privacy guarantees, it is well-known that if only noiseless communication is available, then only the joint distributions, for which common information equals mutual information, can be securely sampled. We consider the problem where the parties may also interact via a given set of general communication primitives (multi-input/output channels). Our feasibility characterization of this problem can be stated as a zero-one law: primitives are either complete (enabling the secure sampling of any distribution) or useless (only enabling the secure sampling of trivial distributions). Our characterization of the complete primitives also extends to the more general class of secure two-party computation problems.

•Feb 18, 2014•0 citations

Chain Independence and Common Information

Konstantin Makarychev, Yury Makarychev

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$\alpha_{1},\ldots\alpha_{n}$and$\beta_{1},\ldots,\beta_{n}$of random variables, where pairs$(\alpha_{1},\beta_{1}),\ldots, (\alpha_{n},\beta_{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$(\alpha_{i},\beta_{i})$is a block matrix.

IEEE Transactions on Information Theory•Jul 10, 2012•2 citations
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).
Secure multi-party computation is a central problem in modern cryptography. An important sub-class of this are problems of the following form: Alice and Bob desire to produce sample(s) of a pair of jointly distributed random variables. Each party must learn nothing more about the other party's output than what its own output reveals. To aid in this, they have available a set up - correlated random variables whose distribution is different from the desired distribution - as well as unlimited noiseless communication. In this paper we present an upperbound on how efficiently a given set up can be used to produce samples from a desired distribution. The key tool we develop is a generalization of the concept of common information of two dependent random variables [Gács-Körner, 1973]. Our generalization - a three-dimensional region - remedies some of the limitations of the original definition which captured only a limited form of dependence. It also includes as a special case Wyner's common information [Wyner, 1975]. To derive the cryptographic bounds, we rely on a monotonicity property of this region: the region of the “views” of Alice and Bob engaged in any protocol can only monotonically expand and not shrink. Thus, by comparing the regions for the target random variables and the given random variables, we obtain our upperbound.
We presented assisted common information as a generalization of Gacs-Korner (GK) common information at last year's ISIT. The motivation for our formulation was to improve upperbounds on the efficiency of protocols for secure two-party sampling (which is a form of secure multi-party computation). Our upperbound was based on a monotonicity property of a rate region (called the assisted residual information region) associated with the assisted common information formulation. In this note we present further results. We explore the connection of assisted common information with the Gray-Wyner system. We show that the assisted residual information region and the Gray-Wyner region are connected by a simple relationship: the assisted residual information region is the increasing hull of the Gray-Wyner region under an affine map. Several known relationships between GK common information and Gray-Wyner system fall out as consequences of this. Quantities which arise in other source coding contexts acquire new interpretations. In previous work we showed that assisted common information can be used to derive upperbounds on the rate at which a pair of parties can securely sample correlated random variables, given correlated random variables from another distribution. Here we present an example where the bound derived using assisted common information is much better than previously known bounds, and in fact is tight. This example considers correlated random variables defined in terms of standard variants of oblivious transfer, and is interesting on its own as it answers a natural question about these cryptographic primitives.
We address the problem of quantifying the cryptographic content of probability distributions, in relation to an application to secure multi-party sampling against a passive t-adversary. We generalize a recently introduced notion of assisted common information of a pair of correlated sources to that of K sources and define a family of monotone rate regions indexed by K. This allows for a simple characterization of all t-private distributions that can be statistically securely sampled without any auxiliary setup of pre-shared noisy correlations. We also give a new monotone called the residual total correlation that admits a simple operational interpretation. Interestingly, for sampling with non-trivial setups (K > 2) in the public discussion model, our definition of a monotone region differs from the one by Prabhakaran and Prabhakaran (ITW 2012).
In literature, different common informations were defined by Gács and Körner, by Wyner, and by Kumar, Li, and Gamal, respectively. In this paper, we define two generalized versions of common informations, named approximate and exact information-correlation functions, by exploiting the conditional maximal correlation as a commonness or privacy measure. These two generalized common informations encompass the notions of Gács-Körner's, Wyner's, and Kumar-Li-Gamal's common informations as special cases. Furthermore, to give operational characterizations of these two generalized common informations, we also study the problems of private sources synthesis and common information extraction, and show that the information-correlation functions are equal to the minimum rates of commonness needed to ensure that some conditional maximal correlation constraints are satisfied for the centralized setting versions of these problems. As a byproduct, the conditional maximal correlation has been studied as well.
In the secure two-party sampling problem, two parties wish to generate outputs with a desired joint distribution via an interactive protocol, while ensuring that neither party learns more than what can be inferred from only their own output. For semi-honest parties and information-theoretic privacy guarantees, it is well-known that if only noiseless communication is available, then only the joint distributions, for which common information equals mutual information, can be securely sampled. We consider the problem where the parties may also interact via a given set of general communication primitives (multi-input/output channels). Our feasibility characterization of this problem can be stated as a zero-one law: primitives are either complete (enabling the secure sampling of any distribution) or useless (only enabling the secure sampling of trivial distributions). Our characterization of the complete primitives also extends to the more general class of secure two-party computation problems.
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,…αn\alpha_{1},\ldots\alpha_{n}α1​,…αn​andβ1,…,βn\beta_{1},\ldots,\beta_{n}β1​,…,βn​of random variables, where pairs(α1,β1),…,(αn,βn)(\alpha_{1},\beta_{1}),\ldots, (\alpha_{n},\beta_{n})(α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)(\alpha_{i},\beta_{i})(αi​,βi​)is a block matrix.