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.

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.

History

Ralph Merkle invented hash-based signatures in 1979.

Hash-based signature schemes

In addition to Merkle's seminal scheme, more recent hash-based signature schemes include the XMSS scheme 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 scheme is stateful, while the SPHINCS scheme is stateless. Two IRTF Internet-Drafts on stateful hash-based schemes are currently active.

References

• J. Buchmann, E. Dahmen, and A. Hülsing. "XMSS — A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions". PQCrypto 2011
• D. Bernstein, D. Hopwood, A. Hülsing, T. Lange, R. Niederhagen, L. Papachristodoulou, M. Schneider, P. Schwabe, Z. Wilcox-O'Hearn. "SPHINCS: practical stateless hash-based signatures". EUROCRYPT 2015
• 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 Garca. "CMSS — an improved merkle signature scheme". Progress in Cryptology - Indocrypt 2006, 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, 2007.
• Ralph Merkle. "Secrecy, authentication and public key systems / A certified digital signature". Ph.D. dissertation, Dept. of Electrical Engineering, Stanford University, 1979. [1]
• Moni Naor, Moti Yung. "Universal One-Way Hash Functions and their Cryptographic Applications". STOC 1989: 33-43
• S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Fractal Merkle Tree Representation and Traversal". RSA-CT 03, 2003

External links

• [2] IRTF Internet-Draft: XMSS: Extended Hash-Based Signatures
• [3] SPHINCS: practical stateless hash-based signatures