Abstract: 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. In particular, we prove quantum query complexity tailored for cryptographic applications, which overcomes some limitations of standard techniques in quantum query complexity such as only considering 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.

Paper: 2016-05-02

Source code: 2016-03-05
The source package contains two branches of XMSS-T: a 'clean' implementation, and an experiment setup that allows for somewhat more flexible configuration (e.g. m not divisible by 8, n unequal to 256). See Andreas' homepage for an overview of XMSS code.

Related talks:
Mitigating Multi-Target-Attacks in Hash-based Signatures
2016-03-07 – PKC 2016 – by Andreas Hülsing –

@inproceedings{HRS16,
  author    = {Andreas H\"ulsing and Joost Rijneveld and Fang Song},
  title     = {Mitigating Multi-Target Attacks in Hash-based Signatures},
  booktitle = {Public Key Cryptography -- {PKC 2016}},
  editor    = {Giuseppe Persiano and Bo-Yin Yang},
  publisher = {Springer-Verlag Berlin Heidelberg},
  series    = {Lecture Notes in Computer Science},
  volume    = {9614},
  year      = {2016},
  pages     = {387--416},
  url       = {https://eprint.iacr.org/2015/1256},
}