Постквантовые двухключевые криптосхемы на конечных алгебрах
Ключевые слова:
постквантовая криптография, многомерная криптография, конечная алгебра, некоммутативная алгебра, векторное конечное поле, нелинейные отображенияАннотация
Одним из направлений разработки практичных постквантовых криптографических алгоритмов с открытым ключом является использование конечных алгебр в качестве их алгебраического носителя. Рассматриваются два подхода в этом направлении: 1) построение алгоритмов электронной цифровой подписи со скрытой группой на некоммутативных ассоциативных алгебр и 2) построение алгоритмов многомерной криптографии с использованием операции экспоненцирования в векторном конечном поле (коммутативной алгебре, являющейся конечным полем) для задания нелинейного отображения с секретной лазейкой. Первый подход включает разработку криптосхем двух типов: основанных на вычислительной трудности а) скрытой задачи дискретного логарифмирования и б) решения большой системы квадратных уравнений. Для второго подхода возникают проблемы обеспечения полной рандомизации цифровой подписи и задания некоммутативных ассоциативных алгебр большой размерности. Обсуждаются способы решения данных проблем. Показана важность исследования строения конечных некоммутативных алгебр с точки зрения декомпозиции на множество коммутативных подалгебр. Другое направление использования конечных алгебр для разработки криптографических алгоритмов с открытым ключом связано с существенным (в 10 и более раз) уменьшением размера открытого ключа в алгоритмах многомерной криптографии. В нем возникает проблема разработки формализованных параметризуемых унифицированных способов задания векторных конечных полей больших размерностей (от 5 до 130) с достаточно большим числом потенциально реализуемых типов и модификаций (до 2500 и более), задаваемых различными наборами структурных констант, с помощью которых определяется операция умножения векторов. Предложены варианты указанных способов и топологий нелинейных отображений на векторных конечных полях различных размерностей. Показано, что использование отображений, задающих операцию экспоненцирования в векторных конечных полях, потенциально обеспечивает устранение основного недостатка известных алгоритмов многомерной криптографии, связанного с большим размером открытого ключа.
Литература
2. Shor P.W. Polynomial-time algorithms for prime factorization and discrete logarithms on quantum computer // SIAM Journal of Computing. 1997. vol. 26. pp. 1484–1509.
3. Post-Quantum Cryptography. Proceedings of the 13th International Conference, PQCrypto 2022 // Lecture Notes in Computer Science. 2022. vol. 13512.
4. Johansson T., Smith-Tone D. Post-Quantum Cryptography. Proceedings of the 14th International Conference, PQCrypto 2023 // Lecture Notes in Computer Science. 2023. vol. 14154.
5. Alagic G, Cooper D., Dang Q., Dang T., Kelsey J., Lichtinger J., Liu Y., Miller C., Moody D., Peralta R., Perlner R., Robinson A., Smith-Tone D., Apon D. Status Report on the Third Round of the NIST Post-Quantum Cryptography Standardization Process // NIST Interagency/Internal Report (NISTIR), National Institute of Standards and Technology. 2022. URL: https://tsapps.nist.gov/publication/get_pdf.cfm?pub_id=934458 (дата обращения: 25.02.2024).
6. Han J., Zhuang J. DLP in semigroups: algorithms and lower bounds // J. Math. Cryptol. 2022. vol. 16. no. 1. pp. 278–288.
7. 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. 2023. vol. 14154. pp. 113–138. DOI: 10.1007/978-3-031-40003-2_5.
8. Vysotskaya V.V., Chizhov I.V. The security of the code-based signature scheme based on the Stern identification protocol // Applied Discrete Mathematics. 2022. № 57. С. 67−90. DOI: 10.17223/20710410/57/5.
9. Kosolapov Y.V., Turchenko O.Y. On the construction of a semantically secure modification of the McEliece cryptosystem // Applied Discrete Mathematics. 2019. № 45. С. 33−43. DOI: 10.17223/20710410/45/4.
10. Gartner J. NTWE: A Natural Combination of NTRU and LWE // Post-Quantum Cryptography. PQCrypto 2023. Lecture Notes in Computer Science, 2023. vol. 14154. pp. 321–353. DOI: 10.1007/978-3-031-40003-2_12.
11. Lysakov I.V.. Solving some cryptanalytic problems for lattice-based cryptosystems with quantum annealing method // Mathematical Aspects of Cryptography. 2023. vol. 14. no. 2. pp. 111–122. DOI: 10.4213/mvk441.
12. 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. 2019. vol. 11505. pp. 329–349. DOI: 10.1007/978-3-030-25510-7_18.
13. Agibalov G.P. ElGamal cryptosystems on Boolean functions / Applied Discrete Mathematics. 2018. № 42. С. 57−65. DOI: 10.17223/20710410/42/4.
14. Ding J., Petzoldt A., Schmidt D.S. Multivariate Cryptography // Multivariate Public Key Cryptosystems. Advances in Information Security. 2020. vol. 80. DOI: 10.1007/978-1-0716-0987-3_2.
15. Debnath S., Kundu N., Mishra D., Choudhury T. Post-quantum digital signature scheme based on multivariate cubic problem // Journal of Information Security and Applications. 2020. vol. 53. DOI: 10.1016/j.jisa.2020.102512.
16. Ding J., Petzoldt A., Schmidt D.S. Oil and Vinegar // Multivariate Public Key Cryptosystems. Advances in Information Security. 2020. vol. 80. pp. 89–151. Springer, New York. DOI: 10.1007/978-1-0716-0987-3_5.
17. Cartor R., Cartor M., Lewis M., Smith-Tone D. IPRainbow // Post-Quantum Cryptography. PQCrypto 2022. Lecture Notes in Computer Science. 2022. vol. 13512. pp. 170–184. DOI: 10.1007/978-3-031-17234-2_9.
18. Beullens W. MAYO: practical post-quantum signatures from oil-and-vinegar maps // Proceedings of the International Conference on Selected Areas in Cryptography (SAC 2021). Lecture Notes in Computer Science. 2022. vol. 13203. pp. 355–376.
19. Молдовян А.А., Молдовян Д.Н., Молдовян Н.А. Новый подход к разработке алгоритмов многомерной криптографии // Вопросы кибербезопасности. 2023. № 2(54). С. 52–64. DOI: 10.21681/2311-3456-2023-2-52-6.
20. Moldovyan A.A., Moldovyan N.A. Vector finite fields of characteristic two as algebraic support of multivariate cryptography // Computer Science Journal of Moldova. 2024. no. 1(94). pp. 46–60. DOI: 10.56415/csjm.v32.04.
21. Duong M.T., Moldovyan D.N., Do B.V., Nguyen M.H. Post-quantum signature algorithms on non-commutative algebras, using difficulty of solving systems of quadratic equations // Computer Standards and Interfaces. 2023, vol. 86. no. 103740. DOI: 10.1016/j.csi.2023.103740.
22. Moldovyan D.N. A practical digital signature scheme based on the hidden logarithm problem // Computer Science Journal of Moldova. 2021. vol. 29, no. 2(86). pp. 206–226.
23. Moldovyan N.A., Moldovyanu P.A. Vector Form of the Finite Fields GF(pm) // Bulletin of Academy of Sciences of Moldova. Mathematics. 2009. no. 3(61). pp. 57–63.
24. Ding J., Petzoldt A., Schmidt D.S. Solving Polynomial Systems // In: Multivariate Public Key Cryptosystems. Advances in Information Security. Springer. New York. 2020. vol. 80. pp. 185–248. DOI: 10.1007/978-1-0716-0987-3_8.
25. Ding J., Petzoldt A. Current State of Multivariate Cryptography // IEEE Security and Privacy. 2017. vol. 15. no. 4. pp. 28–36.
26. Qiao S., Han W., Li Y., Jiao L. Construction of Extended Multivariate Public Key Cryptosystems // International Journal of Network Security. 2016. vol. 18. no. 1. pp. 60–67.
27. Rainbow Signature. One of three NIST Post-quantum Signature Finalists [on line] 2021. URL: https://www.pqcrainbow.org/ (дата обращения: 25.02.2024).
Опубликован
Как цитировать
Раздел
Copyright (c) Николай Андреевич Молдовян, Александр Андреевич Молдовян, Дмитрий Николаевич Молдовян
Это произведение доступно по лицензии Creative Commons «Attribution» («Атрибуция») 4.0 Всемирная.
Авторы, которые публикуются в данном журнале, соглашаются со следующими условиями: Авторы сохраняют за собой авторские права на работу и передают журналу право первой публикации вместе с работой, одновременно лицензируя ее на условиях Creative Commons Attribution License, которая позволяет другим распространять данную работу с обязательным указанием авторства данной работы и ссылкой на оригинальную публикацию в этом журнале. Авторы сохраняют право заключать отдельные, дополнительные контрактные соглашения на неэксклюзивное распространение версии работы, опубликованной этим журналом (например, разместить ее в университетском хранилище или опубликовать ее в книге), со ссылкой на оригинальную публикацию в этом журнале. Авторам разрешается размещать их работу в сети Интернет (например, в университетском хранилище или на их персональном веб-сайте) до и во время процесса рассмотрения ее данным журналом, так как это может привести к продуктивному обсуждению, а также к большему количеству ссылок на данную опубликованную работу (Смотри The Effect of Open Access).