Paper 2022/241

Coalition and Threshold Hash-Based Signatures

Abstract

In a distributed digital signature scheme, coalitions of “trustees” can jointly create a valid signature. We propose a distributed version of stateful hash-based signature schemes like those defined in XMSS (defined in RFC8391) and LMS (defined in RFC8554). Our schemes allow a dealer, who has generated the secret keys and could create valid signatures, to delegate the ability to sign coalitions of trustees. Our schemes support k-of-n threshold signatures, where every k-subset from a total of $n \ge k$ trustees form a coalition, as well as more complex authorization structures. We require only secure point- to-point communications. Our schemes are efficient in terms of communications and computation. They are also storage-efficient, except for needing a large (but practical) public database for non-confidential data. Assuming a secure PRF and the security of the underlying HBS, our schemes are provably secure. Our schemes are practical, if one avoids an excessively large number of coalitions. The security of stateful hash-bases signatures crucially depends on never using a one-time key a second time – else the key would be compromised. We argue that delegating one’s signing capability to some coalitions of trustees, as done by our schemes, substantially decreases the risk of such a compromise.