ECCC-Report TR05-071https://eccc.weizmann.ac.il/report/2005/071Comments and Revisions published for TR05-071en-usWed, 13 Jul 2005 10:22:58 +0300
Paper TR05-071
| Simple extractors via constructions of cryptographic pseudo-random generators |
Marius Zimand
https://eccc.weizmann.ac.il/report/2005/071Trevisan 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}$.
Wed, 13 Jul 2005 10:22:58 +0300https://eccc.weizmann.ac.il/report/2005/071