Extractors Using Hardness Amplification

Zimand [24] presented simple constructions of locally computable strong extractors whose analysis relies on the

direct product theorem

for one-way functions and on the

Blum-Micali-Yao

generator. For

N

-bit sources of entropy

γN

, his extractor has seed

O

(log

2

N

) and extracts

N

γ

/3

random bits.

We show that his construction can be analyzed based solely on the direct product theorem for general functions. Using the direct product theorem of Impagliazzo et al. [6], we show that Zimand’s construction can extract

$\tilde \Omega_\gamma (N^{1/3}) $

random bits. (As in Zimand’s construction, the seed length is

O

(log

2

N

) bits.)

We also show that a simplified construction can be analyzed based solely on the XOR lemma. Using Levin’s proof of the XOR lemma [8], we provide an alternative simpler construction of a locally computable extractor with seed length

O

(log

2

N

) and output length

$\tilde \Omega_\gamma (N^{1/3})$

.

Finally, we show that the

derandomized direct product theorem

of Impagliazzo and Wigderson [7] can be used to derive a locally computable extractor construction with

O

(log

N

) seed length and

$\tilde \Omega (N^{1/5})$

output length. Zimand describes a construction with

O

(log

N

) seed length and

$O(2^{\sqrt{\log N}})$

output length.