Examine individual changes

''''Hash-based cryptography''' is the generic term for constructions of [[cryptographic primitive]]s based on the security of [[hash function]]s. So far, hash-based cryptography is limited to [[digital signature]]s 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 signature]]s 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 and SPHINCS 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 <math>2^h</math> messages can be signed securely, with <math>h</math> 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<ref>{{Cite book|url=http://link.springer.com/chapter/10.1007/978-3-662-46800-5_15|title=Advances in Cryptology -- EUROCRYPT 2015|last=Bernstein|first=Daniel J.|last2=Hopwood|first2=Daira|last3=Hülsing|first3=Andreas|last4=Lange|first4=Tanja|last5=Niederhagen|first5=Ruben|last6=Papachristodoulou|first6=Louiza|last7=Schneider|first7=Michael|last8=Schwabe|first8=Peter|last9=Wilcox-O’Hearn|first9=Zooko|date=2015-04-26|publisher=Springer Berlin Heidelberg|isbn=9783662467992|editor-last=Oswald|editor-first=Elisabeth|series=Lecture Notes in Computer Science|pages=368–397|language=en|doi=10.1007/978-3-662-46800-5_15|editor-last2=Fischlin|editor-first2=Marc}}</ref> scheme. Most hash-based signature schemes are [[State (computer science)|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 [[Internet Research Task Force|IRTF]] [[Internet Draft]]s on stateful hash-based schemes (XMSS and LMS) are currently active. ==References== * J. Buchmann, E. Dahmen, A. Hülsing. "XMSS — A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions". PQCrypto 2011. * 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. [http://www.merkle.com/papers/Thesis1979.pdf] * 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== * [https://datatracker.ietf.org/doc/draft-irtf-cfrg-xmss-hash-based-signatures/] A. Hülsing, D. Butin, S. Gazdag, A. Mohaisen. IRTF Internet-Draft: "XMSS: Extended Hash-Based Signatures". * [https://datatracker.ietf.org/doc/draft-mcgrew-hash-sigs/] D. McGrew, M. Curcio, S. Fluhrer. IRTF Internet-Draft: "Hash-Based Signatures". * [http://sphincs.cr.yp.to/] "SPHINCS: practical stateless hash-based signatures". {{Cryptography navbox}} [[Category:Hash-based cryptography]] [[Category:Post-quantum cryptography]] [[Category:Public-key cryptography]] {{Crypto-stub}}'