Paper 2026/1159

Quadratic Asynchronous DKG from Plain Setup

Abstract

Asynchronous distributed key generation (ADKG) is a fundamental primitive for building threshold cryptosystems and fault-tolerant distributed protocols in adversarial network settings. A central objective in this line of work is to achieve ADKG with $O(n^2)$ communication and constant round complexity under minimal setup assumptions. Recent progress has led to subcubic-communication ADKG protocols under different trade-offs. Feng and Tang (CRYPTO 2025) presented an ADKG protocol with $O(n^2)$ communication and $O(1)$ rounds, but at the cost of a cubic-communication setup phase in which each party posts a linear-sized public key on a public bulletin board. In contrast, Abraham et al. (PODC 2026) achieved an ADKG protocol with a standard setup phase, where each party posts only a constant-sized public key, but with $O(n^{2+1/k})$ communication and $O(k)$ rounds for a tunable parameter $k\leq \log{n}$. These results leave open whether one can simultaneously obtain constant-round complexity and quadratic communication under a standard setup phase. In this work, we resolve this open problem by presenting the first ADKG protocol that achieves $O(n^2)$ communication and $O(1)$ rounds while requiring only a standard setup phase in which each party posts a constant-sized public key on a public bulletin board. Our protocol is resilient to a strongly adaptive adversary corrupting up to $f < n/3$ parties and assumes only random oracles and secure erasures, both of which are also assumed by prior subcubic-communication ADKG constructions.