Порівняльний аналіз постквантових протоколів цифрового підпису, базованих на геш-функціях

Башук, О. (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.24

В епоху активного розвитку інформаційних технологій і пристроїв поява портативних та загальнозастосовних квантових комп'ютерів є лише питанням часу. І хоч користь від їхньої в рази більшої ефективності, порівняно зі звичайними бітовими комп'ютерами, буде очевидною, водночас вони принесуть і багато вразливостей до сучасних алгоритмів криптографії та кібербезпеки. Щоб запобігти цьому, фахівці вже розпочали роботу над дослідженнями постквантових протоколів замість сучасних.
Не стали винятком і протоколи цифрового підпису. Наприклад, одним із підходів розв'язання окресленої проблеми є побудова постквантових протоколів цифрового підпису, базованих на геш-функціях. Першими варіантами стали схеми одноразових підписів, базованих на геш-функціях, які були захищені від можливостей квантових комп'ютерів, проте мали очевидну ваду одноразовості. Найвідомішим вважають так званий одноразовий підпис Лампорта. Однак цей недолік одноразовості усунули, запропонувавши різні схеми багаторазових цифрових підписів, базованих на створенні та використанні багатьох одноразових підписів. Були запропоновані ланцюгоподібні та деревоподібні схеми багаторазових підписів. Саме реалізації та порівнянню різних схем багаторазового підпису і присвячено пропоновану роботу.
У ході досліджень наведено теоретичні оцінки використання пам'яті та часу, необхідні для роботи різних схем. Подальша реалізація цих схем й остаточні заміри виявили відповідність теоретичних оцінок емпіричним результатам, а також явно продемонстрували переваги та недоліки різних схем. Найкращу продуктивність, зокрема, показали деревоподібні схеми, особливо ті, у яких дерево будується послідовно. Проте в певних випадках має сенс використовувати дерево з повним заглибленням під час побудови.
З огляду на відносну новизну та малу кількість досліджень у цій галузі, багаторазові цифрові підписи мають великий простір для подальших досліджень, наприклад, розгляд N-арних дерев та їхнього порівняння з бінарними.