Hash-based cryptography is the generic term for constructions of cryptographic primitives based on the security of hash functions. So far, hash-based cryptography is limited to digital signatures schemes such as the Merkle signature scheme. Hash-based signature schemes combine a one-time signature scheme with a Merkle tree structure. Since a one-time signature scheme key can only sign a single message securely, it is practical to combine many such keys within a single, larger structure. A Merkle tree structure is used to this end. Lamport signatures are an example of a one-time signature scheme that can be combined with a Merkle tree structure. Hash-based cryptography is a type of post-quantum cryptography.
History
Ralph Merkle invented hash-based signatures in 1979. The XMSS[1] and SPHINCS[2] hash-based signature schemes were introduced in 2011 and 2015, respectively. XMSS is based on a previous hash-based signature scheme, the Generalized Merkle Signature Scheme (GMSS)[3].
Properties of hash-based signature schemes
Hash-based signature schemes rely on security assumptions about the underlying hash function, but any hash function fulfilling these assumptions can be used. As a consequence, each adequate hash function yields a different corresponding hash-based signature scheme. Even if a given hash function becomes insecure, it is sufficient to replace it by a different, secure one to obtain a secure instantiation of the hash-based signature scheme under consideration. Some hash-based signature schemes (such as XMSS with pseudorandom key generation) are forward secure, meaning that previous signatures remain valid if a secret key is compromised.
Because of their reliance on an underlying one-time signature scheme, hash-based signature schemes can only sign a fixed amount of messages securely. In the case of the Merkle and XMSS schemes, a maximum of messages can be signed securely, with the total Merkle tree height.
Examples of hash-based signature schemes
In addition to Merkle's seminal scheme, more recent hash-based signature schemes include the XMSS scheme, the Leighton-Micali (LMS) and the SPHINCS scheme. Most hash-based signature schemes are stateful, meaning that signing requires updating the secret key, unlike conventional digital signature schemes. For stateful hash-based signature schemes, signing requires keeping state of the used one-time keys and making sure they are never reused. The XMSS and LMS schemes are stateful, while the SPHINCS scheme is stateless. SPHINCS signatures are larger than XMSS and LMS signatures. Two IRTF Internet Drafts on stateful hash-based schemes (XMSS and LMS) are currently active.[4][5] Practical improvement have been proposed in the literature that alleviate the concerns introduced by stateful schemes.[6] Hash functions appropriate for these schemes include SHA-2, SHA-3 and BLAKE
References
- ^ Buchmann, Johannes; Dahmen, Erik; Hülsing, Andreas (2011). "XMSS - A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions". Lecture Notes in Computer Science. 7071. Springer Berlin Heidelberg: 117–129. doi:10.1007/978-3-642-25405-5_8. ISSN 0302-9743.
{{cite journal}}
: Cite journal requires|journal=
(help) - ^ Bernstein, Daniel J.; Hopwood, Daira; Hülsing, Andreas; Lange, Tanja; Niederhagen, Ruben; Papachristodoulou, Louiza; Schneider, Michael; Schwabe, Peter; Wilcox-O’Hearn, Zooko (2015). Oswald, Elisabeth; Fischlin, Marc (eds.). Advances in Cryptology -- EUROCRYPT 2015. Lecture Notes in Computer Science. Vol. 9056. Springer Berlin Heidelberg. pp. 368–397. doi:10.1007/978-3-662-46800-5_15. ISBN 9783662467992.
- ^ Buchmann, Johannes; Dahmen, Erik; Klintsevich, Elena; Okeya, Katsuyuki; Vuillaume, Camille (2007). "Merkle Signatures with Virtually Unlimited Signature Capacity". Lecture Notes in Computer Science. 4521 (Applied Cryptography and Network Security). Springer, Berlin, Heidelberg: 31–45. doi:10.1007/978-3-540-72738-5_3.
- ^ Hülsing, Andreas; Butin, Denis; Gazdag, Stefan; Mohaisen, Aziz. "draft-irtf-cfrg-xmss-hash-based-signatures-09 - XMSS: Extended Hash-Based Signatures". datatracker.ietf.org. IETF.
- ^ McGrew, David; Curcio, Michael; Fluhrer, Scott. "draft-mcgrew-hash-sigs-06 - Hash-Based Signatures". datatracker.ietf.org. IETF.
- ^ McGrew, David; Kampanakis, Panos; Fluhrer, Scott; Gazdag, Stefan-Lukas; Butin, Denis; Buchmann, Johannes (2016). "State Management for Hash-Based Signatures". Security Standardisation Research. 10074. Springer, Cham: 244–260. doi:10.1007/978-3-319-49100-4_11.
- G. Becker. "Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis", seminar 'Post Quantum Cryptology' at the Ruhr-University Bochum, Germany.
- E. Dahmen, M. Dring, E. Klintsevich, J. Buchmann, L.C. Coronado Garcia. "CMSS — an improved merkle signature scheme". Progress in Cryptology - Indocrypt 2006. [1]
- R. Merkle. "Secrecy, authentication and public key systems / A certified digital signature". Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, 1979. [2]
- M. Naor, M. Yung. "Universal One-Way Hash Functions and their Cryptographic Applications". STOC 1989. [3]
- S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Fractal Merkle Tree Representation and Traversal". RSA-CT 03. [4]
- P. Kampanakis, S. Fluhrer. "LMS vs XMSS: A comparison of the Stateful Hash-Based Signature Proposed Standards". Cryptology ePrint Archive, Report 2017/349. [5]