Постквантовый алгоритм ЭЦП на основе трудности решения степенных уравнений
Ключевые слова:
постквантовая криптография, алгоритм ЭЦП, конечная алгебра матриц, система степенных уравнений, секретная группаАннотация
Вычислительная сложность нахождения решений больших систем нелинейных уравнений (БСНУ) лежит в основе ряда постквантовых двухключевых криптосхем, включая алгебраические алгоритмы цифровой подписи с использованием матриц в качестве элементов секретного ключа. Такие алгоритмы относятся к вероятностным криптосхемам и характеризуются использованием некоторой матрицы S в качестве подгоночного элемента подписи. Последнее обусловливает актуальность рассмотрения стойкости к атакам, использующим известные подписи. При этом лобовой (прямой) атакой является атака на основе решения БСНУ. В известных алгебраических алгоритмах цифровой подписи в рамках лобовой атаки возникают недоопределенные БСНУ с большим числом решений, что создает предпосылки к атакам на основе эквивалентных ключей. В статье рассматривается построение постквантового алгоритма на конечных алгебрах квадратных матриц, при прямой атаке на который возникают близкие к сбалансированным (с равным числом уравнений и неизвестных) и переопределенные БСНУ (с числом уравнений, превышающим число неизвестных). Особенностью предложенного алгоритма является использование вспомогательных скрытых групп, вспомогательного параметра рандомизации ЭЦП, вычисляемого как значение сжимающей односторонней функции от значения S. Приводится оценка стойкости к лобовой атаке и нескольким вариантам атак на основе известных подписей.
Литература
1. Post-Quantum Cryptography. 16-th International Conference, PQCrypto 2025, Taipei, Taiwan, April 8–10, 2025. Proceedings, Part I // Lecture Notes in Computer Science. Springer. 2023. vol. 15577. DOI: 10.1007/978-3-031-86599-2.
2. Post-Quantum Cryptography. 16-th International Conference, PQCrypto 2025, Taipei, Taiwan, April 8–10, 2025. Proceedings, Part II // Lecture Notes in Computer Science. Springer. 2023. vol. 15578. DOI: 10.1007/978-3-031-86602-9.
3. Post-Quantum Cryptography. 15-th International Conference, PQCrypto 2024, Oxford, UK, June 12–14, 2024, Proceedings // Lecture Notes in Computer Science. Springer. 2024. vol. 14771–14772. DOI: 10.1007/978-3-031-62743-9.
4. Yan S.Y. Quantum Computational Number Theory // Cham: Springer, 2015. 252 p. DOI: 10.1007/978-3-319-25823-2.
5. Yan S.Y. Quantum Attacks on Public-Key Cryptosystems // New York: Springer, 2013. 207 p. DOI: 10.1007/978-1-4419-7722-9.
6. Codes, Cryptology and Information Security. 4th International Conference, C2SI 2023, Rabat, Morocco, May 29–31, 2023 // Lecture Notes in Computer Science. Springer. 2023. vol. 13874. 265 p. DOI: 10.1007/978-3-031-33017-9.
7. Baldi M., Battaglioni M., Chiaraluce F., et al. A new path to code-based signatures via identification schemes with restricted errors // Advances in Mathematics of Communications. 2025. vol. 19. no. 5. pp. 13601381. DOI: 10.3934/amc.2024058.
8. Vysotskaya V.V., Chizhov I.V. The security of the code-based signature scheme based on the Stern identification protocol // Прикладная дискретная математика. 2022. №57. С. 67–90. DOI: 10.17223/20710410/57/5.
9. Ниткин И.С. Применение метода компактного описания подстановки для модификации схемы цифровой подписи на основе протокола аутентификации Штерна // Информационно-управляющие системы. 2025. №6. С. 51–63. DOI: 10.31799/1684-8853-2025-6-51-63.
10. Bidoux L., Gaborit P., Kulkarni M., et al. Code-based signatures from new proofs of knowledge for the syndrome decoding problem // Designs, Codes and Cryptography. 2023. vol. 91. pp. 497–544. DOI: 10.1007/s10623-022-01114-3.
11. Baldi M., Bitzer S., Pavoni A., Santini P., Wachter-Zeh A., Weger V. Zero Knowledge Protocols and Signatures from the Restricted Syndrome Decoding Problem / In: Tang, Q., Teague, V. (eds) / Public-Key Cryptography – PKC 2024. PKC 2024 // Lecture Notes in Computer Science. Springer. 2024. vol. 14602. pp. 243–274. DOI: 0.1007/978-3-031-57722-2_8.
12. Feneuil T., Joux A., Rivain M. Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature // Designs, Codes and Cryptography. 2023. vol. 91. pp. 563–608. DOI: 10.1007/s10623-022-01116-1.
13. Feneuil T., Joux A., Rivain M. Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs // Lecture Notes in Computer Science. Springer. 2022. vol. 13508. pp. 541–572. DOI: 10.1007/978-3-031-15979-4_19.
14. Battarbee C., Kahrobaei D., Perret L., Shahandashti S.F. SPDH-Sign: Towards Efficient, Post-quantum Group-Based Signatures / In: Johansson T., Smith-Tone D. (eds) / Post-Quantum Cryptography. PQCrypto 2023 // Lecture Notes in Computer Science. Springer. 2023. vol. 14154. pp. 113–138. DOI: 10.1007/978-3-031-40003-2_5.
15. Agibalov G.P. ElGamal cryptosystems on Boolean functions // Прикладная дискретная математика. 2018. №42. C. 57–65. DOI: 10.17223/20710410/42/4.
16. Gartner J. NTWE: A Natural Combination of NTRU and LWE / In: Johansson T., Smith-Tone D. (eds) / Post-Quantum Cryptography. PQCrypto 2023 // Lecture Notes in Computer Science. Springer. 2023. vol. 14154. pp. 321–353. DOI: 10.1007/978-3-031-40003-2_12.
17. Lysakov I.V. Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method // Математические вопросы криптографии. 2023. Т. 14. №2. С. 111–122. DOI: 10.4213/mvk441.
18. Hamlin B., Song F. Quantum Security of Hash Functions and Property-Preservation of Iterated Hashing / In: Ding, J., Steinwandt, R. (eds) / Post-Quantum Cryptography. PQCrypto 2019 // Lecture Notes in Computer Science. Springer. 2019. vol. 11505. pp. 329–349. DOI: 10.1007/978-3-030-25510-7_18.
19. Ikematsu Y., Nakamura S., Takagi T. Recent progress in the security evaluation of multivariate public‐key cryptography // IET Information Security. 2022. vol. 17. no. 2. pp. 210–226. DOI: 10.1049/ise2.12092.
20. Ding J., Petzoldt A., Schmidt D.S. Multivariate Cryptography / In: Multivariate Public Key Cryptosystems // Advances in Information Security. Springer. 2020. vol. 80. pp. 7–23. DOI: 10.1007/978-1-0716-0987-3_2.
21. Ding J., Petzoldt A., Schmidt D.S. Oil and Vinegar / In: Multivariate Public Key Cryptosystems // Advances in Information Security. Springer. 2020. vol. 80. pp. 89–150. DOI: 10.1007/978-1-0716-0987-3_5.
22. Moldovyan N.A. Parameterized method for specifying vector finite fields of arbitrary dimensions // Quasigroups and related systems. 2024. vol. 32. no. 2. pp. 299–312. DOI: 10.56415/qrs.v32.21.
23. Moldovyan N.A. Finite algebras in the design of multivariate cryptography algorithms // Bulletin of Academy of Sciences of Moldova. Mathematics. 2023. no. 3(103). pp. 80–89. DOI: 10.56415/basm.y2023.i3.p80.
24. Молдовян А.А., Молдовян Д.Н., Молдовян Н.А. Постквантовые двухключевые криптосхемы на конечных алгебрах // Информатика и автоматизация. 2024. Т. 23. №4. С. 1246–1276. DOI: 10.15622/ia.23.4.12.
25. Молдовян А.А., Молдовян Д.Н., Костина А.А. Рандомизация в постквантовых алгоритмах ЭЦП с секретной группой // Информатика и автоматизация. 2025. Т. 24. №6. С. 1810–1835. DOI: 10.15622/ia.24.6.9.
26. Dinh K.L., Do T.B., Moldovyan N.A., Petrenko A.S. Typical Algebraic Signature Schemes with Two Hidden Groups / In: Dang, T.K., Kung, J., Chung, T.M. (eds) / Future Data and Security Engineering. FDSE 2025 // Communications in Computer and Information Science. Springer. 2026. vol 2709. pp. 83–99. DOI: 10.1007/978-981-95-4724-1_7.
27. Ma Y. Cryptanalysis of the cryptosystems based on the generalized hidden discrete logarithm problem // Computer Science Journal of Moldova. 2024. vol. 32. no. 2(95). pp. 289–3070. DOI: 10.56415/csjm.v.32.15.
28. Ding J., Petzoldt A. Current State of Multivariate Cryptography // IEEE Security and Privacy Magazine. 2017. vol. 15. no. 4. pp. 28–36. DOI: 10.1109/MSP.2017.3151328.
2. Post-Quantum Cryptography. 16-th International Conference, PQCrypto 2025, Taipei, Taiwan, April 8–10, 2025. Proceedings, Part II // Lecture Notes in Computer Science. Springer. 2023. vol. 15578. DOI: 10.1007/978-3-031-86602-9.
3. Post-Quantum Cryptography. 15-th International Conference, PQCrypto 2024, Oxford, UK, June 12–14, 2024, Proceedings // Lecture Notes in Computer Science. Springer. 2024. vol. 14771–14772. DOI: 10.1007/978-3-031-62743-9.
4. Yan S.Y. Quantum Computational Number Theory // Cham: Springer, 2015. 252 p. DOI: 10.1007/978-3-319-25823-2.
5. Yan S.Y. Quantum Attacks on Public-Key Cryptosystems // New York: Springer, 2013. 207 p. DOI: 10.1007/978-1-4419-7722-9.
6. Codes, Cryptology and Information Security. 4th International Conference, C2SI 2023, Rabat, Morocco, May 29–31, 2023 // Lecture Notes in Computer Science. Springer. 2023. vol. 13874. 265 p. DOI: 10.1007/978-3-031-33017-9.
7. Baldi M., Battaglioni M., Chiaraluce F., et al. A new path to code-based signatures via identification schemes with restricted errors // Advances in Mathematics of Communications. 2025. vol. 19. no. 5. pp. 13601381. DOI: 10.3934/amc.2024058.
8. Vysotskaya V.V., Chizhov I.V. The security of the code-based signature scheme based on the Stern identification protocol // Прикладная дискретная математика. 2022. №57. С. 67–90. DOI: 10.17223/20710410/57/5.
9. Ниткин И.С. Применение метода компактного описания подстановки для модификации схемы цифровой подписи на основе протокола аутентификации Штерна // Информационно-управляющие системы. 2025. №6. С. 51–63. DOI: 10.31799/1684-8853-2025-6-51-63.
10. Bidoux L., Gaborit P., Kulkarni M., et al. Code-based signatures from new proofs of knowledge for the syndrome decoding problem // Designs, Codes and Cryptography. 2023. vol. 91. pp. 497–544. DOI: 10.1007/s10623-022-01114-3.
11. Baldi M., Bitzer S., Pavoni A., Santini P., Wachter-Zeh A., Weger V. Zero Knowledge Protocols and Signatures from the Restricted Syndrome Decoding Problem / In: Tang, Q., Teague, V. (eds) / Public-Key Cryptography – PKC 2024. PKC 2024 // Lecture Notes in Computer Science. Springer. 2024. vol. 14602. pp. 243–274. DOI: 0.1007/978-3-031-57722-2_8.
12. Feneuil T., Joux A., Rivain M. Shared permutation for syndrome decoding: new zero-knowledge protocol and code-based signature // Designs, Codes and Cryptography. 2023. vol. 91. pp. 563–608. DOI: 10.1007/s10623-022-01116-1.
13. Feneuil T., Joux A., Rivain M. Syndrome Decoding in the Head: Shorter Signatures from Zero-Knowledge Proofs // Lecture Notes in Computer Science. Springer. 2022. vol. 13508. pp. 541–572. DOI: 10.1007/978-3-031-15979-4_19.
14. Battarbee C., Kahrobaei D., Perret L., Shahandashti S.F. SPDH-Sign: Towards Efficient, Post-quantum Group-Based Signatures / In: Johansson T., Smith-Tone D. (eds) / Post-Quantum Cryptography. PQCrypto 2023 // Lecture Notes in Computer Science. Springer. 2023. vol. 14154. pp. 113–138. DOI: 10.1007/978-3-031-40003-2_5.
15. Agibalov G.P. ElGamal cryptosystems on Boolean functions // Прикладная дискретная математика. 2018. №42. C. 57–65. DOI: 10.17223/20710410/42/4.
16. Gartner J. NTWE: A Natural Combination of NTRU and LWE / In: Johansson T., Smith-Tone D. (eds) / Post-Quantum Cryptography. PQCrypto 2023 // Lecture Notes in Computer Science. Springer. 2023. vol. 14154. pp. 321–353. DOI: 10.1007/978-3-031-40003-2_12.
17. Lysakov I.V. Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method // Математические вопросы криптографии. 2023. Т. 14. №2. С. 111–122. DOI: 10.4213/mvk441.
18. Hamlin B., Song F. Quantum Security of Hash Functions and Property-Preservation of Iterated Hashing / In: Ding, J., Steinwandt, R. (eds) / Post-Quantum Cryptography. PQCrypto 2019 // Lecture Notes in Computer Science. Springer. 2019. vol. 11505. pp. 329–349. DOI: 10.1007/978-3-030-25510-7_18.
19. Ikematsu Y., Nakamura S., Takagi T. Recent progress in the security evaluation of multivariate public‐key cryptography // IET Information Security. 2022. vol. 17. no. 2. pp. 210–226. DOI: 10.1049/ise2.12092.
20. Ding J., Petzoldt A., Schmidt D.S. Multivariate Cryptography / In: Multivariate Public Key Cryptosystems // Advances in Information Security. Springer. 2020. vol. 80. pp. 7–23. DOI: 10.1007/978-1-0716-0987-3_2.
21. Ding J., Petzoldt A., Schmidt D.S. Oil and Vinegar / In: Multivariate Public Key Cryptosystems // Advances in Information Security. Springer. 2020. vol. 80. pp. 89–150. DOI: 10.1007/978-1-0716-0987-3_5.
22. Moldovyan N.A. Parameterized method for specifying vector finite fields of arbitrary dimensions // Quasigroups and related systems. 2024. vol. 32. no. 2. pp. 299–312. DOI: 10.56415/qrs.v32.21.
23. Moldovyan N.A. Finite algebras in the design of multivariate cryptography algorithms // Bulletin of Academy of Sciences of Moldova. Mathematics. 2023. no. 3(103). pp. 80–89. DOI: 10.56415/basm.y2023.i3.p80.
24. Молдовян А.А., Молдовян Д.Н., Молдовян Н.А. Постквантовые двухключевые криптосхемы на конечных алгебрах // Информатика и автоматизация. 2024. Т. 23. №4. С. 1246–1276. DOI: 10.15622/ia.23.4.12.
25. Молдовян А.А., Молдовян Д.Н., Костина А.А. Рандомизация в постквантовых алгоритмах ЭЦП с секретной группой // Информатика и автоматизация. 2025. Т. 24. №6. С. 1810–1835. DOI: 10.15622/ia.24.6.9.
26. Dinh K.L., Do T.B., Moldovyan N.A., Petrenko A.S. Typical Algebraic Signature Schemes with Two Hidden Groups / In: Dang, T.K., Kung, J., Chung, T.M. (eds) / Future Data and Security Engineering. FDSE 2025 // Communications in Computer and Information Science. Springer. 2026. vol 2709. pp. 83–99. DOI: 10.1007/978-981-95-4724-1_7.
27. Ma Y. Cryptanalysis of the cryptosystems based on the generalized hidden discrete logarithm problem // Computer Science Journal of Moldova. 2024. vol. 32. no. 2(95). pp. 289–3070. DOI: 10.56415/csjm.v.32.15.
28. Ding J., Petzoldt A. Current State of Multivariate Cryptography // IEEE Security and Privacy Magazine. 2017. vol. 15. no. 4. pp. 28–36. DOI: 10.1109/MSP.2017.3151328.
Опубликован
2026-06-08
Как цитировать
Молдовян, А. А., Молдовян, Н. А., Молдовян, Д. Н., & Костина, А. А. (2026). Постквантовый алгоритм ЭЦП на основе трудности решения степенных уравнений. Информатика и автоматизация, 25(3), 958-985. https://doi.org/10.15622/ia.25.3.11
Раздел
Информационная безопасность
Copyright (c) Александр Андреевич Молдовян, Николай Молдовян, Дмитрий Молдовян, Анна Костина
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).