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

IEEE Symposium on Security and Privacy (S&P)May 1, 202247 citations

On public-coin zero-error randomized communication complexity

Ben Davis, Hamed Hatami, William Pires +2 more

Information Processing LettersJun 22, 20222 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.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, 202410 citations

Round Complexity of Common Randomness Generation: The Amortized Setting

Noah Golowich, Madhu Sudan

In this work we study the effect of rounds of interaction on the common randomness generation (CRG) problem. In the CRG problem, two parties, Alice and Bob, receive samples Xi and Yi, respectively, where (Xi, Yi) are drawn jointly from a source distribution μ. The two parties wish to agree on a common random key consisting of many bits of randomness, by exchanging messages that depend on each party's respective input and the previous messages. In this work we study the amortized version of the problem, i.e., the number of bits of communication needed per random bit output by Alice and Bob, in the limit as the number of bits generated tends to infinity. The amortized version of the CRG problem has been extensively studied in the information theory literature, though very little was known about the effect of interaction on this problem. Recently Bafna et al. (SODA 2019) considered the non-amortized version of the problem (so here the goal of the interaction is to generate a fixed number of random bits): they gave a family of sources μr,n parameterized by r,n ϵ ℕ, such that with r + 2 rounds of communication one can generate n bits of common randomness with this source with O(r log n) communication, whereas with roughly r/2 rounds the communication complexity is Ω(n/ poly log n). Note in particular that their source is designed with the target number of bits in mind and hence the result does not apply to the amortized setting. In this work we strengthen the work of Bafna et al. in two ways: First we show that the results extend to the classical amortized setting. We also reduce the gap between the round complexity in the upper and lower bounds to an additive constant. Specifically we show that for every pair r, n ϵ ℕ the (amortized) communication complexity to generate Ω(n) bits of common randomness from the source μr,n using r + 2 rounds of communication is O(r log n) whereas the amortized communication required to generate the same amount of randomness from r rounds is . Our techniques exploit known connections between information complexity and CRG, and the main novelty is our ability to analyze the information complexity of protocols getting inputs from the source μr,n.In this work we study the effect of rounds of interaction on the common randomness generation (CRG) problem. In the CRG problem, two parties, Alice and Bob, receive samples Xi and Yi, respectively, where (Xi, Yi) are drawn jointly from a source distribution μ. The two parties wish to agree on a common random key consisting of many bits of randomness, by exchanging messages that depend on each party's respective input and the previous messages. In this work we study the amortized version of the problem, i.e., the number of bits of communication needed per random bit output by Alice and Bob, in the limit as the number of bits generated tends to infinity. The amortized version of the CRG problem has been extensively studied in the information theory literature, though very little was known about the effect of interaction on this problem. Recently Bafna et al. (SODA 2019) considered the non-amortized version of the problem (so here the goal of the interaction is to generate a fixed number of random bits): they gave a family of sources μr,n parameterized by r,n ϵ ℕ, such that with r + 2 rounds of communication one can generate n bits of common randomness with this source with O(r log n) communication, whereas with roughly r/2 rounds the communication complexity is Ω(n/ poly log n). Note in particular that their source is designed with the target number of bits in mind and hence the result does not apply to the amortized setting. In this work we strengthen the work of Bafna et al. in two ways: First we show that the results extend to the classical amortized setting. We also reduce the gap between the round complexity in the upper and lower bounds to an additive constant. Specifically we show that for every pair r, n ϵ ℕ the (amortized) communication complexity to generate Ω(n) bits of common randomness from the source μr,n using r + 2 rounds of communication is O(r log n) whereas the amortized communication required to generate the same amount of randomness from r rounds is . Our techniques exploit known connections between information complexity and CRG, and the main novelty is our ability to analyze the information complexity of protocols getting inputs from the source μr,n.

arXiv:1909.00323Society for Industrial and Applied Mathematics eBooksDec 23, 20193 citations

Uniform Common Randomness Generation Over Arbitrary Point-to-Point Channels

Rami Ezzine, Moritz Wiese, Christian Deppe +1 more

IEEE Transactions on Information TheoryApr 30, 20250 citations

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.