On extracting private randomness over a public channel

Yevgeniy Dodis, Roberto Oliveira

Research output: Contribution to journalArticlepeer-review

Abstract

We introduce strong blenders. A strong blender BLE(· ·) uses weak sources X, Y to produce BLE(X, Y) that is statistically random even if one is given Y. Strong blenders generalize strong extractors [15] and extractors from two weak random sources [25, 6]. We show that non-constructive strong blenders can extract all the randomness from X, as long as Y has logarithmic min-entropy. We also give explicit strong blenders which work provided the sum of the min-entropies of X and Y is at least their block length. Finally, we show that strong blenders have applications to cryptographic systems for parties that have independent weak sources of randomness. In particular, we extend the results of Maurer and Wolf [12] and show that parties that are not able to sample even a single truly random bit can still perform privacy amplification over an adversarially controlled channel.

Original languageEnglish (US)
Pages (from-to)252-263
Number of pages12
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume2764
StatePublished - 2003

ASJC Scopus subject areas

  • Theoretical Computer Science
  • Computer Science(all)

Fingerprint Dive into the research topics of 'On extracting private randomness over a public channel'. Together they form a unique fingerprint.

Cite this