Extracting pure randomness from multiple impure sources of randomness
Speaker: Anup Rao , UT Austin
Date: March 13 2007
Time: 4:15PM to 5:30PM
Location: 32-G449 (Patil/Kiva)
Host: Madhu Sudan, MIT
Contact: Alexandr Andoni, andoni@mit.edu
Relevant URL: http://theory.lcs.mit.edu/theory-seminars/calendar.htmlIt is a widely acknowledged that the physical universe is unpredictable. In computer science this unpredictability, modeled as randomness, turns out to be an enabling feature in algorithm design, cryptography and distributed computing.
Unfortunately, there is a gap between the physical assumption of unpredictability and the computer science model of pure randomness. Physical sources don't yield pure independent random bits, instead they produce "impure" bits, with some entropy.
A randomness extractor is an algorithm that attempts to convert unpredictability into pure randomness either by injecting a few pure random bits (which is good enough for algorithmic usage), or by combining multiple independent sources of impure randomness (which may be the only reasonable way to produce cryptographically strong randomness).
In this talk, we describe work along the second direction above: We show how to extract pure randomness from several independent sources of impure randomness. Specifically, we construct an extractor that can extract from a constant number of independent impure random sources of length n, each of which have min-entropy that is polynomially small in n (say n^delta for some arbitrarily small constant delta).
See other events that are part of Theory Colloquium Spring 2007
See other events happening in March 2007
