Quantum Computation and Information Seminar 

21/07/2010, 16:15 — 17:15 — Room P4.35, Mathematics Building
Jan Bouda, Masaryk University, Brno

Randomness Extractors

The main problem of many practical random number generators is that they produce non-uniform, i.e. biased, output. Moreover, the actual probability distribution may be not fixed and can be (in a limited way) controlled by an adversary. The main goal of randomness extractors is to postprocess the output of an extractor in such a way that the extractor output is (almost) uniformly distributed. A dual siuation is when the adversary does not control the probability distribution of the random number generator, but can learn some information (fixed number of bits) about the bit sequence output by the generator. It is easy to show that such situation is equivalent to modification of the probability distribution and extractors are able to annihilate adversary's knowledge, i.e. to produce output adversary has (almost) no information about. This is also tightly related to the problem of privacy amplification, where two communicating participants want to eliminate adversary's (limited) knowledge of a commonly shared bit string using public discussion the adversary can eavesdrop.