Paper 2025/149
Practical Asynchronous Distributed Key Reconfiguration and Its Applications
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.
Metadata
- Available format(s)
-
PDF
- Category
- Cryptographic protocols
- Publication info
- Preprint.
- Contact author(s)
-
hanw feng94 @ gmail com
yingzi2019 @ iscas ac cn
luyuan @ iscas ac cn
qiang tang @ sydney edu au
xujing @ iscas ac cn - History
- 2025-01-31: approved
- 2025-01-30: received
- See all versions
- Short URL
- https://ia.cr/2025/149
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2025/149, author = {Hanwen Feng and Yingzi Gao and Yuan Lu and Qiang Tang and Jing Xu}, title = {Practical Asynchronous Distributed Key Reconfiguration and Its Applications}, howpublished = {Cryptology {ePrint} Archive, Paper 2025/149}, year = {2025}, url = {https://eprint.iacr.org/2025/149} }