Practical Asynchronous Distributed Key Generation

Sourav Das, Thomas Yurek, Zhuolun Xiang, Andrew Miller, Lefteris Kokoris-Kogias, Ling Ren

Research output: Chapter in Book/Report/Conference proceedingConference contribution


Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted third party and is a building block to decentralized protocols such as randomness beacons, threshold signatures, and general multiparty computation. Until recently, DKG protocols have assumed the synchronous model and thus are vulnerable when their underlying network assumptions do not hold. The recent advancements in asynchronous DKG protocols are insufficient as they either have poor efficiency or limited functionality, resulting in a lack of concrete implementations. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol. In a network of n nodes, our ADKG protocol can tolerate up to t\lt n/3 malicious nodes and have an expected O(? n{3}) communication cost, where ? is the security parameter. Our ADKG protocol produces a field element as the secret and is thus compatible with off-the-shelf threshold cryptosystems. We implement our ADKG protocol and evaluate it using a network of up to 128 nodes in geographically distributed AWS instances. Our evaluation shows that our protocol takes as low as 3 and 9.5 seconds to terminate for 32 and 64 nodes, respectively. Also, each node sends only 0.7 Megabytes and 2.9 Megabytes of data during the two experiments, respectively.

Original languageEnglish (US)
Title of host publicationProceedings - 43rd IEEE Symposium on Security and Privacy, SP 2022
PublisherInstitute of Electrical and Electronics Engineers Inc.
Number of pages17
ISBN (Electronic)9781665413169
StatePublished - 2022
Event43rd IEEE Symposium on Security and Privacy, SP 2022 - San Francisco, United States
Duration: May 23 2022May 26 2022

Publication series

NameProceedings - IEEE Symposium on Security and Privacy
ISSN (Print)1081-6011


Conference43rd IEEE Symposium on Security and Privacy, SP 2022
Country/TerritoryUnited States
CitySan Francisco


  • Distributed-Key-Generation,-Asynchronous-Networks,-Threshold-Cryptography,-Distributed-Cryptography

ASJC Scopus subject areas

  • Safety, Risk, Reliability and Quality
  • Software
  • Computer Networks and Communications


Dive into the research topics of 'Practical Asynchronous Distributed Key Generation'. Together they form a unique fingerprint.

Cite this