Cryptology ePrint Archive: Report 2021/1096

Mt. Random: Multi-Tiered Randomness Beacons

Ignacio Cascudo and Bernardo David and Omer Shlomovits and Denis Varlakov

Abstract: Many decentralized applications require a common source of randomness that cannot be biased by any single party. Randomness beacons provide such a functionality, allowing any (third) party to periodically obtain random values and verify their validity (i.e. check that they are indeed produced by the beacon and consequently random). Protocols implementing randomness beacons have been constructed via a number of different techniques. In particular, several beacons based on time-based cryptography, Publicly Verifiable Secret Sharing (PVSS), Verifiable Random Functions (VRF) and their threshold variant (TVRF) have been proposed. These protocols provide a range of efficiency/randomness quality trade-offs but guarantee security under different setups, assumptions and adversarial models.

In this work, we propose Mt. Random, a multi-tiered randomness beacon that combines PVSS and (T)VRF techniques in order to provide an optimal efficiency/quality trade-off without sacrificing security guarantees. Each tier is based on a different technique and provides a constant stream of random outputs offering progressing efficiency vs. quality trade-offs: true uniform randomness is refreshed less frequently than pseudorandomness, which in turn is refreshed less frequently than (bounded) biased randomness. This wide span of efficiency/quality allows for applications to consume random outputs from an optimal point in this trade-off spectrum. In order to achieve these results, we construct two new building blocks of independent interest: GULL, a PVSS-based beacon that preprocesses a large batch of random outputs but allows for gradual release of smaller ``sub-batches'', which is a first in the literature of randomness beacons; and a publicly verifiable and unbiasable protocol for Distributed Key Generation protocol (DKG), which is significantly more efficient than most of previous DKGs secure under standard assumptions and closely matches the efficiency of the currently most efficient biasable DKG protocol.

Mt. Random (and all of its building blocks) can be proven secure under the standard DDH assumption (in the random oracle model) using only a bulletin board as setup, which is a requirement for the vast majority of beacons. We showcase the efficiency of our novel building blocks and of the Mt. Random beacon via benchmarks made with a prototype implementation. Our experimental results confirm the benefits of our multi-tiered approach, showing that even though higher tiers provide fresh random outputs more often, lower tiers can be executed fast enough to keep higher tiers freshly seeded.

Category / Keywords: cryptographic protocols / Randomness, Random Beacons, Publicly Verifiable Secret Sharing, Distributed Key Generation

Date: received 25 Aug 2021

Contact author: ignacio cascudo at imdea org, bernardo at bmdavid com, omer at zengo com, denis at zengo com

Available format(s): PDF | BibTeX Citation

Version: 20210826:115152 (All versions of this report)

Short URL: ia.cr/2021/1096


[ Cryptology ePrint archive ]