Assisted Common Information with Applications to Secure Two-Party Computation

Details Assisted Common Information with Applications to Secure Two-Party Computation Assisted Common Information with Applications to Secure Two-Party Computation

2010-02-09

arxiv.org/abs/1002.1916v1

Computer Science

Information Theory

submitted to IEEE International Symposium on Information Theory 2010

Scientific paper

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.

Affiliated with

Also associated with

No associations

Rating

Assisted Common Information with Applications to Secure Two-Party Computation does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Assisted Common Information with Applications to Secure Two-Party Computation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Assisted Common Information with Applications to Secure Two-Party Computation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-125083