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 (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 () 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.

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
Creative Commons Attribution
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}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.