Yaoyun Shi, University of Michigan
How can one be certain that the output of an alleged random
number generator is indeed random? This question is important not
only for the efficiency and the security of information
processing, but also for understanding how intrinsically
unpredictable events are possible in Nature. Practical random
number generators have often been found to be insecure. All
existing theoretical solutions require a certain form of
independence among two or more sources of randomness, a condition
impossible to test and difficult to guarantee.
In this talk, I will show how this fundamental limit can be
circumvented by extractors that base security on the validity of
physical laws. In conjunction with the recent work of Miller and
Shi (arXiv:1402.0489), our "physical extractor" uses just a
single and arbitrarily weak source, produces an arbitrarily long
and near-uniform output, secure against all-powerful quantum
adversaries, tolerating a constant level of implementation
imprecision, with a near-optimal error. Our method enables
practical provably secure random number generation with minimal
assumptions. It also implies that unless the world is
deterministic, we can experimentally create arbitrarily many,
inherently random events and be confident of their
unpredictability. I will conclude with several major open
problems on this new paradigm of randomness extraction.
Joint work with Kai-Min Chung and Xiaodi Wu (arXiv:1402.4797).
About the speaker: Yaoyun Shi received his Bachelor's degree from
Beijing University in 1997 and his PhD from Princeton University
in 2001, both in Computer Science. He was a postdoc at the
Institute of Quantum Information at Caltech and is currently an
Associate Professor at the University of Michigan, Ann Arbor. His
research focuses on the theory of quantum information processing.qnc