Cryptology ePrint Archive: Report 2018/096

Paralysis Proofs: Secure Access-Structure Updates for Cryptocurrencies and More

Fan Zhang and Philip Daian and Gabriel Kaptchuk and Iddo Bentov and Ian Miers and Ari Juels

Abstract: Conventional (M, N )-threshold signature schemes leave users with a painful choice. Setting M = N offers maximum resistance to key compromise. With this choice, though, loss of a single key renders the signing capability unavailable, creating paralysis in systems that use signatures for access control. Lower M improves availability, but at the expense of security. For example, (3, 3)-multisig wallet experiences access-control paralysis upon loss of a single key, but a (2, 3)-multisig allows any two players to collude and steal funds from the third. In this paper, we introduce techniques that address this impasse by making general cryptographic access structures dynamic. Our schemes permit, e.g., a (3, 3)-multisig, to be downgraded to a (2, 3)- multisig if a player goes missing. This downgrading is secure in the sense that it occurs only if a player is provably unavailable. Our main tool is what we call a Paralysis Proof, evidence that play- ers, i.e., key holders, are unavailable or incapacitated. Using Paraly- sis Proofs, we show how to construct a Dynamic Access Structure System, which can securely and flexibly update target access struc- tures without a trusted third party such as a system administrator. We present DASS constructions that combine a trust anchor (a trusted execution environment or smart contract) with a censorship- resistant channel in the form of a blockchain. We offer a formal framework for specifying DASS policies, and define and show how to achieve critical security and usability properties (safety, liveness, and paralysis-freeness) in a DASS. Paralysis Proofs can help address pervasive key-management chal- lenges in many different settings. We present DASS schemes for three important example use cases: recovery of cryptocurrency funds should players become unavailable, returning funds to users when cryptocurrency custodians fail, and remediating critical smart- contract failures such as frozen funds. We report on practical im- plementations for Bitcoin and Ethereum.

Category / Keywords: cryptographic protocols / blockchain, access structure, trusted hardware, Intel SGX, Bitcoin

Original Publication (with minor differences): ACM AFT 2019
DOI: 10.1145/3318041.3355459

Date: received 26 Jan 2018, last revised 2 Sep 2019

Contact author: fz84 at cornell edu

Available format(s): PDF | BibTeX Citation

Version: 20190902:173658 (All versions of this report)

Short URL: ia.cr/2018/096