Hash-based cryptography: Difference between revisions

Revision as of 08:52, 4 November 2023

Revision as of 18:33, 5 December 2023

Line 1:

'''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], Ben-Sasson, Eli and Bentov, Iddo and Horesh, Yinon and Riabzev, Michael, 2018.

</ref> proof system and range proofs over issued credentials via the HashWires<ref name="kchalkias2021">{{cite journal |last1=Chalkias |first1=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.

Line 9:

== History ==

[[Leslie Lamport]] invented hash-based signatures in 1979. The XMSS (eXtended Merkle Signature Scheme)<ref name="BuchmannDahmen2011">{{cite book |last1=Buchmann |first1=Johannes |title=Post-Quantum Cryptography |last2=Dahmen |first2=Erik |last3=Hülsing |first3=Andreas |titleyear=Post2011 |isbn=978-Quantum3-642-25404-8 Cryptography|series=Lecture Notes in Computer Science |volume=7071 |pages=117–129 |chapter=XMSS -– A Practical Forward Secure Signature Scheme Based on Minimal Security Assumptions |seriesciteseerx=Lecture10.1.1.400.6086 Notes in Computer Science |volume=7071|pages=117–129|year=2011|issn=0302-9743|doi=10.1007/978-3-642-25405-5_8|isbn=978-3-642-25404-8 |citeseerxissn=10.1.1.400.60860302-9743}}</ref> and SPHINCS<ref>{{Cite book|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=Advances in Cryptology -- EUROCRYPT 2015 |chapter=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 book|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 |series=Lecture Notes in Computer Science |date=2007|volume=4521|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^''MT'', 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 XMSS MT |series=Lecture Notes in Computer Science |date=2013|volume=8128|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 ==

Line 27:

Some hash-based signature schemes use multiple layers of tree, offering faster signing at the price of larger signatures. In such schemes, only the lowest layer of trees is used to sign messages, while all other trees sign root values of lower trees.

The Naor–Yung work<ref>M. Naor, M. Yung. "Universal One-Way Hash Functions and their Cryptographic Applications". STOC 1989. [http://www.wisdom.weizmann.ac.il/~naor/PAPERS/uowhf.pdf].</ref> shows the pattern by which to transfer a limited time signature of the Merkle type family into an unlimited (regular) signature scheme.

== Properties of hash-based signature schemes ==

Line 37:

== 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 |series=Lecture Notes in Computer Science |date=2002|volume=2384|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^''MT'' 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 book|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 |series=Lecture Notes in Computer Science |date=2016|volume=10074|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]].

The stateful hash-based schemes XMSS and XMSS^''MT'' 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 book|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 |series=Lecture Notes in Computer Science |date=2016|volume=10074|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 ==

Line 48 ⟶ 46:

== References ==

{{Reflist}}

* T. Lange. "Hash-Based Signatures". Encyclopedia of Cryptography and Security, Springer USU.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://www.google.com/patents/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]

* 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 }}

* S. Micali, M. Jakobsson, T. Leighton, M. Szydlo. "Fractal Merkle Tree Representation and Traversal". RSA-CT 03. [https://link.springer.com/chapter/10.1007/3-540-36563-X_21]