Башук, ОлексійОлексійБашук2026-06-302026-06-302026-06-05Башук, О. (2026). Comparative analysis of post-quantum digital signature protocols based on hash functions. Bulletin of Taras Shevchenko National University of Kyiv. Physics and Mathematics, 82(1), 2218–2055. https://doi.org/10.17721/1812-5409.2026/1.2410.17721/1812-5409.2026/1.24https://ir.library.knu.ua/handle/15071834/26001In 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В епоху активного розвитку інформаційних технологій і пристроїв поява портативних та загальнозастосовних квантових комп'ютерів є лише питанням часу. І хоч користь від їхньої в рази більшої ефективності, порівняно зі звичайними бітовими комп'ютерами, буде очевидною, водночас вони принесуть і багато вразливостей до сучасних алгоритмів криптографії та кібербезпеки. Щоб запобігти цьому, фахівці вже розпочали роботу над дослідженнями постквантових протоколів замість сучасних. Не стали винятком і протоколи цифрового підпису. Наприклад, одним із підходів розв'язання окресленої проблеми є побудова постквантових протоколів цифрового підпису, базованих на геш-функціях. Першими варіантами стали схеми одноразових підписів, базованих на геш-функціях, які були захищені від можливостей квантових комп'ютерів, проте мали очевидну ваду одноразовості. Найвідомішим вважають так званий одноразовий підпис Лампорта. Однак цей недолік одноразовості усунули, запропонувавши різні схеми багаторазових цифрових підписів, базованих на створенні та використанні багатьох одноразових підписів. Були запропоновані ланцюгоподібні та деревоподібні схеми багаторазових підписів. Саме реалізації та порівнянню різних схем багаторазового підпису і присвячено пропоновану роботу. У ході досліджень наведено теоретичні оцінки використання пам'яті та часу, необхідні для роботи різних схем. Подальша реалізація цих схем й остаточні заміри виявили відповідність теоретичних оцінок емпіричним результатам, а також явно продемонстрували переваги та недоліки різних схем. Найкращу продуктивність, зокрема, показали деревоподібні схеми, особливо ті, у яких дерево будується послідовно. Проте в певних випадках має сенс використовувати дерево з повним заглибленням під час побудови. З огляду на відносну новизну та малу кількість досліджень у цій галузі, багаторазові цифрові підписи мають великий простір для подальших досліджень, наприклад, розгляд N-арних дерев та їхнього порівняння з бінарними.enhash functiondigital signaturespost-quantum protocolsone-time digital signaturesmulti-time digital signatureschain-based schemestree-based schemesгеш-функціяцифрові підписипостквантові протоколиодноразові цифрові підписибагаторазові цифрові підписиланцюгоподібні схемидеревоподібні схемиСтаття