Security and Composability of Randomness Expansion from Bell Inequalities

Abstract

The nonlocal behavior of quantum mechanics can be used to generate guaranteed fresh randomness from an untrusted device that consists of two nonsignalling components; since the generation process requires some initial fresh randomness to act as a catalyst, one also speaks of randomness expansion. Colbeck and Kent proposed the first method for generating randomness from untrusted devices, however, without providing a rigorous analysis. This was addressed subsequently by Pironio et al. [Nature 464 (2010)], who aimed at deriving a lower bound on the min-entropy of the data extracted from an untrusted device, based only on the observed non-local behavior of the device. Although that article succeeded in developing important tools towards the acquired goal, it failed in putting the tools together in a rigorous and correct way, and the given formal claim on the guaranteed amount of min-entropy needs to be revisited. In this paper we show how to combine the tools provided by Pironio et al., as to obtain a meaningful and correct lower bound on the min-entropy of the data produced by an untrusted device, based on the observed non-local behavior of the device. Our main result confirms the essence of the improperly formulated claims of Pironio et al., and puts them on solid ground. We also address the question of composability and show that different untrusted devices can be composed in an alternating manner under the assumption that they are not entangled. This enables for superpolynomial randomness expansion based on two untrusted yet unentangled devices.

12 pages, v3: significant changes: security is proven against adversaries holding only classical side information

References in corpus (7)

• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• Bounding the set of quantum correlations
• Private Randomness Expansion With Untrusted Devices
• Randomness vs Non Locality and Entanglement
• Memory Attacks on Device-Independent Quantum Cryptography
• Security of practical private randomness generation
• Certifiable Quantum Dice - Or, testable exponential randomness expansion

Cited by in corpus (62)

• Bell nonlocality
• Advances in Quantum Cryptography
• Quantum Random Number Generators
• Fully device independent quantum key distribution
• Detection-Loophole-Free Test of Quantum Nonlocality, and Applications
• Quantum random number generation
• Quantum Cryptography Beyond Quantum Key Distribution
• Full randomness from arbitrarily deterministic events
• Experimentally Generated Randomness Certified by the Impossibility of Superluminal Signals
• Memory Attacks on Device-Independent Quantum Cryptography
• Security of practical private randomness generation
• Simple and tight device-independent security proofs
• Quantum randomness extraction for various levels of characterization of the devices
• Device-independent randomness expansion against quantum side information
• More Randomness from the Same Data
• High speed self-testing quantum random number generation without detection loophole
• Using complete measurement statistics for optimal device-independent randomness evaluation
• A Comprehensive Review of Quantum Random Number Generators: Concepts, Classification and the Origin of Randomness
• Experimental Realization of Device-Independent Quantum Randomness Expansion
• Robust Device-Independent Randomness Amplification with Few Devices
• High Speed Continuous Variable Source-Independent Quantum Random Number Generation
• Device-independent quantum key distribution secure against adversaries with no long-term quantum memory
• Device-Independent Randomness Generation in the Presence of Weak Cross-Talk
• A framework for quantum-secure device-independent randomness expansion
• Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions
• Realization of a quantum random generator certified with the Kochen-Specker theorem
• Provably-secure quantum randomness expansion with uncharacterised homodyne detection
• Device-independent randomness generation from several Bell estimators
• Certifying Quantum Randomness by Probability Estimation
• Randomness Certification from Multipartite Quantum Steering for Arbitrary Dimensional Systems
• Quantum to Classical Randomness Extractors
• Semi-definite programming and quantum information
• Entropy bounds for multiparty device-independent cryptography
• Quantum Randomness Generation by Probability Estimation with Classical Side Information
• Semi-Device-Independent Random Number Generation with Flexible Assumptions
• Certifiable Quantum Dice - Or, testable exponential randomness expansion
• Robust amplification of Santha-Vazirani sources with three devices
• Device-Independent Bit Commitment based on the CHSH Inequality
• Neither Contextuality nor Nonlocality Admits Catalysts
• Boosting device-independent cryptography with tripartite nonlocality
• Semi-device-independent randomness expansion with partially free random sources
• Infinite Randomness Expansion and Amplification with a Constant Number of Devices
• Quantum Probability Estimation for Randomness with Quantum Side Information
• Searching for evidence of algorithmic randomness and incomputability in the output of quantum random number generators
• Classical Cryptographic Protocols in a Quantum World
• Certified randomness in tight space
• Network quantum steering enables randomness certification without seed randomness
• Universal security for randomness expansion from the spot-checking protocol
• Experimental certification of more than one bit of quantum randomness in the two inputs and two outputs scenario
• Clauser-Horne Bell test with imperfect random inputs
• Correlations and randomness generation based on energy constraints
• The violation of Bell-CHSH inequalities leads to different conclusions depending on the description used
• Parity-based, bias-free optical quantum random number generation with min-entropy estimation
• Efficiently verifiable quantum advantage on near-term analog quantum simulators
• Robust protocols for securely expanding randomness and distributing keys using untrusted quantum devices
• Experimental test of measurement dependent local Bell inequality with human free will
• Regularising data for practical randomness generation
• Robust Randomness Amplifiers: Upper and Lower Bounds
• Graphical Methods in Device-Independent Quantum Cryptography
• Bounding Large-Scale Bell Inequalities
• Interactive proofs with approximately commuting provers
• Interplay between Quantumness, Randomness, and Selftesting