TY - GEN

T1 - Extractors using hardness amplification

AU - De, Anindya

AU - Trevisan, Luca

PY - 2009

Y1 - 2009

N2 - 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(log2 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 Ωγ(N1/3) random bits. (As in Zimand's construction, the seed length is O(log2 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(log2 N) and output length Ωγ(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(logN) seed length and Ω(N1/5) output length. Zimand describes a construction with O(logN) seed length and O(2√log N) output length.

AB - 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(log2 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 Ωγ(N1/3) random bits. (As in Zimand's construction, the seed length is O(log2 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(log2 N) and output length Ωγ(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(logN) seed length and Ω(N1/5) output length. Zimand describes a construction with O(logN) seed length and O(2√log N) output length.

KW - Direct product theorems

KW - Extractors

KW - Hardness amplification

UR - http://www.scopus.com/inward/record.url?scp=70350589607&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=70350589607&partnerID=8YFLogxK

U2 - 10.1007/978-3-642-03685-9_35

DO - 10.1007/978-3-642-03685-9_35

M3 - Conference contribution

AN - SCOPUS:70350589607

SN - 3642036848

SN - 9783642036842

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 462

EP - 475

BT - Approximation, Randomization, and Combinatorial Optimization

T2 - 12th International Workshop on Approximation Algorithms for Combinatorial Optimization Problems, APPROX 2009 and 13th International Workshop on Randomization and Computation, RANDOM 2009

Y2 - 21 August 2009 through 23 August 2009

ER -