Extracting Correlations

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 = Omega(n) instances using O(n) bits of communication, even when t = Omega(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 side-channel 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.