Improved randomness extraction from two independent sources
Yevgeniy Dodis, Ariel Elbaz, Roberto I. Oliveira, Ran Raz · 2004
Abstract. Given two independent weak random sources X, Y, with the same length ℓ and min-entropies bX, bY whose sum is greater than ℓ + Ω(polylog(ℓ/ε)), we construct a deterministic two-source extractor (aka “blender”) that extracts max(bX, bY) + (bX + bY − ℓ − 4log(1/ε)) bits which are ε-close to uniform. In contrast, best previously published construction [4] extracted at most 1 (bX + bY − ℓ − 2log(1/ε)) bits. Our 2 main technical tool is a construction of a strong two-source extractor that extracts (bX + bY − ℓ) − 2log(1/ε) bits which are ε-close to being uniform and independent of one of the sources (aka “strong blender”), so that they can later be reused as a seed to a seeded extractor. Our strong two-source extractor construction improves the best previously published construction of such strong blenders [7] by a factor of 2, applies to more sources X and Y, and is considerably simpler than the latter. Our methodology also unifies several of the previous two-source extractor constructions from the literature. 1