Paper 2020/1590

RandPiper -- Reconfiguration-Friendly Random Beacons with Quadratic Communication

Adithya Bhat, Nibesh Shrestha, Aniket Kate, and Kartik Nayak


Random beacon protocols provide a continuous public source of randomness and their applications range from public lotteries to zero-knowledge proofs. Existing random beacon protocols in the bounded synchronous model sacrifice either the fault tolerance or the communication complexity for security, or ease of reconfigurability. This work overcomes the challenges with the existing works through a novel communication efficient combination of state machine replication and (publicly) verifiable secret sharing (PVSS/VSS) protocols. We first design a new Byzantine fault-tolerant state machine replication protocol with $O(\kappa n^2)$ bits communication per consensus decision without using threshold signatures. Next, we design GRandPiper (Good Pipelined Random beacon), a random beacon protocol with bias-resistance and unpredictability, that uses PVSS and has a communication complexity of $O(\kappa n^2)$ always (best and worst cases), for a static adversary. However, GRandPiper allows an adaptive adversary to predict beacon values up to $t+1$ epochs into the future. Therefore, we design BRandPiper (Better RandPiper), that uses VSS and has a communication complexity of $O(\kappa fn^2)$, where $f$ is the actual number of faults, while offering a strong unpredictability with an advantage of only a single round even for an adaptive adversary.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. CCS 2021
Random Beacons
Contact author(s)
bhat24 @ purdue edu
nxs4564 @ rit edu
aniket @ purdue edu
kartik @ cs duke edu
2022-02-17: last of 4 revisions
2020-12-21: received
See all versions
Short URL
Creative Commons Attribution


      author = {Adithya Bhat and Nibesh Shrestha and Aniket Kate and Kartik Nayak},
      title = {RandPiper -- Reconfiguration-Friendly Random Beacons with Quadratic Communication},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1590},
      year = {2020},
      doi = {10.1145/3460120.3484574},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.