Improved randomness extraction from two independent sources

Yevgeniy Dodis, Ariel Elbaz, Roberto Oliveira, Ran Raz

Research output: Chapter in Book/Report/Conference proceedingChapter

42 Scopus citations

Abstract

Given two independent weak random sources X, Y, with the same length l and min-entropies bx,by whose sum is greater than l + Ω(polylog(l/ε)), we construct a deterministic two-source extractor (aka "blender") that extracts max(bx,by) + (bx + by - l - 41og(1/ε)) bits which are ε-close to uniform. In contrast, best previously published construction [4] extracted at most 1/2(bx+by-l-2 log(1/ε)) bits. Our main technical tool is a construction of a strong two-source extractor that extracts (bx+by-l)-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.

Original languageEnglish (US)
Title of host publicationLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
EditorsKlaus Jansen, Sanjeev Khanna, Jose D. P. Rolim, Dana Ron
PublisherSpringer Verlag
Pages334-344
Number of pages11
ISBN (Print)3540228942, 9783540228943
DOIs
StatePublished - 2004
Externally publishedYes

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume3122
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'Improved randomness extraction from two independent sources'. Together they form a unique fingerprint.

  • Cite this

    Dodis, Y., Elbaz, A., Oliveira, R., & Raz, R. (2004). Improved randomness extraction from two independent sources. In K. Jansen, S. Khanna, J. D. P. Rolim, & D. Ron (Eds.), Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics) (pp. 334-344). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 3122). Springer Verlag. https://doi.org/10.1007/978-3-540-27821-4_30