Stronger Notions and New Constructions for Non-malleable Extractors and Non-malleable Codes

Randomness extractors and error correcting codes are fundamental objects in computer science. Recently, there have been several natural generalizations of these objects, in the context and study of tamper resilient cryptography. These are \emph{seeded non-malleable extractors}, introduced by Dodis and Wichs \cite{DW09}; \emph{seedless non-malleable extractors}, introduced by Cheraghchi and Guruswami \cite{CG14b}; and \emph{non-malleable codes}, introduced by Dziembowski, Pietrzak and Wichs \cite{DPW10}. Besides being interesting on their own, they also have important applications in cryptography. For example, seeded non-malleable extractors are closely related to privacy amplification with an active adversary, non-malleable codes are related to non-malleable secret sharing, and seedless non-malleable extractors provide a universal way to construct explicit non-malleable codes. However, explicit constructions of non-malleable extractors appear to be hard, and the known constructions are far behind their non-tampered counterparts.

In this paper we make progress towards obtaining better constructions of these primitives. Our contributions are as follows.

1) We construct an explicit seeded non-malleable extractor for min-entropy k >= log 2 n. This dramatically improves all previous results and gives a simpler 2-round privacy amplification protocol with optimal entropy loss, matching the best known result in \cite{Li15b}. The best known seeded non-malleable extractor previously required min-entropy rate at least 0.49 \cite{Li12b}.
2) We construct the first explicit non-malleable two-source extractor. This settles an open question raised by Cheraghchi and Guruswami \cite{CG14b}.
3) We motivate and initiate the study of two natural generalizations of seedless non-malleable extractors and non-malleable codes, where the sources or the codeword may be tampered many times. This leads to what we call many-many non-malleable codes.

Our constructions are elementary and avoid the heavy combinatorial tools used in prior works. Our techniques have also found applications to problems outside the domain of non-malleable extractors / codes.
Joint work with Eshan Chattopadhyay, and, Xin Li