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 an efficient \textit{share-dispersal-then-agree-and-recast} paradigm for constructing efficient $\mathsf{ADKR}$ while preserving adaptive security. Our method reduces the total overhead to $O(\kappa n^2)$ from $O(n^3)$, where $\kappa$ is a small constant (typically $\sim$30 or less). And our further optimizations in $\mathsf{PVSS}$ minimize redundant computations across different parties and reduce the dominating $\mathsf{PVSS}$ verification cost by about one-third. Our techniques developed for $\mathsf{ADKR}$ can also be leveraged to improve the asymptotic efficiency of various other asynchronous protocols: (i) it implies the first (coin-assisted) quadratic-communication $\mathsf{ADKG}$; and (ii) it can be extended to realize the first quadratic-communication asynchronous dynamic proactive secret sharing ($\mathsf{APSS}$) with adaptive security. Experimental evaluations on a global network of 256 AWS servers show up to 40\% lower latency compared to the state-of-the-art $\mathsf{ADKG}$ protocols that are simplified to the reconfiguration setting, highlighting the practicality of our $\mathsf{ADKR}$ in large-scale asynchronous systems.