Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Log inSign up
Challenges
Datasets
Workspaces
Papers
Discussions
Leaderboard
Blog
Job Board
Q3AS

© 2026 Aqora Quantum S.A.S.

TermsPrivacyLegal Notice

arXiv:1708.04338 · Physical Review A

Local randomness: Examples and application

Honghao Fu, Carl A. Miller

Published Mar 19, 2018• 26 citations
arXivHTMLPDF

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 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).

DOI
10.1103/physreva.97.032324

Related papers

Randomness in nonlocal games between mistrustful players

Carl A. Miller, Yaoyun Shi

If two quantum players at a nonlocal game G achieve a superclassical score, then their measurement outcomes must be at least partially random from the perspective of any third player. This is the basis for device-independent quantum cryptography. In this paper we address a related question: does a superclassical score at G guarantee that one player has created randomness from the perspective of the other player? We show that for complete-support games, the answer is yes: even if the second player is given the first player’s input at the conclusion of the game, he cannot perfectly recover her output. Thus some amount of local randomness (i.e., randomness possessed by only one player) is always obtained when randomness is certified from nonlocal games with quantum strategies. This is in contrast to non-signaling game strategies, which may produce global randomness without any local randomness. We discuss potential implications for cryptographic protocols between mistrustful parties.

arXiv:1706.04984•Quantum Information and Computation•May 1, 2017•8 citations

Certified randomness between mistrustful players

Carl A. Miller, Yaoyun Shi

It is known that if two players achieve a superclassical score at a nonlocal game $G$, then their outputs are certifiably random - that is, regardless of the strategy used by the players, a third party will not be able to perfectly predict their outputs (even if he were given their inputs). We prove that for any complete-support game $G$, there is an explicit nonzero function $F_G$ such that if Alice and Bob achieve a superclassical score of $s$ at $G$, then Bob has a probability of at most $1 - F_G ( s )$ of correctly guessing Alice's output after the game is played. Our result implies that certifying global randomness through such games must necessarily introduce local randomness.

arXiv:1610.05140•Oct 17, 2016•0 citations

Trading Isolation for Certifiable Randomness Expansion

Matthew Coudron

A source of bits is an important resource in modern cryptography, algorithms and statistics. Can one ever be sure that a random source is truly random, or in the case of cryptography, secure against potential adversaries or eavesdroppers? Recently the study of non-local properties of entanglement has produced an interesting new perspective on this question, which we will refer to broadly as Certifiable Randomness Expansion (CRE). CRE refers generally to a process by which a source of information-theoretically certified randomness can be constructed based only on two simple assumptions: the prior existence of a short seed and the ability to ensure that two or more black-box devices do not communicate (i.e. are non-signaling). In this work we make progress on a conjecture of [Col09] which proposes a method for indefinite certifiable randomness expansion using a growing number of devices (we actually prove a slight modification of the original conjecture in which we use the CHSH game as a subroutine rather than the GHZ game as originally proposed). The proof requires a technique not used before in the study of randomness expansion, and inspired by the tools developed in [RUV12]. The result also establishes the existence of a protocol for constant factor CRE using a finite number of devices (here the constant factor can be much greater than 1). While much better expansion rates (polynomial, and even exponential) have been achieved with only two devices, our analysis requires techniques not used before in the study of randomness expansion, and represents progress towards a protocol which is provably secure against a quantum eavesdropper who knows the input to the protocol.

•Jan 1, 2013•0 citations

No Bound Randomness in Quantum Nonlocality

Ravishankar Ramanathan, Yuan Liu, Y. M. Wu +1 more

Recently it has been found that there exist maximally nonlocal quantum correlations that fail to certify randomness for any fixed input pair, rendering them useless for device-independent spot-checking randomness expansion schemes. Here we show that conversely, in DI randomness amplification protocols where all input pairs are used for randomness generation, any amount of quantum nonlocality is sufficient to certify randomness. This shows that no bound randomness exists in quantum nonlocality - any quantum nonlocal behavior is useful in a DI randomness generation task with appropriate modification of protocol structure. Secondly, we show that in contrast to the hitherto considered fixed-input guessing probability, the average guessing probability over all inputs is a faithful and monotonic measure of nonlocality. We use the average guessing probability to show that in contrast to findings in PRL 134, 090201, the detection efficiency threshold for randomness generation is never lower than that for nonlocality detection. Finally, we analytically compute the average guessing probability by a quantum adversary of a single player's measurement outputs in a standard CHSH Bell test, and use it to demonstrate an improvement in the generation rate in state-of-art amplification protocols.

arXiv:2509.08623•Sep 10, 2025•5 citations

Certifying the absence of quantum nonlocality

Carl A. Miller, Yaoyun Shi

Quantum nonlocality is an inherently non-classical feature of quantum mechanics and manifests itself through violation of Bell inequalities for nonlocal games. We show that in a fairly general setting, a simple extension of a nonlocal game can certify instead the absence of quantum nonlocality. Through contraposition, our result implies that a super-classical performance for such a game ensures that a player's output is unpredictable to the other player. Previously such output unpredictability was known with respect to a third party.

arXiv:1608.01011•Aug 2, 2016•1 citation

Quantum Nonlocality and Device-Independent Randomness Robust to Relaxations of Bell Assumptions

Ravishankar Ramanathan, Yuan Liu

The question of certifying quantum nonlocality under a relaxation of the assumptions in the Bell theorem has gained traction, with potential for device-independent applications under weak seeds and cross-talk. Recently, it was shown that quantum nonlocality can be certified even under a simultaneous arbitrary (but not full) relaxation of the assumptions of Measurement Independence (MI) and Parameter Independence (PI), using states of local dimension $d = poly((1-ε)^{-1})$ for an $ε\in [0,1)$-relaxation. Here, we derive three results strengthening the state-of-art. Firstly, we show that states of constant local dimension $d$ are already sufficient to certify quantum nonlocality under arbitrary MI and PI relaxation, albeit in a non-robust manner. Secondly, and as a theoretical paradigm to derive the above, we introduce the notion of \textit{measurement-dependent parameter-dependent locality} as the set of input-output behaviors under simultaneous relaxations of measurement and parameter independence. We provide a rigorous characterisation of the vertices of the polytope of joint input-output behaviors that obey a $μ$-relaxation of MI and $ε$-relaxation of PI. We highlight a relation between nonlocality certification under PI relaxation and that under detection inefficiencies by pointing out alternative extremal correlations to the Eberhard correlations that also allow to achieve detection efficiency of $η= 2/3$ in the two-input scenario. Finally, we study the implication of the relaxed assumptions for device-independent randomness certification. We analytically derive the quantum guessing probability for one player's outcomes in the CHSH Bell test, as a function of the noise in the test as well as of a leakage of an average amount of $I(X:B) < 1$ bits of input information per measurement round.

quant-pharXiv:2512.18513•Dec 23, 2025•3 citations
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).
If two quantum players at a nonlocal game G achieve a superclassical score, then their measurement outcomes must be at least partially random from the perspective of any third player. This is the basis for device-independent quantum cryptography. In this paper we address a related question: does a superclassical score at G guarantee that one player has created randomness from the perspective of the other player? We show that for complete-support games, the answer is yes: even if the second player is given the first player’s input at the conclusion of the game, he cannot perfectly recover her output. Thus some amount of local randomness (i.e., randomness possessed by only one player) is always obtained when randomness is certified from nonlocal games with quantum strategies. This is in contrast to non-signaling game strategies, which may produce global randomness without any local randomness. We discuss potential implications for cryptographic protocols between mistrustful parties.
It is known that if two players achieve a superclassical score at a nonlocal game GGG, then their outputs are certifiably random - that is, regardless of the strategy used by the players, a third party will not be able to perfectly predict their outputs (even if he were given their inputs). We prove that for any complete-support game GGG, there is an explicit nonzero function FGF_GFG​ such that if Alice and Bob achieve a superclassical score of sss at GGG, then Bob has a probability of at most 1−FG(s)1 - F_G ( s )1−FG​(s) of correctly guessing Alice's output after the game is played. Our result implies that certifying global randomness through such games must necessarily introduce local randomness.
A source of bits is an important resource in modern cryptography, algorithms and statistics. Can one ever be sure that a random source is truly random, or in the case of cryptography, secure against potential adversaries or eavesdroppers? Recently the study of non-local properties of entanglement has produced an interesting new perspective on this question, which we will refer to broadly as Certifiable Randomness Expansion (CRE). CRE refers generally to a process by which a source of information-theoretically certified randomness can be constructed based only on two simple assumptions: the prior existence of a short seed and the ability to ensure that two or more black-box devices do not communicate (i.e. are non-signaling). In this work we make progress on a conjecture of [Col09] which proposes a method for indefinite certifiable randomness expansion using a growing number of devices (we actually prove a slight modification of the original conjecture in which we use the CHSH game as a subroutine rather than the GHZ game as originally proposed). The proof requires a technique not used before in the study of randomness expansion, and inspired by the tools developed in [RUV12]. The result also establishes the existence of a protocol for constant factor CRE using a finite number of devices (here the constant factor can be much greater than 1). While much better expansion rates (polynomial, and even exponential) have been achieved with only two devices, our analysis requires techniques not used before in the study of randomness expansion, and represents progress towards a protocol which is provably secure against a quantum eavesdropper who knows the input to the protocol.
Recently it has been found that there exist maximally nonlocal quantum correlations that fail to certify randomness for any fixed input pair, rendering them useless for device-independent spot-checking randomness expansion schemes. Here we show that conversely, in DI randomness amplification protocols where all input pairs are used for randomness generation, any amount of quantum nonlocality is sufficient to certify randomness. This shows that no bound randomness exists in quantum nonlocality - any quantum nonlocal behavior is useful in a DI randomness generation task with appropriate modification of protocol structure. Secondly, we show that in contrast to the hitherto considered fixed-input guessing probability, the average guessing probability over all inputs is a faithful and monotonic measure of nonlocality. We use the average guessing probability to show that in contrast to findings in PRL 134, 090201, the detection efficiency threshold for randomness generation is never lower than that for nonlocality detection. Finally, we analytically compute the average guessing probability by a quantum adversary of a single player's measurement outputs in a standard CHSH Bell test, and use it to demonstrate an improvement in the generation rate in state-of-art amplification protocols.
Quantum nonlocality is an inherently non-classical feature of quantum mechanics and manifests itself through violation of Bell inequalities for nonlocal games. We show that in a fairly general setting, a simple extension of a nonlocal game can certify instead the absence of quantum nonlocality. Through contraposition, our result implies that a super-classical performance for such a game ensures that a player's output is unpredictable to the other player. Previously such output unpredictability was known with respect to a third party.
The question of certifying quantum nonlocality under a relaxation of the assumptions in the Bell theorem has gained traction, with potential for device-independent applications under weak seeds and cross-talk. Recently, it was shown that quantum nonlocality can be certified even under a simultaneous arbitrary (but not full) relaxation of the assumptions of Measurement Independence (MI) and Parameter Independence (PI), using states of local dimension d=poly((1−ε)−1)d = poly((1-ε)^{-1})d=poly((1−ε)−1) for an ε∈[0,1)ε\in [0,1)ε∈[0,1)-relaxation. Here, we derive three results strengthening the state-of-art. Firstly, we show that states of constant local dimension ddd are already sufficient to certify quantum nonlocality under arbitrary MI and PI relaxation, albeit in a non-robust manner. Secondly, and as a theoretical paradigm to derive the above, we introduce the notion of \textit{measurement-dependent parameter-dependent locality} as the set of input-output behaviors under simultaneous relaxations of measurement and parameter independence. We provide a rigorous characterisation of the vertices of the polytope of joint input-output behaviors that obey a μμμ-relaxation of MI and εεε-relaxation of PI. We highlight a relation between nonlocality certification under PI relaxation and that under detection inefficiencies by pointing out alternative extremal correlations to the Eberhard correlations that also allow to achieve detection efficiency of η=2/3η= 2/3η=2/3 in the two-input scenario. Finally, we study the implication of the relaxed assumptions for device-independent randomness certification. We analytically derive the quantum guessing probability for one player's outcomes in the CHSH Bell test, as a function of the noise in the test as well as of a leakage of an average amount of I(X:B)<1I(X:B) < 1I(X:B)<1 bits of input information per measurement round.