Paper 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.