One approach to constructing a multiply transitive class of block transformations

I. V. Cherednik

Prikladnaya Diskretnaya Matematika. Supplement, no. 13 (2020), pp. 69-71

Résumé

Let $\Omega$ be an arbitrary finite set, $\mathcal B(\Omega)$ — the collection of all binary operations defined on the set $\Omega$, $\mathcal B^*(\Omega)$ — the family of all binary operations that are invertible in the right variable, $x_1,\ldots,x_n$ — variables over $\Omega$, and $*_1,\ldots,*_k$ — general symbols of binary operations. A fixed cortege $W=(w_1,\ldots,w_m)$ of formulas in the alphabet $\{x_1,\ldots,x_n,*_1,\ldots,*_k\}$ implements the mapping $W^{F_1,\ldots,F_k}\colon\Omega^n\to\Omega^m$ when replacing symbols $*_1,\ldots,*_k$ with an arbitrary binary operations $F_1,\ldots, F_k\in\mathcal B(\Omega)$, respectively. In this paper we offer a visual representation of the transformation family $\{W^{F_1,\ldots,F_k} : F_1,\ldots,F_k\in\mathcal B^*(\Omega)\}$ in the form of a binary functional network. This representation allows us to strictly describe the methods of research on the multiply transitivity of an arbitrary family $\{W^{F_1,\ldots,F_k} : F_1,\ldots,F_k\in\mathcal B^*(\Omega)\}$. In addition, network view makes it possible to construct cortege of formulas $W=(w_1,\ldots,w_n)$ such that the family $\{W^{F_1,\ldots,F_k} : F_1,\ldots,F_k\in\mathcal B^*(\Omega)\}$ is multiply transitive. Moreover, some block ciphers (Blowfish, Twofish, etc), in which the S-boxes depend on the key, can be “approximated” by family of the form $\{W^{F_1,\ldots,F_k} : F_1,\ldots,F_k\in\mathcal B^*(\Omega)\}$ and, as a result, it becomes possible to evaluate the multiple transitivity of such ciphers.

Détail

Keywords: block transformation, multiply transitive class of block transformations, functional binary network.