Welcome to the resource topic for 2025/149
Title:
Practical Asynchronous Distributed Key Reconfiguration and Its Applications
Authors: Hanwen Feng, Yingzi Gao, Yuan Lu, Qiang Tang, Jing Xu
Abstract:In this paper, we study practical constructions of asynchronous distributed key reconfiguration (\mathsf{ADKR}), which enables an asynchronous fault-tolerant system with an existing threshold cryptosystem to efficiently generate a new threshold cryptosystem for a reconfigured set of participants. While existing asynchronous distributed threshold key generation (\mathsf{ADKG}) protocols theoretically solve \mathsf{ADKR}, they fail to deliver satisfactory scalability due to cubic communication overhead, even with simplifications to the reconfiguration setting.
We introduce a more efficient \textit{share-dispersal-then-agree-and-recast} paradigm for constructing \mathsf{ADKR} with preserving adaptive security. The method replaces expensive O(n) asynchronous verifiable secret sharing protocols in classic \mathsf{ADKG} with O(n) cheaper dispersals of publicly-verifiable sharing transcripts; after consensus confirms a set of finished dispersals, it selects a small \kappa-subset of finished dispersals for verification, reducing the total overhead to O(\kappa n^2) from O(n^3), where \kappa is a small constant (typically $\sim$30 or less). To further optimize concrete efficiency, we propose an interactive protocol with linear communication to generate publicly verifiable secret sharing (PVSS) transcripts, avoiding computationally expensive non-interactive PVSS. Additionally, we introduce a distributed PVSS verification mechanism, minimizing redundant computations across different parties and reducing the dominating PVSS verification cost by about one-third.
Our design also enables diverse applications: (i) given a quadratic-communication asynchronous coin-flipping protocol, it implies the first quadratic-communication \mathsf{ADKG}; and (ii) it can be extended to realize the first quadratic-communication asynchronous dynamic proactive secret sharing (ADPSS) protocol with adaptive security. Experimental evaluations on a global network of 256 AWS servers show up to 40% lower latency compared to state-of-the-art \mathsf{ADKG} protocols (with simplifications to the reconfiguration setting), highlighting the practicality of our \mathsf{ADKR} in large-scale asynchronous systems.
ePrint: https://eprint.iacr.org/2025/149
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 .