Paper 2022/1389

Practical Asynchronous High-threshold Distributed Key Generation and Distributed Polynomial Sampling

Sourav Das, University of Illinois Urbana-Champaign
Zhuolun Xiang, Aptos
Lefteris Kokoris-Kogias, IST Austria
Ling Ren, University of Illinois Urbana-Champaign

Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a trusted party. DKG is an essential building block to many decentralized protocols such as randomness beacons, threshold signatures, Byzantine consensus, and multiparty computation. While significant progress has been made recently, existing asynchronous DKG constructions are inefficient when the reconstruction threshold is larger than one-third of the total nodes. In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol among $n=3t+1$ nodes that can tolerate up to $t$ malicious nodes and support any reconstruction threshold $\ell\ge t$. Our protocol has an expected $O(\kappa n^3)$ communication cost, where $\kappa$ is a security parameter, and only assumes the hardness of Discrete Logarithm. The core ingredient of our ADKG protocol is an asynchronous protocol to secret share a random polynomial of degree $\ell\ge t$, which has other applications such as asynchronous proactive secret sharing and asynchronous multiparty computation. We implement our high-threshold ADKG protocol and evaluate it using a network of up to 128 geographically distributed nodes. Our evaluation shows that our high-threshold ADKG protocol reduces the running time by $90\%$ and reduces the bandwidth usage by $80\%$ over state-of-the-art.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. USENIX Security 2023
Distributed Key GenerationHigh-thresholdAsynchronous NetworksDistributed Polynomial Sampling
Contact author(s)
souravd2 @ illinois edu
xiangzhuolun @ gmail com
ekokoris @ ist ac at
renling @ illinois edu
2023-04-24: revised
2022-10-14: received
See all versions
Short URL
Creative Commons Attribution


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