Paper 2019/1328

Refresh When You Wake Up: Proactive Threshold Wallets with Offline Devices

Yashvanth Kondi, Bernardo Magri, Claudio Orlandi, and Omer Shlomovits

Abstract

Proactive security is the notion of defending a distributed system against an attacker who compromises different devices through its lifetime, but no more than a threshold number of them at any given time. The emergence of threshold wallets for more secure cryptocurrency custody warrants an efficient proactivization protocol tailored to this setting. While many proactivization protocols have been devised and studied in the literature, none of them have communication patterns ideal for threshold wallets. In particular a $(t,n)$ threshold wallet is designed to have $t$ parties jointly sign a transaction (of which only one may be honest) whereas even the best current proactivization protocols require at least an additional $t-1$ honest parties to come online simultaneously to refresh the system. In this work we formulate the notion of refresh with offline devices, where any $\rho$ parties may proactivize the system at any time and the remaining $n-\rho$ offline parties can non-interactively "catch up'' at their leisure. However, many subtle issues arise in realizing this pattern. We identify that this problem is divided into two settings: $(2,n)$ and $(t,n)$ where $t>2$. We develop novel techniques to address both settings as follows: - We show that the $(2,n)$ setting permits a tight $\rho$ for refresh. In particular we give a highly efficient $\rho=2$ protocol to upgrade a number of standard $(2,n)$ threshold signature schemes to proactive security with offline refresh. This protocol can augment existing implementations of threshold wallets for immediate use- we show that proactivization does not have to interfere with their native mode of operation. This technique is compatible with Schnorr, EdDSA, and even sophisticated ECDSA protocols. By implementation we show that proactivizing two different recent $(2,n)$ ECDSA protocols incurs only 14% and 24% computational overhead respectively, less than 200 bytes, and no extra round of communication. - For the general $(t,n)$ setting we prove that it is impossible to construct an offline refresh protocol with $\rho<2(t-1)$, i.e. tolerating a dishonest majority of online parties. Our techniques are novel in reasoning about the message complexity of proactive security, and may be of independent interest. Our results are positive for small-scale decentralization (such as 2FA with threshold wallets), and negative for large-scale distributed systems with higher thresholds. We thus initiate the study of proactive security with offline refresh, with a comprehensive treatment of the dishonest majority case.

Note: Full version of IEEE S&P 2021 conference paper.