Turning Hash-Based Signatures into Distributed Signatures and Threshold Signatures

Published

July 7, 2025

Author(s)

John Kelsey, Stefan Lucks, Nathalie Lang

Abstract

We introduce techniques to transform existing stateful hash based signature (HBS) schemes, such as LMS [MCF19] or XMSS [HBG+18], into efficient threshold and distributed signature schemes. Our approach requires a trusted dealer for setup, and uses a large (up to a few GiB, typically) common reference value (CRV) for each new public key. The dealer generates the keypair and distributes shares of the signing key to the trustees, while creating the CRV. Signing involves an untrusted aggregator communicating point-to-point with a set of trustees. Only the aggregator needs access to the CRV; the trustees need only a PRF key and enough space to remember which one-time keys they have helped to sign with so far. Signing requires two round trips between the aggregator and each participating trustee, and only a little more computation from the trustees and aggregator than is done when signing with the underlying HBS scheme. We reduce the security of our scheme to that of the underlying HBS scheme, assuming the availability of a secure PRF. A dishonest aggregator or tampered CRV can prevent valid signatures from being constructed, but does not allow forgeries. Our techniques offer a powerful practical defense against accidental reuse of a one-time key in stateful HBS schemes by requiring multiple trustees to fail in the same way in order for key reuse to occur.

Citation

IACR Communications in Cryptology

Volume

2

Issue

2

Pub Type

Journals

Download Paper

DOI Link

Keywords

hash-based signatures, distributed signatures, provable security

Citation

Kelsey, J. , Lucks, S. and Lang, N. (2025), Turning Hash-Based Signatures into Distributed Signatures and Threshold Signatures, IACR Communications in Cryptology, [online], https://doi.org/10.62056/a6ksudy6b (Accessed October 9, 2025)