International Association for Cryptologic Research

International Association
for Cryptologic Research


Extractors: Low Entropy Requirements Colliding With Non-Malleability

Divesh Aggarwal , National University of Singapore
Eldon Chung , Centre for Quantum Technologies (NUS)
Maciej Obremski , National University of Singapore
DOI: 10.1007/978-3-031-38545-2_19 (login may be required)
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2023
Abstract: 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 two- source 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 non- malleable 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.
  title={Extractors: Low Entropy Requirements Colliding With Non-Malleability},
  author={Divesh Aggarwal and Eldon Chung and Maciej Obremski},