Paper 2024/168

Dragon: Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic DKG and Interactive Consistency

Hanwen Feng, University of Sydney
Zhenliang Lu, University of Sydney
Qiang Tang, University of Sydney
Abstract

Several distributed protocols, including distributed key generation (DKG) and interactive consistency (IC), depend on $\mathcal{O}(n)$ instances of Byzantine Broadcast or Byzantine Agreement among $n$ nodes, resulting in ${\Theta}(n^3)$ communication overhead. In this paper, we provide a new methodology of realizing such broadcasts we call DRAGON: Decentralization at the cost of Representation after Arbitrary GrOupiNg. At the core of it, we arbitrarily group nodes into small ``shards'' and paired with multiple new primitives we call consortium-sender (dealer) broadcast (and secret sharing). The new tools enable a shard of nodes to jointly broadcast (or securely contribute a secret) to the whole population only at the cost of one dealer ({\em as if} there is a representative). With our new Dragon method, we construct 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, which makes it directly compatible with various off-the-shelf DLog-based threshold cryptographic systems. We also construct a first deterministic IC with sub-cubic communication. Along the way, we also formalize simulation-based security and proved it for publicly verifiable secret sharing (PVSS), making it possible for a modular analysis, which might be of independent interest.

Note: A previous version of this paper appeared in the IACR ePrint archive under the title "Breaking the Cubic Barrier: Distributed Key and Randomness Generation through Deterministic Sharding."

Metadata
Available format(s)
PDF
Category
Cryptographic protocols
Publication info
Published elsewhere. Major revision. ACM PODC 2024
Keywords
Distributed Key GenerationDistributed Common RandomnessInteractive Consistency
Contact author(s)
hanwen feng @ sydney edu au
zhenliang lu @ sydney edu au
qiang tang @ sydney edu au
History
2024-05-09: last of 2 revisions
2024-02-05: received
See all versions
Short URL
https://ia.cr/2024/168
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2024/168,
      author = {Hanwen Feng and Zhenliang Lu and Qiang Tang},
      title = {Dragon: Decentralization at the cost of Representation after Arbitrary Grouping and Its Applications to Sub-cubic {DKG} and Interactive Consistency},
      howpublished = {Cryptology {ePrint} Archive, Paper 2024/168},
      year = {2024},
      url = {https://eprint.iacr.org/2024/168}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.