Mitigating multi-target attacks in hash-based signatures

A.T. Hülsing, J. Rijneveld, F. Song

Research output: Chapter in Book/Report/Conference proceedingConference contributionAcademicpeer-review

68 Citations (Scopus)


This work introduces XMSS-T, a new stateful hash-based signature scheme with tight security. Previous hash-based signatures are facing a loss of security, linear in performance parameters such as the total tree height. Our new scheme can achieve the same security level but using hash functions with a smaller output length, which immediately leads to a smaller signature size. The same techniques also apply directly to the recent stateless hash-based signature scheme SPHINCS (Eurocrypt 2015), and the signature size is reduced as well. 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 show 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 query complexity tailored for cryptographic applications, which overcome some limitations of standard techniques in quantum query complexity 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 XMSS (PQCrypto 2011), the most recent stateful hash-based signature scheme before our work.
Original languageEnglish
Title of host publicationPublic-Key Cryptography - PKC 2016 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings, part I
EditorsC.-M. Cheng, K.-M. Chung, G. Persiano, B.-Y. Yang
Number of pages30
ISBN (Electronic)978-3-662-49384-7
ISBN (Print)978-3-662-49383-0
Publication statusPublished - 2016
Event19th IACR International Conference on Practice and Theory in Public-Key Cryptography (PKC 2016) - Taipei, Taiwan
Duration: 6 Mar 20169 Mar 2016

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
ISSN (Print)03029743
ISSN (Electronic)16113349


Conference19th IACR International Conference on Practice and Theory in Public-Key Cryptography (PKC 2016)
Abbreviated titlePKC 2016


  • Hash function security
  • Hash-based signatures
  • Multi-target attacks
  • Post-quantum cryptography
  • Quantum query complexity


Dive into the research topics of 'Mitigating multi-target attacks in hash-based signatures'. Together they form a unique fingerprint.

Cite this