Extractors: Low Entropy Requirements Colliding with Non-malleability

Two-source extractors are deterministic functions that, given two independent weak sources of randomness, output a (close to) uniformly random string of bits. Cheraghchi and Guruswami (TCC 2015) introduced twosource non-malleable extractors that combine the properties of randomness extraction with tamper resilience. Two-source non-malleable extractors have since then attracted a lot of attention, and have very quickly become fundamental objects in cryptosystems involving communication channels that cannot be fully trusted. Various applications of two-source non-malleable extractors include in particular non-malleable codes, non-malleable commitments, non-malleable secret sharing, network extraction, and privacy amplification with tamperable memory.

The best known constructions of two-source non-malleable extractors are due to Chattopadhyay, Goyal, and Li (STOC 2016), Li (STOC 2017), and Li (CCC 2019). All of these constructions require both sources to have min-entropy at least 0.99n, where n is the bit-length of each source.

In this work, we introduce collision-resistant randomness extractors. This allows us to design a compiler that, given a two-source non-malleable extractor, and a collision-resistant extractor, outputs a two-source nonmalleable extractor that inherits the non-malleability property from the non-malleable extractor, and the entropy requirement from the collision-resistant extractor. Nested application of this compiler leads to a dramatic improvement of the state-of-the-art mentioned above. We obtain a construction of a two-source non-malleable extractor where one source is required to have min-entropy greater than 0.8n, and the other source is required to have only polylog(n) min-entropy. Moreover, the other parameters of our construction, i.e., the output length, and the error remain comparable to prior constructions.