Paper 2021/1480

Extractors: Low Entropy Requirements Colliding With Non-Malleability

Divesh Aggarwal, National University of Singapore
Eldon Chung, Centre for Quantum Technologies
Maciej Obremski, National University of Singapore
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.99 n$, 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 $\text{polylog} (n)$ min-entropy. Moreover, the other parameters of our construction, i.e., the output length, and the error remain comparable to prior constructions.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
A major revision of an IACR publication in CRYPTO 2023
Keywords
non-malleable extractorsprivacy amplificationextractors
Contact author(s)
divesh @ comp nus edu sg
echung math @ gmail com
cqtmlo @ nus edu sg
History
2023-08-16: revised
2021-11-08: received
See all versions
Short URL
https://ia.cr/2021/1480
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1480,
      author = {Divesh Aggarwal and Eldon Chung and Maciej Obremski},
      title = {Extractors: Low Entropy Requirements Colliding With Non-Malleability},
      howpublished = {Cryptology {ePrint} Archive, Paper 2021/1480},
      year = {2021},
      url = {https://eprint.iacr.org/2021/1480}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.