Paper 2021/100

SPURT: Scalable Distributed Randomness Beacon with Transparent Setup

Sourav Das, University of Illinois Urbana-Champaign
Vinith Krishnan, University of Illinois Urbana-Champaign
Irene Miriam Isaac, University of Illinois Urbana-Champaign
Ling Ren, University of Illinois Urbana-Champaign

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.

Note: Partially synchronous Randomness beacon with Quadratic Communication, Nearly simultaneous decision SMR, New PVSS scheme assuming DBDH and experimental results.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. IEEE S&P 2022
Random BeaconsDistributed RandomnessPVSS
Contact author(s)
souravd2 @ illinois edu
vinithk2 @ illinois edu
irenemi2 @ illinois edu
renling @ illinois edu
2023-12-14: last of 4 revisions
2021-01-27: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sourav Das and Vinith  Krishnan and Irene Miriam Isaac and Ling Ren},
      title = {{SPURT}: Scalable Distributed Randomness Beacon with Transparent Setup},
      howpublished = {Cryptology ePrint Archive, Paper 2021/100},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.