Cryptology ePrint Archive: Report 2021/1591

Practical Asynchronous Distributed Key Generation

Sourav Das and Tom Yurek and Zhuolun Xiang and Andrew Miller and Lefteris Kokoris-Kogias and Ling Ren

Abstract: Distributed Key Generation (DKG) is a technique to bootstrap threshold cryptosystems without a central trust. DKG can be a building block to decentralized protocols such as randomness beacons, threshold signatures, and general multiparty computation. Many previous DKG protocols assume the synchronous model and asynchronous DKG received attention only recently. Existing asynchronous DKG protocols have either poor efficiency or limited functionality, resulting in a lack of concrete implementations.

In this paper, we present a simple and concretely efficient asynchronous DKG (ADKG) protocol. In a network of $n$ nodes, our ADKG protocol can tolerate up to $t<n/3$ malicious nodes and have an expected $O(\kappa n^3)$ communication cost, where $\kappa$ is the security parameter. Our ADKG protocol produces a field element as the secret and is thus compatible with off-the-shelf threshold cryptosystems. We implement our ADKG protocol and evaluate it using a network of up to 128 nodes in geographically distributed AWS instances. Our evaluation shows that our protocol takes as low as 3 and 9.5 seconds to terminate for 32 and 64 nodes, respectively. Also, each node sends only 0.7 Megabytes and 2.9 Megabytes of data during the two experiments, respectively.

Category / Keywords: cryptographic protocols / Distributed Key Generation; Asynchronous Networks; Threshold Cryptography; Distributed Cryptography;

Date: received 4 Dec 2021, last revised 4 Dec 2021

Contact author: souravd2 at illinois edu, yurek2 at illinois edu, xiangzl at illinois edu, soc1024 at illinois edu, ekokoris at ist ac at, renling at illinois edu

Available format(s): PDF | BibTeX Citation

Version: 20211206:035203 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]