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•3 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.

arXiv:2303.01625•ACM Symposium on Theory of Computing (STOC)•May 16, 2023•42 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

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•1 citation

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•20 citations

Certified randomness using a trapped-ion quantum processor

Minzhao Liu, Ruslan Shaydulin, Pradeep Niroula +29 more

Abstract Although quantum computers can perform a wide range of practically important tasks beyond the abilities of classical computers 1,2 , realizing this potential remains a challenge. An example is to use an untrusted remote device to generate random bits that can be certified to contain a certain amount of entropy 3 . Certified randomness has many applications but is impossible to achieve solely by classical computation. Here we demonstrate the generation of certifiably random bits using the 56-qubit Quantinuum H2-1 trapped-ion quantum computer accessed over the Internet. Our protocol leverages the classical hardness of recent random circuit sampling demonstrations 4,5 : a client generates quantum ‘challenge’ circuits using a small randomness seed, sends them to an untrusted quantum server to execute and verifies the results of the server. We analyse the security of our protocol against a restricted class of realistic near-term adversaries. Using classical verification with measured combined sustained performance of 1.1 × 10 18 floating-point operations per second across multiple supercomputers, we certify 71,313 bits of entropy under this restricted adversary and additional assumptions. Our results demonstrate a step towards the practical applicability of present-day quantum computers.

arXiv:2503.20498•Nature•Mar 26, 2025•56 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.
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.
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.
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.
Abstract Although quantum computers can perform a wide range of practically important tasks beyond the abilities of classical computers 1,2 , realizing this potential remains a challenge. An example is to use an untrusted remote device to generate random bits that can be certified to contain a certain amount of entropy 3 . Certified randomness has many applications but is impossible to achieve solely by classical computation. Here we demonstrate the generation of certifiably random bits using the 56-qubit Quantinuum H2-1 trapped-ion quantum computer accessed over the Internet. Our protocol leverages the classical hardness of recent random circuit sampling demonstrations 4,5 : a client generates quantum ‘challenge’ circuits using a small randomness seed, sends them to an untrusted quantum server to execute and verifies the results of the server. We analyse the security of our protocol against a restricted class of realistic near-term adversaries. Using classical verification with measured combined sustained performance of 1.1 × 10 18 floating-point operations per second across multiple supercomputers, we certify 71,313 bits of entropy under this restricted adversary and additional assumptions. Our results demonstrate a step towards the practical applicability of present-day quantum computers.