Randomness amplification against no-signaling adversaries using two devices

Abstract

Recently, a physically realistic protocol amplifying the randomness of Santha-Vazirani sources producing cryptographically secure random bits was proposed; however for reasons of practical relevance, the crucial question remained open whether this can be accomplished under the minimal conditions necessary for the task. Namely, is it possible to achieve randomness amplification using only two no-signaling components and in a situation where the violation of a Bell inequality only guarantees that some outcomes of the device for specific inputs exhibit randomness? Here, we solve this question and present a device-independent protocol for randomness amplification of Santha-Vazirani sources using a device consisting of two non-signaling components. We show that the protocol can amplify any such source that is not fully deterministic into a fully random source while tolerating a constant noise rate and prove the composable security of the protocol against general no-signaling adversaries. Our main innovation is the proof that even the partial randomness certified by the two-party Bell test (a single input-output pair (${\text{u}}^{\ast },{\text{x}}^{\ast }$) for which the conditional probability $P({\text{x}}^{\ast }|{\text{u}}^{\ast })$ is bounded away from $1$ for all no-signaling strategies that optimally violate the Bell inequality) can be used for amplification. We introduce the methodology of a partial tomographic procedure on the empirical statistics obtained in the Bell test that ensures that the outputs constitute a linear min-entropy source of randomness. As a technical novelty that may be of independent interest, we prove that the Santha-Vazirani source satisfies an exponential concentration property given by a recently discovered generalized Chernoff bound.

15 pages, 3 figures

References in corpus (1)

• Experimentally testable state-independent quantum contextuality

Cited by in corpus (22)

• Certified randomness in quantum physics
• Randomness in Quantum Mechanics: Philosophy, Physics and Technology
• Towards device-independent information processing on general quantum networks
• Device-independent randomness generation from several Bell estimators
• Experimental robust self-testing of the state generated by a quantum network
• Gadget structures in proofs of the Kochen-Specker theorem
• Practical randomness amplification and privatisation with implementations on quantum computers
• Non-signaling Causal Hierarchy of General Multisource Networks
• Amplifying the randomness of weak sources correlated with devices
• Tilted Hardy paradoxes for device-independent randomness extraction
• Test of the physical significance of Bell nonlocality
• Large violations in Kochen Specker contextuality and their applications
• Quantum nonlocality in presence of strong measurement dependence
• Optimal Measurement Structures for Contextuality Applications
• Generalised Kochen-Specker Theorem for Finite Non-Deterministic Outcome Assignments
• Experimental test of measurement dependent local Bell inequality with human free will
• Regularising data for practical randomness generation
• Complete extension: the non-signaling analog of quantum purification
• Relativistic Causality vs. No-Signaling as the limiting paradigm for correlations in physical theories
• Seedless extractors for device-independent quantum cryptography
• Private Weakly-Random Sequences from Human Heart Rate for Quantum Amplification
• Hybrid no-signaling-quantum correlations