| Abstract | 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 N and seed length d=O(logn)+O(log(1/N)loglog(1/N)), that supports min-entropy k=I(c)(d) and outputs I(c)(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 I(c)(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/N)2Oaloglog(1/N), and only give two round privacy amplification protocols with optimal entropy loss for security parameter up to k/2O(alogk). (2) An explicit non-malleable two-source extractor for min entropy k a (1aI)n, some constant I\textbackslashtextgreater0, that outputs I(c)(k) bits with error 2aI(c)(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 I(c)(1/logn). This exponentially improves previous constructions, all of which only achieve rate naI(c)(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(alogn), which gives a Ramsey graph with K=(logN)2O(alogloglogN). 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 N is log(1/N)poly loglog(1/N) and the two-source extractor requires min-entropy logn poly loglogn. |
Improved Non-malleable Extractors, Non-malleable Codes and Independent Source Extractors