Paper 2015/1256

Mitigating Multi-Target Attacks in Hash-based Signatures

Andreas Hülsing, Joost Rijneveld, and Fang Song


This work introduces XMSS-T, a new hash-based signature scheme with tight security. Previous hash-based signature schemes are facing a loss of security, linear in performance parameters like the total tree height. Our new scheme can use hash functions with a smaller output length at the same security level, immediately leading to a smaller signature size. XMSS-T is stateful, however, the same techniques also apply directly to the recent stateless hash-based signature scheme SPHINCS (Eurocrypt 2015), and the signature size is improved as a result. Being a little more specific and technical, the tight security stems from new multi-target notions of hash-function properties which we define and analyze. We give precise complexity for breaking these security properties under both classical and quantum generic attacks, thus establishing a reliable estimate for the quantum security of XMSS-T. Especially, we prove quantum upper and lower bounds for the query complexity tailored for cryptographic applications, whereas standard techniques in quantum query complexity have limitations such as they usually only consider worst-case complexity. Our proof techniques may be useful elsewhere. We also implement XMSS-T and compare its performance to that of the most recent stateful hash-based signature scheme XMSS (PQCrypto 2011).

Note: Fixed two critical typos.

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2016
post-quantum cryptographyhash-based signatureshash function securitymulti-target attacksquantum algorithms
Contact author(s)
authors-multi-target @ huelsing net
2018-03-01: last of 3 revisions
2016-01-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Andreas Hülsing and Joost Rijneveld and Fang Song},
      title = {Mitigating Multi-Target Attacks in Hash-based Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2015/1256},
      year = {2015},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.