International Association
for Cryptologic Research

Dynamic-committee Proactive Secret Sharing (DPSS) has gained increased attention for its ability to dynamically update shareholder committees and refresh secret shares, even under adversaries that gradually corrupt all nodes. However, existing state-of-the-art asynchronous DPSS protocols suffer from significant $\mathcal{O}(n^3)$ message complexity and $\mathcal{O}(\lambda n^3)$ communication complexity, where $\lambda$ denotes the security parameter and $n$ is the committee size.

In this paper, under the trusted setup assumption, we propose the first asynchronous DPSS protocol with $\mathcal{O}(n^2)$ message complexity in all scenarios. Additionally, our protocol achieves $\mathcal{O}(\lambda n^2)$ communication complexity in the optimistic case, where all nodes are honest and the network is synchronous, and $\mathcal{O}(\lambda n^3)$ communication complexity in the worst case. Without a trusted setup, in the optimistic case, the message complexity is $\mathcal{O}(n^2)$, and the communication complexity is $\mathcal{O}(\lambda n^2 \log n)$. In the worst case, our protocol preserves state-of-the-art message and communication complexities, i.e., $\mathcal{O}(n^3)$ and $\mathcal{O}(\lambda n^3)$, respectively. Besides, our protocol supports batch amortization and accommodates high thresholds. For committee sizes of 4 to 400, the estimated concrete communication cost of our DPSS is 19--100x (resp., 8--14x) smaller in the optimistic case (resp., worst case) compared to the state-of-the-art. Experiments in AWS show that our DPSS achieves a latency of 1.9--8 seconds for committee sizes from 4 to 64. Single-machine benchmarks reveal a (computational) runtime reduction of up to 44%.