One approach to constructing a multiply transitive class of block transformations
Prikladnaâ diskretnaâ matematika, no. 4 (2018), pp. 18-47.

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

In this work, we continue to study the cryptographic properties of block transformations of a new type, which can be used to construct hash functions and block ciphers. Let $\Omega$ be an arbitrary finite set, $\mathcal Q(\Omega)$ be the collection of all binary quasigroups defined on the set $\Omega$, and $\Sigma^F\colon\Omega^n\to\Omega^n$ be a mapping that is implemented by a network $\Sigma$ of width $n$ with one binary operation $F\in\mathcal Q(\Omega)$. The network $\Sigma$ is called bijective if the mapping $\Sigma^F$ is bijective for each $F\in\mathcal Q(\Omega)$ and all finite sets $\Omega$. The networks $\Sigma_1,\Sigma_2$ are called equivalent if the map $\Sigma_1^F$ of $\Sigma_1$ coincides with the map $\Sigma_2^F$ of $\Sigma_2$ for each $F\in\mathcal Q(\Omega)$ and for all finite sets $\Omega$. It is not difficult to define the elementary networks by analogy with the elementary matrices and 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\|$. A bijective network $\Sigma$ is called $k$-transitive for $\Omega$ if the family $\{\Sigma^F: F\in\mathcal Q(\Omega)\}$ is $k$-transitive. We prove that the bijective network $\Sigma$ is $k$-transitive for all sufficiently large finite sets iff $\Sigma$ is \linebreak$k$-transitive for some finite set $\Omega$ such that $|\Omega|\ge k\|\Sigma\|+kn$. In addition, we propose an effective method for verifying the network's $k$-transitivity for all sufficiently large finite sets, namely, the bijective network $\Sigma$ is $k$-transitive for $\Omega$ such that $|\Omega|\ge k\|\Sigma\|+kn$ whenever it is $k$-transitive for some $(k+1)$-element subset of $\Omega$. Also, we describe an algorithm for constructing $k$-transitive networks. For a given bijective network $\Sigma$ of a width $n$, the algorithm adds $6n-7$ 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 $k$-transitive for every sufficiently large finite set $\Omega$, namely for $|\Omega|\ge k\|\widehat{\Sigma}\|+kn$.
Keywords: network, block transformation, $k$-transitive class of block transformations.
Mots-clés : quasigroup
@article{PDM_2018_4_a2,
     author = {I. V. Cherednik},
     title = {One approach to constructing a multiply transitive class of block transformations},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {18--47},
     publisher = {mathdoc},
     number = {4},
     year = {2018},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2018_4_a2/}
}
TY  - JOUR
AU  - I. V. Cherednik
TI  - One approach to constructing a multiply transitive class of block transformations
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2018
SP  - 18
EP  - 47
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2018_4_a2/
LA  - ru
ID  - PDM_2018_4_a2
ER  - 
%0 Journal Article
%A I. V. Cherednik
%T One approach to constructing a multiply transitive class of block transformations
%J Prikladnaâ diskretnaâ matematika
%D 2018
%P 18-47
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2018_4_a2/
%G ru
%F PDM_2018_4_a2
I. V. Cherednik. One approach to constructing a multiply transitive class of block transformations. Prikladnaâ diskretnaâ matematika, no. 4 (2018), pp. 18-47. http://geodesic.mathdoc.fr/item/PDM_2018_4_a2/

[1] Cherednik I. V., “One approach to constructing a transitive class of block transformations”, Prikladnaya Diskretnaya Matematika, 2017, no. 38, 5–34 (in Russian)

[2] Belousov V. D., Foundations of the Quasigroups and Loops Theory, Nauka Publ., M., 1967 (in Russian)