Simple extractors via constructions of cryptographic pseudo-random generators
| dc.creator | Zimand, Marius | |
| dc.date | 2005-01-25 | |
| dc.date | 2005-05-09 | |
| dc.date.accessioned | 2026-07-07T03:22:24Z | |
| dc.date.available | 2026-07-07T03:22:24Z | |
| dc.description | 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 $λn$, for arbitrary constant $λ> 0$, have seed length $O(\log^2 n)$, and their output length is $\approx n^{λ/3}$. | |
| dc.description | 21 pages, an extended abstract will appear in Proc. ICALP 2005; small corrections, some comments and references added | |
| dc.identifier | https://arxiv.org/abs/cs/0501075 | |
| dc.identifier | http://arxiv.org/abs/cs/0501075 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/32581 | |
| dc.subject | Computational Complexity | |
| dc.subject | Cryptography and Security | |
| dc.title | Simple extractors via constructions of cryptographic pseudo-random generators | |
| dc.type | text |