|
'''Hash-based cryptography''' is the generic term for constructions of [[cryptographic primitive]]s based on the security of [[hash function]]s. It is of interest as a type of [[post-quantum cryptography]].
So far, hash-based cryptography is used to construct [[digital signature]]s schemes such as the [[Merkle signature scheme]], zero knowledge and computationally integrity proofs, such as the zk-STARK<ref name="bensasson2018">Ben-Sasson, Eli and Bentov, Iddo and Horesh, Yinon and Riabzev, Michael, 2018. [https://eprint.iacr.org/2018/046 Scalable, transparent, and post-quantum secure computational integrity].</ref> proof system and range proofs over issued credentials via the HashWires<ref name="kchalkias2021">{{Cite journal |lastlast1=Chalkias |firstfirst1=Konstantinos |last2=Cohen |first2=Shir |last3=Lewi |first3=Kevin |last4=Moezinia |first4=Fredric |last5=Romailler |first5=Yolan |year=2021 |title=HashWires: Hyperefficient Credential-Based Range Proofs |url=https://eprint.iacr.org/2021/297 |journal=Privacy Enhancing Technologies Symposium (PETS) 2021}}</ref> protocol. Hash-based signature schemes combine a one-time signature scheme, such as a [[Lamport signature]], 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. In this hierarchical data structure, a hash function and concatenation are used repeatedly to compute tree nodes.
One consideration with hash-based signature schemes is that they can only sign a limited number of messages securely, because of their use of one-time signature schemes. The US [[National Institute of Standards and Technology]] (NIST), specified that algorithms in its [[post-quantum cryptography]] competition support a minimum of 2{{Superscript|64}} signatures safely.<ref>{{Cite web |title=Submission Requirements and Evaluation Criteria for the Post-Quantum Cryptography Standardization Process |url=https://csrc.nist.gov/CSRC/media/Projects/Post-Quantum-Cryptography/documents/call-for-proposals-final-dec-2016.pdf |website=NIST CSRC}}</ref>
In 2022, NIST announced [[SPHINCS+]] as one of three algorithms to be standardized for digital signatures.<ref>{{Cite web |date=2022-07-05 |title=NIST announces four quantum-resistant algorithms |url=https://venturebeat.com/2022/07/05/nist-post-quantum-cryptography-standard/ |access-date=2022-07-10 |website=VentureBeat |language=en-US}}</ref> NIST standardized stateful hash-based cryptography based on the [[eXtended Merkle Signature Scheme]] (XMSS) and [[Leighton–Micali Signatures]] (LMS),<ref name="rfc8554" /> which are applicable in different circumstances, in 2020, but noted that the requirement to maintain state when using them makes them more difficult to implement in a way that avoids misuse.<ref>{{Cite web |last=Computer Security Division |first=Information Technology Laboratory |date=2019-02-01 |title=Request for Public Comments on Stateful HBS {{!}} CSRC |url=https://csrc.nist.gov/news/2019/stateful-hbs-request-for-public-comments |access-date=2019-02-04 |website=CSRC {{!}} NIST |language=EN-US}}</ref><ref>{{Cite journal |lastlast1=Alagic |firstfirst1=Gorjan |last2=Apon |first2=Daniel |last3=Cooper |first3=David |last4=Dang |first4=Quynh |last5=Dang |first5=Thinh |last6=Kelsey |first6=John |last7=Lichtinger |first7=Jacob |last8=Miller |first8=Carl |last9=Moody |first9=Dustin |last10=Peralta |first10=Rene |last11=Perlner |first11=Ray |date=2022-07-05 |title=Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process |url=https://csrc.nist.gov/publications/detail/nistir/8413/final |journal=NIST IRIr 8413 |language=en |doi=10.6028/NIST.IR.8413-upd1|doi-access=free }}</ref><ref>{{Cite journal |lastlast1=Cooper |firstfirst1=David |last2=Apon |first2=Daniel |last3=Dang |first3=Quynh |last4=Davidson |first4=Michael |last5=Dworkin |first5=Morris |last6=Miller |first6=Carl |date=2020-10-29 |title=Recommendation for Stateful Hash-Based Signature Schemes |url=https://csrc.nist.gov/publications/detail/sp/800-208/final |journal=NIST Special publicationPublication 800-208 |language=en |doi=10.6028/NIST.SP.800-208}}</ref>
In 2022, NIST announced [[SPHINCS+]] as one of three algorithms to be standardized for digital signatures.<ref>{{Cite web |date=2022-07-05 |title=NIST announces four quantum-resistant algorithms |url=https://venturebeat.com/2022/07/05/nist-post-quantum-cryptography-standard/ |access-date=2022-07-10 |website=VentureBeat |language=en-US}}</ref> and in 2024 NIST announced the Stateless Hash-Based Digital Signature Standard. (SLH-DSA)<ref>{{Cite webjournal |date=August 2024 |title=Stateless Hash-Based Digital Signature Standard |url=https://nvlpubs.nist.gov/nistpubs/FIPS/NIST.FIPS.205.pdf |website=[[NIST.gov]] |doi=10.6028/NIST.FIPS.205}}</ref> based on SPHINCS+.
== History ==
[[Leslie Lamport]] invented hash-based signatures in 1979. The XMSS (eXtended Merkle Signature Scheme)<ref name="BuchmannDahmen2011">{{Cite book |lastlast1=Buchmann |firstfirst1=Johannes |title=Post-Quantum Cryptography |last2=Dahmen |first2=Erik |last3=Hülsing |first3=Andreas |year=2011 |isbn=978-3-642-25404-8 |series=Lecture Notes in Computer Science |volume=7071 |pages=117–129 |chapter=XMSS – A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions |citeseerx=10.1.1.400.6086 |doi=10.1007/978-3-642-25405-5_8 |issn=0302-9743}}</ref> and SPHINCS<ref>{{Cite book |lastlast1=Bernstein |firstfirst1=Daniel J. |title=Advances in Cryptology -- EUROCRYPT 2015 |last2=Hopwood |first2=Daira |last3=Hülsing |first3=Andreas |last4=Lange |first4=Tanja |author-link4=Tanja Lange |last5=Niederhagen |first5=Ruben |last6=Papachristodoulou |first6=Louiza |last7=Schneider |first7=Michael |last8=Schwabe |first8=Peter |last9=Wilcox-O’Hearn |first9=Zooko |publisher=Springer Berlin Heidelberg |year=2015 |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 |chapter=SPHINCS: Practical Stateless Hash-Based Signatures |citeseerx=10.1.1.690.6403 |doi=10.1007/978-3-662-46800-5_15 |editor-last2=Fischlin |editor-first2=Marc}}</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 book |lastlast1=Buchmann |firstfirst1=Johannes |title=Applied Cryptography and Network Security |last2=Dahmen |first2=Erik |last3=Klintsevich |first3=Elena |last4=Okeya |first4=Katsuyuki |last5=Vuillaume |first5=Camille |date=2007 |isbn=978-3-540-72737-8 |series=Lecture Notes in Computer Science |volume=4521 |pages=31–45 |language=en |chapter=Merkle Signatures with Virtually Unlimited Signature Capacity |doi=10.1007/978-3-540-72738-5_3 |doi-access=free}}</ref> A multi-tree variant of XMSS, XMSS<sup>''MT''</sup>, was described in 2013.<ref>{{Cite book |lastlast1=Hülsing |firstfirst1=Andreas |title=Security Engineering and Intelligence Informatics |last2=Rausch |first2=Lea |last3=Buchmann |first3=Johannes |date=2013 |isbn=978-3-642-40587-7 |series=Lecture Notes in Computer Science |volume=8128 |pages=194–208 |language=en |chapter=Optimal Parameters for XMSS MT |doi=10.1007/978-3-642-40588-4_14|chapter-url=https://hal.inria.fr/hal-01506577 }}</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 book |lastlast1=Dods |firstfirst1=C. |title=Cryptography and Coding |last2=Smart |first2=N. P. |last3=Stam |first3=M. |date=2005 |isbn=978-3-540-30276-6 |series=Lecture Notes in Computer Science |volume=3796 |pages=96–115 |language=en |chapter=Hash Based Digital Signature Schemes |doi=10.1007/11586821_8}}</ref> and its improvements, such as the W-OTS<sup>+</sup> scheme.<ref name="wotsplus">{{Cite book |last=Hülsing |first=Andreas |title=Progress in Cryptology – AFRICACRYPT 2013 |date=2013 |isbn=978-3-642-38552-0 |series=Lecture Notes in Computer Science |volume=7918 |pages=173–188 |chapter=W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes |doi=10.1007/978-3-642-38553-7_10}}</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 |lastlast1=Chalkias |firstfirst1=Konstantinos |last2=Brown |first2=James |last3=Hearn |first3=Mike |last4=Lillehagen |first4=Tommy |last5=Nitto |first5=Igor |last6=Schroeter |first6=Thomas |year=2018 |title=Blockchained Post-Quantum Signatures |url=https://eprint.iacr.org/2018/658.pdf |journal=Proceedings of the IEEE International Conference on Blockchain (Cybermatics-2018) |pages=1196–1203}}</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 |lastlast1=Reyzin |firstfirst1=Leonid |title=Information Security and Privacy |last2=Reyzin |first2=Natan |date=2002 |isbn=978-3-540-43861-8 |series=Lecture Notes in Computer Science |volume=2384 |pages=144–153 |language=en |chapter=Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying |citeseerx=10.1.1.24.7320 |doi=10.1007/3-540-45450-0_11}}</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 |lastlast1=Hülsing |firstfirst1=Andreas |last2=Butin |first2=Denis |last3=Gazdag |first3=Stefan |last4=Rijneveld |first4=Joost |last5=Mohaisen |first5=Aziz |date=May 2018 |title=RFC 8391 – XMSS: eXtended Merkle Signature Scheme |url=https://tools.ietf.org/html/rfc8391 |language=en |publisher=IETF |website=tools.ietf.org}}</ref> Leighton–Micali Hash-Based Signatures are specified in [[Request for Comments|RFC]] 8554.<ref name="rfc8554">{{Cite journal |lastlast1=McGrew |firstfirst1=David |last2=Curcio |first2=Michael |last3=Fluhrer |first3=Scott |date=April 2019 |title=RFC 8554 – Leighton–Micali Hash-Based Signatures |url=https://tools.ietf.org/html/rfc8554 |language=en |publisher=IETF |website=tools.ietf.org}}</ref> Practical improvements have been proposed in the literature that alleviate the concerns introduced by stateful schemes.<ref>{{Cite book |lastlast1=McGrew |firstfirst1=David |title=Security Standardisation Research |last2=Kampanakis |first2=Panos |last3=Fluhrer |first3=Scott |last4=Gazdag |first4=Stefan-Lukas |last5=Butin |first5=Denis |last6=Buchmann |first6=Johannes |date=2016 |isbn=978-3-319-49099-1 |series=Lecture Notes in Computer Science |volume=10074 |pages=244–260 |language=en |chapter=State Management for Hash-Based Signatures |doi=10.1007/978-3-319-49100-4_11 |chapter-url=https://pdfs.semanticscholar.org/502a/2a2f5043f0d32fec0a5818d203fb4c9cd266.pdf |archive-url=https://web.archive.org/web/20170818214629/https://pdfs.semanticscholar.org/502a/2a2f5043f0d32fec0a5818d203fb4c9cd266.pdf |archive-date=2017-08-18 |url-status=dead |s2cid=809073}}</ref> Hash functions appropriate for these schemes include [[SHA-2]], [[SHA-3]] and [[BLAKE (hash function)|BLAKE]].
The stateless hash-based scheme SLH-DSA is specified in [https://doi.org/10.6028/NIST.FIPS.205 FIPS-205].
== Implementations ==
* T. Lange. "Hash-Based Signatures". Encyclopedia of Cryptography and Security, Springer U.S., 2011. [https://link.springer.com/referenceworkentry/10.1007%2F978-1-4419-5906-5_413]
* F. T. Leighton, S. Micali. "Large provably fast and secure digital signature schemes based one secure hash functions". US Patent 5,432,852, [https://patents.google.com/patent/US5432852] 1995.
* G. Becker. "Merkle Signature Schemes, Merkle Trees and Their Cryptanalysis", seminar 'Post Quantum Cryptology' at the Ruhr-University Bochum, Germany, 2008. [https://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf] {{Webarchive|url=https://web.archive.org/web/20170830030943/http://www.emsec.rub.de/media/crypto/attachments/files/2011/04/becker_1.pdf |date=2017-08-30 }}
* E. Dahmen, M. Dring, E. Klintsevich, J. Buchmann, L. C. Coronado Garcia. "CMSS — An Improved Merkle Signature Scheme". Progress in Cryptology – Indocrypt 2006. [https://eprint.iacr.org/2006/320.pdf]
* 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] {{Webarchive|url=https://web.archive.org/web/20180814211110/http://www.merkle.com/papers/Thesis1979.pdf |date=2018-08-14 }}
| 