Paper 2023/1887

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

Renas Bacho, CISPA Helmholtz Center for Information Security, Saarland University
Christoph Lenzen, CISPA Helmholtz Center for Information Security
Julian Loss, CISPA Helmholtz Center for Information Security
Simon Ochsenreither, Saarland University
Dimitrios Papachristoudis

A randomness beacon is a source of continuous and publicly verifiable randomness which is of crucial importance for many applications. Existing works on distributed randomness beacons suffer from at least one of the following drawbacks: (i) security only against a static/non-adaptive adversary, (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 paper, we introduce $\mathsf{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 $\mathsf{GRand}$ that runs in $\mathcal{O}(\lambda n^2\log{n})$ bits of communication but, unlike most conventional DKG protocols, outputs both secret and public keys as group elements. Here, $\lambda$ denotes the security parameter. Second, following termination of $\mathsf{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 $\mathcal{O}(\lambda n^2)$ bits of communication. We implement $\mathsf{GRandLine}$ and evaluate it using a network of up to 64 parties running in geographically distributed AWS instances. Our evaluation shows that $\mathsf{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 in the same setting and observe that it vastly outperforms them.

Available format(s)
Cryptographic protocols
Publication info
Adaptive SecurityRandomness BeaconAggregatable PVSSDKGPairing-Based Cryptography
Contact author(s)
renas bacho @ cispa de
lenzen @ cispa de
loss @ cispa de
s ochsenreither @ gmail com
jim papachristoudis @ gmail com
2023-12-17: last of 4 revisions
2023-12-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Renas Bacho and Christoph Lenzen and Julian Loss and Simon Ochsenreither and Dimitrios Papachristoudis},
      title = {{GRandLine}: Adaptively Secure {DKG} and Randomness Beacon with (Almost) Quadratic Communication Complexity},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1887},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.