Paper 2023/1755

HashRand: Efficient Asynchronous Random Beacon without Threshold Cryptographic Setup

Akhil Bandarupalli, Purdue University West Lafayette
Adithya Bhat, Visa Research
Saurabh Bagchi, Purdue University West Lafayette
Aniket Kate, Purdue University West Lafayette, Supra Research
Michael Reiter, Duke University

Regular access to unpredictable and bias-resistant randomness is important for applications such as blockchains, voting, and secure distributed computing. Distributed random beacon protocols address this need by distributing trust across multiple nodes, with the majority of them assumed to be honest. These protocols have found applications in blockchain technology, leading to the proposal of several distributed random beacon protocols, with some already implemented. However, many current random beacon systems rely on threshold cryptographic setups or exhibit high computational costs, while others assume partial or bounded synchronous networks. To overcome these limitations, we propose HashRand, a computation and communication-efficient asynchronous random beacon protocol that uses a secure Hash function to generate beacons and pairwise secure channels. HashRand has a per-node communication complexity of $\mathcal{O}(\lambda n \log(n))$ bits per beacon. The computational efficiency of HashRand is attributed to the two orders of magnitude lower time of a one-way Hash computation compared to discrete log exponentiation. Interestingly, besides reduced overhead, HashRand achieves Post-Quantum security by leveraging the secure Hash function against quantum adversaries, setting it apart from other random beacon protocols that use discrete log cryptography. In a geo-distributed testbed of $n=160$ nodes, HashRand produces 1 beacon every second, which is at least 4x higher than Spurt. We also demonstrate the practical utility of HashRand by implementing a Post-Quantum secure Asynchronous SMR protocol, which has a response rate of over 122k txns per second over a WAN at $n=40$ nodes.

Available format(s)
Cryptographic protocols
Publication info
Random BeaconHash functionAsynchronous protocol
Contact author(s)
abandaru @ purdue edu
haxolotl research @ gmail com
sbagchi @ purdue edu
aniket @ purdue edu
michael reiter @ duke edu
2023-12-01: revised
2023-11-13: received
See all versions
Short URL
Creative Commons Attribution


      author = {Akhil Bandarupalli and Adithya Bhat and Saurabh Bagchi and Aniket Kate and Michael Reiter},
      title = {HashRand: Efficient Asynchronous Random Beacon without Threshold Cryptographic Setup},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1755},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.