Hash-based digital signature schemes — standardized as SLH-DSA (FIPS 205, 2024), XMSS (RFC 8391) and LMS (RFC 8554) — are the only signature family whose security rests solely on cryptographic hash functions, making them the most conservative post-quantum choice. The 2009 survey chapter of Buchmann, Dahmen and Szydlo noted that general hash-based schemes had no proof of quantum-computer resistance beyond the stated reductions, and that their cost trade-offs among key size, signature size and signing time were unresolved. Two of the chapter's threads have since been settled: Merkle-tree traversal has proven optimal time-space trade-offs (2007), and tight, partly machine-checked proofs in the quantum random-oracle model now exist for adversaries with classical access to the signing oracle. The surviving open core lies in the stronger quantum-access model, where the adversary may query the signing oracle in superposition (EUF-qCMA / plus-one security; blind unforgeability): concrete superposition attacks break the deterministic variants of SPHINCS/SPHINCS+ at about 2432^{43} queries versus 21282^{128} classically, the only provably quantum-access-secure variant pays roughly 60% larger signatures, and the standardized hedged SLH-DSA, XMSS and LMS have neither proof nor attack in that model. The problem asks for the quantum-access security status of the standardized schemes and for the cost, if any, that quantum-access security imposes — i.e., the security-cost frontier of hash-based signatures under stronger oracle models.

Background

Digital signatures provide authenticity, integrity and non-repudiation, and the schemes in wide use today (RSA, DSA, ECDSA) would be broken by Shor's quantum factoring and discrete-logarithm algorithms. Hash-based signature schemes are the one family whose security rests only on cryptographic hash functions, which against quantum attackers lose at most Grover's quadratic search advantage; they are therefore viewed as the most conservative post-quantum option. The basic building block is a one-time signature (OTS), such as the Lamport or Winternitz construction: the private key is a set of secret strings, the public key is their hash images, and each signature reveals a message-dependent subset of the secrets, so each key may sign only once. A Merkle tree — a binary tree of hash values whose leaves are OTS public keys and whose root is the scheme's public key — amortizes exponentially many one-time keys under one small public key; a signature carries the OTS signature plus an authentication path (the sibling hash values along the path from the used leaf to the root). Because each leaf may be used only once, XMSS (RFC 8391) and LMS (RFC 8554) are stateful schemes (recommended in NIST SP 800-208, 2020): the signer must never reuse a one-time key, which is operationally hazardous. Stateless schemes remove that state by signing each message with a few-time signature called FORS (forest of random subsets — each signature reveals a pseudorandom small subset of a large pool of secret values), placed at a pseudorandomly chosen leaf of a hypertree (a tree of Merkle trees); the resulting scheme SPHINCS+ was standardized as SLH-DSA in FIPS 205 (August 2024), which specifies both a hedged (randomized) and a deterministic signing variant.

Security is stated as existential unforgeability under chosen-message attack (EUF-CMA): no adversary with oracle access to the signer can produce a valid signature for a new message. For quantum adversaries, reductions are proven in the quantum random-oracle model (QROM), where the hash function is a random function that the adversary may query in superposition, so that only Grover-type quadratic speedups are available to it. For adversaries that reach the signing oracle only with classical queries, this story is now essentially complete for the standardized schemes: Eaton (SAC 2017) proved LMS secure in the QROM; after Kudinov, Kiktenko and Fedorov (2020) exposed a flaw in the security bounds for W-OTS+ (the randomized Winternitz one-time signature used in XMSS and SPHINCS+) underlying the SPHINCS+ and XMSS tight proofs, Hülsing and Kudinov recovered a tight SPHINCS+ proof, and the groups of Barbosa and colleagues machine-checked the XMSS proof in the EasyCrypt proof assistant (CRYPTO 2023), formally verified the tight SPHINCS+ proof (2024), and delivered verified implementations of XMSS (2026).

A strictly stronger model, introduced by Boneh and Zhandry (CRYPTO 2013), also grants the adversary quantum access to the signing oracle itself: it may submit a superposition of messages and receive a superposition of signatures. This yields the notions of existential unforgeability under quantum chosen-message attacks (EUF-qCMA, also called plus-one security) and the related blind unforgeability (the adversary must produce a valid signature on a message outside the set it has queried with non-negligible amplitude). It is the strongest standard signing-oracle model, and it is where the general gap flagged by the 2009 survey chapter of Buchmann, Dahmen and Szydlo — hash-based schemes had reductions, but no proof of quantum-computer resistance in general — still survives. The gap is concrete rather than merely definitional: Yuan, Tibouchi and Abe (ACISP 2023) gave superposition attacks on the deterministic variants of SPHINCS and SPHINCS+ (for SPHINCS-256, about 2432^{43} quantum signing queries and 2432^{43} hash queries suffice, versus roughly 21282^{128} hash queries for the best classical chosen-message attack), and the first provably quantum-access-secure stateless construction — their SPHINCS-FORS variant — enlarges signatures from 29,272 to 47,072 bytes. On the cost side, the chapter's trade-off concern has become a quantitative frontier: the constant-sum Winternitz encoding (the checksum-based Winternitz one-time signature used in SPHINCS-alpha) is now known to be size-optimal among tree-based one-time signatures (Zhang, Cui and Yu, CRYPTO 2023), and Khovratovich, Kudinov and Wagner (CRYPTO 2025) proved the first lower bound on verification cost for a given signature size for general Winternitz-type encodings — but none of these results speaks to the cost of quantum-access security.

Problem Statement

Determine the achievable security-cost frontier of practical hash-based signature schemes when the adversary has quantum (superposition) access to the signing oracle — the strongest standard signing-oracle model. The problem has two open directions: part (1) settles the quantum-access security status of the standardized hash-based signature schemes, and part (2) determines whether quantum-access security forces a worse cost trade-off among key size, signature size, and signing/verification cost.

(1) Settle the quantum-access security status of the standardized hash-based signature schemes — the hedged and deterministic signing variants of SLH-DSA (FIPS 205) and the as-standardized signing procedures of XMSS (RFC 8391) and LMS (RFC 8554) — in the EUF-qCMA (plus-one) or blind-unforgeability sense in the quantum random-oracle model. For each scheme and variant, either give a security proof with an explicit concrete bound (as a function of the number of quantum signing queries and the number of quantum hash queries) that, evaluated on the standardized parameter sets, supports their claimed security levels, or give an attack establishing the actual security level in that model. Known superposition attacks already place the deterministic variants far below their classical security level, but no proof covers the hedged variant or the stateful schemes, and no attack analysis has been transferred to the standardized FIPS 205 parameter sets.

(2) Determine whether provable quantum-access security forces a worse trade-off among key size, signature size, and signing/verification cost. Either construct a practical hash-based signature scheme (stateless in the manner of SLH-DSA, or stateful in the manner of XMSS/LMS) that is provably EUF-qCMA-secure and whose key size, signature size, and signing/verification cost match those of the best classical-oracle schemes at the same security level, or prove a lower bound (in the spirit of the emerging size-time lower-bound program for Winternitz-type encodings) showing that quantum-access security necessarily costs more.

The two directions share a common motivation in the chapter's concerns — whether a hash-based signature scheme can be secure in the strongest quantum signing-oracle model, and at what cost in key size, signature size, and signing time. Part (1) fixes the security baseline of the schemes actually deployed and standardized; part (2) decides whether that baseline can be reached at no extra cost.

References

  1. Johannes Buchmann, Erik Dahmen, Michael Szydlo: Hash-based Digital Signature Schemes. In: Post-Quantum Cryptography, Springer, 2009, pp. 35-93. DOI: 10.1007/978-3-540-88702-7_3. https://doi.org/10.1007/978-3-540-88702-7_3
  2. Michael Szydlo: Merkle Tree Traversal in Log Space and Time. In: Advances in Cryptology - EUROCRYPT 2004, LNCS 3027. DOI: 10.1007/978-3-540-24676-3_32. https://doi.org/10.1007/978-3-540-24676-3_32
  3. Markus Jakobsson, Tom Leighton, Silvio Micali, Michael Szydlo: Fractal Merkle Tree Representation and Traversal. In: Topics in Cryptology - CT-RSA 2003, LNCS 2612. DOI: 10.1007/3-540-36563-X_21. https://doi.org/10.1007/3-540-36563-X_21
  4. Piotr Berman, Marek Karpinski, Yakov Nekrich: Optimal trade-off for Merkle tree traversal. Theoretical Computer Science 372(1):26-36, 2007. DOI: 10.1016/j.tcs.2006.11.029. https://doi.org/10.1016/j.tcs.2006.11.029
  5. Edward Eaton: Leighton-Micali Hash-Based Signatures in the Quantum Random-Oracle Model. In: Selected Areas in Cryptography - SAC 2017, LNCS 10759, pp. 263-280. DOI: 10.1007/978-3-319-72565-9_13. https://doi.org/10.1007/978-3-319-72565-9_13 (also IACR ePrint 2017/607, https://eprint.iacr.org/2017/607)
  6. M. A. Kudinov, E. O. Kiktenko, A. K. Fedorov: Security analysis of the W-OTS+ signature scheme: Updating security bounds. arXiv:2002.07419, 2020. https://arxiv.org/abs/2002.07419
  7. Andreas Hülsing, Mikhail Kudinov: Recovering the tight security proof of SPHINCS+. IACR ePrint 2022/346, 2022. https://eprint.iacr.org/2022/346
  8. Manuel Barbosa, François Dupressoir, Benjamin Grégoire, Andreas Hülsing, Matthias Meijers, Pierre-Yves Strub: Machine-Checked Security for XMSS as in RFC 8391 and SPHINCS+. In: Advances in Cryptology - CRYPTO 2023, LNCS. DOI: 10.1007/978-3-031-38554-4_14. https://doi.org/10.1007/978-3-031-38554-4_14 (also IACR ePrint 2023/408)
  9. Manuel Barbosa, François Dupressoir, Andreas Hülsing, Matthias Meijers, Pierre-Yves Strub: A Tight Security Proof for SPHINCS+, Formally Verified. IACR ePrint 2024/910, 2024. https://eprint.iacr.org/2024/910
  10. Manuel Barbosa, François Dupressoir, Rui Fernandes, Andreas Hülsing, Matthias Meijers, Pierre-Yves Strub: Completing the Chain: Verified Implementations of Hash-Based Signatures and Their Security. IACR ePrint 2026/134, 2026. https://eprint.iacr.org/2026/134
  11. Quan Yuan, Mehdi Tibouchi, Masayuki Abe: Quantum-Access Security of Hash-Based Signature Schemes. In: Information Security and Privacy (ACISP 2023), LNCS. DOI: 10.1007/978-3-031-35486-1_16. https://doi.org/10.1007/978-3-031-35486-1_16 (also IACR ePrint 2023/556)
  12. Christian Majenz, Chanelle Matadah Manfouo, Maris Ozols: Quantum-access security of the Winternitz one-time signature scheme. IACR ePrint 2021/387, 2021. https://eprint.iacr.org/2021/387
  13. Dan Boneh, Mark Zhandry: Secure Signatures and Chosen Ciphertext Security in a Quantum Computing World. In: Advances in Cryptology - CRYPTO 2013. IACR ePrint 2013/088. https://eprint.iacr.org/2013/088
  14. Haruhisa Kosuge, Keita Xagawa: The Security of Hash-and-Sign with Retry against Superposition Attacks. In: Public-Key Cryptography - PKC 2025. IACR ePrint 2025/363. https://eprint.iacr.org/2025/363
  15. Kaiyi Zhang, Hongrui Cui, Yu Yu: SPHINCS-alpha: A Compact Stateless Hash-Based Signature Scheme. In: Advances in Cryptology - CRYPTO 2023. IACR ePrint 2022/059. https://eprint.iacr.org/2022/059
  16. Dmitry Khovratovich, Mikhail Kudinov, Benedikt Wagner: At the Top of the Hypercube - Better Size-Time Tradeoffs for Hash-Based Signatures. In: Advances in Cryptology - CRYPTO 2025. IACR ePrint 2025/889. https://eprint.iacr.org/2025/889
  17. Scott Fluhrer, Quynh Dang: Smaller Sphincs+. IACR ePrint 2024/018, 2024. https://eprint.iacr.org/2024/018
  18. NIST: FIPS 205, Stateless Hash-Based Digital Signature Standard (SLH-DSA), published August 13, 2024. https://csrc.nist.gov/pubs/fips/205/final
  19. NIST: SP 800-208, Recommendation for Stateful Hash-Based Signature Schemes, October 2020. https://csrc.nist.gov/pubs/sp/800/208/final
  20. IETF RFC 8391: XMSS: eXtended Merkle Signature Scheme, 2018. https://www.rfc-editor.org/rfc/rfc8391
  21. IETF RFC 8554: Leighton-Micali Hash-Based Signatures, 2019. https://www.rfc-editor.org/rfc/rfc8554
  22. Efat Fathalla, Mohamed Azab: Beyond Classical Cryptography: A Systematic Review of Post-Quantum Hash-Based Signature Schemes, Security, and Optimizations. IEEE Access, 2024. DOI: 10.1109/ACCESS.2024.3485602. https://doi.org/10.1109/ACCESS.2024.3485602
  23. Quan Yuan: Improving Hash-Based Signature Schemes: From Theory to Practice. In: Mathematical Foundations for Post-Quantum Cryptography, Springer (Mathematics for Industry), 2025. DOI: 10.1007/978-981-96-1218-5_21. https://doi.org/10.1007/978-981-96-1218-5_21