Preview

Чебышевский сборник

Расширенный поиск

Об одном алгоритме проверки существования подквазигрупп

https://doi.org/10.22405/2226-8383-2021-22-2-76-89

Полный текст:

Аннотация

Криптографические алгоритмы на основе квазигрупп активно изучаются в рамках перспективных исследований; кроме того, в последние годы регулярно появляются квази-
групповые алгоритмы-кандидаты на конкурсах криптографических стандартов. С точки зрения обеспечения стойкости одним из желательных требований, предъявляемых к квазигруппам, является отсутствие подквазигрупп (в противном случае преобразование
может вырождаться). В работе предлагаются оптимизированные по временной сложности
(за счет увеличения пространственной сложности) алгоритмы проверки наличия подквазигрупп и подквазигрупп порядка не меньше 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.


Для цитирования:


Галатенко А.В., Панкратьев А.Е., Староверов В.М. Об одном алгоритме проверки существования подквазигрупп. Чебышевский сборник. 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

Просмотров: 10


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 2226-8383 (Print)