Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR05-071 | 29th June 2005 00:00

Simple extractors via constructions of cryptographic pseudo-random generators

RSS-Feed




TR05-071
Authors: Marius Zimand
Publication: 13th July 2005 10:22
Downloads: 3058
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