On a relationship between linear and differential characteristics of binary vector spaces mappings and diffusion characteristics over blocks of imprimitivity systems of translation group of the binary vector space

D. A. Burov

Diskretnaya Matematika, Tome 35 (2023) no. 1, pp. 3-34.

Résumé

We examine relationships between the nonlinearity parameters of mappings $f\colon V_{n} \to V_{m} $ of binary vector spaces $V_{n} =\mathrm{GF}(2)^n $, ${V_{m} =\mathrm{GF}(2)^{m} }$, diffusion properties of imprimitivity systems of the translation group $V_{n}^{+} $ of space $V_{n} $, and also (for $m=n$ and $f\in S(V_{n} )$) transitivity and primitivity properties of the groups $\langle W^{+} ,f\rangle $, where $W^{+} $ is the translation group of the subspace $W$. It is shown that, in some methods of cryptoanalysis of block cipher algorithms, in fact, insufficient diffusion of blocks of the imprimitivity system of the group $V_{n}^{+} $ is used.

Détail

Keywords: nonlinearitry, differential characteristic, linear characteristic, transitivity, primitivity.

Bibliographie

[1] Burov D. A., “O svyazi parametrov, kharakterizuyuschikh nelineinost i negomomorfnost preobrazovanii vektornykh prostranstv”, Diskretnaya matematika, 30:3 (2018), 14–24

[2] Burov D. A., “O svoistvakh rasseivaniya operatsiei modulnogo slozheniya po sistemam imprimitivnosti gruppy sdvigov vektornogo prostranstva”, Diskretnaya matematika, 33:3 (2021), 3–40

[3] Gorchinskii Yu. N., “O gomomorfizmakh mnogoosnovnykh universalnykh algebr v svyazi s kriptograficheskimi primeneniyami”, Trudy po diskretnoi matematike, 1 (1997), 67–84 | MR

[4] De La Krus Khimenes R. A., Kamlovskii O. V., “Summy modulei koeffitsientov Uolsha–Adamara bulevykh funktsii”, Diskretnaya matematika, 27:4 (2015), 49–66

[5] Logachev O. A., Fedorov S. N., Yaschenko V. V., “Summy modulei koeffitsientov Uolsha–Adamara bulevykh funktsii”, Diskretnaya matematika, 30:1 (2015), 39–55

[6] Malyshev F. M., “Veroyatnostnye kharakteristiki raznostnykh i lineinykh sootnoshenii dlya neodnorodnoi lineinoi sredy”, Matematicheskie voprosy kriptografii, 10:1 (2019), 41–72

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

[8] Sidelnikov V. M., “O vzaimnoi korrelyatsii posledovatelnostei”, Dokl. AN SSSR, 196:3 (1971), 531-534 | MR

[9] Aragona R., Calderini M., Tortora A., Tota M., “Primitivity of Present and other lightweight ciphers”, J. Algebra and Appl., 17:6 (2018) | DOI | MR

[10] Bar-On A., Dunkelman O., Keller N., Weizman A., “DLCT: a new tool for differential-linear cryptanalysis”, Eurocrypt 2019, Lect. Notes Comput. Sci., 11476, 2019, 313–342 | DOI | MR

[11] Bannier A., Bodin N., Filiol E., Partition-based trapdoor ciphers, IACR Cryptology Archive, Report 2016/493, 2016

[12] Beierle C., Canteaut A., Leander G., “Nonlinear approximations in cryptanalysis revisited”, IACR Trans. Symm. Cryptology, 2018:4 (2018), 80–101 | DOI

[13] Beierle C., Leander G., “4-uniform permutations with null nonlinearity”, Cryptogr. Commun., 12 (2020), 1133–1141 | DOI | MR

[14] Blondeau C., Leander G., Nyberg K., “Differential-linear cryptanalysis revisited”, J. Cryptology, 30:3 (2017), 859–888 | DOI | MR

[15] Blondeau C., Nyberg K., “New links between differential and linear cryptanalysis”, Eurocrypt 2013, Lect. Notes Comput. Sci., 7881, 2013, 388–404 | DOI | MR

[16] Bogdanov A., Leander G., Nyberg K., Wang M., “Integral and multidimensional linear distinguishers with correlation zero”, Asiacrypt 2012, Lect. Notes Comput. Sci., 7658, 2012, 244–261 | DOI | MR

[17] Burov D. A., Pogorelov B. A., “An attack on 6 rounds of Khazad”, Matematicheskie voprosy kriptografii, 7:2 (2016), 35–46 | MR

[18] Calderini M., “Primitivity of the group of a cipher involving the action of the key-schedule”, J. Algebra and Appl., 2020 | MR

[19] Caranti A., Dalla Volta F., Sala M., “On some block ciphers and imprimitive groups”, Appl. Flgebra in Eng., Commun. Comput., 20 (2009), 339–350 | DOI | MR

[20] Carlet C., Boolean Functions for Cryptography and Coding Theory, Cambridge Univ. Press, Cambridge, 2021

[21] Cid C., Huang T., Peyrin T., Sasaki Y., Song L., “Boomerang connectivity table: a new cryptanalysis tool”, Eurocrypt 2018, Lect. Notes Comput. Sci., 10821, 2018, 683–714 | DOI | MR

[22] Chabaud F., Vaudenay S., “Links between differential and linear cryptanalysis”, Eurocrypt 1994, Lect. Notes Comput. Sci., 950, 1995, 356–365 | DOI | MR

[23] Courtois N.T., Pieprzyk J., “Cryptanalysis of block ciphers with overdefined systems of equations”, Asiacrypt 2002, Lect. Notes Comput. Sci., 2501, 2002, 267–287 | DOI | MR

[24] Daemen J., Govaerts R., Vandewalle J., “Correlation matrices”, FSE 1994, Lect. Notes Comput. Sci., 1008, 1995, 275–285 | DOI

[25] Dib S., “Asymptotic nonlinearity of vectorial Boolean functions”, Cryptogr. Communic., 6:2 (2013), 103–115 | DOI | MR

[26] Harpes C., Massey J., “Partitioning cryptanalysis”, FSE 1997, Lect. Notes Comput. Sci., 1267, 1995, 13–27 | DOI

[27] Hemerlin M., Cho J. Y., Nyberg K., “Multidimensional linear cryptanalysis”, J. Cryptology, 32:2 (2019), 1–34 | MR

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

[29] Kovács I., Malnič A., Marušič D., Miklavič Š., “Transitive group actions: (im)primitivity and semiregular subgroups”, J. Algebr. Combin., 41 (2014), 867–885 | MR

[30] Leander G., Abdelraheem M. A., AlKhzaimi H., Zenner E., “A cryptanalysis of PRINTCIPHER: the invariant subspace attack”, CRYPTO 2011, Lect. Notes Comput. Sci., 6841, 2011, 206–221 | DOI | MR

[31] Leander G., Poschmann A., “On the classification of 4 bit s-boxes”, WAIFI 2007, Lect. Notes Comput. Sci., 4547, 2007, 159–176 | DOI | MR

[32] Malyshev F. M., Trishin A. E., “Linear and differential cryptanalysis: another viewpoint”, Matematicheskie voprosy kriptografii, 11:2 (2020), 83–98 | MR

[33] Nyberg K., The extended autocorrelation and boomerang tables and links between nonlinearity properties of vectorial Boolean functions, IACR Cryptology Archive, Report 2019/1381, 2019

[34] Nyberg K., “Perfect nonlinear S-boxes”, Eurocrypt 1991, Lect. Notes Comput. Sci., 547, 1991, 378–386 | DOI | MR

[35] Nyberg K., “Differentially uniform mappings for cryptography”, Eurocrypt 1993, Lect. Notes Comput. Sci., 765, 1994, 55–64 | DOI | MR

[36] Todo Y., Leander G., Sasaki Y., “Nonlinear invariant attack — practical attack on full SCREAM, iSCREAM, and Midori64”, Asiacrypt 2016, Lect. Notes Comput. Sci., 10032, 2016, 3–33 | DOI | MR

[37] Wallen J., “Linear approximations of addition modulo $mod2^{n} $”, FSE 2003, Lect. Notes Comput. Sci., 2887, 2003, 261–273 | DOI

[38] Zhang X.-M., Zheng Y., Imai H., “Relating differential distribution tables to other properties of substitution boxes”, Des. Codes Cryptogr., 19:1 (2000), 45–63 | DOI | MR