TY - GEN

T1 - Non-malleable extractors - New tools and improved constructions

AU - Cohen, Gil

N1 - Publisher Copyright:
© Gil Cohen.

PY - 2016/5/1

Y1 - 2016/5/1

N2 - A non-malleable extractor is a seeded extractor with a very strong guarantee - The output of a non-malleable 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 non-malleable extractors: We construct a non-malleable extractor with seed-length O(log n · log log n) that works for entropy (log n). This improves upon a recent exciting construction by Chattopadhyay, Goyal, and Li (STOC'16) that has seed length O(log2 n) and requires entropy (log2 n). Secondly, we construct a non-malleable extractor with optimal seed length O(log n) for entropy n/polylog n. Prior to this construction, non-malleable extractors with a logarithmic seed length, due to Li (FOCS'12), required entropy 0.49n. Even non-malleable 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 non-malleable extractor in a black-box manner. One such tool is an algorithm that reduces the entropy requirement of a non-malleable extractor at the expense of a slightly longer seed. A second algorithm increases the output length of a non-malleable extractor from constant to linear in the entropy of the source. We also devise an algorithm that transforms a non-malleable extractor to the so-called t-non-malleable extractor for any desired t. Besides being useful building blocks for our constructions, we consider these modular tools to be of independent interest.

AB - A non-malleable extractor is a seeded extractor with a very strong guarantee - The output of a non-malleable 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 non-malleable extractors: We construct a non-malleable extractor with seed-length O(log n · log log n) that works for entropy (log n). This improves upon a recent exciting construction by Chattopadhyay, Goyal, and Li (STOC'16) that has seed length O(log2 n) and requires entropy (log2 n). Secondly, we construct a non-malleable extractor with optimal seed length O(log n) for entropy n/polylog n. Prior to this construction, non-malleable extractors with a logarithmic seed length, due to Li (FOCS'12), required entropy 0.49n. Even non-malleable 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 non-malleable extractor in a black-box manner. One such tool is an algorithm that reduces the entropy requirement of a non-malleable extractor at the expense of a slightly longer seed. A second algorithm increases the output length of a non-malleable extractor from constant to linear in the entropy of the source. We also devise an algorithm that transforms a non-malleable extractor to the so-called t-non-malleable extractor for any desired t. Besides being useful building blocks for our constructions, we consider these modular tools to be of independent interest.

KW - Explicit constructions

KW - Extractors

KW - Non-malleable

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

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

U2 - 10.4230/LIPIcs.CCC.2016.8

DO - 10.4230/LIPIcs.CCC.2016.8

M3 - Conference contribution

AN - SCOPUS:84973322934

T3 - Leibniz International Proceedings in Informatics, LIPIcs

SP - 8:1-8:29

BT - 31st Conference on Computational Complexity, CCC 2016

A2 - Raz, Ran

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - 31st Conference on Computational Complexity, CCC 2016

Y2 - 29 May 2016 through 1 June 2016

ER -