Paper 2021/1336

Improved Computational Extractors and their Applications

Dakshita Khurana, University of Illinois Urbana-Champaign
Akshayaram Srinivasan, Tata Institute of Fundamental Research

Recent exciting breakthroughs, starting with the work of Chattopadhyay and Zuckerman (STOC 2016) have achieved the first two-source extractors that operate in the low min-entropy regime. Unfortunately, these constructions suffer from non-negligible error, and reducing the error to negligible remains an important open problem. In recent work, Garg, Kalai, and Khurana (GKK, Eurocrypt 2020) investigated a meaningful relaxation of this problem to the computational setting, in the presence of a common random string (CRS). In this relaxed model, their work built explicit two-source extractors for a restricted class of unbalanced sources with min-entropy $n^{\gamma}$ (for some constant $\gamma$) and negligible error, under the sub-exponential DDH assumption. In this work, we investigate whether computational extractors in the CRS model be applied to more challenging environments. Specifically, we study network extractor protocols (Kalai et al., FOCS 2008) and extractors for adversarial sources (Chattopadhyay et al., STOC 2020) in the CRS model. We observe that these settings require extractors that work well for balanced sources, making the GKK results inapplicable. We remedy this situation by obtaining the following results, all of which are in the CRS model and assume the sub-exponential hardness of DDH. - We obtain ``optimal'' computational two-source and non-malleable extractors for balanced sources: requiring both sources to have only poly-logarithmic min-entropy, and achieving negligible error. To obtain this result, we perform a tighter and arguably simpler analysis of the GKK extractor. - We obtain a single-round network extractor protocol for poly-logarithmic min-entropy sources that tolerates an optimal number of adversarial corruptions. Prior work in the information-theoretic setting required sources with high min-entropy rates, and in the computational setting had round complexity that grew with the number of parties, required sources with linear min-entropy, and relied on exponential hardness (albeit without a CRS). - We obtain an ``optimal'' {\em adversarial source extractor} for poly-logarithmic min-entropy sources, where the number of honest sources is only 2 and each corrupted source can depend on either one of the honest sources. Prior work in the information-theoretic setting had to assume a large number of honest sources.

Note: Full version of the CRYPTO paper.

Available format(s)
Publication info
A major revision of an IACR publication in CRYPTO 2021
Contact author(s)
dakshita @ illinois edu
akshayaram @ berkeley edu
2022-07-07: revised
2021-10-05: received
See all versions
Short URL
Creative Commons Attribution


      author = {Dakshita Khurana and Akshayaram Srinivasan},
      title = {Improved Computational Extractors and their Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1336},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.