On extracting private randomness over a public channel

We introduce strong blenders. A strong blender BLE(· ·) uses weak sources X, Y to produce BLE(X, Y) that is statistically random even if one is given Y. Strong blenders generalize strong extractors [15] and extractors from two weak random sources [25, 6]. We show that non-constructive strong blenders can extract all the randomness from X, as long as Y has logarithmic min-entropy. We also give explicit strong blenders which work provided the sum of the min-entropies of X and Y is at least their block length. Finally, we show that strong blenders have applications to cryptographic systems for parties that have independent weak sources of randomness. In particular, we extend the results of Maurer and Wolf [12] and show that parties that are not able to sample even a single truly random bit can still perform privacy amplification over an adversarially controlled channel.