Paper 2021/1096

Mt. Random: Multi-Tiered Randomness Beacons

Ignacio Cascudo, IMDEA Software Institute
Bernardo David, IT University of Copenhagen
Omer Shlomovits
Denis Varlakov
Abstract

Many decentralized applications require a common source of randomness that cannot be biased or predicted by any single party. Randomness beacons provide such a functionality, allowing parties to periodically obtain fresh random outputs and verify that they are computed correctly. In this work, we propose Mt. Random, a multi-tiered randomness beacon that combines Publicly Verifiable Secret Sharing (PVSS) and (Threshold) Verifiable Random Function (VRF) techniques in order to provide efficiency/randomness quality trade-offs with security under the standard DDH assumption (in the random oracle model) using only a bulletin board as setup (a requirement for the vast majority of beacons). Each tier provides a constant stream of random outputs offering progressive 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. We showcase the efficiency of our novel building blocks and of the Mt. Random beacon via benchmarks made with a prototype implementation.

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Minor revision. ACNS 23
DOI
10.1007/978-3-031-33491-7_24
Keywords
RandomnessRandom BeaconsPublicly Verifiable Secret SharingDistributed Key Generation
Contact author(s)
ignacio cascudo @ imdea org
bernardo @ bmdavid com
omer shlomovits @ gmail com
denis @ varlakov me
History
2023-09-12: revised
2021-08-26: received
See all versions
Short URL
https://ia.cr/2021/1096
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/1096,
      author = {Ignacio Cascudo and Bernardo David and Omer Shlomovits and Denis Varlakov},
      title = {Mt. Random: Multi-Tiered Randomness Beacons},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1096},
      year = {2021},
      doi = {10.1007/978-3-031-33491-7_24},
      note = {\url{https://eprint.iacr.org/2021/1096}},
      url = {https://eprint.iacr.org/2021/1096}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.