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:1111.6054 · Philosophical Transactions of the Royal Society A Mathematical Physical and Engineering Sciences

Certifiable quantum dice

Umesh V. Vazirani, Thomas Vidick

Published Jun 18, 2012• 91 citations
arXivHTMLPDF

Abstract

We introduce a protocol through which a pair of quantum mechanical devices may be used to generate n random bits that are ε-close in statistical distance from n uniformly distributed bits, starting from a seed of uniform bits. The bits generated are certifiably random, based only on a simple statistical test that can be performed by the user, and on the assumption that the devices obey the no-signalling principle. No other assumptions are placed on the devices' inner workings: it is not necessary to even assume the validity of quantum mechanics.

DOI
10.1098/rsta.2011.0336

Related papers

Certifiable quantum dice: or, true random number generation secure against quantum adversaries

Umesh V. Vazirani, Thomas Vidick

We introduce a protocol through which a pair of quantum mechanical devices may be used to generate n bits that are ε-close in statistical distance from n uniformly distributed bits, starting from a seed of O(log n log 1/ε) uniform bits. The bits generated are certifiably random based only on a simple statistical test that can be performed by the user, and on the assumption that the devices do not communicate in the middle of each phase of the protocol. No other assumptions are placed on the devices' inner workings. A modified protocol uses a seed of O(log3 n) uniformly random bits to generate n bits that are poly-1(n)-indistinguishable from uniform even from the point of view of a quantum adversary who may have had prior access to the devices, and may be entangled with them.

ACM Symposium on Theory of Computing (STOC)•May 19, 2012•85 citations

Efficient Certifiable Randomness from a Single Quantum Device

Urmila Mahadev, Umesh V. Vazirani, Thomas Vidick

Brakerski et. al [BCM+18] introduced the model of cryptographic testing of a single untrusted quantum device and gave a protocol for certifiable randomness generation. We use the leakage resilience properties of the Learning With Errors problem to address a key issue left open in previous work - the rate of generation of randomness. Our new protocol can certify $Ω(n)$ fresh bits of randomness in constant rounds, where $n$ is a parameter of the protocol and the total communication is $O(n)$, thus achieving a nearly optimal rate. The proof that the output is statistically random is conceptually simple and technically elementary.

arXiv:2204.11353•Apr 24, 2022•15 citations

Security of practical private randomness generation

Stefano Pironio, Serge Massar

Measurements on entangled quantum systems necessarily yield outcomes that are intrinsically unpredictable if they violate a Bell inequality. This property can be used to generate certified randomness in a device-independent way, i.e., without making detailed assumptions about the internal working of the quantum devices used to generate the random numbers. Furthermore these numbers are also private; i.e., they appear random not only to the user but also to any adversary that might possess a perfect description of the devices. Since this process requires a small initial random seed to sample the behavior of the quantum devices and to extract uniform randomness from the raw outputs of the devices, one usually speaks of device-independent randomness expansion. The purpose of this paper is twofold. First, we point out that in most real, practical situations, where the concept of device independence is used as a protection against unintentional flaws or failures of the quantum apparatuses, it is sufficient to show that the generated string is random with respect to an adversary that holds only classical side information; i.e., proving randomness against quantum side information is not necessary. Furthermore, the initial random seed does not need to be private with respect to the adversary, provided that it is generated in a way that is independent from the measured systems. The devices, however, will generate cryptographically secure randomness that cannot be predicted by the adversary, and thus one can, given access to free public randomness, talk about private randomness generation. The theoretical tools to quantify the generated randomness according to these criteria were already introduced in S. Pironio et al. [Nature (London) 464, 1021 (2010)], but the final results were improperly formulated. The second aim of this paper is to correct this inaccurate formulation and therefore lay out a precise theoretical framework for practical device-independent randomness generation.

arXiv:1111.6056•Physical Review A•Jan 30, 2013•173 citations

Quantum Random Numbers: Certication and Generation

Alastair A. Abbott

In this thesis we study the generation of randomness from quantum mechanical sources: quantum random number generators (QRNGs). Such devices are thought to provide a better quality of randomness than is possible with classical devices, but the issue is in need of more rigorous study. In Chapter 1 we provide the necessary background for the thesis from both computability and probability theory. We then present and extend some recent results providing a more theoretical grounding for the indeterminism in quantum mechanics. In particular, we show that sequences of quantum random bits are incomputable in the strongest sense: no bit can be provably computed in advance. In Chapter 2 we study in detail the use of von Neumann normalisation for QRNGs producing both finite strings and infinite sequences of bits; such normalisation methods are necessary in order to counter for experimental imperfections. We show that, in the case of a constantly biased source, this normalisation gives the desired uniform distribution. The effect of this normalisation on the (in)computability of the generated sequences is studied, and it is shown that algorithmic randomness and Borel normality are preserved, but e-randomness (and thus incomputability) is, in general, not. Experimental bounds for the extent of departure from the uniform distribution in the non-ideal case of a slowly drifting bias are derived. In Chapter 3 we propose a new QRNG which uses entangled photon pairs and is certified to produce incomputable bits by value indefiniteness; this is the first QRNG with explicit certification by a physical principle. The effects of various experimental imperfections are discussed in detail, and care is taken to make the proposed QRNG as robust as is possible to these. A robust method based on XORing the produced bitstrings together is proposed to further improve the quality of the distribution produced by the QRNG. Various improvements and optimisations to this scheme are discussed.

•Jan 1, 2011•0 citations

Certification of randomness without seed randomness

Shubhayan Sarkar

The security of any cryptographic scheme relies on access to random number generators. Device-independently certified random number generators provide maximum security as one can discard the presence of an intruder by considering only the statistics generated by these devices. Any of the known device-independent schemes to certify randomness require an initial feed of randomness into the devices, which can be called seed randomness. In this work, we propose a one-sided device-independent scheme to certify two bits of randomness without the initial seed randomness. For our purpose, we utilise the framework of quantum networks with no inputs and two independent sources shared among two parties with one of them being trusted. Along with it, we also certify the maximally entangled state and the Bell basis measurement with the untrusted party which is then used to certify the randomness generated from the untrusted device.

arXiv:2307.11492•Jul 21, 2023•0 citations

Infinite randomness expansion with a constant number of devices

Matthew Coudron, Henry Yuen

We present a device-independent randomness expansion protocol, involving only a constant number of non-signaling quantum devices, that achieves infinite expansion: starting with m bits of uniform private randomness, the protocol can produce an unbounded amount of certified randomness that is exp(--Ω(m1/3))-close to uniform and secure against a quantum adversary. The only parameters which depend on the size of the input are the soundness of the protocol and the security of the output (both are inverse exponential in m). This settles a long-standing open problem in the area of randomness expansion and device-independence.

ACM Symposium on Theory of Computing (STOC)•May 31, 2014•47 citations
We introduce a protocol through which a pair of quantum mechanical devices may be used to generate n random bits that are ε-close in statistical distance from n uniformly distributed bits, starting from a seed of uniform bits. The bits generated are certifiably random, based only on a simple statistical test that can be performed by the user, and on the assumption that the devices obey the no-signalling principle. No other assumptions are placed on the devices' inner workings: it is not necessary to even assume the validity of quantum mechanics.
We introduce a protocol through which a pair of quantum mechanical devices may be used to generate n bits that are ε-close in statistical distance from n uniformly distributed bits, starting from a seed of O(log n log 1/ε) uniform bits. The bits generated are certifiably random based only on a simple statistical test that can be performed by the user, and on the assumption that the devices do not communicate in the middle of each phase of the protocol. No other assumptions are placed on the devices' inner workings. A modified protocol uses a seed of O(log3 n) uniformly random bits to generate n bits that are poly-1(n)-indistinguishable from uniform even from the point of view of a quantum adversary who may have had prior access to the devices, and may be entangled with them.
Brakerski et. al [BCM+18] introduced the model of cryptographic testing of a single untrusted quantum device and gave a protocol for certifiable randomness generation. We use the leakage resilience properties of the Learning With Errors problem to address a key issue left open in previous work - the rate of generation of randomness. Our new protocol can certify Ω(n)Ω(n)Ω(n) fresh bits of randomness in constant rounds, where nnn is a parameter of the protocol and the total communication is O(n)O(n)O(n), thus achieving a nearly optimal rate. The proof that the output is statistically random is conceptually simple and technically elementary.
Measurements on entangled quantum systems necessarily yield outcomes that are intrinsically unpredictable if they violate a Bell inequality. This property can be used to generate certified randomness in a device-independent way, i.e., without making detailed assumptions about the internal working of the quantum devices used to generate the random numbers. Furthermore these numbers are also private; i.e., they appear random not only to the user but also to any adversary that might possess a perfect description of the devices. Since this process requires a small initial random seed to sample the behavior of the quantum devices and to extract uniform randomness from the raw outputs of the devices, one usually speaks of device-independent randomness expansion. The purpose of this paper is twofold. First, we point out that in most real, practical situations, where the concept of device independence is used as a protection against unintentional flaws or failures of the quantum apparatuses, it is sufficient to show that the generated string is random with respect to an adversary that holds only classical side information; i.e., proving randomness against quantum side information is not necessary. Furthermore, the initial random seed does not need to be private with respect to the adversary, provided that it is generated in a way that is independent from the measured systems. The devices, however, will generate cryptographically secure randomness that cannot be predicted by the adversary, and thus one can, given access to free public randomness, talk about private randomness generation. The theoretical tools to quantify the generated randomness according to these criteria were already introduced in S. Pironio et al. [Nature (London) 464, 1021 (2010)], but the final results were improperly formulated. The second aim of this paper is to correct this inaccurate formulation and therefore lay out a precise theoretical framework for practical device-independent randomness generation.
In this thesis we study the generation of randomness from quantum mechanical sources: quantum random number generators (QRNGs). Such devices are thought to provide a better quality of randomness than is possible with classical devices, but the issue is in need of more rigorous study. In Chapter 1 we provide the necessary background for the thesis from both computability and probability theory. We then present and extend some recent results providing a more theoretical grounding for the indeterminism in quantum mechanics. In particular, we show that sequences of quantum random bits are incomputable in the strongest sense: no bit can be provably computed in advance. In Chapter 2 we study in detail the use of von Neumann normalisation for QRNGs producing both finite strings and infinite sequences of bits; such normalisation methods are necessary in order to counter for experimental imperfections. We show that, in the case of a constantly biased source, this normalisation gives the desired uniform distribution. The effect of this normalisation on the (in)computability of the generated sequences is studied, and it is shown that algorithmic randomness and Borel normality are preserved, but e-randomness (and thus incomputability) is, in general, not. Experimental bounds for the extent of departure from the uniform distribution in the non-ideal case of a slowly drifting bias are derived. In Chapter 3 we propose a new QRNG which uses entangled photon pairs and is certified to produce incomputable bits by value indefiniteness; this is the first QRNG with explicit certification by a physical principle. The effects of various experimental imperfections are discussed in detail, and care is taken to make the proposed QRNG as robust as is possible to these. A robust method based on XORing the produced bitstrings together is proposed to further improve the quality of the distribution produced by the QRNG. Various improvements and optimisations to this scheme are discussed.
The security of any cryptographic scheme relies on access to random number generators. Device-independently certified random number generators provide maximum security as one can discard the presence of an intruder by considering only the statistics generated by these devices. Any of the known device-independent schemes to certify randomness require an initial feed of randomness into the devices, which can be called seed randomness. In this work, we propose a one-sided device-independent scheme to certify two bits of randomness without the initial seed randomness. For our purpose, we utilise the framework of quantum networks with no inputs and two independent sources shared among two parties with one of them being trusted. Along with it, we also certify the maximally entangled state and the Bell basis measurement with the untrusted party which is then used to certify the randomness generated from the untrusted device.
We present a device-independent randomness expansion protocol, involving only a constant number of non-signaling quantum devices, that achieves infinite expansion: starting with m bits of uniform private randomness, the protocol can produce an unbounded amount of certified randomness that is exp(--Ω(m1/3))-close to uniform and secure against a quantum adversary. The only parameters which depend on the size of the input are the soundness of the protocol and the security of the output (both are inverse exponential in m). This settles a long-standing open problem in the area of randomness expansion and device-independence.