Perfect diffusion of partitions of finite Abelian groups

B. A. Pogorelov ; M. A. Pudovkina

Matematičeskie voprosy kriptografii, Tome 15 (2024) no. 4, pp. 61-90

Résumé

We consider an Abelian group $(X, + )$ and study properties of permutations on $X$ acting on partitions ${{\mathbf{W}}^{(t)}}$ of ${\bar X^t}$, which consist of pairwise different elements from ${X^t}$, $t = 2,3,\ldots$ These partitions are generalizations of classical differential partitions for $t = 2$. High order differential, truncated differential, impossible differential, polytopic and multiple differential techniques use such partitions. Let $d_{{\mathbf{W}}^{(t)}}(s)$ be the minimum Hamming distance between a permutation $s$ and the set of all permutations on $X$ preserving ${{\mathbf{W}}^{(t)}}$. We describe properties of permutations $s$ with the maximal value $d_{{\mathbf{W}}^{(t)}}(s)$, which perfectly diffuse ${{\mathbf{W}}^{(t)}}$. We find a criterion of perfect diffusion of ${{\mathbf{W}}^{(t)}}$ for any $t\in \mathbb{N}$. For the additive group of a vector space over $\mathbb{F}_{2^m}$, we show the connections between permutations perfectly diffusing ${{\mathbf{W}}^{(t)}}$, APN-permutations, AB-permutations and differentially $2r$-uniform permutations, $r \ge 1$. For additive groups of vector spaces and residue rings, we also compare diffusion property of well-known $S$-boxes for ${{\mathbf{W}}^{(3)}}$.

Bibliographie

[1] Biham E., Shamir A., “Differential cryptanalysis of DES-like cryptosystems”, J. Cryptology, 4:1 (1991), 3–72 | DOI | MR | Zbl

[2] Lai X., “Higher order derivatives and differential cryptanalysis”, Commun. Cryptography, 1994, 227–233 | DOI | Zbl

[3] Knudsen L. R., “Truncated and higher order differentials”, FSE 1994, Lect. Notes Comput. Sci., 1008, 1995, 196–211 | DOI | Zbl

[4] Tiessen T., “Polytopic cryptanalysis”, EUROCRYPT 2016, Lect. Notes Comput. Sci., 9665, 2016, 214–239 | DOI | MR | Zbl

[5] Tiessen T., “From higher-order differentials to polytopic cryptanalysis”, Paradigms in Cryptology – Mycrypt 2016, Lect. Notes Comput. Sci., 10311, 2017, 544–552 | DOI | MR | Zbl

[6] Blondeau C., Gerard B., “Multiple differential cryptanalysis: theory and practice (corrected)”, FSE 2011, Lect. Notes Comput. Sci., 6733, 2011, 35–54 | DOI | Zbl

[7] Samajder S., Sarkar P., Multiple differential cryptanalysis: a rigorous analysis, Cryptology ePrint Archive, Report 2016/405, 2016, 20 pp. | Zbl

[8] Pogorelov B. A., Pudovkina M. A., “O rasstoyaniyakh ot podstanovok do imprimitivnykh grupp pri fiksirovannoi sisteme imprimitivnosti”, Diskretnaya matematika, 25:3 (2013), 78–95 | DOI

[9] Pogorelov B. A., Pudovkina M. A., “Multipodstanovki na dekartovom proizvedenii grupp i ikh svoistva”, Matematicheskie voprosy kriptografii, 14:4 (2023), 111–142 | DOI | MR | Zbl

[10] Nyberg K., “Differentially uniform mappings for cryptography”, EUROCRYPT'93, Lect. Notes Comput. Sci., 765, 1994, 55–64 | DOI | MR | Zbl

[11] Carlet C., “Relating three nonlinearity parameters of vectorial functions and building APN functions from bent functions”, Designs, Codes Cryptography, 59:1 (2011), 89–109 | DOI | MR | Zbl

[12] Bending T., Fon-Der-Flaass D., “Crooked functions, bent functions and distance-regular graphs”, Electron. J. Comb., 1998, no. 5, R34, 14 pp. | DOI | MR | Zbl

[13] Pogorelov B. A., Pudovkina M. A., “Razbieniya na bigrammakh i markovost algoritmov blochnogo shifrovaniya”, Matematicheskie voprosy kriptografii, 8:1 (2017), 5–40 | DOI | MR

[14] Massey J. L., “SAFER K-64: a byte-oriented block-ciphering algorithm”, FSE 1993, Lect. Notes Comput. Sci., 809, 1994, 1–17 | DOI | Zbl

[15] Maslennikov M., 2008 http://registercsp.nets.co.kr/MCSSHA/MCSSHA-3.pdf | Zbl

[16] Aumasson J.-P., Naya-Plasencia M., “Cryptanalysis of the MCSSHA Hash Functions”, Western European Workshop on Research in Cryptology, 2009 https://www.aumasson.jp/data/papers/AN09.pdf

[17] Budaghyan L., Construction and Analysis of Cryptographic Functions, Springer International Publishing, Switzerland, 2014 | MR | Zbl