Paper 2026/1321
Signing It Twice: Mitigating the Effects of State Reuse for Stateful Signatures
Abstract
Stateful hash-based signature schemes like LMS and XMSS are built on the Winternitz one-time signature. The effect of state reuse for these schemes has been shown to be disastrous [1][2]. This paper shows that the signer can mitigate this effect if a state is reused only once. This is achieved by repeating the randomized hashing step until a hash value with specific properties is found. Our results show that at least 80 bits of security can be achieved in 99% of the key reuses, an improvement of 49 bits. This requires the signer to repeat the randomized hashing step 1.4 million times on average. Slightly lower security can be reached with much less hashing.
Metadata
- Available format(s)
-
PDF
- Category
- Public-key cryptography
- Publication info
- Preprint.
- Keywords
- hash-based signaturesone-time signaturestwo-message attackspost-quantum cryptography
- Contact author(s)
-
niels duif @ sentyron com
daan meijer @ sentyron com - History
- 2026-06-29: approved
- 2026-06-26: received
- See all versions
- Short URL
- https://ia.cr/2026/1321
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2026/1321,
author = {Niels Duif and Daan S. Meijer},
title = {Signing It Twice: Mitigating the Effects of State Reuse for Stateful Signatures},
howpublished = {Cryptology {ePrint} Archive, Paper 2026/1321},
year = {2026},
url = {https://eprint.iacr.org/2026/1321}
}
