TY - GEN
T1 - Mitigating multi-target attacks in hash-based signatures
AU - Hülsing, A.T.
AU - Rijneveld, J.
AU - Song, F.
PY - 2016
Y1 - 2016
N2 - 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.
AB - 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.
KW - Hash function security
KW - Hash-based signatures
KW - Multi-target attacks
KW - Post-quantum cryptography
KW - Quantum query complexity
UR - http://www.scopus.com/inward/record.url?scp=84961167404&partnerID=8YFLogxK
U2 - 10.1007/978-3-662-49384-7_15
DO - 10.1007/978-3-662-49384-7_15
M3 - Conference contribution
AN - SCOPUS:84961167404
SN - 978-3-662-49383-0
VL - 9614
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 387
EP - 416
BT - Public-Key Cryptography - PKC 2016 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, Proceedings, part I
A2 - Cheng, C.-M.
A2 - Chung, K.-M.
A2 - Persiano, G.
A2 - Yang, B.-Y.
PB - Springer
T2 - 19th IACR International Conference on Practice and Theory in Public-Key Cryptography (PKC 2016)
Y2 - 6 March 2016 through 9 March 2016
ER -