How can two parties jointly sample from a source of correlated randomness (X,Y), say two hands of cards in a poker game, without leaking any extra information? This secure sampling question is strongly motivated by the design of efficient protocols for secure computation, allowing the two parties to compute a function of their secret inputs without revealing their inputs to each other.
While there has been major progress on securely sampling some useful correlations, others seem much more costly to generate. This motivates the study of efficient techniques for securely converting copies of a given source correlation into copies of a given target correlation.
This talk will discuss a systematic study of such secure conversion protocols that involve only a single message. We present a general rejection-sampling based technique for designing such protocols, and apply them towards improving the communication complexity of distributed symmetric cryptography. On the negative side, we show lower bounds on the communication complexity for such conversions, matching our positive results up to small constant factors.
