Постквантовые двухключевые криптосхемы на конечных алгебрах

Обложка

Цитировать

Полный текст

Аннотация

Одним из направлений разработки практичных постквантовых криптографических алгоритмов с открытым ключом является использование конечных алгебр в качестве их алгебраического носителя. Рассматриваются два подхода в этом направлении: 1) построение алгоритмов электронной цифровой подписи со скрытой группой на некоммутативных ассоциативных алгебр и 2) построение алгоритмов многомерной криптографии с использованием операции экспоненцирования в векторном конечном поле (коммутативной алгебре, являющейся конечным полем) для задания нелинейного отображения с секретной лазейкой. Первый подход включает разработку криптосхем двух типов: основанных на вычислительной трудности а) скрытой задачи дискретного логарифмирования и б) решения большой системы квадратных уравнений. Для второго подхода возникают проблемы обеспечения полной рандомизации цифровой подписи и задания некоммутативных ассоциативных алгебр большой размерности. Обсуждаются способы решения данных проблем. Показана важность исследования строения конечных некоммутативных алгебр с точки зрения декомпозиции на множество коммутативных подалгебр. Другое направление использования конечных алгебр для разработки криптографических алгоритмов с открытым ключом связано с существенным (в 10 и более раз) уменьшением размера открытого ключа в алгоритмах многомерной криптографии. В нем возникает проблема разработки формализованных параметризуемых унифицированных способов задания векторных конечных полей больших размерностей (от 5 до 130) с достаточно большим числом потенциально реализуемых типов и модификаций (до 2500 и более), задаваемых различными наборами структурных констант, с помощью которых определяется операция умножения векторов. Предложены варианты указанных способов и топологий нелинейных отображений на векторных конечных полях различных размерностей. Показано, что использование отображений, задающих операцию экспоненцирования в векторных конечных полях, потенциально обеспечивает устранение основного недостатка известных алгоритмов многомерной криптографии, связанного с большим размером открытого ключа.

Об авторах

А. А Молдовян

Санкт-Петербургский Федеральный исследовательский центр Российской академии наук (СПб ФИЦ РАН)

Email: maa1305@yandex.ru
14-я линия В.О. 39

Д. Н Молдовян

Санкт-Петербургский государственный электротехнический университет «ЛЭТИ»

Email: mdn.spectr@mail.ru
улица профессора Попова 5

Н. А Молдовян

Санкт-Петербургский Федеральный исследовательский центр Российской академии наук (СПб ФИЦ РАН)

Email: nmold@mail.ru
14-я линия В.О. 39

Список литературы

  1. Ekert A., Jozsa R. Quantum computation and Shor’s factoring algorithm // Reviews of Modern Physics. 1996. vol. 68. no. 3. pp. 733–752.
  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).

Дополнительные файлы

Доп. файлы
Действие
1. JATS XML
Скачать

Согласие на обработку персональных данных

 

Используя сайт https://journals.rcsi.science, я (далее – «Пользователь» или «Субъект персональных данных») даю согласие на обработку персональных данных на этом сайте (текст Согласия) и на обработку персональных данных с помощью сервиса «Яндекс.Метрика» (текст Согласия).