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.

Bibliographie

[1] Gligoroski D., Markovski S., Kocarev L., Gusev M., Edon80, eSTREAM, ECRYPT Stream Cipher Project, http://www.ecrypt.eu.org/stream/edon80p3.html

[2] Gligoroski D., Markovski S., Kocarev L., “Edon-R, An infinite family of cryptographic hash functions”, Second NIST Cryptographic Hash Workshop http://csrc.nist.gov/pki/HashWorkshop/2006/Papers/GLIGOROSKI_EdonR-ver06.pdf

[3] Gligoroski D., Markovski S., Knapskog S., A public key block cipher based on multivariate quadratic quasigroups, Cryptology ePrint Archive, http://eprint.iacr.org/2008/320

[4] Cherednik I. V., “Ob odnom podkhode k postroeniyu tranzitivnogo mnozhestva blochnykh preobrazovanii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2017, no. 10, 27–29

[5] Cherednik I. V., “Odin podkhod k postroeniyu tranzitivnogo mnozhestva blochnykh preobrazovanii”, Prikladnaya diskretnaya matematika, 2017, no. 38, 5–34

[6] Cherednik I. V., “$k$-Tranzitivnost odnogo klassa blochnykh preobrazovanii”, Prikladnaya diskretnaya matematika. Prilozhenie, 2018, no. 11, 21–23

[7] Cherednik I. V., “Odin podkhod k postroeniyu kratno tranzitivnogo mnozhestva blochnykh preobrazovanii”, Prikladnaya diskretnaya matematika, 2018, no. 42, 18–47

[8] Cherednik I. V., “Ob ispolzovanii binarnykh operatsii pri postroenii tranzitivnogo mnozhestva blochnykh preobrazovanii”, Diskretnaya matematika, 31:3 (2019), 93–113 | MR

[9] Cherednik I. V., “Ob ispolzovanii binarnykh operatsii pri postroenii kratno tranzitivnogo mnozhestva blochnykh preobrazovanii”, Diskretnaya matematika, 32:2 (2020), 85–111 | MR