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 general transformation converting any 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). This transformation does not incur any additional assumptions. Our analysis makes a novel use of the leakage lemma of Gentry and Wichs [GW11].
Category / Keywords: foundations / computational extractors, two source, non-malleable Date: received 29 Sep 2019 Contact author: garga at microsoft com,yael@microsoft com,dakshita@illinois edu Available format(s): PDF | BibTeX Citation Version: 20191001:151050 (All versions of this report) Short URL: ia.cr/2019/1116