Paper 2025/006

Nearly Quadratic Asynchronous Distributed Key Generation from Recursive Consensus

Abstract

Distributed key generation (DKG) is a Byzantine fault tolerant protocol among a set of $n$ parties that enables generation of a public-secret key pair for threshold cryptosystems without a trusted third party. It serves as a building block for many decentralized protocols, such as randomness beacons, threshold encryption and signing, consensus, and general multi-party computation. Of particular importance are asynchronous DKG protocols with low communication and round complexity. However, all existing constructions for asynchronous DKG require cubic or higher communication costs in the number of parties (including setup costs) to terminate. This severely limits their practicality, especially in large-scale systems such as the internet or blockchains, where communication and round complexity are the main bottlenecks to efficiency. In this paper, we present the first asynchronous DKG protocol that overcomes this limitation. Our protocol has the following desirable properties. It is resilient to a strongly adaptive adversary that can corrupt up to $f < n/3$ parties. Parameterized by a natural number $1 \leq k \leq \log{n}$, it has an expected communication cost of $O(\lambda^2 n^{2+1/k})$ bits and terminates in expected $O(k)$ rounds, where $\lambda$ denotes the security parameter. Furthermore, for setup, it requires a plain public key infrastructure (PKI) and random oracles, which is standard in the literature on DKG protocols. From a conceptual perspective, our main contribution is to adapt the classical recursive paradigm (for distributed protocols) from the synchronous to the asynchronous model and to apply it to asynchronous DKG.