Computational Extractors with Negligible Error in the CRS Model

Ankit Garg; Yael Tauman Kalai; Dakshita Khurana

Paper 2019/1116

Computational Extractors with Negligible Error in the CRS Model

Ankit Garg, Yael Tauman Kalai, and Dakshita Khurana

Abstract

In recent years, there has been exciting progress on building two-source extractors for sources with low min-entropy. Unfortunately, all known explicit constructions of two-source extractors in the low entropy regime suffer from non-negligible error, and building such extractors with negligible error remains an open problem. We investigate this problem in the computational setting, and obtain the following results. We construct an explicit 2-source extractor, and even an explicit non-malleable extractor, with negligible error, for sources with low min-entropy, under computational assumptions in the Common Random String (CRS) model. More specifically, we assume that a CRS is generated once and for all, and allow the min-entropy sources to depend on the CRS. We obtain our constructions by using the following transformations. 1. Building on the technique of [BHK11], we show a general transformation for converting any computational 2-source extractor (in the CRS model) into a computational non-malleable extractor (in the CRS model), for sources with similar min-entropy. We emphasize that the resulting computational non-malleable extractor is resilient to arbitrarily many tampering attacks (a property that is impossible to achieve information theoretically). This may be of independent interest. This transformation uses cryptography, and relies on the sub-exponential hardness of the Decisional Diffie Hellman (DDH) assumption. 2. Next, using the blueprint of [BACDLT17], we give a transformation converting our computational non-malleable seeded extractor (in the CRS model) into a computational 2-source extractor for sources with low min-entropy (in the CRS model). Our 2-source extractor works for unbalanced sources: specifically, we require one of the sources to be larger than a specific polynomial in the other. This transformation does not incur any additional assumptions. Our analysis makes a novel use of the leakage lemma of Gentry and Wichs [GW11].

Note: Full version of Eurocrypt 2020 paper titled "Low Error Efficient Computational Extractors in the CRS Model".

Metadata

Available format(s): PDF
Category: Foundations
Publication info: A major revision of an IACR publication in EUROCRYPT 2020
Keywords: computational extractors two source non-malleable
Contact author(s): dakshita @ illinois edu
History: 2020-05-13: last of 2 revisions; 2019-10-01: received; See all versions
Short URL: https://ia.cr/2019/1116
License: CC BY

BibTeX

@misc{cryptoeprint:2019/1116,
      author = {Ankit Garg and Yael Tauman Kalai and Dakshita Khurana},
      title = {Computational Extractors with Negligible Error in the CRS Model},
      howpublished = {Cryptology ePrint Archive, Paper 2019/1116},
      year = {2019},
      note = {\url{https://eprint.iacr.org/2019/1116}},
      url = {https://eprint.iacr.org/2019/1116}
}