**Extractors: Low Entropy Requirements Colliding With Non-Malleability**

*Eldon Chung and Maciej Obremski and Divesh Aggarwal*

**Abstract: **The known constructions of negligible error (non-malleable) two-source extractors can be broadly classified in three categories:

(1) Constructions where one source has min-entropy rate about $1/2$, the other source can have small min-entropy rate, but the extractor doesn't guarantee non-malleability.

(2) Constructions where one source is uniform, and the other can have small min-entropy rate, and the extractor guarantees non-malleability when the uniform source is tampered.

(3) Constructions where both sources have entropy rate very close to $1$ and the extractor guarantees non-malleability against the tampering of both sources.

We introduce a new notion of collision resistant extractors and in using it we obtain a strong two source non-malleable extractor where we require the first source to have $0.8$ entropy rate and the other source can have min-entropy polylogarithmic in the length of the source.

We show how the above extractor can be applied to obtain a non-malleable extractor with output rate $\frac 1 2$, which is optimal. We also show how, by using our extractor and extending the known protocol, one can obtain a privacy amplification secure against memory tampering where the size of the secret output is almost optimal.

**Category / Keywords: **foundations / pseudo-randomness

**Date: **received 7 Nov 2021

**Contact author: **echung math at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20211108:135740 (All versions of this report)

**Short URL: **ia.cr/2021/1480

[ Cryptology ePrint archive ]