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.

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