An algorithm for checking the existence of subquasigroups
https://doi.org/10.22405/2226-8383-2021-22-2-76-89
Abstract
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 contests
for 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 International
Conference «Algebra, Number Theory and Discrete Geometry: modern problems, applications and problems of history».
About the Authors
Alexei Vladimirovich Galatenko
Lomonosov Moscow State University
Russian Federation
Russian Federation
candidate of physical and mathematical sciences
Anton Evgen’evich Pankratiev
Lomonosov Moscow State University
Russian Federation
Russian Federation
candidate of physical and mathematical sciences
Vladimir Mikhailovich Staroverov
Lomonosov Moscow State University
Russian Federation
Russian Federation
candidate of physical and mathematical sciences
References
1. 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.
2. Shannon, C. 1949, “Communication theory of secrecy systems“, Bell Syst. tech., vol. 28, no. 4,
3. pp. 656–715. doi: 10.1002/j.1538-7305.1949.tb00928.x
4. Glukhov, M. M. 2008, “Some applications of quasigroups in cryptography“, Prikl. Discr. Mat., no. 2, pp. 28–32 (in Russian).
5. Shcherbacov, V. A. 2009, “Quasigroups in cryptology“, CSJM, vol. 17, no. 2(50), pp. 193–228.
6. 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.
7. on Security and Communication Networks. Trondheim, 2009, pp. 1–9.
8. Gligoroski, D. On the S-box in GAGE and InGAGE (2019), Available at http://gageingage.
9. org/upload/LWC2019NISTWorkshop.pdf (accessed 14 October 2020).
10. Gligoroski, D., Ødeg˚ard, R., Jensen, R., Perret, L., Faug`ere, J.-C., Knapskog, S. & Markovski, S.
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-
12. -3_13.
13. 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:
14. 1016/j.tcs.2008.08.028.
15. Larose, 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.
16. 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.
17. Galatenko, 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:
18. 1515/dma-2020-0016.
19. 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.
20. 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-J
21. 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/S1995080220020079
22. Sobyanin, 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).
23. Galatenko, 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).
Review
For citations:
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
Views:
540
Email this article 