[Resource Topic] 2019/1328: Refresh When You Wake Up: Proactive Threshold Wallets with Offline Devices

Welcome to the resource topic for 2019/1328

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

Authors: Yashvanth Kondi, Bernardo Magri, Claudio Orlandi, Omer Shlomovits


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.

ePrint: https://eprint.iacr.org/2019/1328

See all topics related to this paper.

Feel free to post resources that are related to this paper below.

Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.

For more information, see the rules for Resource Topics .