Proper families of functions and their applications

A. V. Galatenko ; V. A. Nosov ; A. E. Pankratiev ; K. D. Tsaregorodtsev

Matematičeskie voprosy kriptografii, Tome 14 (2023) no. 2, pp. 43-58

Résumé

Proper families of functions provide a convenient and memory-efficient method for specification of large parametric families of quasigroups and $d$-quasigroups of large order. We present a number of examples of proper families, outline connections between proper families and quasigroups or $d$-quasigroups, discuss equivalent definitions of properness and various operations on proper families, analyze the complexity of deciding properness and study possible configurations of essential dependence inside proper families.

Bibliographie

[1] Shcherbacov V. A., Quasigroups in cryptology, arXiv: 1007.3572

[2] D{ö}m{ö}si P., Horváth G., “A novel cryptosystem based on abstract automata and Latin cubes”, Studia Sci. Math. Hungarica, 52:2 (2015), 221–232 | MR | Zbl

[3] Nosov V. A., “The criterion of regularity of a Boolean non-autonomous automaton with split input”, Intellektualnye Sistemy, 3:3–4 (1998), 269–280 (In Russian)

[4] Nosov V. A., “Construction of classes of Latin squares in a Boolean database”, Intellektualnye Sistemy, 4:3–4 (1999), 307–320 (In Russian)

[5] Nosov V. A., “Construction of a parametric family of Latin squares in a vector database”, Intellektualnye Sistemy, 8:1–4 (2004), 517–528 (In Russian)

[6] Nosov V. A., “Constructing families of Latin squares over Boolean domains”, Boolean Functions in Cryptology and Information Security, IOS Press, Amsterdam, 2008, 200–207 | MR | Zbl

[7] Nosov V. A., Pankratiev A. E., “Latin squares over Abelian groups”, J. Math. Sci., 149:5 (2008), 1230–1234 | DOI | MR | Zbl

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

[9] Tsaregorodtsev K. D., “Properties of proper families of Boolean functions”, Diskretnaya Matematika, 33:1 (2021), 91–102 (In Russian) | DOI | MR

[10] Nosov V. A., Pankratiev A. E., “On functional specification of Latin squares”, J. Math. Sci., 169:4 (2010), 533–540 | DOI | MR | Zbl

[11] Kozlov A. A., Nosov V. A., Pankratiev A. E., “Matrices and graphs of essential dependence of proper families of functions”, J. Math. Sci., 163:5 (2009), 534–542 | DOI | MR | Zbl

[12] Nosov V. A., Pankratiev A. E., “Families of functions specifying Latin squares over Abelian groups”, Lesnoi Vestnik, 2 (2007), 141–144 (In Russian) | MR

[13] Galatenko A. V., Nosov V. A., Pankratiev A. E., “Generation of multivariate quadratic quasigroups by proper families of Boolean functions”, Journal of Mathematical Sciences, 262:5 (2022), 630-641 | DOI | MR

[14] Plaksina I. A., “Construction of a parametric family of multidimensional Latin squares”, Intellektualnye Sistemy. Teoria i Prilojenia, 18:2 (2014), 323–330 (In Russian) | MR

[15] Galatenko A. V., Nosov V. A., Pankratiev A. E., “Functional specification of quasigroup operations”, Proc. XIX Int. Conf. “Problems of Theoretical Cybernetics” (Kazan, 2021), 2021, 35–37

[16] Piven N. A., “Investigation of quasigroups generated by proper families of Boolean functions of the order 2”, Intellektualnye Sistemy. Teoria i Prilojenia, 22:1 (2018), 21–35 (In Russian)

[17] Gligoroski D., Markovski S., Knapskog J., “Multivariate quadratic trapdoor functions based on multivariate quadratic quasigroups”, Proc. Amer. Conf. Appl. Math., MATH'08, WSEAS Press, 2008, 44–49

[18] Szabo T., Welzl E., “Unique sink orientations of cubes”, Proc. 42nd IEEE Symp. Found. Comput. Sci., 2001, 547–555 | DOI | MR

[19] Tsaregorodtsev K. D., “One-to-one correspondense between proper families of Boolean functions and unique sink orientations of cubes”, Prikladnaya Diskretnaya Matematika, 2020, no. 48, 16–21 (In Russian) | DOI | MR | Zbl

[20] Galatenko A. V., Nosov V. A., Pankratiev A. E., Staroverov V. M, “A criterion of properness of a family of functions”, Proc. XIX Int. Conf. “Algebra, Number Theory, Discrete Geometry and Multiscale Modeling: modern problems, applications and problems of history” (Tula, 2021), 2021, 103–106 (In Russian)

[21] Galatenko A. V., Nosov V. A., Pankratiev A. E., “An algorithm for generation of proper families of functions”, Proc. XVIII Int. Conf. “Algebra, Number Theory and Discrete Geometry: modern problems, applications and problems of history” (Tula, 2020), 2020, 141–145 (In Russian)

[22] Galatenko A. V., Nosov V. A., Pankratiev A. E., Staroverov V. M., “Generation of proper families of functions”, Intellektualnye Sistemy. Teoria i Prilojenia, 25:4 (2021), 100–103 (In Russian) | MR

[23] Rykov D. O., “Algorithms for checking properness of family of functions”, Intellektualnye Sistemy. Teoria i Prilojenia, 14:1–4 (2010), 261–276 (In Russian) | MR

[24] Lau D., Function Algebras on Finite Sets: a Basic Course on Many-valued Logic and Clone Theory, Springer, 2006, XIV+670 pp. | MR | Zbl

[25] Samardjiska S., Chen Y., Gligoroski D., “Construction of multivariate quadratic quasigroups (MQQs) in arbitrary Galois fields”, 7th Int. Conf. Inf. Assurance and Security (IAS) (Melacca, Malaysia, 2011), 314–319 | DOI

[26] Galatenko A. V., Pankratiev A. E., Staroverov V. M., “Algorithms for checking some properties of $n$-quasigroups”, Program. Computer Software, 48:1 (2022), 36–48 | DOI | MR | Zbl