{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T07:26:16Z","timestamp":1775633176895,"version":"3.50.1"},"reference-count":62,"publisher":"Springer Science and Business Media LLC","issue":"1","license":[{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T00:00:00Z","timestamp":1656633600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100001809","name":"National Natural Science Foundation of China","doi-asserted-by":"publisher","award":["61972391"],"award-info":[{"award-number":["61972391"]}],"id":[{"id":"10.13039\/501100001809","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Cybersecurity"],"published-print":{"date-parts":[[2022,12]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>The current development toward quantum attack has shocked our confidence on classical digital signature schemes. As one of the mainstreams of post quantum cryptography primitives, hash-based signature has attracted more and more concern in both cryptographic research and application in recent years. The goal of this paper is to present, classify and discuss different solutions for hash-based signature. Firstly, this paper discusses the research progress in the component of hash-based signature, i.e., one-time signature and few-time signature; then classifies the tree-based public key authentication schemes of hash-based signature into limited number and stateful schemes, unlimited number and stateful schemes and unlimited number and stateless schemes. The above discussion aims to analyze the overall design idea of different categories of hash-based signatures, as well as the construction, security reduction and performance efficiency of specific schemes. Finally, the perspectives and possible development directions of hash-based signature are briefly discussed.<\/jats:p>","DOI":"10.1186\/s42400-022-00117-w","type":"journal-article","created":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T01:02:58Z","timestamp":1656637378000},"update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":29,"title":["Hash-based signature revisited"],"prefix":"10.1186","volume":"5","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1125-7437","authenticated-orcid":false,"given":"Lingyun","family":"Li","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Xianhui","family":"Lu","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kunpeng","family":"Wang","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2022,7,1]]},"reference":[{"key":"117_CR1","unstructured":"Aumasson JP, Endignoux G (2017) Gravity SPHINCS, A submission to the NIST standardization project on post-quantum cryptography. https:\/\/github.com\/gravity-postquantum\/gravity-sphincs. Accessed 09 Jan 2018"},{"key":"117_CR2","doi-asserted-by":"crossref","unstructured":"Aumasson JP, Endignoux G (2018) Improving stateless hash-based signatures. In: Cryptographers\u2019 track at the RSA conference. Springer, Cham, pp 219\u2013242","DOI":"10.1007\/978-3-319-76953-0_12"},{"key":"117_CR3","doi-asserted-by":"crossref","unstructured":"Bellare M, Miner SK (1999) A forward-secure digital signature scheme. In: Annual international cryptology conference. Springer, Berlin, pp 431\u2013448","DOI":"10.1007\/3-540-48405-1_28"},{"issue":"21","key":"117_CR4","doi-asserted-by":"publisher","first-page":"3121","DOI":"10.1103\/PhysRevLett.68.3121","volume":"68","author":"CH Bennett","year":"1992","unstructured":"Bennett CH (1992) Quantum cryptography using any two nonorthogonal states. Phys Rev Lett 68(21):3121","journal-title":"Phys Rev Lett"},{"issue":"1","key":"117_CR5","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1007\/BF00191318","volume":"5","author":"CH Bennett","year":"1992","unstructured":"Bennett CH, Bessette F, Brassard G et al (1992) Experimental quantum cryptography. J Cryptol 5(1):3\u201328","journal-title":"J Cryptol"},{"issue":"8","key":"117_CR6","doi-asserted-by":"publisher","first-page":"719","DOI":"10.1016\/S0167-4048(02)00813-1","volume":"21","author":"F Bergadano","year":"2002","unstructured":"Bergadano F, Cavagnino D, Crispo B (2002) Individual authentication in multiparty communications. Comput Secur 21(8):719\u2013735","journal-title":"Comput Secur"},{"issue":"1","key":"117_CR7","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1016\/j.tcs.2006.11.029","volume":"372","author":"P Berman","year":"2007","unstructured":"Berman P, Karpinski M, Nekrich Y (2007) Optimal trade-off for Merkle tree traversal. Theoret Comput Sci 372(1):26\u201336","journal-title":"Theoret Comput Sci"},{"key":"117_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-540-88702-7","volume-title":"Introduction to post-quantum cryptography\/\/Post-quantum cryptography","author":"DJ Bernstein","year":"2009","unstructured":"Bernstein DJ (2009) Introduction to post-quantum cryptography\/\/Post-quantum cryptography. Springer, Berlin, pp 1\u201314"},{"key":"117_CR9","doi-asserted-by":"crossref","unstructured":"Bernstein DJ, Hopwood D, H\u00fclsing A et al (2015) Sphincs: practical stateless hash-based signatures. In: Annual international conference on the theory and applications of cryptographic techniques. Springer, pp 368\u2013397","DOI":"10.1007\/978-3-662-46800-5_15"},{"key":"117_CR10","unstructured":"Bernstein DJ, Dobraunig C, Eichlseder M et al (2017) SPHINCS+, A submission to the NIST standardization project on post-quantum cryptography. https:\/\/sphincs.org\/. Accessed 09 Jan 2018"},{"key":"117_CR11","doi-asserted-by":"crossref","unstructured":"Bernstein DJ, H\u00fclsing A, K\u00f6lbl S et al (2019) The SPHINCS+ signature framework. In: Proceedings of the 2019 ACM SIGSAC conference on computer and communications security, pp 2129\u20132146","DOI":"10.1145\/3319535.3363229"},{"key":"117_CR12","doi-asserted-by":"crossref","unstructured":"Black J, Rogaway P, Shrimpton T (2002) Black-box analysis of the block-cipher-based hash-function constructions from PGV. In: Advances in cryptology\u2014CRYPTO 2002, California, USA","DOI":"10.1007\/3-540-45708-9_21"},{"key":"117_CR13","doi-asserted-by":"crossref","unstructured":"Bleichenbacher D, Maurer UM (1994) Directed acyclic graphs, one-way functions and digital signatures. In: Advances in cryptology\u2014CRYPTO \u201994, volume 839 of lecture notes in computer science, pp 75\u201382","DOI":"10.1007\/3-540-48658-5_9"},{"issue":"6","key":"117_CR14","doi-asserted-by":"publisher","first-page":"1330","DOI":"10.1103\/PhysRevLett.85.1330","volume":"85","author":"G Brassard","year":"2000","unstructured":"Brassard G, L\u00fctkenhaus N, Mor T et al (2000) Limitations on practical quantum cryptography. Phys Rev Lett 85(6):1330","journal-title":"Phys Rev Lett"},{"key":"117_CR15","doi-asserted-by":"crossref","unstructured":"Buchmann J, Garc\u00eda LCC, Dahmen E et al (2006) CMSS\u2014an improved Merkle signature scheme. In: International conference on cryptology in India. Springer, pp 349\u2013363","DOI":"10.1007\/11941378_25"},{"key":"117_CR16","doi-asserted-by":"crossref","unstructured":"Buchmann J, Dahmen E, Klintsevich E et al (2007) Merkle signatures with virtually unlimited signature capacity. In: International conference on applied cryptography and network security. Springer, Berlin, pp 31\u201345","DOI":"10.1007\/978-3-540-72738-5_3"},{"key":"117_CR17","doi-asserted-by":"crossref","unstructured":"Buchmann J, Dahmen E, Schneider M (2008) Merkle tree traversal revisited. In: International workshop on post-quantum cryptography. Springer, Berlin, pp 63\u201378","DOI":"10.1007\/978-3-540-88403-3_5"},{"key":"117_CR18","doi-asserted-by":"crossref","unstructured":"Buchmann J, Dahmen E, Ereth S et al (2011a) On the security of the Winternitz one-time signature scheme. In: International conference on cryptology in Africa. Springer, Berlin, pp 363\u2013378","DOI":"10.1007\/978-3-642-21969-6_23"},{"key":"117_CR19","doi-asserted-by":"crossref","unstructured":"Buchmann J, Dahmen E, H\u00fclsing A (2011b) Xmss-a practical forward secure signature scheme based on minimal security assumptions. In: International workshop on post-quantum cryptography. Springer, pp 117\u2013129","DOI":"10.1007\/978-3-642-25405-5_8"},{"key":"117_CR20","doi-asserted-by":"crossref","unstructured":"Buldas A, Laanoja R, Truu A (2017) A server-assisted hash-based signature scheme. In: Nordic conference on secure IT systems. Springer, Cham, pp 3\u201317","DOI":"10.1007\/978-3-319-70290-2_1"},{"key":"117_CR21","doi-asserted-by":"crossref","unstructured":"Buldas A, Laanoja R, Truu A (2018) A blockchain-assisted hash-based signature scheme. In: Nordic conference on secure IT systems. Springer, Cham, pp. 138\u2013153","DOI":"10.1007\/978-3-030-03638-6_9"},{"key":"117_CR22","doi-asserted-by":"crossref","unstructured":"Cooper D, Apon D, Dang Q, et al (2019) Recommendation for stateful hash-based signature schemes. draft NIST Special Publication 800\u2013208. NIST. SP, pp 800\u2013208","DOI":"10.6028\/NIST.SP.800-208-draft"},{"key":"117_CR23","doi-asserted-by":"crossref","unstructured":"Coppersmith D, Jakobsson M (2002) Almost optimal hash sequence traversal. In: International conference on financial cryptography. Springer, Berlin, pp 102\u2013119","DOI":"10.1007\/3-540-36504-4_8"},{"key":"117_CR24","doi-asserted-by":"crossref","unstructured":"Coron JS, Dodis Y, Malinaud C et al (2005) Merkle-Damg\u00e5rd revisited: how to construct a hash function. In: Annual international cryptology conference. Springer, Berlin, pp 430\u2013448","DOI":"10.1007\/11535218_26"},{"key":"117_CR25","doi-asserted-by":"crossref","unstructured":"Damg\u00e5rd I (1989) A design principle for hash functions. In: Crypto \u201989. LNCS No. 435, pp 416\u2013427","DOI":"10.1007\/0-387-34805-0_39"},{"key":"117_CR26","doi-asserted-by":"crossref","unstructured":"Dods C, Smart NP, Stam M (2005) Hash based digital signature schemes. In: IMA international conference on cryptography and coding. Springer, Berlin, pp 96\u2013115","DOI":"10.1007\/11586821_8"},{"key":"117_CR27","doi-asserted-by":"crossref","unstructured":"Eaton E (2017) Leighton-Micali hash-based signatures in the quantum random-oracle model. In: International conference on selected areas in cryptography. Springer, Cham, pp 263\u2013280","DOI":"10.1007\/978-3-319-72565-9_13"},{"issue":"6","key":"117_CR28","doi-asserted-by":"publisher","first-page":"661","DOI":"10.1103\/PhysRevLett.67.661","volume":"67","author":"AK Ekert","year":"1991","unstructured":"Ekert AK (1991) Quantum cryptography based on Bell\u2019s theorem. Phys Rev Lett 67(6):661","journal-title":"Phys Rev Lett"},{"issue":"4","key":"117_CR29","doi-asserted-by":"publisher","first-page":"469","DOI":"10.1109\/TIT.1985.1057074","volume":"31","author":"T ElGamal","year":"1985","unstructured":"ElGamal T (1985) A public key cryptosystem and a signature scheme based on discrete logarithms. IEEE Trans Inf Theory 31(4):469\u2013472","journal-title":"IEEE Trans Inf Theory"},{"key":"117_CR30","doi-asserted-by":"crossref","unstructured":"Even S, Goldreich O, Micali S (1996) On-line\/off-line digital signatures. In: 1996 International association for cryptologic research","DOI":"10.1007\/BF02254791"},{"issue":"1","key":"117_CR31","doi-asserted-by":"publisher","first-page":"145","DOI":"10.1103\/RevModPhys.74.145","volume":"74","author":"N Gisin","year":"2002","unstructured":"Gisin N, Ribordy G, Tittel W et al (2002) Quantum cryptography. Rev Mod Phys 74(1):145","journal-title":"Rev Mod Phys"},{"issue":"2","key":"117_CR32","doi-asserted-by":"publisher","first-page":"281","DOI":"10.1137\/0217017","volume":"17","author":"S Goldwasser","year":"1988","unstructured":"Goldwasser S, Micali S, Rivest RL (1988) A digital signature scheme secure against adaptive chosen-message attacks. SIAM J Comput 17(2):281\u2013308","journal-title":"SIAM J Comput"},{"issue":"5","key":"117_CR33","doi-asserted-by":"publisher","first-page":"75","DOI":"10.1088\/1367-2630\/8\/5\/075","volume":"8","author":"S Gr\u00f6blacher","year":"2006","unstructured":"Gr\u00f6blacher S, Jennewein T, Vaziri A et al (2006) Experimental quantum cryptography with qutrits. New J Phys 8(5):75","journal-title":"New J Phys"},{"key":"117_CR34","doi-asserted-by":"crossref","unstructured":"Halevi S, Krawczyk H (2006) Strengthening digital signatures via randomized hashing. In: CRYPTO 06","DOI":"10.1007\/11818175_3"},{"key":"117_CR35","doi-asserted-by":"crossref","unstructured":"H\u00fclsing A (2013) W-OTS+\u2013shorter signatures for hash-based signature schemes. In: International conference on cryptology in Africa. Springer, Berlin, pp 173\u2013188","DOI":"10.1007\/978-3-642-38553-7_10"},{"key":"117_CR36","doi-asserted-by":"crossref","unstructured":"H\u00fclsing A, Rausch L, Buchmann J (2013) Optimal parameters for XMSSMT. In: International conference on availability, reliability, and security. Springer, pp 194\u2013208","DOI":"10.1007\/978-3-642-40588-4_14"},{"key":"117_CR37","doi-asserted-by":"crossref","unstructured":"H\u00fclsing A, Rijneveld J, Song F (2016) Mitigating multi-target attacks in hash-based signatures. In: Public-key cryptography\u2013PKC 2016. Springer, Berlin, pp 387\u2013416","DOI":"10.1007\/978-3-662-49384-7_15"},{"key":"117_CR38","doi-asserted-by":"crossref","unstructured":"H\u00fclsing A, Butin D, Gazdag S, Rijneveld J, Mohaisen A (2018) RFC8391-XMSS: eXtended hash-based signatures. RFC 8391, RFC Editor","DOI":"10.17487\/RFC8391"},{"key":"117_CR39","doi-asserted-by":"crossref","unstructured":"Jakobsson M (2002) Fractal hash sequence representation and traversal. In: Proceedings IEEE international symposium on information theory. IEEE, p 437","DOI":"10.1109\/ISIT.2002.1023709"},{"key":"117_CR40","doi-asserted-by":"crossref","unstructured":"Jakobsson M, Leighton T, Micali S et al (2003) Fractal Merkle tree representation and traversal. In: Cryptographers\u2019 track at the RSA conference. Springer, Berlin, pp 314\u2013326","DOI":"10.1007\/3-540-36563-X_21"},{"key":"117_CR41","unstructured":"Kampanakis P, Fluhrer SR (2017) Lms vs xmss: a comparison of the stateful hash-based signature proposed standards. IACR Cryptology ePrint Archive"},{"key":"117_CR42","doi-asserted-by":"crossref","unstructured":"Katz J (2016) Analysis of a proposed hash-based signature standard. In: International conference on research in security standardisation. Springer, pp 261\u2013273","DOI":"10.1007\/978-3-319-49100-4_12"},{"key":"117_CR43","unstructured":"Knecht M, Meier W, Nicola CU (2014) A space-and time-efficient Implementation of the Merkle Tree Traversal Algorithm. arXiv:1409.4081"},{"key":"117_CR44","doi-asserted-by":"crossref","unstructured":"Krawczyk H (2000) Simple forward-secure signatures from any signature scheme. In: Proceedings of the 7th ACM conference on computer and communications security, pp 108\u2013115","DOI":"10.1145\/352600.352617"},{"key":"117_CR45","unstructured":"Lamport L (1979) Constructing digital signatures from a one-way function. Technical Report CSL-98, SRI International Palo Alto"},{"key":"117_CR46","unstructured":"Leighton FT, Micali A (1995) Large provably fast and secure digital signature schemes based on secure hash functions. US Patent 5,432,852"},{"key":"117_CR47","doi-asserted-by":"crossref","unstructured":"McGrew D, Curcio M, Fluhrer S (2019) Leighton-Micali hash-based signatures. RFC 8554, IRTF","DOI":"10.17487\/RFC8554"},{"key":"117_CR48","doi-asserted-by":"publisher","DOI":"10.1201\/9780429466335","volume-title":"Handbook of applied cryptography","author":"AJ Menezes","year":"2018","unstructured":"Menezes AJ, Van Oorschot PC, Vanstone SA (2018) Handbook of applied cryptography. CRC Press, Boca Raton"},{"key":"117_CR49","volume-title":"Secrecy, authentication, and public key systems","author":"RC Merkle","year":"1979","unstructured":"Merkle RC (1979a) Secrecy, authentication, and public key systems. Stanford University, Stanford"},{"key":"117_CR50","unstructured":"Merkle RC (1979b) Secrecy, \u201cAuthentication and public key systems\u201d. Ph.D. Thesis, Stanford"},{"key":"117_CR51","doi-asserted-by":"crossref","unstructured":"Merkle RC (1989) A certified digital signature. In: Conference on the theory and application of cryptology. Springer, New York, pp 218\u2013238","DOI":"10.1007\/0-387-34805-0_21"},{"key":"117_CR52","unstructured":"Naor D, Shenhav A, Wool A (2005) One-time signatures revisited: Have they become practical? IACR Cryptol. ePrint Arch"},{"key":"117_CR53","doi-asserted-by":"crossref","unstructured":"Naor D, Shenhav A, Wool A (2006) One-time signatures revisited: practical fast signatures using fractal merkle tree traversal. In: 2006 IEEE 24th convention of electrical and electronics engineers in Israel. IEEE, pp 255\u2013259","DOI":"10.1109\/EEEI.2006.321066"},{"key":"117_CR54","doi-asserted-by":"crossref","unstructured":"Perrig A (2001) The BiBa one-time signature and broadcast authentication protocol. In: Proceedings of the 8th ACM conference on computer and communications security, pp 28\u201337","DOI":"10.1145\/501983.501988"},{"key":"117_CR55","unstructured":"Perrig A, Canetti R, Song D et al (2001) Efficient and secure source authentication for multicast. In: Network and distributed system security symposium, NDSS, vol 1, pp 35\u201346"},{"issue":"2","key":"117_CR56","first-page":"2","volume":"5","author":"A Perrig","year":"2002","unstructured":"Perrig A, Canetti R, Tygar JD et al (2002) The TESLA broadcast authentication protocol. RSA Cryptobytes 5(2):2\u201313","journal-title":"RSA Cryptobytes"},{"key":"117_CR57","doi-asserted-by":"crossref","unstructured":"Preneel B, Govaerts R, Vandewalle J (1993) Hash functions based on block ciphers: a synthetic approach. In: Advances in cryptology\u2014CRYPTO \u201993. Santa Barbara, California, USA","DOI":"10.1145\/168588.168611"},{"key":"117_CR58","doi-asserted-by":"crossref","unstructured":"Reyzin L, Reyzin N (2002) Better than BiBa: short one-time signatures with fast signing and verifying. In: Australasian conference on information security and privacy. Springer, pp 144\u2013153","DOI":"10.1007\/3-540-45450-0_11"},{"issue":"2","key":"117_CR59","doi-asserted-by":"publisher","first-page":"120","DOI":"10.1145\/359340.359342","volume":"21","author":"RL Rivest","year":"1978","unstructured":"Rivest RL, Shamir A, Adleman L (1978) A method for obtaining digital signatures and public-key cryptosystems. Commun ACM 21(2):120\u2013126","journal-title":"Commun ACM"},{"key":"117_CR60","doi-asserted-by":"crossref","unstructured":"Rogaway P, Shrimpton T (2004) Cryptographic hash-function basics: definitions, implications, and separations for preimage resistance, second-preimage resistance, and collision resistance. In: International workshop on fast software encryption. Springer, Berlin, pp 371\u2013388","DOI":"10.1007\/978-3-540-25937-4_24"},{"key":"117_CR61","doi-asserted-by":"crossref","unstructured":"Sella Y (2003) On the computation-storage trade-offs of hash chain traversal. In: International conference on financial cryptography. Springer, Berlin, pp 270\u2013285","DOI":"10.1007\/978-3-540-45126-6_20"},{"issue":"2","key":"117_CR62","doi-asserted-by":"publisher","first-page":"303","DOI":"10.1137\/S0036144598347011","volume":"41","author":"PW Shor","year":"1999","unstructured":"Shor PW (1999) Polynomial-time algorithms for prime factorization and discrete logarithms on a quantum computer. SIAM Rev 41(2):303\u2013332","journal-title":"SIAM Rev"}],"container-title":["Cybersecurity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-022-00117-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/article\/10.1186\/s42400-022-00117-w\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1186\/s42400-022-00117-w.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,7,1]],"date-time":"2022-07-01T01:03:47Z","timestamp":1656637427000},"score":1,"resource":{"primary":{"URL":"https:\/\/cybersecurity.springeropen.com\/articles\/10.1186\/s42400-022-00117-w"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,1]]},"references-count":62,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2022,12]]}},"alternative-id":["117"],"URL":"https:\/\/doi.org\/10.1186\/s42400-022-00117-w","relation":{},"ISSN":["2523-3246"],"issn-type":[{"value":"2523-3246","type":"electronic"}],"subject":[],"published":{"date-parts":[[2022,7,1]]},"assertion":[{"value":"19 November 2021","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"15 February 2022","order":2,"name":"accepted","label":"Accepted","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"1 July 2022","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}},{"order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Declarations"}},{"value":"The authors declare that they have no competing interests.","order":2,"name":"Ethics","group":{"name":"EthicsHeading","label":"Competing interests"}}],"article-number":"13"}}