Hash-based cryptography: Difference between revisions

Revision as of 03:24, 18 June 2025

Latest revision as of 05:01, 24 August 2025

(One intermediate revision by one other user not shown)

Line 6:

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 |last1=Alagic |first1=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 Ir 8413 |language=en |doi=10.6028/NIST.IR.8413-upd1|doi-access=free }}</ref><ref>{{Cite journal |last1=Cooper |first1=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 Publication 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 journal |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 ==

Line 42:

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 |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 |last1=McGrew |first1=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 |last1=McGrew |first1=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 ==

Line 50 ⟶ 52:

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