Biblio

In this paper we give improved constructions of several central objects in the literature of randomness extraction and tamper-resilient cryptography. Our main results are: (1) An explicit seeded non-malleable extractor with error � and seed length d=O(logn)+O(log(1/�)loglog(1/�)), that supports min-entropy k=Ω(d) and outputs Ω(k) bits. Combined with the protocol by Dodis and Wichs, this gives a two round privacy amplification protocol with optimal entropy loss in the presence of an active adversary, for all security parameters up to Ω(k/logk), where k is the min-entropy of the shared weak random source. Previously, the best known seeded non-malleable extractors require seed length and min-entropy O(logn)+log(1/�)2O�loglog(1/�), and only give two round privacy amplification protocols with optimal entropy loss for security parameter up to k/2O(�logk). (2) An explicit non-malleable two-source extractor for min entropy k � (1��)n, some constant �\textbackslashtextgreater0, that outputs Ω(k) bits with error 2�Ω(n/logn). We further show that we can efficiently uniformly sample from the pre-image of any output of the extractor. Combined with the connection found by Cheraghchi and Guruswami this gives a non-malleable code in the two-split-state model with relative rate Ω(1/logn). This exponentially improves previous constructions, all of which only achieve rate n�Ω(1). (3) Combined with the techniques by Ben-Aroya et. al, our non-malleable extractors give a two-source extractor for min-entropy O(logn loglogn), which also implies a K-Ramsey graph on N vertices with K=(logN)O(logloglogN). Previously the best known two-source extractor by Ben-Aroya et. al requires min-entropy logn 2O(�logn), which gives a Ramsey graph with K=(logN)2O(�logloglogN). We further show a way to reduce the problem of constructing seeded non-malleable extractors to the problem of constructing non-malleable independent source extractors. Using the non-malleable 10-source extractor with optimal error by Chattopadhyay and Zuckerman, we give a 10-source extractor for min-entropy O(logn). Previously the best known extractor for such min-entropy by Cohen and Schulman requires O(loglogn) sources. Independent of our work, Cohen obtained similar results to (1) and the two-source extractor, except the dependence on � is log(1/�)poly loglog(1/�) and the two-source extractor requires min-entropy logn poly loglogn.