Description
Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions
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 Nature. The mathematical theory of randomness extraction from weak randomness sources requires that two or more *independent* sources are available.
To circumvent this fundamental and hard-to-enforce limit, here we propose a framework of extracting randomness from physical systems following the emerging paradigm of untrusted-device quantum cryptography, with security based on the validity of physical theories. We construct the first such extractor and prove its quantum security under a minimal set of assumptions: it uses just one and arbitrarily weak classical source and interacts classically with a set of non-communicating quantum devices whose inner-workings are unknown or may even be malicious. Our construction can reach close to optimal security parameter, and is efficient and tolerates a constant level of implementation imprecision for important cases. Thus our result enables practical and provably secure randomness generation without the currently required independence assumptions on the randomness sources or the trust on quantum devices. Furthermore, it implies that unless the world is deterministic, we can experimentally create inherently random events and be confident of their unpredictability. This provides a practical and strongest known method for mitigating the Freedom-of-Choice loophole in experimental verifications of quantum non-locality.
A main technical contribution is our "Equivalence Lemma'', which states that the performance parameters of a untrusted-device randomness generating protocol remain unchanged when its globally uniformly random input is replaced by an input uniform only to the devices. This fundamental and powerful principle for the secure composition of untrusted-device protocols has found several other important applications.