International Association for Cryptologic Research

International Association
for Cryptologic Research


Aggregatable Distributed Key Generation

Kobi Gurkan , cLabs, Ethereum Foundation
Philipp Jovanovic , University College London
Mary Maller , Ethereum Foundation
Sarah Meiklejohn , University College London, Google
Gilad Stern , Hebrew University
Alin Tomescu , VMware Research
DOI: 10.1007/978-3-030-77870-5_6 (login may be required)
Search ePrint
Search Google
Conference: EUROCRYPT 2021
Abstract: In this paper we introduce a distributed key generation (DKG) protocol with aggregatable and publicly verifiable transcripts. As compared with prior approaches, our DKG reduces the size of the final transcript and the time to verify it from O(n^2) to O(n), where n denotes the number of parties. We also revisit existing DKG security definitions, which are quite strong, and propose new and natural relaxations. As a result, we can prove the security of our aggregatable DKG as well as that of several existing DKGs, including the popular Pedersen variant. We show that, under these new definitions, these existing DKGs can be used to yield secure threshold variants of popular cryptosystems such as El-Gamal encryption and BLS signatures. We also prove that our DKG can be securely combined with a new efficient verifiable unpredictable function (VUF), whose security we prove in the random oracle model. Finally, we experimentally evaluate our DKG and show that the per-party overheads scale linearly and are practical: for 64 parties it takes 71ms to share and 359ms to verify the overall transcript, while these respective costs for 8192 parties are 8s and 42.2s.
Video from EUROCRYPT 2021
  title={Aggregatable Distributed Key Generation},
  author={Kobi Gurkan and Philipp Jovanovic and Mary Maller and Sarah Meiklejohn and Gilad Stern and Alin Tomescu},