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: ia.cr/2015/1256 Discussion forum: Show discussion | Start new discussion