Hash-based cryptography

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.

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 ${\displaystyle 2^{h}}$  messages can be signed securely, with ${\displaystyle h}$  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. The XMSS and LMS schemes are stateful, while the SPHINCS scheme is stateless. Two IRTF Internet Drafts on stateful hash-based schemes (XMSS and LMS) are currently active.^[3]

References

1. 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)
2. 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.
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.

• 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.
• E. Klintsevich, K. Okeya, C. Vuillaume, J. Buchmann, E. Dahmen. "Merkle signatures with virtually unlimited signature capacity". 5th International Conference on Applied Cryptography and Network Security - ACNS07.
• R. Merkle. "Secrecy, authentication and public key systems / A certified digital signature". Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, 1979. [1]
• M. Naor, M. Yung. "Universal One-Way Hash Functions and their Cryptographic Applications". STOC 1989.
• S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Fractal Merkle Tree Representation and Traversal". RSA-CT 03.

External links

• [2] A. Hülsing, D. Butin, S. Gazdag, A. Mohaisen. IRTF Internet-Draft: "XMSS: Extended Hash-Based Signatures".
• [3] D. McGrew, M. Curcio, S. Fluhrer. IRTF Internet-Draft: "Hash-Based Signatures".
• [4] "SPHINCS: practical stateless hash-based signatures".