Mitigating multi-target attacks in hash-based signatures

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

Onderzoeksoutput: Hoofdstuk in Boek/Rapport/CongresprocedureConferentiebijdrageAcademicpeer review

39 Citaten (Scopus)

Samenvatting

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.
Originele taal-2Engels
TitelPublic-Key Cryptography - PKC 2016 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings, part I
RedacteurenC.-M. Cheng, K.-M. Chung, G. Persiano, B.-Y. Yang
UitgeverijSpringer
Pagina's387-416
Aantal pagina's30
Volume9614
ISBN van elektronische versie978-3-662-49384-7
ISBN van geprinte versie978-3-662-49383-0
DOI's
StatusGepubliceerd - 2016
Evenement19th IACR International Conference on Practice and Theory in Public-Key Cryptography (PKC 2016) - Taipei, Taiwan
Duur: 6 mrt 20169 mrt 2016

Publicatie series

NaamLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume9614
ISSN van geprinte versie03029743
ISSN van elektronische versie16113349

Congres

Congres19th IACR International Conference on Practice and Theory in Public-Key Cryptography (PKC 2016)
Verkorte titelPKC 2016
LandTaiwan
StadTaipei
Periode6/03/169/03/16

    Vingerafdruk

Citeer dit

Hülsing, A. T., Rijneveld, J., & Song, F. (2016). Mitigating multi-target attacks in hash-based signatures. In C-M. Cheng, K-M. Chung, G. Persiano, & B-Y. Yang (editors), Public-Key Cryptography - PKC 2016 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings, part I (Vol. 9614, blz. 387-416). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9614). Springer. https://doi.org/10.1007/978-3-662-49384-7_15