Paper 2012/377

Distributed Key Generation in the Wild

Aniket Kate, Yizhou Huang, and Ian Goldberg


Distributed key generation (DKG) has been studied extensively in the cryptographic literature. However, it has never been examined outside of the synchronous setting, and the known DKG protocols cannot guarantee safety or liveness over the Internet. In this work, we present the first realistic DKG protocol for use over the Internet. We propose a practical system model for the Internet and define an efficient verifiable secret sharing (VSS) scheme in it. We observe the necessity of Byzantine agreement for asynchronous DKG and analyze the difficulty of using a randomized protocol for it. Using our VSS scheme and a leader-based agreement protocol, we then design a provably secure DKG protocol. We also consider and achieve cryptographic properties such as uniform randomness of the shared secret and compare static versus adaptive adversary models. Finally, we implement our DKG protocol, and establish its efficiency and reliability by extensively testing it on the PlanetLab platform. Counter to a general non-scalability perception about asynchronous systems, our experiments demonstrate that our asynchronous DKG protocol scales well with the system size and it is suitable for realizing multiparty computation and threshold cryptography over the Internet.

Available format(s)
Cryptographic protocols
Publication info
Published elsewhere. A preliminary version of this paper appeared at IEEE ICDCS '09.
asynchronous communication modeldistributed key generationuniform randomnessimplementation
Contact author(s)
aniket @ mpi-sws org
2012-07-05: received
Short URL
Creative Commons Attribution


      author = {Aniket Kate and Yizhou Huang and Ian Goldberg},
      title = {Distributed Key Generation in the Wild},
      howpublished = {Cryptology ePrint Archive, Paper 2012/377},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.