Paper 2021/005

Aggregatable Distributed Key Generation

Kobi Gurkan, Philipp Jovanovic, Mary Maller, Sarah Meiklejohn, Gilad Stern, and Alin Tomescu

Abstract

In this paper, we introduce a distributed key generation (DKG) protocol with aggregatable and publicly-verifiable transcripts. Compared with prior publicly-verifiable approaches, our DKG reduces the size of the final transcript and the time to verify it from $O(n^2)$ to $O(n log(n))$, where $n$ denotes the number of parties. As compared with prior non-publicly-verifiable approaches, our DKG leverages gossip rather than all-to-all communication to reduce verification and communication complexity. 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 $71$ms to share and $359$ms to verify the overall transcript, while for $8192$ parties, it takes $8$s and $42.2$s respectively.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
distributed key generation
Contact author(s)
mary maller @ ethereum org
History
2021-01-02: received
Short URL
https://ia.cr/2021/005
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2021/005,
      author = {Kobi Gurkan and Philipp Jovanovic and Mary Maller and Sarah Meiklejohn and Gilad Stern and Alin Tomescu},
      title = {Aggregatable Distributed Key Generation},
      howpublished = {Cryptology ePrint Archive, Paper 2021/005},
      year = {2021},
      note = {\url{https://eprint.iacr.org/2021/005}},
      url = {https://eprint.iacr.org/2021/005}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.