One approach to constructing a~transitive class of block transformations

I. V. Cherednik

Prikladnaâ diskretnaâ matematika, no. 4 (2017), pp. 5-34.

Résumé

In the paper, a new type of block transformations is determined and investigated. These transformations can be used to construct hash functions and block ciphers. Let $\Omega$ be an arbitrary finite set, and $\mathcal Q(\Omega)$ be the collection of all binary quasigroups defined on the set $\Omega$. We consider the mappings $\Sigma^F\colon\Omega^n\to\Omega^n$ that are implemented by a network $\Sigma$ of a width $n$ with one binary operation $F\in\mathcal Q(\Omega)$. The network $\Sigma$ is called bijective for $\Omega$ if the mapping $\Sigma^F$ is bijective for each $F\in\mathcal Q(\Omega)$. We show that the network $\Sigma$ is bijective for all finite sets iff the network $\Sigma$ is bijective for some finite set $\Omega$ such that $|\Omega|\ge2$. Therefore, we say that the network $\Sigma$ is bijective if it is bijective for a nontrivial finite set. The networks $\Sigma_1$, $\Sigma_2$ are called equivalent for $\Omega$ if the map $\Sigma_1^F$ coincides with the map $\Sigma_2^F$ for each $F\in\mathcal Q(\Omega)$. Moreover, we say that the networks $\Sigma_1$, $\Sigma_2$ are equivalent if the networks $\Sigma_1$, $\Sigma_2$ are equivalent for all finite sets. It is easy to define the elementary networks by analogy with the elementary matrices. We prove that every bijective network $\Sigma$ is equivalent to a unique product of elementary networks. This product is called the canonical representation of $\Sigma$ and its length is denoted by $\|\Sigma\|$. We prove that bijective networks $\Sigma_1$, $\Sigma_2$ of equal width $n$ are equivalent iff they are equivalent for some finite set $\Omega$ such that $|\Omega|\ge\|\Sigma_1\|+\|\Sigma_2\|+n$. A bijective network $\Sigma$ is called transitive for $\Omega$ if the set $\{\Sigma^F\colon F\in\mathcal Q(\Omega)\}$ is transitive. We prove that the bijective network $\Sigma$ is transitive for all sufficiently large finite sets iff $\Sigma$ is transitive for some finite set $\Omega$ such that $|\Omega|\ge\|\Sigma\|+n$. In addition, we propose an effective method for verifying the network transitivity for all sufficiently large finite sets, namely the bijective network $\Sigma$ is transitive for $\Omega$ such that $|\Omega|\ge\|\Sigma\|+n$ whenever it is transitive for some two-element subset of $\Omega$. In the final section, we expound an algorithm for constructing transitive networks. For a given bijective network $\Sigma$ of a width $n$, the algorithm adds $3n-3$ elementary networks to the canonical representation of $\Sigma$ without changing the existing contents. As a result of these modifications, we obtain a bijective network $\widehat\Sigma$ that is transitive for every sufficiently large finite set $\Omega$ ($|\Omega|\ge\|\widehat\Sigma\|+n$).

Détail

Keywords: network, block transformation, transitive class of block transformations.
Mots-clés : quasigroup

Bibliographie

[1] Belousov V. D., Foundations of the Quasigroups and Loops theory, Nauka Publ., Moscow, 1967 (in Russian) | MR

[2] Mink Kh., Permanents, Mir Publ., Moscow, 1982 (in Russian) | MR

[3] Sachkov V. N., Tarakanov V. E., Combinatorics of Nonnegative Matrices, TVP Publ., Moscow, 2000, 448 pp. (in Russian) | MR

[4] Evans T., “Embedding incomplete latin squares”, Amer. Math. Monthly, 67 (1960), 959–961 | MR

[5] Smetaniuk B., “A new construction on latin squares I. A proof of the Evans conjecture”, Ars Combinatoria, 11 (1981), 155–172 | MR | Zbl

[6] Anderson L. D., Hilton A. J. W., “Thank Evans!”, Proc. London Math. Soc., 47 (1983), 507–522 | DOI | MR