Geodesic
An algorithm for checking the existence of subquasigroups
Čebyševskij sbornik, Tome 22 (2021) no. 2, pp. 76-89.

Voir la notice de l'article provenant de la source Math-Net.Ru

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».
Keywords: quasigroup, subquasigroup, Cayley table. 
@article{CHEB_2021_22_2_a4,
     author = {A. V. Galatenko and A. E. Pankratiev and V. M. Staroverov},
     title = {An algorithm for checking the existence of subquasigroups},
     journal = {\v{C}eby\v{s}evskij sbornik},
     pages = {76--89},
     publisher = {mathdoc},
     volume = {22},
     number = {2},
     year = {2021},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/CHEB_2021_22_2_a4/}
}
TY  - JOUR
AU  - A. V. Galatenko
AU  - A. E. Pankratiev
AU  - V. M. Staroverov
TI  - An algorithm for checking the existence of subquasigroups
JO  - Čebyševskij sbornik
PY  - 2021
SP  - 76
EP  - 89
VL  - 22
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/CHEB_2021_22_2_a4/
LA  - ru
ID  - CHEB_2021_22_2_a4
ER  - 
%0 Journal Article
%A A. V. Galatenko
%A A. E. Pankratiev
%A V. M. Staroverov
%T An algorithm for checking the existence of subquasigroups
%J Čebyševskij sbornik
%D 2021
%P 76-89
%V 22
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/CHEB_2021_22_2_a4/
%G ru
%F CHEB_2021_22_2_a4
A. V. Galatenko; A. E. Pankratiev; V. M. Staroverov. An algorithm for checking the existence of subquasigroups. Čebyševskij sbornik, Tome 22 (2021) no. 2, pp. 76-89. http://geodesic.mathdoc.fr/item/CHEB_2021_22_2_a4/

[1] Markov V. T., Mikhalev A. V., Nechaev A. A., “Nonassociative algebraic structures in cryptography and coding”, Journal of Mathematical Sciences, 245:2 (2020), 178–196 | DOI | MR | Zbl

[2] Shannon C., “Communication theory of secrecy systems”, Bell System Technical Journal, 28:4 (1949), 656–715 | DOI | MR | Zbl

[3] Glukhov M. M., “O primeneniyakh kvazigrupp v kriptografii”, Prikladnaya diskretnaya matematika, 2008, no. 2, 28–32 | Zbl

[4] Shcherbacov V. A., “Quasigroups in cryptology”, Computer Science Journal of Moldova, 17:2(50) (2009), 193–228 | MR | Zbl

[5] Gligoroski D., Ødegǎrd 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 Workshop on Security and Communication Networks, 2009, 1–9

[6] Gligoroski D., On the S-box in GAGE and InGAGE, 2019 (accessed 14 October 2020) http://gageingage.org/upload/LWC2019NISTWorkshop.pdf

[7] Gligoroski D., Ødeg{å}rd R., Jensen R., Perret L., Faugère J.-C., Knapskog S., Markovski S., “MQQ–SIG: an ultra-fast and provably CMA resistant digital signature scheme”, INTRUST'11: Proceedings of the Third international conference on Trusted Systems, 2011, 184–203 | DOI

[8] Horváth G, Nehaniv Gh. L, Szabó Cs., “An assertion concerning functionally complete algebras and NP-completeness”, Theoretical Computer Science, 407 (2008), 591–595 | DOI | MR | Zbl

[9] Larose B., Zádori L., “Taylor terms, constraint satisfaction and the complexity of polynomial equations over finite algebras”, International Journal of Algebra and Computation, 16 (2006), 563–581 | DOI | MR | Zbl

[10] Cameron P.J., “Almost all quasigroups have rank 2”, Discrete Mathematics, 106–107 (1992), 111–115 | DOI | MR | Zbl

[11] Galatenko A. V., Pankratiev A.E., “The complexity of checking the polynomial completeness of finite quasigroups”, Discrete Mathematics and Applications, 30:3 (2020), 169–175 | DOI | MR | Zbl

[12] Galatenko A. V., Pankratiev A.E., Staroverov V. M., “Efficient verification of polynomial completeness of quasigroups”, Lobachevskii Journal of Mathematics, 41:8 (2020) (to appear) | DOI | MR

[13] Jacobson M. T., Matthews P., “Generating uniformly distributed random latin squares”, Journal of Combinatorial Designs, 4:6 (1996), 405–437 | 3.0.CO;2-J class='badge bg-secondary rounded-pill ref-badge extid-badge'>DOI | MR | Zbl

[14] Galatenko A. V., Nosov V. A., Pankratiev A.E., “Latin squares over quasigroups”, Lobachevskii Journal of Mathematics, 41:2 (2020), 194–203 | DOI | MR | Zbl

[15] Sobyanin P. I., “Ob algoritme proverki nalichiya podkvazigruppy v kvazigruppe”, Intellektualnye sistemy. Teoriya i prilozheniya, 23:2 (2019), 79–84

[16] Galatenko A. V., Pankratev A. E., Staroverov V. M., “Ob odnom algoritme proverki suschestvovaniya netrivialnykh podkvazigrupp”, Materialy XVIII Mezhdunarodnoi konferentsii «Algebra, teoriya chisel i diskretnaya geometriya: sovremennye problemy, prilozheniya i problemy istorii» (Tula, 2020), 150–153