Cohen, Gil
NonMalleable Extractors  New Tools and Improved Constructions
Abstract
A nonmalleable extractor is a seeded extractor with a very strong guarantee  the output of a nonmalleable extractor obtained using a typical seed is close to uniform even conditioned on the output obtained using any other seed. The first contribution of this paper consists of two new and improved constructions of nonmalleable extractors:
 We construct a nonmalleable extractor with seedlength O(log(n) * log(log(n))) that works for entropy Omega(log(n)). This improves upon a recent exciting construction by Chattopadhyay, Goyal, and Li (STOC'16) that has seed length O(log^{2}(n)) and requires entropy Omega(log^{2}(n)).
 Secondly, we construct a nonmalleable extractor with optimal seed length O(log(n)) for entropy n/log^{O(1)}(n). Prior to this construction, nonmalleable extractors with a logarithmic seed length, due to Li (FOCS'12), required entropy 0.49*n. Even nonmalleable condensers with seed length O(log(n)), by Li (STOC'12), could only support linear entropy.
We further devise several tools for enhancing a given nonmalleable extractor in a blackbox manner. One such tool is an algorithm that reduces the entropy requirement of a nonmalleable extractor at the expense of a slightly longer seed. A second algorithm increases the output length of a nonmalleable extractor from constant to linear in the entropy of the source. We also devise an algorithm that transforms a nonmalleable extractor to the socalled tnonmalleable extractor for any desired t. Besides being useful building blocks for our constructions, we consider these modular tools to be of independent interest.
BibTeX  Entry
@InProceedings{cohen:LIPIcs:2016:5834,
author = {Gil Cohen},
title = {{NonMalleable Extractors  New Tools and Improved Constructions}},
booktitle = {31st Conference on Computational Complexity (CCC 2016)},
pages = {8:18:29},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770088},
ISSN = {18688969},
year = {2016},
volume = {50},
editor = {Ran Raz},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/5834},
URN = {urn:nbn:de:0030drops58348},
doi = {10.4230/LIPIcs.CCC.2016.8},
annote = {Keywords: extractors, nonmalleable, explicit constructions}
}
2016
Keywords: 

extractors, nonmalleable, explicit constructions 
Seminar: 

31st Conference on Computational Complexity (CCC 2016)

Issue date: 

2016 
Date of publication: 

2016 