True Randomness: Its Origin and Expansion

How can we produce randomness of almost perfect quality, in large quantities, and under minimal assumptions? This question is fundamental not only to modern day information processing but also to physics. Yet a satisfactory answer is still elusive to both the practice and the theory of randomness extraction. Here we propose a solution through a new paradigm of extracting randomness from physical systems and basing security on the validity of physical theories, such as quantum mechanics and special relativity. We construct such "physical extractors" extracting from non-interacting quantum devices, whose inner-workings may be imperfect or even malicious. Composing our extractors gives a protocol that starts with a single and arbitrarily weak source of a fixed length and produces an arbitrarily long random output of close to optimal quality, and provable security against all-powerful quantum adversaries. Several desirable features of our protocols, including tolerance of device imprecisions, enable their implementations with the current quantum technology. Our work also implies that unless the world is deterministic, we can experimentally create inherently random events and be confident of their unpredictability. It thus provides a practical and strongest method known for mitigating the "freedom of choice" loophole for experimentally validating quantum mechanics. Based on joint works with Carl A. Miller (arXiv:1402.0489), Kai-Min Chung and Xiaodi Wu (arXiv:1402.4797).