Paper 2022/241

Coalition and Threshold Hash-Based Signatures

John Kelsey
Stefan Lucks
Nathalie Lang

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.

Available format(s)
Public-key cryptography
Publication info
threshold cryptography hash functions hash-based signatures
Contact author(s)
stefan lucks @ uni-weimar de
nathalie lang @ uni-weimar de
2022-07-13: revised
2022-02-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {John Kelsey and Stefan Lucks and Nathalie Lang},
      title = {Coalition and Threshold Hash-Based Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2022/241},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.