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.
Metadata
- Available format(s)
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Keywords
- Distributed Key GenerationDistributed Common Randomness
- Contact author(s)
-
hanwen feng @ sydney edu au
zhenliang lu @ sydney edu au
qiang tang @ sydney edu au - History
- 2024-02-06: approved
- 2024-02-05: received
- See all versions
- Short URL
- https://ia.cr/2024/168
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2024/168, author = {Hanwen Feng and Zhenliang Lu and Qiang Tang}, title = {Breaking the Cubic Barrier: Distributed Key and Randomness Generation through Deterministic Sharding}, howpublished = {Cryptology ePrint Archive, Paper 2024/168}, year = {2024}, note = {\url{https://eprint.iacr.org/2024/168}}, url = {https://eprint.iacr.org/2024/168} }