Fully distributed verifiable random functions and their application to decentralised random beacons

Galindo, D.; Liu, J.; Ordean, M.; Wong, J.-M. ORCID: 2021 Fully distributed verifiable random functions and their application to decentralised random beacons. 2021 IEEE European Symposium on Security and Privacy (EuroS&P). 88-102.

Full text not available from this repository. (Request a copy)


We provide a systematic analysis of two related multiparty protocols, namely (Non-Interactive Fully) Distributed Verifiable Random Functions (DVRFs) and Decentralised Random Beacons (DRBs), including their syntax and definition of robustness and privacy properties. These two protocols are run by multiple network nodes where each node contributes with a partial evaluation and the collection of these partial values is used to evaluate a pseudorandom function. We refine current pseudorandomness definitions for distributed functions and show that the privacy provided by strong pseudorandomness, where an adversary is allowed to make partial function evaluation queries on the challenge value, is strictly better than that provided by standard pseudorandomness, where such adversarial queries are disallowed. We provide two new DVRF instantiations, named DDH-DVRF and GLOW-DVRF, that meet strong pseudorandomness under widely accepted cryptographic assumptions. We show the usefulness of our DRB formalism in two different ways. Firstly, we give a rigorous treatment of a folklore generic construction that builds a Decentralized Random Beacon from any DVRF instance and prove that it satisfies robustness and pseudorandomness provided that the original DVRF protocol is secure. Secondly, we capture several existing DRB protocols from academia and industry within our framework, which serves as an evidence of its wider applicability. Finally, we report on experimental evaluations of our newly introduced DVRFs with implementations under different cryptographic libraries, and we also report preliminary benchmark results on two of the DRBs obtained from the generic DVRF-to-DRB transformation. Our benchmarks can be independently verified as we provide an open source C++ reference implementation of the new DVRFs. Finally, we conclude that our new DRB instantiations are the most efficient instantiations currently available while enjoying strong and formally proven security properties.

Item Type: Publication - Article
Digital Object Identifier (DOI):
Additional Keywords: Blockchain; Cryptography; Distributed Computation; Implementation; Leader Election; Open Source; Pseudorandom Functions; Random Beacon; Threshold Signatures
Related URLs:
Date made live: 25 Nov 2021 14:42 +0 (UTC)

Actions (login required)

View Item View Item

Document Downloads

Downloads for past 30 days

Downloads per month over past year

More statistics for this item...