Paper 2020/259

Computational and Information-Theoretic Two-Source (Non-Malleable) Extractors

Divesh Aggarwal, Maciej Obremski, João Ribeiro, Mark Simkin, and Luisa Siniscalchi

Abstract

Two-source non-malleable extractors are pseudorandom objects which extract randomness even when an adversary is allowed to learn the behavior of the extractor on tamperings of the input weak sources, and they have found important applications in non-malleable coding and secret sharing. We begin by asking how hard it is to improve upon the best known constructions of such objects (Chattopadhyay, Goyal, Li, STOC 2016, and Li, STOC 2017). We show that even small improvements to these constructions lead to explicit low-error two-source extractors for very low linear min-entropy, a longstanding open problem in pseudorandomness. Given the result above in the information-theoretic setting, we turn to studying two-source non-malleable extractors in the computational setting, namely in the CRS model first considered in (Garg, Kalai, Khurana, Eurocrypt 2020). We enforce that both the sampling process for the input sources and the tampering functions must be efficient, but we do not necessarily put such a constraint on the adversary distinguishing the output of the extractor from uniform. We obtain results about two-source non-malleable extractors in the CRS model under different types of hardness assumptions: - Under standard assumptions, we show that small improvements upon state-of-the-art statistical two-source non-malleable extractors also yield explicit low-error two-source non-malleable extractors in the CRS model for low min-entropy against computationally unbounded distinguishers. Remarkably, all previous results on computational extractors require much stronger assumptions; - Under a quasi-polynomial hardness assumption, we give explicit constructions of low-error two-source non-malleable extractors in the CRS model with much lower min-entropy requirements than their best statistical counterparts, against a computationally bounded distinguisher; - Assuming the existence of nearly optimal collision-resistant hash functions, we give a simple explicit construction of a low-error two-source non-malleable extractors in the CRS model for very low min-entropy, against a computationally unbounded distinguisher.

Note: Superseded by https://eprint.iacr.org/2020/1371, which features modified constructions of non-malleable extractors and a new section on privacy amplification. The original construction in Section 5 of this paper may be of independent interest, and so we have decided to leave it as is.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Preprint. MINOR revision.
Keywords
two-source extractorsnon-malleabilitycomputational extractors
Contact author(s)
dcsdiva @ nus edu sg
obremski math @ gmail com
j lourenco-ribeiro17 @ imperial ac uk
simkin @ cs au dk
lsiniscalchi @ cs au dk
History
2020-11-06: revised
2020-02-25: received
See all versions
Short URL
https://ia.cr/2020/259
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2020/259,
      author = {Divesh Aggarwal and Maciej Obremski and João Ribeiro and Mark Simkin and Luisa Siniscalchi},
      title = {Computational and Information-Theoretic Two-Source (Non-Malleable) Extractors},
      howpublished = {Cryptology ePrint Archive, Paper 2020/259},
      year = {2020},
      note = {\url{https://eprint.iacr.org/2020/259}},
      url = {https://eprint.iacr.org/2020/259}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.