Comparative analysis of post-quantum digital signature protocols based on hash functions
DOI:
https://doi.org/10.17721/1812-5409.2026/1.24Keywords:
hash function, digital signatures, post-quantum protocols, one-time digital signatures, multi-time digital signatures, chain-based schemes, tree-based schemesAbstract
In the era of active information technologies and device development, the emergence of portable and general-purpose quantum computers is only a matter of time. And although the benefit of their many times greater efficiency, compared to ordinary bit computers, will be obvious, at the same time, they will bring many vulnerabilities to modern algorithms of cryptography and cybersecurity. To prevent this from happening, society has already started researching post-quantum protocols to replace modern ones.
Digital signature protocols were no exception. Thus, one of the approaches was constructing post-quantum digital signature protocols based on hash functions. The first representatives were schemes of one-time signatures based on hash functions, which were protected from the capabilities of quantum computers but had the obvious disadvantage of one-time use. The most famous is the so-called Lamport one-time signature. However, this disadvantage of one-time use has been solved by proposing different schemes of multi-time digital signatures based on the creation and use of many one-time signatures. Thus, chain-based and tree-based schemes of multi-time signatures were proposed. This work is devoted to the implementation and comparison of various multi-time signature schemes.
During the research, theoretical estimates of memory usage and time required for the operations of various schemes were given. Further implementation of these schemes and final measurements showed the correspondence of theoretical estimates with empirical results and clearly demonstrated the advantages and disadvantages of different schemes. Thus, tree-based schemes showed the best performance, especially those where the tree is built sequentially. However, in certain cases, it makes sense to use a tree with full-depth construction.
Due to the relative novelty and small amount of research in this field, multi-time digital signatures have much room for further research, for example, considering N-ary trees and comparing them with binary ones.
Pages of the article in the issue: 176 - 186
Language of the article: Ukrainian
References
Bleichenbacher, D., & Maurer, U. M. (1994). Directed Acyclic Graphs, One-way Functions and Digital Signatures. In Y. G. Desmedt (Eds.), Lecture Notes in Computer Science: Vol. 839. Advances in Cryptology – CRYPTO '94 (pp. 75–82). Springer. https://doi.org/10.1007/3-540-48658-5_9
Boneh D., & Shoup, V. (2017). A Graduate Course in Applied Cryptography. https://crypto.stanford.edu/~dabo/cryptobook/BonehShoup_0_6.pdf
Hülsing, A. (2013). W-OTS+ – Shorter Signatures for Hash-Based Signature Schemes. In A. Youssef, A. Nitaj, & A. E. Hassanien, (Eds.), Lecture Notes in Computer Science: Vol. 7918. Progress in Cryptology – AFRICACRYPT 2013 (pp. 173–188). Springer. https://doi.org/10.1007/978-3-642-38553-7_10
Katz, J., & Lindell, Y. (2014). Introduction to Modern Cryptography (Second Edition). Chapman and Hall/CRC. https://doi.org/10.1201/b17668
Lizama-Pérez, L. A. (2022). Digital signatures over HMAC entangled chains. Engineering Science and Technology, an International Journal, 32(101076). https://doi.org/10.1016/j.jestch.2021.11.002
Merkle, R. C. (1989). A Certified Digital Signature. In G. Brassard (Eds.), Lecture Notes in Computer Science: Vol. 435. Advances in Cryptology – CRYPTO' 89 Proceedings (pp. 218–238). Springer. https://doi.org/10.1007/0-387-34805-0_21
NIST (2015). FIPS PUB 180-4: Secure Hash Standard (SHS). https://doi.org/10.6028/NIST.FIPS.180-4
Perrig, A. (2001). The BiBa one-time signature and broadcast authentication protocol. In P. Samarati (Eds.), CCS '01: Proceedings of the 8th ACM conference on Computer and Communications Security (pp. 28–37). Association for Computing Machinery. https://doi.org/10.1145/501983.501988
Reyzin, L., & Reyzin, N. (2002). Better than BiBa: Short One-Time Signatures with Fast Signing and Verifying. In L. Batten, & J. Seberry (Eds.), Lecture Notes in Computer Science: Vol. 2384. Information Security and Privacy (pp. 144–153). Springer. https://doi.org/10.1007/3-540-45450-0_11
Downloads
Published
Issue
Section
License
Copyright (c) 2026 Oleksii Bashuk
This work is licensed under a Creative Commons Attribution 4.0 International License.
Authors who publish with this journal agree to the following terms:
- Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
- Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
- Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work (See The Effect of Open Access).
