One approach to constructing a multiply transitive class of block transformations

I. V. Cherednik

Prikladnaâ diskretnaâ matematika, no. 4 (2018), pp. 18-47

Résumé

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$.

Détail

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