Cryptology ePrint Archive: Report 2015/1256

Mitigating Multi-Target Attacks in Hash-based Signatures

Andreas Hülsing and Joost Rijneveld and Fang Song

Abstract: 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).

Category / Keywords: public-key cryptography / post-quantum cryptography, hash-based signatures, hash function security, multi-target attacks, quantum algorithms

Original Publication (with major differences): IACR-PKC-2016

Date: received 2 Jan 2016, last revised 1 May 2016

Contact author: authors-multi-target at huelsing net

Available format(s): PDF | BibTeX Citation

Note: Added more benchmarks as well as signature and key sizes

Version: 20160502:032625 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]