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

IEEE Symposium on Security and Privacy (S&P)

Spurt: Scalable Distributed Randomness Beacon with Transparent Setup

Sourav Das, Vinith Krishnan, Irene Miriam Isaac, Ling Ren

Published May 1, 2022• 52 citations
Publisher

Abstract

Having shared access to high-quality random numbers is essential in many important applications. Yet, existing constructions of distributed random beacons still have limitations such as imperfect security guarantees, strong setup or network assumptions, or high costs. In this paper, we present Spurt, an efficient distributed randomness beacon protocol that does not require any trusted or expensive setup and is secure against a malicious adversary that controls up to one-third of the nodes in a partially synchronous network. We formally prove that each output of Spurt is unpredictable, bias-resistant, and publicly verifiable. Spurt has an amortized total communication cost of $O(\lambda n^{2})$ per beacon output where $\lambda$ is the security parameter. While designing Spurt, we also design a publicly verifiable secret sharing (PVSS) scheme whose security is based on the standard Decisional Bilinear Diffie-Hellman assumption and does not require a Random Oracle. We implement Spurt and evaluate it using a network of up to 128 nodes running in geographically distributed AWS instances. Our evaluation shows that Spurt can produce about 84 beacon outputs per minute in a network of 32 nodes and is comparable to systems with stronger assumptions or weaker security.

DOI
10.1109/sp46214.2022.9833580

Related papers

Silk: Computation-Efficient and Post-Quantum-Friendly Randomness Beacon

Binyang Hou, Jiamian Yan, Liang ZHANG +2 more

Distributed randomness beacons enable mutually distrustful parties to jointly generate public randomness. Several existing beacons built from secret sharing use costly pairings or group operations to verify shares. Their underlying discrete-logarithm assumptions are also vulnerable to quantum attacks. Moreover, running a separate Byzantine fault-tolerant (BFT) consensus instance for each output incurs repeated computation and communication costs, even when secrets are shared in batches. We present Silk, a computation-efficient, post-quantum-friendly and deterministic randomness beacon under partial synchrony. Silk's sharing protocol, Mulberry, realizes batched asynchronous verifiable secret sharing with partial output (bAVSS-PO), using hash-based share verification to reduce computation cost. Silk further amortizes BFT consensus across a batch of outputs, requiring only one BFT instance per batch. We establish Mulberry's bAVSS-PO properties and Silk's beacon properties under static corruption and the stated security assumptions. We implement Silk and Mulberry in Rust and evaluate their computation and communication costs. In WAN experiments with 121 replicas across eight AWS regions, Silk achieves a throughput of 5.414 outputs/s, 1.53× that of Rondo [NDSS'25] and 4.18× that of Spurt [IEEE S&P'22].

•Jan 1, 2026•0 citations

GRandLine: Adaptively Secure DKG and Randomness Beacon with (Log-)Quadratic Communication Complexity

Renas Bacho, Christoph Lenzen, Julian Loss +2 more

A randomness beacon is a source of continuous and publicly verifiable randomness which is of crucial importance for many applications. Existing works on randomness beacons suffer from at least one of the following drawbacks: (i) security only against static (i.e., non-adaptive) adversaries, (ii) each epoch takes many rounds of communication, or (iii) computationally expensive tools such as proof-of-work (PoW) or verifiable delay functions (VDF). In this work, we introduce GRandLine, the first adaptively secure randomness beacon protocol that overcomes all these limitations while preserving simplicity and optimal resilience in the synchronous network setting. We achieve our result in two steps. First, we design a novel distributed key generation (DKG) protocol GRand that runs in O(λ n2 log n ) bits of communication but, unlike most conventional DKG protocols, outputs both secret and public keys as group elements. Here, λ denotes the security parameter. Second, following termination of GRand, parties can use their keys to derive a sequence of randomness beacon values, where each random value costs only a single asynchronous round and O(λ n2) bits of communication. We implement GRandLine and evaluate it using a network of up to 64 parties running in geographically distributed AWS instances. Our evaluation shows that GRandLine can produce about 2 beacon outputs per second in a network of 64 parties. We compare our protocol to the state-of-the-art randomness beacon protocols OptRand (NDSS '23), BRandPiper (CCS '21), and Drand, in the same setting and observe that it vastly outperforms them.

ACM SIGSAC Conference on Computer and Communications Security (CCS)•Dec 2, 2024•12 citations

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

QuoRand: Distributed Certified Randomness over Mutually-Distrusting Quantum Servers

Ruilin Zhou, Jinglei Cheng, Yuhang Gan +1 more

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.

•Aug 17, 2026•0 citations

Practical Asynchronous Distributed Key Generation

Sourav Das, Thomas Yurek, Zhuolun Xiang +3 more

Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted third party and is a building block to decentralized protocols such as randomness beacons, threshold signatures, and general multiparty computation. Until recently, DKG protocols have assumed the synchronous model and thus are vulnerable when their underlying network assumptions do not hold. The recent advancements in asynchronous DKG protocols are insufficient as they either have poor efficiency or limited functionality, resulting in a lack of concrete implementations. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol. In a network of n nodes, our ADKG protocol can tolerate up to $t\lt n/3$ malicious nodes and have an expected $O(\kappa n^{3})$ communication cost, where $\kappa$ is the security parameter. Our ADKG protocol produces a field element as the secret and is thus compatible with off-the-shelf threshold cryptosystems. We implement our ADKG protocol and evaluate it using a network of up to 128 nodes in geographically distributed AWS instances. Our evaluation shows that our protocol takes as low as 3 and 9.5 seconds to terminate for 32 and 64 nodes, respectively. Also, each node sends only 0.7 Megabytes and 2.9 Megabytes of data during the two experiments, respectively.

IEEE Symposium on Security and Privacy (S&P)•May 1, 2022•119 citations

Powers of Tau in Asynchrony

Sourav Das, Zhuolun Xiang, Ling Ren

The q-Strong Diffie-Hellman (q-SDH) parameters are foundational to efficient constructions of many cryptographic primitives such as zero-knowledge succinct non-interactive arguments of knowledge, polynomial/vector commitments, verifiable secret sharing, and randomness beacon.The only existing method to generate these parameters securely is highly sequential, requires synchrony assumptions, and has very high communication and computation costs.For example, to generate parameters for any given q, each party incurs a communication cost of Ω(nq) and requires Ω(n) rounds.Here n is the number of parties in the secure multiparty computation protocol.Since q is typically large, i.e., on the order of billions, the cost is highly prohibitive.In this paper, we present a distributed protocol to generate q-SDH parameters in an asynchronous network.In a network of n parties, our protocol tolerates up to one-third of malicious parties.Each party incurs a communication cost of O(q+n 2 log q) and the protocol finishes in O(log q + log n) expected rounds.We provide a rigorous security analysis of our protocol.We implement our protocol and evaluate it with up to 128 geographically distributed parties.Our evaluation illustrates that our protocol is highly scalable and results in a 2-6× better runtime and 4-13× better per-party bandwidth usage compared to the state-of-theart synchronous protocol for generating q-SDH parameters.

Network and Distributed System Security Symposium•Jan 1, 2024•5 citations
Having shared access to high-quality random numbers is essential in many important applications. Yet, existing constructions of distributed random beacons still have limitations such as imperfect security guarantees, strong setup or network assumptions, or high costs. In this paper, we present Spurt, an efficient distributed randomness beacon protocol that does not require any trusted or expensive setup and is secure against a malicious adversary that controls up to one-third of the nodes in a partially synchronous network. We formally prove that each output of Spurt is unpredictable, bias-resistant, and publicly verifiable. Spurt has an amortized total communication cost of O(λn2)O(\lambda n^{2})O(λn2) per beacon output where λ\lambdaλ is the security parameter. While designing Spurt, we also design a publicly verifiable secret sharing (PVSS) scheme whose security is based on the standard Decisional Bilinear Diffie-Hellman assumption and does not require a Random Oracle. We implement Spurt and evaluate it using a network of up to 128 nodes running in geographically distributed AWS instances. Our evaluation shows that Spurt can produce about 84 beacon outputs per minute in a network of 32 nodes and is comparable to systems with stronger assumptions or weaker security.
Distributed randomness beacons enable mutually distrustful parties to jointly generate public randomness. Several existing beacons built from secret sharing use costly pairings or group operations to verify shares. Their underlying discrete-logarithm assumptions are also vulnerable to quantum attacks. Moreover, running a separate Byzantine fault-tolerant (BFT) consensus instance for each output incurs repeated computation and communication costs, even when secrets are shared in batches. We present Silk, a computation-efficient, post-quantum-friendly and deterministic randomness beacon under partial synchrony. Silk's sharing protocol, Mulberry, realizes batched asynchronous verifiable secret sharing with partial output (bAVSS-PO), using hash-based share verification to reduce computation cost. Silk further amortizes BFT consensus across a batch of outputs, requiring only one BFT instance per batch. We establish Mulberry's bAVSS-PO properties and Silk's beacon properties under static corruption and the stated security assumptions. We implement Silk and Mulberry in Rust and evaluate their computation and communication costs. In WAN experiments with 121 replicas across eight AWS regions, Silk achieves a throughput of 5.414 outputs/s, 1.53× that of Rondo [NDSS'25] and 4.18× that of Spurt [IEEE S&P'22].
A randomness beacon is a source of continuous and publicly verifiable randomness which is of crucial importance for many applications. Existing works on randomness beacons suffer from at least one of the following drawbacks: (i) security only against static (i.e., non-adaptive) adversaries, (ii) each epoch takes many rounds of communication, or (iii) computationally expensive tools such as proof-of-work (PoW) or verifiable delay functions (VDF). In this work, we introduce GRandLine, the first adaptively secure randomness beacon protocol that overcomes all these limitations while preserving simplicity and optimal resilience in the synchronous network setting. We achieve our result in two steps. First, we design a novel distributed key generation (DKG) protocol GRand that runs in O(λ n2 log n ) bits of communication but, unlike most conventional DKG protocols, outputs both secret and public keys as group elements. Here, λ denotes the security parameter. Second, following termination of GRand, parties can use their keys to derive a sequence of randomness beacon values, where each random value costs only a single asynchronous round and O(λ n2) bits of communication. We implement GRandLine and evaluate it using a network of up to 64 parties running in geographically distributed AWS instances. Our evaluation shows that GRandLine can produce about 2 beacon outputs per second in a network of 64 parties. We compare our protocol to the state-of-the-art randomness beacon protocols OptRand (NDSS '23), BRandPiper (CCS '21), and Drand, in the same setting and observe that it vastly outperforms them.
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.
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.
Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted third party and is a building block to decentralized protocols such as randomness beacons, threshold signatures, and general multiparty computation. Until recently, DKG protocols have assumed the synchronous model and thus are vulnerable when their underlying network assumptions do not hold. The recent advancements in asynchronous DKG protocols are insufficient as they either have poor efficiency or limited functionality, resulting in a lack of concrete implementations. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol. In a network of n nodes, our ADKG protocol can tolerate up to t<n/3t\lt n/3t<n/3 malicious nodes and have an expected O(κn3)O(\kappa n^{3})O(κn3) communication cost, where κ\kappaκ is the security parameter. Our ADKG protocol produces a field element as the secret and is thus compatible with off-the-shelf threshold cryptosystems. We implement our ADKG protocol and evaluate it using a network of up to 128 nodes in geographically distributed AWS instances. Our evaluation shows that our protocol takes as low as 3 and 9.5 seconds to terminate for 32 and 64 nodes, respectively. Also, each node sends only 0.7 Megabytes and 2.9 Megabytes of data during the two experiments, respectively.
The q-Strong Diffie-Hellman (q-SDH) parameters are foundational to efficient constructions of many cryptographic primitives such as zero-knowledge succinct non-interactive arguments of knowledge, polynomial/vector commitments, verifiable secret sharing, and randomness beacon.The only existing method to generate these parameters securely is highly sequential, requires synchrony assumptions, and has very high communication and computation costs.For example, to generate parameters for any given q, each party incurs a communication cost of Ω(nq) and requires Ω(n) rounds.Here n is the number of parties in the secure multiparty computation protocol.Since q is typically large, i.e., on the order of billions, the cost is highly prohibitive.In this paper, we present a distributed protocol to generate q-SDH parameters in an asynchronous network.In a network of n parties, our protocol tolerates up to one-third of malicious parties.Each party incurs a communication cost of O(q+n 2 log q) and the protocol finishes in O(log q + log n) expected rounds.We provide a rigorous security analysis of our protocol.We implement our protocol and evaluate it with up to 128 geographically distributed parties.Our evaluation illustrates that our protocol is highly scalable and results in a 2-6× better runtime and 4-13× better per-party bandwidth usage compared to the state-of-theart synchronous protocol for generating q-SDH parameters.