Cryptology ePrint Archive: Report 2022/241

Coalition and Threshold Hash-Based Signatures

John Kelsey and Stefan Lucks

Abstract: We show how to construct a threshold version of stateful hash-based signature schemes like those defined in XMSS (defined in RFC8391) and LMS (defined in RFC8554). Our techniques assume a trusted dealer and secure point-to-point communications; are efficient in terms of communications and computation; and require at least one party to have a large (but practical) amount of storage. We propose the addition of an untrusted Helper to manage the large storage required without being given access to any secret information. We prove the security of our schemes in a straightforward way, reducing their strength to that of the underlying hash-based signature scheme. Our schemes are quite practical, and substantially decrease the risk of accidental key reuse in hash-based signature schemes.

Category / Keywords: public-key cryptography / threshold cryptography, hash functions, hash-based signatures

Date: received 25 Feb 2022

Contact author: john kelsey at nist gov

Available format(s): PDF | BibTeX Citation

Version: 20220225:081240 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]