Рандомизация в постквантовых алгоритмах ЭЦП с секретной группой
Ключевые слова:
постквантовая криптография, многомерная криптография, алгоритм ЭЦП, рандомизация ЭЦП, криптоалгоритм на конечных алгебрах, криптосхема на некоммутативных алгебрах, секретная группаАннотация
В области постквантовой двухключевой криптографии значительный интерес представляет разработка практичных алгебраических схем электронной цифровой подписи (ЭЦП) с секретной группой, стойкость которых базируется на вычислительной сложности решения систем степенных уравнений с многими неизвестными. В качестве алгебраического носителя в таких криптосхемах используются ассоциативные некоммутативные конечные алгебры (АНКА). Специфическим моментом, связанным с обеспечением стойкости к атакам на основе известных подписей при разработке схем ЭЦП данного типа, является наличие проблемы совершенствования механизма рандомизации подгоночного элемента цифровой подписи, представляющего собой вектор S, многократно входящий в уравнение верификации в качестве множителя. Известное решение этой проблемы на основе вычисления S в зависимости от двух векторов, выбираемых случайным образом из двух коммутативных секретных групп, таких, что элементы одной из них некоммутативны с элементами другой, при использовании в проверочном уравнении значения хеш-функции от S приводит к увеличению размера ЭЦП, обусловленного необходимостью задания двух вспомогательных подгоночных элементов подписи. В статье предлагается новый механизм рандомизации подписи, отличающийся вычислением значения S в зависимости от двух векторов, выбираемых случайным образом из одной коммутативной секретной группы. Предложенный механизм обеспечивает приемлемый уровень стойкости к атакам на основе известных подписей и может быть положен в основу разработки схем ЭЦП с одним уравнением верификации и одним вспомогательным подгоночным элементом подписи. Разработан новый алгебраический алгоритм ЭЦП, представляющий интерес как прототип практичного постквантового стандарта ЭЦП. Даны оценки его параметров при реализации на четырехмерных АНКА и на алгебре матриц 3×3, заданных над простым конечным полем.
Литература
2. Johansson T., Smith-Tone D. Post-Quantum Cryptography. 14-th International Conference, PQCrypto 2023, College Park, MD, USA, Proceedings // Lecture Notes in Computer Science. Springer, Cham, 2023. 714 p. DOI: 10.1007/978-3-031-40003-2.
3. Yan S.Y. Quantum Computational Number Theory. Springer. 2015. 252 p. DOI: 10.1007/978-3-319-25823-2.
4. Yan S.Y. Quantum Attacks on Public-Key Cryptosystems. Springer. 2014. 207 p. DOI: 10.1007/978-1-4419-7722-9.
5. Battarbee C., Kahrobaei D., Perret L., Shahandashti S.F. SPDH-Sign: Towards Efficient, Post-quantum Group-Based Signatures // Post-Quantum Cryptography. PQCrypto 2023. Lecture Notes in Computer Science. Springer, Cham, 2023. vol. 14154. DOI: 10.1007/978-3-031-40003-2_5.
6. Alamelou Q., Blazy O., Cauchie S., Gaborit P. A code-based group signature scheme // Designs, Codes and Cryptography. 2017. vol. 82. pp. 469–493. DOI: 10.1007/s10623-016-0276-6.
7. Kosolapov Y.V., Turchenko O.Y. On the construction of a semantically secure modification of the McEliece cryptosystem // Prikladnaya Diskretnaya Matematika. 2019. no. 45. pp. 33−43. DOI: 10.17223/20710410/45/4.
8. Gärtner J. NTWE: A Natural Combination of NTRU and LWE // Post-Quantum Cryptography. PQCrypto 2023. Lecture Notes in Computer Science, Springer, Cham, 2023. vol. 14154. DOI: 10.1007/978-3-031-40003-2_12.
9. Lysakov I.V. Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method // Matematicheskie Voprosy Kriptografii [Mathematical Aspects of Cryptography]. 2023. vol. 14. no. 2. pp. 111–122. DOI: 10.4213/mvk441.
10. Hamlin B., Song F. Quantum Security of Hash Functions and Property-Preservation of Iterated Hashing. Post-Quantum Cryptography. PQCrypto 2019. Lecture Notes in Computer Science. Springer, Cham, 2019. vol. 11505. pp. 329–349. DOI: 10.1007/978-3-030-25510-7_18.
11. Agibalov G.P. ElGamal cryptosystems on Boolean functions // Prikladnaya Diskretnaya Matematika. 2018. no. 42. pp. 57–65. DOI: 10.17223/20710410/42/4.
12. Shuaiting Q., Wenbao H., Yifa Li, Luyao J. Construction of Extended Multivariate Public Key Cryptosystems // International Journal of Network Security. 2016. vol. 18. no. 1. pp. 60–67.
13. Ding J., Petzoldt A. Current State of Multivariate Cryptography // IEEE Security and Privacy Magazine. 2017. vol. 15. no. 4. pp. 28–36.
14. Ding J., Petzoldt A., Schmidt D.S. Multivariate Cryptography // Multivariate Public Key Cryptosystems. Advances in Information Security. Springer, New York, NY, 2020. vol. 80. pp. 7–23. DOI: 10.1007/978-1-0716-0987-3_2.
15. Cartor R., Cartor M., Lewis M., Smith-Tone D. IPRainbow // Post-Quantum Cryptography. Lecture Notes in Computer Science. Springer, Cham, 2022. vol. 13512. pp. 170–184. DOI: 10.1007/978-3-031-17234-2_9.
16. 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.
17. 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.
18. Moldovyan N.A. Algebraic signature algorithms with a hidden group, based on hardness of solving systems of quadratic equations // Quasigroups and Related Systems. 2022. vol. 30. no. 2(48). pp. 287–298. DOI: 10.56415/qrs.v30.24.
19. Moldovyan D.N. A new type of digital signature algorithms with a hidden group // Computer Science Journal of Moldova. 2023. vol. 31. no. 1(91). pp. 111–124. DOI: 10.56415/csjm.v31.06.
20. Молдовян А.А., Молдовян Д.Н., Молдовян Н.А. Постквантовые двухключевые криптосхемы на конечных алгебрах // Информатика и автоматизация. 2024. Т. 23. № 4. С. 1246–1276. DOI: 10.15622/ia.23.4.12.
21. Молдовян Н.А, Петренко А.С. Алгебраический алгоритм ЭЦП с двумя скрытыми группами // Вопросы кибербезопасности. 2024. № 6(64). С. 98–107. DOI: 10.21681/2311-3456-2024-6-98-107.
22. Молдовян Н.А, Петренко А.С. Типовые уравнения верификации в схемах ЭЦП с двумя скрытыми группами // Вопросы кибербезопасности. 2025. № 3(67). С. 45–54. DOI: 10.21681/2311-3456-2025-3-ХХ-ХХ. (в печати)
23. Moldovyan N.A. Unified Method for Defining Finite Associative Algebras of Arbitrary Even Dimensions // Quasigroups and Related Systems. 2018. vol. 26. no. 2. pp. 263–270.
24. Moldovyan N.A., Moldovyan A.A. Finite Non-commutative Associative Algebras as carriers of Hidden Discrete Logarithm Problem. Bulletin of the South Ural State University. Ser. Mathematical Modelling, Programming and Computer Software (Bulletin SUSU MMCS). 2019. vol. 12. no. 1. pp. 66–81. DOI: 10.14529/mmp190106.
25. Moldovyan D.N., Moldovyan A.A., Moldovyan N.A. Structure of a finite non-commutative algebra set by a sparse multiplication table // Quasigroups and Related Systems. 2022, vol. 30. no. 1. pp. 133–140. DOI: 10.56415/qrs.v30.11.
26. Duong M.T., Moldovyan A.A., Moldovyan D.N., Nguyen M.H., Do B.T. Structure of quaternion-type algebras and a post-quantum signature algorithm // International Journal of Electrical and Computer Engineering (IJECE). 2025. vol. 15. no. 3. pp. 2965–2976. DOI: 10.11591/ijece.v15i3.pp2965-2976.
Опубликован
Как цитировать
Раздел
Copyright (c) Александр Андреевич Молдовян, Дмитрий Николаевич Молдовян, Анна Александровна Костина
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).