Paper 2022/1586

Practical Asynchronous Proactive Secret Sharing and Key Refresh

Abstract

With the emergence of decentralized systems, spearheaded by blockchains, threshold cryptography has seen unprecedented adoption. Just recently, the trustless distribution of threshold keys over an unreliable network has started to become practical. The next logical step is ensuring the security of these keys against persistent adversaries attacking the system over long periods of time. In this work, we tackle this problem and give two practical constructions for Asynchronous Proactive Secret Sharing. Our first construction uses recent advances in asynchronous protocols and achieves a communication complexity of $O(n^3)$ where $n$ is the total number of nodes in the network. The second protocol builds upon the first and uses sortition to drive down the communication complexity to $O(c n^2)$. Here, $c$ is a tunable parameter that controls the expected size of the sharing committee chosen using the existing random coin. Additionally, we identify security flaws in prior work and ensure that our protocols are secure by giving rigorous proofs. Moreover, we introduce a related notion which we term Asynchronous Refreshable Secret Sharing — a functionality that also re-randomizes the secret itself. Finally, we demonstrate the practicability of our constructions by implementing them in Rust and running large-scale, geo-distributed benchmarks.