## 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 [5], 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 [1], we give a transformation converting our computational non-malleable 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 [18].

Original language | English (US) |
---|---|

Title of host publication | Advances in Cryptology – EUROCRYPT 2020 - 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, Proceedings |

Editors | Anne Canteaut, Yuval Ishai |

Publisher | Springer |

Pages | 373-402 |

Number of pages | 30 |

ISBN (Print) | 9783030457204 |

DOIs | |

State | Published - 2020 |

Event | 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 - Zagreb, Croatia Duration: May 10 2020 → May 14 2020 |

### Publication series

Name | Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) |
---|---|

Volume | 12105 LNCS |

ISSN (Print) | 0302-9743 |

ISSN (Electronic) | 1611-3349 |

### Conference

Conference | 39th Annual International Conference on the Theory and Applications of Cryptographic Techniques, EUROCRYPT 2020 |
---|---|

Country/Territory | Croatia |

City | Zagreb |

Period | 5/10/20 → 5/14/20 |

## ASJC Scopus subject areas

- Theoretical Computer Science
- General Computer Science