Universal security for randomness expansion from the spot-checking protocol

Abstract

Colbeck (Thesis, 2006) proposed using Bell inequality violations to generate certified random numbers. While full quantum-security proofs have been given, it remains a major open problem to identify the broadest class of Bell inequalities and lowest performance requirements to achieve such security. In this paper, working within the broad class of spot-checking protocols, we prove exactly which Bell inequality violations can be used to achieve full security. Our result greatly improves the known noise tolerance for secure randomness expansion: for the commonly used CHSH game, full security was only known with a noise tolerance of 1.5%, and we improve this to 10.3%. We also generalize our results beyond Bell inequalities and give the first security proof for randomness expansion based on Kochen-Specker inequalities. The central technical contribution of the paper is a new uncertainty principle for the Schatten norm, which is based on the uniform convexity inequality of Ball, Carlen, and Lieb (Inventiones mathematicae, 115:463-482, 1994).

v3: The main result has been strengthened and the proofs rewritten. The paper now includes a self-contained proof of security under Renyi entropies (simplifying arXiv:1402.0489). 27 pages

References in corpus (10)

• A simple test for hidden variables in spin-1 system
• Strong Kochen-Specker theorem and incomputability of quantum randomness
• Physical Randomness Extractors: Generating Random Numbers with Minimal Assumptions
• Binary Constraint System Games and Locally Commutative Reductions
• Contextuality offers device-independent security
• Quantum-proof randomness extractors via operator space theory
• Exploring Quantum Contextuality to Generate True Random Numbers
• Multi-Source Randomness Extractors Against Quantum Side Information, and their Applications
• 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

Cited by in corpus (5)

• Certified randomness in quantum physics
• Simple and tight device-independent security proofs
• Randomness in nonlocal games between mistrustful players
• Interplay between Quantumness, Randomness, and Selftesting
• Certifying the absence of quantum nonlocality