SCRAPE: Scalable Randomness Attested by Public Entities

Ignacio Cascudo; Bernardo David

Paper 2017/216

SCRAPE: Scalable Randomness Attested by Public Entities

Ignacio Cascudo and Bernardo David

Abstract

Uniform randomness beacons whose output can be publicly attested to be unbiased are required in several cryptographic protocols. A common approach to building such beacons is having a number parties run a coin tossing protocol with guaranteed output delivery (so that adversaries cannot simply keep honest parties from obtaining randomness, consequently halting protocols that rely on it). However, current constructions face serious scalability issues due to high computational and communication overheads. We present a coin tossing protocol for an honest majority that allows for any entity to verify that an output was honestly generated by observing publicly available information (even after the execution is complete), while achieving both guaranteed output delivery and scalability. The main building block of our construction is the first Publicly Verifiable Secret Sharing scheme for threshold access structures that requires only O(n) exponentiations. Previous schemes required O(nt) exponentiations (where t is the threshold) from each of the parties involved, making them unfit for scalable distributed randomness generation, which requires t=n/2 and thus O(n^2) exponentiations.

Note: Added full benchmarks of proposed protocols and notes about instantiating the pairing based protocol over asymmetric bilinear groups.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Published elsewhere. Major revision. ACNS 2017
Keywords: Publicly Verifiable Secret Sharing Randomness Generation Guaranteed Output Delivery Coin Tossing
Contact author(s): bernardo david @ iohk io
History: 2017-05-02: revised; 2017-03-04: received; See all versions
Short URL: https://ia.cr/2017/216
License: CC BY

BibTeX

@misc{cryptoeprint:2017/216,
      author = {Ignacio Cascudo and Bernardo David},
      title = {{SCRAPE}: Scalable Randomness Attested by Public Entities},
      howpublished = {Cryptology {ePrint} Archive, Paper 2017/216},
      year = {2017},
      url = {https://eprint.iacr.org/2017/216}
}