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: ia.cr/2012/377 Discussion forum: Show discussion | Start new discussion