Physical Randomness Extractors

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 security and the efficiency of modern day information processing, but also for understanding how fundamentally unpredictable events are possible in the physical world. The mathematical theory of randomness extraction from weak randomness sources shows that such certainty is possible only when two or more *independent* sources are available. However, the independence requirement seems hard to enforce or even just to verify.

To circumvent this fundamental and hard-to-enforce limit, we propose a framework of extracting randomness from physical systems, and base the security on the validity of physical theories –we envision a scenario in which in addition to a weak random source, we have access to (multiple, spatially separated, untrusted) physical devices that may have been prepared by the adversary but are nevertheless constrained by quantum mechanics and special relativity. We require that, when the extraction procedure succeeds, the output randomness is close to uniform against any quantum adversary. We call such extraction procedure a *physical randomness extractor*.

We construct the first physical randomness extractor for arbitrary min-entropy sources. Additionally, our extractor enjoys the desirable properties of being efficient and robustness. In particular, one instantiation of our extractor produces arbitrarily long uniform bits against any quantum adversary for an arbitrary min-entropy source (measured against the devices), making use of a constant number of devices and running in optimal time. Our extractor is robust in the sense that it tolerates a constant level of implementation imprecision of the devices.

Our result enables practical and provably secure randomness generation with a minimal assumption on the randomness source and the generating devices. It also implies that unless the world is deterministic, we can experimentally create inherently random events and be confident of its unpredictability.

This is joint work with Kai-Min Chung and Yaoyun Shi
Xiaodi Wu is currently a Simons research fellow at the Simons Institute for the theory of computing, UC Berkeley. He is also a postdoctoral associate at MIT. He obtained his Ph.D. degree in computer science from University of Michigan, Ann Arbor in 2013. Prior to that, he obtained his B.S. degree in mathematics and physics from Tsinghua University in 2008. He mainly works on quantum computation and information, and occasionally thinks about optimization and general complexity problems