Paper 2025/1631

Computationally and Communication Efficient Batched Asynchronous DPSS from Lightweight Cryptography

Abstract

Verifiable Secret Sharing (VSS) is a fundamental primitive in threshold cryptography and multi-party computation. It preserves secrecy, integrity, and availability of a shared secret for a fixed set of parties, with a subset of them being malicious. In practical applications, especially when the secret sharing is expected to be maintained over long durations, the VSS scheme should be able to cater to a dynamic setting where involved parties may change. The primitive known as Dynamic Proactive Secret Sharing (DPSS) is beneficial here, as it facilitates the secure transfer of secrets from the original committee to a new committee. Nevertheless, prior works on DPSS protocols either rely on unrealistic time bounds on message delivery or have a high computational cost, which limits their scalability beyond tens of parties. In this work, we present a scalable asynchronous DPSS protocol that utilizes lightweight cryptographic tools, such as hash functions and symmetric-key encryption. Our protocol achieves full security and optimal fault tolerance with amortized linear communication costs. Unlike existing solutions, our proposed protocol is also post-quantum secure. By balancing computation and communication, our approach offers practical performance at scale. Our implementation results demonstrate improved scalability and efficiency, surpassing the current state-of-the-art achieving a $22.1\times$ lower latency than the prior best work. Furthermore, our solution also scales gracefully with increasing $n$ and reshares a batch of $100,000$ secrets between committees of sizes $n=112$ parties in under a minute.

Note: Added comparison with a concurrent work.