Paper 2021/1591

Practical Asynchronous Distributed Key Generation

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


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<n/3$ malicious nodes and have an expected $O(\kappa n^3)$ communication cost, where $\kappa$ 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.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. IEEE S&P 2022
Distributed Key GenerationAsynchronous NetworksThreshold CryptographyDistributed Cryptography
Contact author(s)
souravd2 @ illinois edu
yurek2 @ illinois edu
xiangzl @ illinois edu
soc1024 @ illinois edu
ekokoris @ ist ac at
renling @ illinois edu
2022-04-08: revised
2021-12-06: received
See all versions
Short URL
Creative Commons Attribution


      author = {Sourav Das and Thomas Yurek and Zhuolun Xiang and Andrew Miller and Lefteris Kokoris-Kogias and Ling Ren},
      title = {Practical Asynchronous Distributed Key Generation},
      howpublished = {Cryptology ePrint Archive, Paper 2021/1591},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.