Extracting randomness from multiple independent sources

Chia Jung Lee*, Chi Jen Lu, Shi-Chun Tsai, Wen-Guey Tzeng

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

16 Scopus citations

Abstract

We study the problem of deterministically extracting almost perfect random bits from multiple weakly random sources that are mutually independent. With two independent sources, we have an explicit extractor which can extract a number of random bits that matches the best construction currently known, via the generalized leftover hash lemma. We also extend our construction to extract randomness from more independent sources. One nice feature is that the extractor still works even with all but one source exposed. Finally, we apply our extractor for a cryptographic task in which a group of parties wants to agree on a secret key for group communication over an insecure channel, without using ideal local randomness.

Original languageEnglish
Pages (from-to)2224-2227
Number of pages4
JournalIEEE Transactions on Information Theory
Volume51
Issue number6
DOIs
StatePublished - 1 Jun 2005

Keywords

  • Deterministic extractor
  • Leftover hash lemma
  • Multi-sources-extractor
  • Two-sources extractor

Fingerprint Dive into the research topics of 'Extracting randomness from multiple independent sources'. Together they form a unique fingerprint.

Cite this