2017/08/31 by Honghao Fu, Carl A. Miller
Computer Science · Mathematics · Physics and Astronomy · #Computability, Logic, AI Algorithms #Computer science #Computer security #Cryptography #Mathematics #Quantum Computing Algorithms and Architecture #Quantum Mechanics and Applications #Randomness #Realization (probability) #Statistics #Theoretical computer science #quant-ph
paper · pdf · doi:10.1103/physreva.97.032324
published as Phys. Rev. A 97, 032324 (2018) · v3: Minor revisions for journal publication, new plot of the CHSH game and improved accuracy of the Magic Square game result. 13 pages
arxiv created 2018/03/01 · openalex publication_date 2018/03/19 · arxiv updated 2018/03/28 · openalex created_date 2025/10/10 · openalex updated_date 2026/08/05
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 and Y. Shi, Quantum Inf. Computat. 17, 0595 (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 near-optimal bounds on local randomness for the CHSH game, and also proving the security of a cryptographic application of local randomness (single-bit certified deletion).