Local Randomness: Examples and Application

Abstract

When two players achieve a superclassical score at a nonlocal game, their outputs must contain intrinsic randomness. This fact has many useful implications for quantum cryptography. Recently it has been observed (C. Miller, Y. Shi, Quant. Inf. & Comp. 17, pp. 0595-0610, 2017) that such scores also imply the existence of local randomness -- that is, randomness known to one player but not to the other. This has potential implications for cryptographic tasks between two cooperating but mistrustful players. In the current paper we bring this notion toward practical realization, by offering a near-optimal bound on local randomness for the CHSH game, and also proving the security of a cryptographic application of local randomness (single-bit certified deletion).

v3: Minor revisions for journal publication, new plot of the CHSH game and improved accuracy of the Magic Square game result. 13 pages

References in corpus (7)

• A convergent hierarchy of semidefinite programs characterizing the set of quantum correlations
• Simple and tight device-independent security proofs
• Entropy accumulation
• Fully Distrustful Quantum Cryptography
• Parallel Device-Independent Quantum Key Distribution
• Device-independence for two-party cryptography and position verification
• Fully general device-independence for two-party cryptography and position verification

Cited by in corpus (11)

• Quantum encryption with certified deletion
• Generalised entropy accumulation
• Quantum Encryption with Certified Deletion, Revisited: Public Key, Attribute-Based, and Classical Communication
• Device-independent quantum key distribution with arbitrarily small nonlocality
• A device-independent protocol for XOR oblivious transfer
• Equivalence between face nonsignaling correlations, full nonlocality, all-versus-nothing proofs, and pseudotelepathy
• Reductions to IID in Device-independent Quantum Information Processing
• Constant-sized correlations are sufficient to robustly self-test maximally entangled states with unbounded dimension
• Composably secure device-independent encryption with certified deletion
• Device-independent uncloneable encryption
• Tight analytic bound on the trade-off between device-independent randomness and nonlocality