__
TR05-071 | 29th June 2005 00:00
__

#### Simple extractors via constructions of cryptographic pseudo-random generators

**Abstract:**
Trevisan has shown that constructions of pseudo-random generators from

hard functions (the Nisan-Wigderson approach) also produce extractors.

We show that constructions of pseudo-random generators from one-way permutations

(the Blum-Micali-Yao approach) can be used for building extractors as well.

Using this new technique we build extractors that do not use designs or polynomial-based error-correcting codes and that are very simple and efficient. For example, one extractor produces each output bit separately

in $O(\log^2 n)$ time.

These extractors work for weak sources with min entropy $\lambda n$, for arbitrary constant $\lambda > 0$, have

seed length $O(\log^2 n)$, and their output

length is $\approx n^{\lambda/3}$.