pith. sign in

arxiv: cs/0501075 · v3 · submitted 2005-01-25 · 💻 cs.CC · cs.CR

Simple extractors via constructions of cryptographic pseudo-random generators

classification 💻 cs.CC cs.CR
keywords extractorsconstructionsgeneratorslambdapseudo-randomapproachlengthoutput
0
0 comments X
read the original 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 and 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}$.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.