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

QuoRand: Distributed Certified Randomness over Mutually-Distrusting Quantum Servers

Ruilin Zhou, Jinglei Cheng, Yuhang Gan, Chen Qian

Published Aug 17, 2026• 0 citations
Publisher

Abstract

Random beacons—services that periodically emit public, unpredictable, and unbiasable random values—underpin blockchains, lotteries, sharding, and cryptographic parameter generation. To remove single points of trust, modern beacons are distributed, but they rest on classical hardness assumptions that quantum computers threaten. Quantum random beacons instead draw unpredictability directly from quantum mechanics and are quantum-safe by construction. Existing systems sit at two extremes: single-device protocols based on random circuit sampling trust one quantum server, while device-independent beacons require entangled measurement stations and do not fit the commercial quantum cloud. We present QuoRand, a quantum random beacon that combines m mutually distrusting quantum servers into one publicly verifiable source of certified randomness through a fully distributed classical protocol with no trusted party. QuoRand introduces (1) a Certified-Randomness Oracle (CRO) abstraction that captures RCS-, LWE-, and low-depth-unitary instantiations uniformly, so all guarantees hold independently of the quantum-advantage assumption; (2) a hash-chained challenge derivation that self-bootstraps each round from the previous output, removing the trusted coordinator of prior designs; and (3) a verifiable-delay-function audit lottery, drawn only after all servers commit, that renders any spoofing server accountable while amortizing verification across rounds. We prove QuoRand is unpredictable and bias-resistant under an anytrust assumption—a single honest server suffices—accountable under an honest majority, and live under partial synchrony, and confirm the soundness-cost trade-off with lightweight simulations.

DOI
10.1145/3833409.3833447

Related papers

A trustless decentralized protocol for distributed consensus of public quantum random numbers

Lac Nguyen, Jeevanandha Ramanathan, Wang, Michelle Mei +2 more

Quantum random number (QRNG) beacons distinguish themselves from classical counterparts by providing intrinsic unpredictability originating from the fundamental laws of quantum mechanics. Most demonstrations have focused on certifiable randomness generators to guarantee the public that their genuineness is independent from imperfect implementations. These efforts however do not benefit applications where multiple distrusted users need a common set of random numbers, as they must rely on the honesty of beacon owners. In this paper, we formally introduce a design and proof-of-principle experiment of the first consensus protocol producing QRNs in a decentralized environment (dQRNG). Such protocol allows N number of participants contribute in the generation process and publicly verify numbers they collect. Security of the protocol is guaranteed given(N-1) dishonest participants. Our method is thus suited for distribute systems that requires a bias-resistant, highly secure, and public-verifiable random beacon.

arXiv:2108.12038•Jan 1, 2021•2 citations

Certified Randomness from Quantum Supremacy

Scott Aaronson, Shih-Han Hung

We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing “quantum supremacy” experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain Ω(n) min-entropy, where n is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits—thereby “bootstrapping” from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol’s output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most n∼ 60 qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.

ACM Symposium on Theory of Computing (STOC)•May 16, 2023•19 citations

Certified Randomness from Quantum Supremacy

Scott Aaronson, Hung, Shih-Han

We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain $Ω(n)$ min-entropy, where $n$ is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits -- thereby "bootstrapping" from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol's output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most $n\sim 60$ qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.

arXiv:2303.01625•Mar 2, 2023•2 citations

Certified Randomness with Optimal Rate

Siddhartha Jain, Saachi Mutreja, Bhaskar Roberts

The generation of certified random bits is an emerging near-term application of quantum computers. Potential applications, such as randomness beacons and CRS generation, require nearly uniform randomness, whose rate (the ratio of min-entropy to bitlength) is ~ 1. However, existing protocols for certified randomness either produce weakly random strings with rate o(1), or they require a trusted random seed. We show how to certify randomness with the optimal rate ~ 1 without requiring any trusted randomness from the verifier. Our protocol is secure unconditionally in the quantum random oracle model (QROM). This improves the result of Coladangelo et al., who certified weakly random strings unconditionally in the QROM, and answers a question posed by Aaronson and Hung. We also define and construct a proof of conditional min-entropy, which certifies optimal min-entropy even conditioned on an adversarially chosen transcript. We show an application of this primitive to randomness beacons, where each pulse should have high min-entropy conditioned on all previous messages.

quant-pharXiv:2609.38945•Oct 1, 2026•0 citations

A publicly verifiable protocol for random number generation

João Penna, Jeroen van de Graaf

Chance plays an essential role in many decision procedures such as lotteries, draws etc. As such procedures are moving on-line, several web services offering randomness have appeared over the last few years. NIST’s randomness beacon, which publishes a sequence of 512 random bytes every minute, unfortunately lacks transparency: the beacon does not eliminate the possibility of an insider attack who knows the outcomes beforehand. We propose an improvement of NIST’s beacon which is publicly verifiable and fully transparent: any outsider who did not witness the bit generation in person but has internet access can convince himself that the beacon acted honestly, provided he can be sure that fresh, independent random bits were contributed to the seed value. Our proposal is based on a novel cryptographic assumption: the existence of functions that are slow to compute even on the fastest supercomputers.

Simpósio Brasileiro de Cibersegurança (SBSeg)•Nov 6, 2017•0 citations

On Certified Randomness from Fourier Sampling or Random Circuit Sampling

Roozbeh Bassirian, Adam Bouland, Bill Fefferman +2 more

Certified randomness has a long history in quantum information, with many potential applications. Recently Aaronson and Hung proposed a novel public certified randomness protocol based on existing random circuit sampling (RCS) experiments. The security of their protocol, however, relies on non-standard complexity-theoretic conjectures which were not previously studied in the literature. Inspired by this work, we study certified randomness in the quantum random oracle model (QROM). We show that quantum Fourier Sampling can be used to define a publicly verifiable certified randomness protocol with black-box security without any computational assumptions. In addition to giving a certified randomness protocol in the QROM, our work can also be seen as supporting Aaronson and Hung's conjectures for RCS-based randomness generation, as our protocol is in some sense the "black-box version" of Aaronson and Hung's protocol. In further support of Aaronson and Hung's proposal, we prove a Fourier Sampling version of Aaronson and Hung's conjecture by extending Raz and Tal's separation of BQP vs PH. Our work complements the subsequent certified randomness protocol of Yamakawa and Zhandry (2022) in the QROM. Whereas the security of that protocol relied on the Aaronson-Ambainis conjecture, ours does not rely on any computational assumption – at the expense of requiring exponential-time classical verification. Our protocol also has a simple heuristic implementation.

arXiv:2111.14846•Quantum•Feb 10, 2026•3 citations
Random beacons—services that periodically emit public, unpredictable, and unbiasable random values—underpin blockchains, lotteries, sharding, and cryptographic parameter generation. To remove single points of trust, modern beacons are distributed, but they rest on classical hardness assumptions that quantum computers threaten. Quantum random beacons instead draw unpredictability directly from quantum mechanics and are quantum-safe by construction. Existing systems sit at two extremes: single-device protocols based on random circuit sampling trust one quantum server, while device-independent beacons require entangled measurement stations and do not fit the commercial quantum cloud. We present QuoRand, a quantum random beacon that combines m mutually distrusting quantum servers into one publicly verifiable source of certified randomness through a fully distributed classical protocol with no trusted party. QuoRand introduces (1) a Certified-Randomness Oracle (CRO) abstraction that captures RCS-, LWE-, and low-depth-unitary instantiations uniformly, so all guarantees hold independently of the quantum-advantage assumption; (2) a hash-chained challenge derivation that self-bootstraps each round from the previous output, removing the trusted coordinator of prior designs; and (3) a verifiable-delay-function audit lottery, drawn only after all servers commit, that renders any spoofing server accountable while amortizing verification across rounds. We prove QuoRand is unpredictable and bias-resistant under an anytrust assumption—a single honest server suffices—accountable under an honest majority, and live under partial synchrony, and confirm the soundness-cost trade-off with lightweight simulations.
Quantum random number (QRNG) beacons distinguish themselves from classical counterparts by providing intrinsic unpredictability originating from the fundamental laws of quantum mechanics. Most demonstrations have focused on certifiable randomness generators to guarantee the public that their genuineness is independent from imperfect implementations. These efforts however do not benefit applications where multiple distrusted users need a common set of random numbers, as they must rely on the honesty of beacon owners. In this paper, we formally introduce a design and proof-of-principle experiment of the first consensus protocol producing QRNs in a decentralized environment (dQRNG). Such protocol allows N number of participants contribute in the generation process and publicly verify numbers they collect. Security of the protocol is guaranteed given(N-1) dishonest participants. Our method is thus suited for distribute systems that requires a bias-resistant, highly secure, and public-verifiable random beacon.
We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing “quantum supremacy” experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain Ω(n) min-entropy, where n is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits—thereby “bootstrapping” from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol’s output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most n∼ 60 qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.
We propose an application for near-term quantum devices: namely, generating cryptographically certified random bits, to use (for example) in proof-of-stake cryptocurrencies. Our protocol repurposes the existing "quantum supremacy" experiments, based on random circuit sampling, that Google and USTC have successfully carried out starting in 2019. We show that, whenever the outputs of these experiments pass the now-standard Linear Cross-Entropy Benchmark (LXEB), under plausible hardness assumptions they necessarily contain Ω(n)Ω(n)Ω(n) min-entropy, where nnn is the number of qubits. To achieve a net gain in randomness, we use a small random seed to produce pseudorandom challenge circuits. In response to the challenge circuits, the quantum computer generates output strings that, after verification, can then be fed into a randomness extractor to produce certified nearly-uniform bits -- thereby "bootstrapping" from pseudorandomness to genuine randomness. We prove our protocol sound in two senses: (i) under a hardness assumption called Long List Quantum Supremacy Verification, which we justify in the random oracle model, and (ii) unconditionally in the random oracle model against an eavesdropper who could share arbitrary entanglement with the device. (Note that our protocol's output is unpredictable even to a computationally unbounded adversary who can see the random oracle.) Currently, the central drawback of our protocol is the exponential cost of verification, which in practice will limit its implementation to at most n∼60n\sim 60n∼60 qubits, a regime where attacks are expensive but not impossible. Modulo that drawback, our protocol appears to be the only practical application of quantum computing that both requires a QC and is physically realizable today.
The generation of certified random bits is an emerging near-term application of quantum computers. Potential applications, such as randomness beacons and CRS generation, require nearly uniform randomness, whose rate (the ratio of min-entropy to bitlength) is ~ 1. However, existing protocols for certified randomness either produce weakly random strings with rate o(1), or they require a trusted random seed. We show how to certify randomness with the optimal rate ~ 1 without requiring any trusted randomness from the verifier. Our protocol is secure unconditionally in the quantum random oracle model (QROM). This improves the result of Coladangelo et al., who certified weakly random strings unconditionally in the QROM, and answers a question posed by Aaronson and Hung. We also define and construct a proof of conditional min-entropy, which certifies optimal min-entropy even conditioned on an adversarially chosen transcript. We show an application of this primitive to randomness beacons, where each pulse should have high min-entropy conditioned on all previous messages.
Chance plays an essential role in many decision procedures such as lotteries, draws etc. As such procedures are moving on-line, several web services offering randomness have appeared over the last few years. NIST’s randomness beacon, which publishes a sequence of 512 random bytes every minute, unfortunately lacks transparency: the beacon does not eliminate the possibility of an insider attack who knows the outcomes beforehand. We propose an improvement of NIST’s beacon which is publicly verifiable and fully transparent: any outsider who did not witness the bit generation in person but has internet access can convince himself that the beacon acted honestly, provided he can be sure that fresh, independent random bits were contributed to the seed value. Our proposal is based on a novel cryptographic assumption: the existence of functions that are slow to compute even on the fastest supercomputers.
Certified randomness has a long history in quantum information, with many potential applications. Recently Aaronson and Hung proposed a novel public certified randomness protocol based on existing random circuit sampling (RCS) experiments. The security of their protocol, however, relies on non-standard complexity-theoretic conjectures which were not previously studied in the literature. Inspired by this work, we study certified randomness in the quantum random oracle model (QROM). We show that quantum Fourier Sampling can be used to define a publicly verifiable certified randomness protocol with black-box security without any computational assumptions. In addition to giving a certified randomness protocol in the QROM, our work can also be seen as supporting Aaronson and Hung's conjectures for RCS-based randomness generation, as our protocol is in some sense the "black-box version" of Aaronson and Hung's protocol. In further support of Aaronson and Hung's proposal, we prove a Fourier Sampling version of Aaronson and Hung's conjecture by extending Raz and Tal's separation of BQP vs PH. Our work complements the subsequent certified randomness protocol of Yamakawa and Zhandry (2022) in the QROM. Whereas the security of that protocol relied on the Aaronson-Ambainis conjecture, ours does not rely on any computational assumption – at the expense of requiring exponential-time classical verification. Our protocol also has a simple heuristic implementation.