Nearly Quadratic Asynchronous Distributed Key Generation

Ittai Abraham; Renas Bacho; Julian Loss; Gilad Stern

Paper 2025/006

Nearly Quadratic Asynchronous Distributed Key Generation

Ittai Abraham, Intel Labs

Renas Bacho, Helmholtz Center for Information Security

Julian Loss, Helmholtz Center for Information Security

Gilad Stern, Tel Aviv University

Abstract

We prove that for any $1\le k\le \log n$, given a VRF setup and assuming secure erasures, there exists a protocol for Asynchronous Distributed Key Generation (ADKG) that is resilient to a strongly adaptive adversary that can corrupt up to $f<n/3$ parties. With all but negligible probability, all nonfaulty parties terminate in an expected $O(k)$ rounds and send a total expected $\tilde{O}(n^{2+1/k})$ messages.

Metadata

Available format(s): PDF
Category: Cryptographic protocols
Publication info: Preprint.
Keywords: dkg asynchrony consensus
Contact author(s): giladstern @ tauex tau ac il
History: 2025-01-01: approved; 2025-01-01: received; See all versions
Short URL: https://ia.cr/2025/006
License: CC BY

BibTeX

@misc{cryptoeprint:2025/006,
      author = {Ittai Abraham and Renas Bacho and Julian Loss and Gilad Stern},
      title = {Nearly Quadratic Asynchronous Distributed Key Generation},
      howpublished = {Cryptology {ePrint} Archive, Paper 2025/006},
      year = {2025},
      url = {https://eprint.iacr.org/2025/006}
}