Simple extractors via constructions of cryptographic pseudo-random generators

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

2005-01-25

arxiv.org/abs/cs/0501075v3

Computer Science

Computational Complexity

21 pages, an extended abstract will appear in Proc. ICALP 2005; small corrections, some comments and references added

Scientific paper

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

Affiliated with

Also associated with

No associations

Rating

Simple extractors via constructions of cryptographic pseudo-random generators does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Simple extractors via constructions of cryptographic pseudo-random generators, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Simple extractors via constructions of cryptographic pseudo-random generators will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-513161