|
== History ==
[[Leslie Lamport]] invented hash-based signatures in 1979. The XMSS (eXtended Merkle Signature Scheme)<ref name="BuchmannDahmen2011">{{cite journalbook|last1=Buchmann|first1=Johannes|last2=Dahmen|first2=Erik|last3=Hülsing|first3=Andreas|title=Post-Quantum Cryptography |chapter=XMSS –- A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions |journalseries=Lecture Notes in Computer Science |volume=7071|pages=117–129|issue=Post-Quantum Cryptography. PQCrypto 2011|year=2011|issn=0302-9743|doi=10.1007/978-3-642-25405-5_8|isbn=978-3-642-25404-8 |citeseerx=10.1.1.400.6086}}</ref> and SPHINCS<ref>{{Cite book|issue=Advances in Cryptology – EUROCRYPT 2015|last1=Bernstein|first1=Daniel J.|last2=Hopwood|first2=Daira|last3=Hülsing|first3=Andreas|last4=Lange|first4=Tanja|author4-link=Tanja Lange|last5=Niederhagen|first5=Ruben|last6=Papachristodoulou|first6=Louiza|last7=Schneider|first7=Michael|last8=Schwabe|first8=Peter|last9=Wilcox-O’Hearn|first9=Zooko|title=SPHINCS: practical stateless hash-based signatures|year=2015|publisher=Springer Berlin Heidelberg|isbn=9783662467992|editor-last=Oswald|editor-first=Elisabeth|editor-link= Elisabeth Oswald |series=Lecture Notes in Computer Science|volume=9056|pages=368–397|language=en|doi=10.1007/978-3-662-46800-5_15|editor-last2=Fischlin|editor-first2=Marc|citeseerx = 10.1.1.690.6403}}</ref><ref>{{cite web|title=SPHINCS: Introduction|url=http://sphincs.cr.yp.to/}}</ref> hash-based signature schemes were introduced in 2011 and 2015, respectively. XMSS was developed by a team of researchers under the direction of [[Johannes Buchmann]] and is based both on Merkle's seminal scheme and on the 2007 Generalized Merkle Signature Scheme (GMSS).<ref>{{cite journalbook|last1=Buchmann|first1=Johannes|last2=Dahmen|first2=Erik|last3=Klintsevich|first3=Elena|last4=Okeya|first4=Katsuyuki|last5=Vuillaume|first5=Camille|title=Applied Cryptography and Network Security |chapter=Merkle Signatures with Virtually Unlimited Signature Capacity |journalseries=Lecture Notes in Computer Science |date=2007|volume=4521|issue=Applied Cryptography and Network Security|pages=31–45|doi=10.1007/978-3-540-72738-5_3|isbn=978-3-540-72737-8 |language=en|doi-access=free}}</ref> A multi-tree variant of XMSS, XMSS<sup>''MT''</sup>, was described in 2013.<ref>{{cite book|last1=Hülsing|first1=Andreas|last2=Rausch|first2=Lea|last3=Buchmann|first3=Johannes|title=Security Engineering and Intelligence Informatics |chapter=Optimal Parameters for XMSSMTXMSS MT |journalseries=Lecture Notes in Computer Science |date=2013|volume=8128|issue=Security Engineering and Intelligence Informatics|pages=194–208|doi=10.1007/978-3-642-40588-4_14|language=en|isbn=978-3-642-40587-7}}</ref>
== One-time signature schemes ==
Hash-based signature schemes use one-time signature schemes as their building block. A given one-time signing key can only be used to sign a single message securely. Indeed, signatures reveal part of the signing key. The security of (hash-based) one-time signature schemes relies exclusively on the security of an underlying hash function.
Commonly used one-time signature schemes include the [[Lamport signatures|Lamport–Diffie scheme]], the Winternitz scheme<ref>{{cite journalbook|last1=Dods|first1=C.|last2=Smart|first2=N. P.|last3=Stam|first3=M.|title=Cryptography and Coding |chapter=Hash Based Digital Signature Schemes|issue=Cryptography and Coding|journalseries=Lecture Notes in Computer Science |issue=Cryptography and Coding|volume=3796|date=2005|pages=96–115|doi=10.1007/11586821_8|isbn=978-3-540-30276-6 |language=en}}</ref> and its improvements, such as the W-OTS<sup>+</sup> scheme.<ref name="wotsplus">{{cite book|last1=Hülsing|first1=Andreas|title=Progress in Cryptology – AFRICACRYPT 2013 |chapter=W-OTS+ —– Shorter Signatures for Hash-Based Signature Schemes |journalseries=Lecture Notes in Computer Science |date=2013|volume=7918|issue=Progress in Cryptology – AFRICACRYPT 2013|pages=173–188|doi=10.1007/978-3-642-38553-7_10|isbn=978-3-642-38552-0}}</ref> Unlike the seminal Lamport–Diffie scheme, the Winternitz scheme and variants can sign many bits at once. The number of bits to be signed at once is determined by a value: the Winternitz parameter. The existence of this parameter provides a trade-off between size and speed. Large values of the Winternitz parameter yield short signatures and keys, at the price of slower signing and verifying. In practice, a typical value for this parameter is 16.
In the case of stateless hash-based signatures, few-time signature schemes are used. Such schemes allow security to decrease gradually in case a few-time key is used more than once. HORST is an example of a few-time signature scheme.
== Examples of hash-based signature schemes ==
Since Merkle's initial scheme, numerous hash-based signature schemes with performance improvements have been introduced. Recent ones include the XMSS, the Leighton–Micali (LMS), the SPHINCS and the BPQS schemes. Most hash-based signature schemes are [[State (computer science)|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, LMS and BPQS<ref>{{cite journal |last1=Chalkias|first1=Konstantinos|last2=Brown|first2=James|last3=Hearn|first3=Mike|last4=Lillehagen|first4=Tommy|last5=Nitto|first5=Igor|last6=Schroeter|first6=Thomas|title=Blockchained Post-Quantum Signatures|journal=Proceedings of the IEEE International Conference on Blockchain (Cybermatics-2018) |pages=1196–1203|year=2018|url=https://eprint.iacr.org/2018/658.pdf}}</ref> schemes are stateful, while the SPHINCS scheme is stateless. SPHINCS signatures are larger than XMSS and LMS signatures. BPQS has been designed specifically for blockchain systems. Additionally to the WOTS+ one-time signature scheme,<ref name="wotsplus"/> SPHINCS also uses a few-time (hash-based) signature scheme called HORST. HORST is an improvement of an older few-time signature scheme, HORS (Hash to Obtain Random Subset).<ref>{{cite book|last1=Reyzin|first1=Leonid|last2=Reyzin|first2=Natan|title=Information Security and Privacy |chapter=Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying |journalseries=Lecture Notes in Computer Science |date=2002|volume=2384|issue=Information Security and Privacy|pages=144–153|doi=10.1007/3-540-45450-0_11|language=en|isbn=978-3-540-43861-8|citeseerx=10.1.1.24.7320}}</ref>
The stateful hash-based schemes XMSS and XMSS<sup>''MT''</sup> are specified in [[Request for Comments|RFC]] 8391 (XMSS: eXtended Merkle Signature Scheme)
.<ref>{{cite journal|last1=Hülsing|first1=Andreas|last2=Butin|first2=Denis|last3=Gazdag|first3=Stefan|last4=Rijneveld|first4=Joost|last5=Mohaisen|first5=Aziz|title=RFC 8391 – XMSS: eXtended Merkle Signature Scheme|url=https://tools.ietf.org/html/rfc8391|website=tools.ietf.org|date=May 2018 |publisher=IETF|language=en}}</ref>
Leighton–Micali Hash-Based Signatures are specified in [[Request for Comments|RFC]] 8554.<ref>{{cite journal|last1=McGrew|first1=David|last2=Curcio|first2=Michael|last3=Fluhrer|first3=Scott|title=RFC 8554 – Leighton–Micali Hash-Based Signatures|url=https://tools.ietf.org/html/rfc8554|website=tools.ietf.org|date=April 2019 |publisher=IETF|language=en}}</ref> Practical improvements have been proposed in the literature that alleviate the concerns introduced by stateful schemes.<ref>{{cite journalbook|last1=McGrew|first1=David|last2=Kampanakis|first2=Panos|last3=Fluhrer|first3=Scott|last4=Gazdag|first4=Stefan-Lukas|last5=Butin|first5=Denis|last6=Buchmann|first6=Johannes|title=Security Standardisation Research |chapter=State Management for Hash-Based Signatures |journalseries=Lecture Notes in Computer Science |date=2016|volume=10074|issue=Security Standardisation Research|pages=244–260|doi=10.1007/978-3-319-49100-4_11|isbn=978-3-319-49099-1 |s2cid=809073 |chapter-url=https://pdfs.semanticscholar.org/502a/2a2f5043f0d32fec0a5818d203fb4c9cd266.pdf|archive-url=https://web.archive.org/web/20170818214629/https://pdfs.semanticscholar.org/502a/2a2f5043f0d32fec0a5818d203fb4c9cd266.pdf|url-status=dead|archive-date=2017-08-18|language=en}}</ref> Hash functions appropriate for these schemes include [[SHA-2]], [[SHA-3]] and [[BLAKE (hash function)|BLAKE]].
== Implementations ==
| 