Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions

Abstract

How to generate provably true randomness with minimal assumptions? This question is important not only for the efficiency and the security of information processing, but also for understanding how extremely unpredictable events are possible in Nature. All current solutions require special structures in the initial source of randomness, or a certain independence relation among two or more sources. Both types of assumptions are impossible to test and difficult to guarantee in practice. Here we show how this fundamental limit can be circumvented by extractors that base security on the validity of physical laws and extract randomness from untrusted quantum devices. In conjunction with the recent work of Miller and Shi (arXiv:1402:0489), our physical randomness extractor uses just a single and general weak source, produces an arbitrarily long and near-uniform output, with a close-to-optimal error, secure against all-powerful quantum adversaries, and tolerating a constant level of implementation imprecision. The source necessarily needs to be unpredictable to the devices, but otherwise can even be known to the adversary. Our central technical contribution, the Equivalence Lemma, provides a general principle for proving composition security of untrusted-device protocols. It implies that unbounded randomness expansion can be achieved simply by cross-feeding any two expansion protocols. In particular, such an unbounded expansion can be made robust, which is known for the first time. Another significant implication is, it enables the secure randomness generation and key distribution using public randomness, such as that broadcast by NIST's Randomness Beacon. Our protocol also provides a method for refuting local hidden variable theories under a weak assumption on the available randomness for choosing the measurement settings.

A substantial re-writing of V2, especially on model definitions. An abstract model of robustness is added and the robustness claim in V2 is made rigorous. Focuses on quantum-security. A future update is planned to address non-signaling security

References in corpus (14)

• Unconditional Security Of Quantum Key Distribution Over Arbitrarily Long Distances
• Random Numbers Certified by Bell's Theorem
• No Signalling and Quantum Key Distribution
• Fully device independent quantum key distribution
• Free randomness can be amplified
• Full randomness from arbitrarily deterministic events
• Memory Attacks on Device-Independent Quantum Cryptography
• Trevisan's extractor in the presence of quantum side information
• Universally-composable privacy amplification from causality constraints
• Security and Composability of Randomness Expansion from Bell Inequalities
• The Bounded Storage Model in The Presence of a Quantum Adversary
• Robust Device-Independent Randomness Amplification with Few Devices
• Infinite Randomness Expansion and Amplification with a Constant Number of Devices
• Robust Device Independent Randomness Amplification

Cited by in corpus (23)

• Quantum Random Number Generators
• Security in Quantum Cryptography
• Certified randomness in quantum physics
• Simple and tight device-independent security proofs
• Maximal randomness expansion from steering inequality violations using qudits
• Randomness in Quantum Mechanics: Philosophy, Physics and Technology
• Randomness amplification against no-signaling adversaries using two devices
• Generalised entropy accumulation
• Device-independent randomness generation from several Bell estimators
• Certifying Quantum Randomness by Probability Estimation
• Experimental robust self-testing of the state generated by a quantum network
• Physical Security in the Post-quantum Era: A Survey on Side-channel Analysis, Random Number Generators, and Physically Unclonable Functions
• Infinite Randomness Expansion and Amplification with a Constant Number of Devices
• Practical randomness amplification and privatisation with implementations on quantum computers
• Quantum-proof randomness extractors via operator space theory
• Reductions to IID in Device-independent Quantum Information Processing
• Universal security for randomness expansion from the spot-checking protocol
• Computational Notions of Quantum Min-Entropy
• Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices
• Bounding the seed length of Miller and Shi's unbounded randomness expansion protocol
• Interplay between Quantumness, Randomness, and Selftesting
• Interactive proofs with approximately commuting provers
• Private Weakly-Random Sequences from Human Heart Rate for Quantum Amplification