Paper 2024/168

Breaking the Cubic Barrier: Distributed Key and Randomness Generation through Deterministic Sharding

Abstract

There are long line of researches on the fundamental distributed key generation (DKG) protocols. Unfortunately, all of them suffer from a large cubic total communication, due to the fact that $O(n)$ participants need to {\em broadcast} to all $n$ participants. We introduce the first two DKG protocols, both achieving optimal resilience, with sub-cubic total communication and computation. The first DKG generates a secret key within an Elliptic Curve group, incurring $\widetilde{\mathcal{O}}(n^{2.5}\lambda)$ total communication and computation. The second DKG, while slightly increasing communication and computation by a factor of the statistical security parameter, generates a secret key as a field element. This property makes it directly compatible with various off-the-shelf DLog-based threshold cryptographic systems. Additionally, both DKG protocols straightforwardly imply an improved (single-shot) common coin protocol. At the core of our techniques, we develop a simple-yet-effective methodology via deterministic sharding that arbitrarily groups nodes into shards; and a new primitive called consortium-dealer secret sharing, to enable a shard of nodes to securely contribute a secret to the whole population only at the cost of one-dealer. We also formalize simulation-based security for publicly verifiable secret sharing (PVSS), making it possible for a modular analysis for DKG. Those might be of independent interest.