Assisted Common Information with an Application to Secure Two-Party Sampling
Secure multi-party computation is a central problem in modern cryptography. An important sub-class of this problem 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, the authors present an upper bound on how efficiently a given set up can be used to produce samples from a desired distribution.