Permutation homomorphisms of block ciphers and ${\otimes _{\mathbf{W}}}$-Markovian property

B. A. Pogorelov   ; M. A. Pudovkina

Matematičeskie voprosy kriptografii, Tome 9 (2018) no. 3, pp. 109-126

Résumé

We consider $\otimes$-Markov block ciphers on the alphabet $X$ with independent round keys and an Abelian group $(X, \otimes)$ of key addition. Lai X., Massey J. L., Murphy S. in 1991 had proved that the sequence of round differences of the $\otimes$-Markov block cipher forms a Markov chain. In 2017 we have given conditions under which the sequence of lumped round differences of the $\otimes$-Markov block cipher is again a Markov chain. Ciphers with such property were called ${\otimes _{\mathbf{W}}}$-Markovian block ciphers. The definition of ${\otimes _{\mathbf{W}}}$-Markovian block ciphers naturally leads to a notion of ${\otimes _{\mathbf{W}}}$-Markovian transformations. In this paper, we continue to investigate properties of ${\otimes _{\mathbf{W}}}$-Markovian ciphers. We ascertain connections between the existence of homomorphisms of block ciphers and the ${\otimes _{\mathbf{W}}}$-Markovian property.

Bibliographie

[1] Lai X., Massey J. L., Murphy S., “Markov ciphers and differential cryptanalysis”, EUROCRYPT'1991, Lect. Notes Comput. Sci., 547, 1991, 17–38 | DOI | MR | Zbl

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

[3] Knudsen L. R., Mathiassen J. E., “On the role of key schedules in attacks on iterated ciphers”, ESORICS 2004, Lect. Notes Comput. Sci., 3193, 2004, 322–334 | DOI

[4] Hornauer G., Stephan W., Wernsdorf R., “Markov ciphers and alternating groups”, EUROCRYPT'1993, Lect. Notes Comput. Sci., 765, 1993, 453–460 | DOI | MR

[5] Sachkov V. N., “Veroyatnostnye preobrazovateli i pravilnye multigrafy. 1”, Trudy po diskretnoi matematike, 1 (1997), 227–250 | Zbl

[6] Sachkov V. N., “Tsepi Markova iteratsionnykh sistem preobrazovanii”, Trudy po diskretnoi matematike, 6 (2002), 165–183

[7] Sachkov V. N., “Veroyatnostnye preobrazovateli i summy elementarnykh matrits. II”, Trudy po diskretnoi matematike, 8 (2005), 240–252 | Zbl

[8] Kovalchuk L. V., “Obobschennye markovskie shifry: postroenie otsenok prakticheskoi stoikosti k differentsialnym atakam”, Matematika i bezopasnost informatsionnykh tekhnologii (MABIT), MTsNMO, M., 2006

[9] Lisitskaya I. V., Dolgov V. I., “Blochnye simmetrichnye shifry i markovskie protsessy”, Prikladnaya radioelektronika, 11:2 (2012), 137–143

[10] Maksimov Yu. I., “Nekotorye rezultaty dlya zadachi ukrupneniya sostoyanii tsepei Markova”, Trudy po diskretnoi matematike, 8 (2005), 148–154

[11] Vaudenay S., “On the Lai-Massey Scheme”, ASIACRYPT'1999, Lect. Notes Comput. Sci., 1716, 1999, 8–19 | DOI | MR | Zbl

[12] Matsui M., Tokita T., “Cryptanalysis of a reduced version of the block cipher E2”, FSE 1999, Lect. Notes Comput. Sci., 1636, 1999, 71–80 | DOI | Zbl

[13] Moriai S., Sugita M., Aoki K., Kanda M., “Security of E2 against truncated differential cryptanalysis”, SAC 1999, Lect. Notes Comput. Sci., 1758, 2000, 106–117 | Zbl

[14] Reichardt B., Wagner D., “Markov truncated differential cryptanalysis of Skipjack”, SAC 2002, Lect. Notes Comput. Sci., 2595, 2003, 110–128 | DOI | MR | Zbl

[15] Blondeau C., “Improbable differential from impossible differential: on the validity of the model”, INDOCRYPT 2013, Lect. Notes Comput. Sci., 8250, 2013, 149–160 | DOI | Zbl

[16] Kemeni D., Snell D., Konechnye tsepi Markova, Nauka, M., 1970, 272 pp.

[17] Glukhov M. M., Elizarov V. P., Nechaev A. A., Algebra, v 2 t., v. II, Gelios ARV, M., 2003

[18] Pogorelov B. A., Pudovkina M. A., “Faktorstruktury preobrazovanii”, Matematicheskie voprosy kriptografii, 3:3 (2012), 81–104 | DOI

[19] Pogorelov B. A., Pudovkina M. A., “$\otimes_{\mathbf{W}}$-markovost XSL-algoritmov blochnogo shifrovaniya, svyazannaya so svoistvami sloev raundovoi funktsii”, Matematicheskie metody kriptografii, 10 (2019) (to appear)