Cryptology ePrint Archive: Report 2012/377

Distributed Key Generation in the Wild

Aniket Kate and Yizhou Huang and Ian Goldberg

Abstract: 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.

Category / Keywords: cryptographic protocols / asynchronous communication model, distributed key generation, uniform randomness, implementation

Publication Info: A preliminary version of this paper appeared at IEEE ICDCS '09.

Date: received 4 Jul 2012

Contact author: aniket at mpi-sws org

Available format(s): PDF | BibTeX Citation

Version: 20120705:121911 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]