chebЧебышевский сборникChebyshevskii Sbornik2226-8383Tula State Lev Tolstoy Pedagogical University10.22405/2226-8383-2021-22-2-76-89cheb-983Research ArticleСтатьиArticleОб одном алгоритме проверки существования подквазигруппAn algorithm for checking the existence of subquasigroupsГалатенкоАлексей ВладимировичGalatenkoAlexei Vladimirovich

кандидат физико-математических наук

candidate of physical and mathematical sciences

agalat@msu.ruПанкратьевАнтон ЕвгеньевичPankratievAnton Evgen’evich

кандидат физико-математических наук

candidate of physical and mathematical sciences

apankrat@intsys.msu.ruСтароверовВладими МихайловичStaroverovVladimir Mikhailovich

кандидат физико-математических наук

candidate of physical and mathematical sciences

staroverovvl@imscs.msu.ruМосковский государственный университет имени М. В. ЛомоносоваРоссияLomonosov Moscow State UniversityRussian FederationLomonosov Moscow State UniversityRussian Federation2021010620212227689Copyright © Галатенко А.В., Панкратьев А.Е., Староверов В.М., 20212021Галатенко А.В., Панкратьев А.Е., Староверов В.М.Galatenko A.V., Pankratiev A.E., Staroverov V.M.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.chebsbornik.ru/jour/article/view/983

Криптографические алгоритмы на основе квазигрупп активно изучаются в рамках перспективных исследований; кроме того, в последние годы регулярно появляются квази-групповые алгоритмы-кандидаты на конкурсах криптографических стандартов. С точки зрения обеспечения стойкости одним из желательных требований, предъявляемых к квазигруппам, является отсутствие подквазигрупп (в противном случае преобразованиеможет вырождаться). В работе предлагаются оптимизированные по временной сложности(за счет увеличения пространственной сложности) алгоритмы проверки наличия подквазигрупп и подквазигрупп порядка не меньше 2 в квазигруппах, заданных таблицей Кэли.Доказываются утверждения о сложности в худшем случае, а также приводятся оценки эффективности программной реализации на квазигруппах большого порядка. Результа-ты работы были анонсированы в рамках доклада на XVIII Международной конференции «Алгебра, теория чисел и дискретная геометрия: современные проблемы, приложения и проблемы истории».

Quasigroup-based cryptoalgorithms are being actively studied in the framework of theoretic projects; besides that, a number of quasigroup-based algorithms took part in NIST contestsfor selection of cryptographic standards. From the viewpoint of security it is highly desirable to use quasigroups without proper subquasigroups (otherwise transformations can degrade).We propose algorithms that take a quasigroup specified by the Cayley table as the input and decide whether there exist proper subquasigroups or subquasigroups of the order at least 2.Temporal complexity of the algorithms is optimized at the cost of increased spatial complexity.We prove bounds on time and memory and analyze the efficiency of software implementations applied to quasigroups of a large order. The results were reported at the XVIII InternationalConference «Algebra, Number Theory and Discrete Geometry: modern problems, applications and problems of history».

квазигруппаподквазигруппатаблица КэлиquasigroupsubquasigroupCayley tableРабота выполнена при финансовой поддержке DRDO (Индия), проект “Quasigroup Based Cryptography: Security Analysis and Development of Crypto-Primitives and Algorithms (QGSEC)”, номер гранта SAG/4600/TCID/Prog/QGSEC”ReferencesMarkov 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.Markov, V. T., Mikhalev, A. V. & Nechaev, A. A. 2020, “Nonassociative algebraic structures in cryptography and coding“, J. Math. Sci., vol. 245, no. 2, pp. 178–196. doi: 10.1007/s10958-020-04685-5.doi: 10.1007/s10958-020-04685-5.Shannon, C. 1949, “Communication theory of secrecy systems“, Bell Syst. tech., vol. 28, no. 4,Shannon C. Communication theory of secrecy systems // Bell System Technical Journal. 1949.pp. 656–715. doi: 10.1002/j.1538-7305.1949.tb00928.xVol. 28, no. 4. P. 656–715. doi: 10.1002/j.1538-7305. 1949.tb00928.x.Glukhov, M. M. 2008, “Some applications of quasigroups in cryptography“, Prikl. Discr. Mat., no. 2, pp. 28–32 (in Russian).Глухов М. М. О применениях квазигрупп в криптографии // Прикладная дискретная математика. 2008. №2. С. 28–32.Shcherbacov, V. A. 2009, “Quasigroups in cryptology“, CSJM, vol. 17, no. 2(50), pp. 193–228.Shcherbacov V. A. Quasigroups in cryptology // Computer Science Journal of Moldova. 2009. Vol. 17, no. 2(50). P. 193–228.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’“, Proc. 1st Int. Wksh.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 Internationalon Security and Communication Networks. Trondheim, 2009, pp. 1–9.Workshop on Security and Communication Networks. 2009. P. 1–9.Gligoroski, D. On the S-box in GAGE and InGAGE (2019), Available at http://gageingage.Gligoroski D. On the S-box in GAGE and InGAGE [электронный ресурс]. 2019. URL: http:org/upload/LWC2019NISTWorkshop.pdf (accessed 14 October 2020).//gageingage.org/upload/LWC2019NISTWorkshop.pdf (дата обращения: 14.10.2020).Gligoroski, D., Ødeg˚ard, R., Jensen, R., Perret, L., Faug`ere, J.-C., Knapskog, S. & Markovski, S.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:“MQQ–SIG: an ultra-fast and provably CMA resistant digital signature scheme“, INTRUST’11: Proc. 3rd Int. Conf on Trusted Systems. Beijing, 2011. pp. 184–203. doi: 10.1007/978-3-642-Proceedings of the Third international conference on Trusted Systems. 2011. P. 184–203. doi: 10.1007/978-3-642-32298-3_13.-3_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.Horv´ath, G, Nehaniv, Gh. L & Szab´o, Cs. 2008, “An assertion concerning functionally complete algebras and NP-completeness“, Theor. Comput. Sci., vol. 407, pp. 591–595. doi: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.1016/j.tcs.2008.08.028.Vol. 16. P. 563–581. doi: 10.1142/S0218196706003116Larose, B. & Z´adori, L. 2006, “Taylor terms, constraint satisfaction and the complexity of polynomial equations over finite algebras“, Int. J. Algebra Comput., vol. 16, pp. 563–581. doi: 10.1142/S0218196706003116.Cameron P.J. Almost all quasigroups have rank 2 // Discrete Mathematics. 1992. Vol. 106–107.Cameron, P.J. 1992, “Almost all quasigroups have rank 2“, Discrete Math., vol. 116-117, pp. 111– 115. doi: 10.1016/0012-365X(92)90537-P.P. 111–115. doi: 10.1016/0012-365X(92)90537-PGalatenko, A. V. & Pankratiev, A.E. 2020, “The complexity of checking the polynomial completeness of finite quasigroups“, Discret. Math. Appl., vol. 30, no. 3, pp. 169–175. doi: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.1515/dma-2020-0016.doi: 10.1515/dma-2020-0016.Galatenko, A. V., Pankratiev, A. E. & Staroverov, V. M. 2020, “Efficient verification of polynomial completeness of quasigroups“, Lobachevskii J. Math., vol. 41, no. 8, pp. 1444–1453. doi: 10.1134/S1995080220080053.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,Jacobson, M. T. & Matthews, P. 1996, “Generating uniformly distributed random latin squares“, J. Comb. Des., vol. 4, no. 6, pp. 405–437. doi: 10.1002/(SICI)1520-6610(1996)4:6<405::AIDJCD3>3.0.CO;2-Jaccepted for publication.Galatenko, A. V., Nosov, V. A. & Pankratiev, A.E. 2020, “Latin squares over quasigroups“, Lobachevskii J. Math., vol. 41, no. 2, pp. 194–203. doi: 10.1134/S1995080220020079Jacobson 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-JSobyanin, P.I. 2019, “An algorithm that decides if a quasigroup contains subquasigroups“, Intellektualnye sistemy. Teoria i prilojenia, vol. 23, no. 2, pp. 79–84 (in Russian).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/S1995080220020079Galatenko, A. V., Pankratiev, A. E. & Staroverov, V. M. “An algorithm for checking the existence of nontrivial subquasigroups“, Materialy XVIII Mejdunarodnoi Konferentsii “Algebra, Teoria Chisel i Discretnaya Geometria: Sovremennye Problemy, Prilojenia i Problemy Istorii“ (Proc. 18th Int. Conf. “Algebra, number theory and discrete geometry: modern problems, applications and problems of history“). Tula, 2020, pp. 150–153 (in Russian).Собянин П. И. Об алгоритме проверки наличия подквазигруппы в квазигруппе // Интеллектуальные системы. Теория и приложения. 2019. Т. 23, № 2. С. 79–84.Собянин П. И. Об алгоритме проверки наличия подквазигруппы в квазигруппе // Интеллектуальные системы. Теория и приложения. 2019. Т. 23, № 2. С. 79–84.Галатенко А. В., Панкратьев А. Е., Староверов В. М. Об одном алгоритме проверки существования нетривиальных подквазигрупп // Материалы XVIII Международной конференции «Алгебра, теория чисел и дискретная геометрия: современные проблемы, приложенияГалатенко А. В., Панкратьев А. Е., Староверов В. М. Об одном алгоритме проверки существования нетривиальных подквазигрупп // Материалы XVIII Международной конференции «Алгебра, теория чисел и дискретная геометрия: современные проблемы, приложенияи проблемы истории», Тула, 2020, С. 150–153.и проблемы истории», Тула, 2020, С. 150–153.

The authors declare that there are no conflicts of interest present.