IEEE International Symposium on Information Theory (ISIT)

Assisted common information

Vinod M. Prabhakaran, Manoj Prabhakaran

Published Jun 1, 2010• 9 citations

Abstract

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.

DOI: 10.1109/isit.2010.5513743

Related papers

Assisted Common Information with Applications to Secure Two-Party Computation

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 [Gacs-Korner, 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.

arXiv:1002.1916Feb 9, 20109 citations

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

Vinod M. Prabhakaran, Manoj Prabhakaran

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

arXiv:1206.1282IEEE Transactions on Information TheoryApr 7, 201439 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.6163IEEE International Symposium on Information Theory (ISIT)Jul 1, 20117 citations

Assisted common information: Further results

Vinod M. Prabhakaran, Manoj Prabhakaran

Abstract—We presented assisted common information as a generalization of Gács-Körner (GK) common information at ISIT 2010. 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. I.

Jan 1, 20117 citations

Extracting Correlations

Yuval Ishai, Eyal Kushilevitz Z, Rafail Ostrovsky +1 more

Motivated by applications in cryptography, we consider a generalization of randomness extraction and the related notion of privacy amplification to the case of two correlated sources. We introduce the notion of correlation extractors, which extract nearly perfect independent instances of a given joint distribution from imperfect, or "leaky," instances of the same distribution. More concretely, suppose that Alice holds a and Bob holds b, where (a, b) are obtained by taking n independent samples from a joint distribution (X, Y) and letting a include all X instances and b include all Y instances. An adversary Eve obtains partial information about (a, b) by choosing a function L with output length t and learning L(a, b). The goal is to design a protocol between Alice and Bob which may use additional fresh randomness, such that for every L as above the following holds. In the end of the interaction, Alice outputs a' and Bob outputs b' such that (a', b') are statistically indistinguishable from m independent instances of (X, Y) even when conditioned on Eve's view, and even when conditioned on the joint view of Eve together with either Alice or Bob. The standard questions of privacy amplification and randomness extraction correspond to the case where X and Y are identical random bits. In this work we address this question for other types of correlations. A central special case is that of OT extractors, which are correlation extractors for the correlation (X, Y) corresponding to the cryptographic primitive of oblivious transfer. Our main result is that for any finite joint distribution (X, Y) there is an explicit correlation extractor which extracts m = ?(n) instances using O(n) bits of communication, even when t = ?(n) bits of information can be leaked to Eve. We present several applications which motivate the concept of correlation extractors and our main result. These include: ? Protecting certain cryptographic protocols against sidechannel attacks. ? A protocol which realizes m instances of oblivious transfer by communicating only O(m) bits. The security of the protocol relies on a number-theoretic intractability assumption. ? A constant-rate unconditionally secure construction of oblivious transfer (for semi-honest parties) from any nontrivial channel. This establishes constant-rate equivalence of any two nontrivial finite channels.

Annual Symposium on Foundations of Computer ScienceOct 1, 200947 citations

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

Ye Wang, Prakash 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, 20140 citations