No Deterministic Extraction from Santha-Vazirani Sources – A Simple Proof

In my last post I promised a simple proof that there are no deterministic extractors for SV sources. The proof is due to Salil Vadhan, Avi Wigderson and myself and its technique has been used to obtain impossibility results on doing cryptography with SV sources. We show that even more restricted classes of sources are not amenable to deterministic extraction:

Definition For , a source of length is -imbalanced if for every , .

A source which is -imbalanced is an SV source with bias in a very strong sense: every bit has bias at most not only conditioned on the first bits  but also conditioned on all other bits . The following lemma shows that there are no deterministic extractors for imbalanced sources and therefore also for SV-sources.

Lemma For every function and every , there is a -imbalanced source such that has bias at least .

Proof There exists a set of size exactly such that is constant on , say taking value . Consider the source that with probability outputs a uniformly selected element of and with probability outputs a uniformly selected element of . By construction, with probability at least , so it has bias at least . Moreover, assigns every  string in probability mass either or .  Thus is -imbalanced.