Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Paper:

TR05-071 | 29th June 2005 00:00

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

TR05-071
Authors: Marius Zimand
Publication: 13th July 2005 10:22
Keywords:

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}$.

ISSN 1433-8092 | Imprint