Paper 2022/1678

Practical Asynchronous Distributed Key Generation: Improved Efficiency, Weaker Assumption, and Standard Model

Haibin Zhang, Beijing Institute of Technology
Sisi Duan, Tsinghua University
Chao Liu, Quanzhou Normal University
Boxin Zhao, Zhongguancun Laboratory
Xuanji Meng, Tsinghua University
Shengli Liu, Shanghai Jiao Tong University
Yong Yu, Shaanxi Normal University
Fangguo Zhang, Sun Yat-sen University
Liehuang Zhu, Beijing Institute of Technology

Distributed key generation (DKG) allows bootstrapping threshold cryptosystems without relying on a trusted party, nowadays enabling fully decentralized applications in blockchains and multiparty computation (MPC). While we have recently seen new advancements for asynchronous DKG (ADKG) protocols, their performance remains the bottleneck for many applications, with only one protocol being implemented (DYX+ ADKG, IEEE S&P 2022). DYX+ ADKG relies on the Decisional Composite Residuosity assumption (being expensive to instantiate) and the Decisional Diffie-Hellman assumption, incurring a high latency (more than 100s with a failure threshold of 16). Moreover, the security of DYX+ ADKG is based on the random oracle model (ROM) which takes hash function as an ideal function; assuming the existence of random oracle is a strong assumption, and up to now, we cannot find any theoretically-sound implementation. Furthermore, the ADKG protocol needs public key infrastructure (PKI) to support the trustworthiness of public keys. The strong models (ROM and PKI) further limit the applicability of DYX+ ADKG, as they would add extra and strong assumptions to underlying threshold cryptosystems. For instance, if the original threshold cryptosystem works in the standard model, then the system using DYX+ ADKG would need to use ROM and PKI. In this paper, we design and implement a modular ADKG protocol that offers improved efficiency and stronger security guarantees. We explore a novel and much more direct reduction from ADKG to the underlying blocks, reducing the computational overhead and communication rounds of ADKG in the normal case. Our protocol works for both the low-threshold and high-threshold scenarios, being secure under the standard assumption (the well-established discrete logarithm assumption only) in the standard model (no trusted setup, ROM, or PKI).

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. IEEE/IFIP DSN 2023
distributed key generationasychronous distributed key generationADKGconsensusRABAAVSSACSSlocal coins
Contact author(s)
bchainzhang @ aliyun com
duansisi @ tsinghua edu cn
cliu717 @ 163 com
zhaobx @ mail zgclab edu cn
mxj21 @ mails tsinghua edu cn
slliu @ sjtu edu cn
yuyong @ snnu edu cn
isszhfg @ mail sysu edu cn
liehuangz @ bit edu cn
2023-07-11: revised
2022-12-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Haibin Zhang and Sisi Duan and Chao Liu and Boxin Zhao and Xuanji Meng and Shengli Liu and Yong Yu and Fangguo Zhang and Liehuang Zhu},
      title = {Practical Asynchronous Distributed Key Generation: Improved Efficiency, Weaker Assumption, and Standard Model},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1678},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.