Paper 2025/149
Practical Asynchronous Distributed Key Reconfiguration and Its Applications
Hanwen Feng
, University of Sydney
Yingzi Gao, Institute of Software Chinese Academy of Sciences, State Key Laboratory of Cryptology, University of Chinese Academy of Sciences
Yuan Lu, Institute of Software Chinese Academy of Sciences, State Key Laboratory of Cryptology, University of Chinese Academy of Sciences
Qiang Tang, University of Sydney
Jing Xu, Institute of Software Chinese Academy of Sciences, State Key Laboratory of Cryptology, University of Chinese Academy of Sciences
Abstract
In this paper, we study practical constructions of asynchronous distributed key reconfiguration (), 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 () protocols theoretically solve , 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 with preserving adaptive security. The method replaces expensive asynchronous verifiable secret sharing protocols in classic with cheaper dispersals of publicly-verifiable sharing transcripts; after consensus confirms a set of finished dispersals, it selects a small -subset of finished dispersals for verification, reducing the total overhead to from , where is a small constant (typically 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 ; 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 protocols (with simplifications to the reconfiguration setting), highlighting the practicality of our in large-scale asynchronous systems.