Об одном алгоритме проверки существования подквазигрупп
Аннотация
Криптографические алгоритмы на основе квазигрупп активно изучаются в рамках перспективных исследований; кроме того, в последние годы регулярно появляются квази-
групповые алгоритмы-кандидаты на конкурсах криптографических стандартов. С точки зрения обеспечения стойкости одним из желательных требований, предъявляемых к квазигруппам, является отсутствие подквазигрупп (в противном случае преобразование
может вырождаться). В работе предлагаются оптимизированные по временной сложности
(за счет увеличения пространственной сложности) алгоритмы проверки наличия подквазигрупп и подквазигрупп порядка не меньше 2 в квазигруппах, заданных таблицей Кэли.
Доказываются утверждения о сложности в худшем случае, а также приводятся оценки эффективности программной реализации на квазигруппах большого порядка. Результа-
ты работы были анонсированы в рамках доклада на XVIII Международной конференции «Алгебра, теория чисел и дискретная геометрия: современные проблемы, приложения и проблемы истории».
Об авторах
Алексей Владимирович Галатенко
Московский государственный университет имени М. В. Ломоносова
Россия
Россия
кандидат физико-математических наук
Антон Евгеньевич Панкратьев
Lomonosov Moscow State University
Россия
Россия
кандидат физико-математических наук
Владими Михайлович Староверов
Московский государственный университет имени М. В. Ломоносова
Россия
Россия
кандидат физико-математических наук
Список литературы
1. Markov V. T., Mikhalev A. V., Nechaev A. A. Nonassociative algebraic structures in cryptography and coding // Journal of Mathematical Sciences. 2020. Vol. 245, no. 2. P. 178–196.
2. doi: 10.1007/s10958-020-04685-5.
3. Shannon C. Communication theory of secrecy systems // Bell System Technical Journal. 1949.
4. Vol. 28, no. 4. P. 656–715. doi: 10.1002/j.1538-7305. 1949.tb00928.x.
5. Глухов М. М. О применениях квазигрупп в криптографии // Прикладная дискретная математика. 2008. №2. С. 28–32.
6. Shcherbacov V. A. Quasigroups in cryptology // Computer Science Journal of Moldova. 2009. Vol. 17, no. 2(50). P. 193–228.
7. Gligoroski D., Ødegˇard R. S., Mihova M., Knapskog S. J., Drapal A., Kl´ıma V., Amundsen J., El-Hadedy M. Cryptographic hash function EDON-R’ // Proceedings of the 1st International
8. Workshop on Security and Communication Networks. 2009. P. 1–9.
9. Gligoroski D. On the S-box in GAGE and InGAGE [электронный ресурс]. 2019. URL: http:
10. //gageingage.org/upload/LWC2019NISTWorkshop.pdf (дата обращения: 14.10.2020).
11. Gligoroski D., Ødeg˚ard R., Jensen R., Perret L., Faug`ere J.-C., Knapskog S., Markovski S. MQQ–SIG: an ultra-fast and provably CMA resistant digital signature scheme // INTRUST’11:
12. Proceedings of the Third international conference on Trusted Systems. 2011. P. 184–203. doi: 10.1007/978-3-642-32298-3_13.
13. Horv´ath G, Nehaniv Gh. L, Szab´o Cs. An assertion concerning functionally complete algebras and NP-completeness // Theoretical Computer Science. 2008. Vol. 407. P. 591–595. doi: 10.1016/j.tcs.2008.08.028.
14. Larose B., Z´adori L. Taylor terms, constraint satisfaction and the complexity of polynomial equations over finite algebras // International Journal of Algebra and Computation. 2006.
15. Vol. 16. P. 563–581. doi: 10.1142/S0218196706003116
16. Cameron P.J. Almost all quasigroups have rank 2 // Discrete Mathematics. 1992. Vol. 106–107.
17. P. 111–115. doi: 10.1016/0012-365X(92)90537-P
18. Galatenko A. V., Pankratiev A.E. The complexity of checking the polynomial completeness of finite quasigroups // Discrete Mathematics and Applications. 2020. Vol. 30, no. 3. P. 169–175.
19. doi: 10.1515/dma-2020-0016.
20. Galatenko A. V., Pankratiev A.E., Staroverov V. M. Efficient verification of polynomial completeness of quasigroups // Lobachevskii Journal of Mathematics. 2020. Vol. 41, no. 8,
21. accepted for publication.
22. Jacobson M. T., Matthews P. Generating uniformly distributed random latin squares // Journal of Combinatorial Designs. 1996. Vol. 4, no. 6. P. 405–437. doi: 10.1002/(SICI)1520- 6610(1996)4:6<405::AID-JCD3>3.0.CO;2-J
23. Galatenko A. V., Nosov V. A., Pankratiev A.E. Latin squares over quasigroups // Lobachevskii Journal of Mathematics. 2020. Vol. 41, no. 2. P. 194–203. doi: 10.1134/S1995080220020079
24. Собянин П. И. Об алгоритме проверки наличия подквазигруппы в квазигруппе // Интеллектуальные системы. Теория и приложения. 2019. Т. 23, № 2. С. 79–84.
25. Галатенко А. В., Панкратьев А. Е., Староверов В. М. Об одном алгоритме проверки существования нетривиальных подквазигрупп // Материалы XVIII Международной конференции «Алгебра, теория чисел и дискретная геометрия: современные проблемы, приложения
26. и проблемы истории», Тула, 2020, С. 150–153.
При поддержке: Работа выполнена при финансовой поддержке DRDO (Индия), проект “Quasigroup Based Cryptography: Security Analysis and Development of Crypto-Primitives and Algorithms (QGSEC)”, номер гранта SAG/4600/TCID/Prog/QGSEC”
Для цитирования:
Галатенко А.В., Панкратьев А.Е., Староверов В.М. Об одном алгоритме проверки существования подквазигрупп. Чебышевский сборник. 2021;22(2):76-89. https://doi.org/10.22405/2226-8383-2021-22-2-76-89
For citation:
Galatenko A.V., Pankratiev A.E., Staroverov V.M. An algorithm for checking the existence of subquasigroups. Chebyshevskii Sbornik. 2021;22(2):76-89. (In Russ.) https://doi.org/10.22405/2226-8383-2021-22-2-76-89
Просмотров: 104
Послать статью по эл. почте 