Welcome to the resource topic for 2024/168
Title:
Breaking the Cubic Barrier: Distributed Key and Randomness Generation through Deterministic Sharding
Authors: Hanwen Feng, Zhenliang Lu, Qiang Tang
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.
ePrint: https://eprint.iacr.org/2024/168
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .