Haystack: Threshold and Distributed Stateful Hash-Based Signatures

"Preview Talk" (by Team Haystack) @ MPTS 2026, in reply to the NIST Threshold Call

Abstract. In this presentation, I'll explain how to take a stateful hash-based signature scheme like LMS, and turn it into a threshold hash-based signature scheme.  It is surprising that this is even possible, given the complete lack of nice algebraic structure in these schemes.  However, it turns out that the resulting schemes are quite practical and efficient.  Our techniques require a trusted dealer for setup, and assume signing happens between an untrusted aggregator and several trustees, each with a share of the private key.  The aggregator also needs access to a large common reference string defined for each public key, with a size of 0.1 GiB -- 10 GiB for typical LMS parameters.  All communications in the scheme are point-to-point, and during signing the aggregator and trustees each do about the same amount of computation required for an ordinary LMS signature.  Verification is the same as for any other LMS signature.  The aggregator needs access to a reasonable-sized hard drive to access the CRS; the trustees can be implemented on low-end devices such as smartcards.  Threshold signatures are especially valuable for stateful hash-based signatures, because they solve the state-management problems; instead of a single device failure leading to key reuse, many trustees' devices must fail at the same time in order for a key to be reused.

Joint work: John Kelsey, Stefan Lucks, Nathalie Lang.

[Slides] Suggested readings:

• Preview Writeup: Haystack: Threshold and Distributed Stateful Hash-Based Signatures
• Turning Hash-Based Signatures into Distributed Signatures and Threshold Signatures (cic.iacr.org/p/2/2/24)