On scatter properties of modular addition operation over imprimitivity systems of the translation group of the binary vector space

D. A. Burov

Diskretnaya Matematika, Tome 33 (2021) no. 3, pp. 3-40.

Résumé

We study scatter properties of the modular addition operation for imprimitivity systems of the translation group of the binary vector space $V_n = \{0,1\}^n$. We describe all the subspaces of the space $V_n$ that induce imprimitivity systems with worst possible scatter by the modular addition operation.

Détail

Keywords: cryptographic algorithm, modular addition operation, scattering transformations, binary space, translation group, imprimitivity system.

Bibliographie

[1] Burov D. A., “On relationship between the parameters characterizing nonlinearity and nonhomomorphy of vector spaces transformation”, Discrete Math. Appl., 29:5 (2019), 287–294 | DOI | MR | Zbl

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

[3] GOST R 34.12-2015 Informatsionnaya tekhnologiya. Kriptograficheskaya zaschita informatsii. Blochnye shifry. Izdanie ofitsialnoe, Standartinform, Moskva, 2015

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

[5] Malyshev F.M., “Raznostnye kharakteristiki osnovnykh operatsii ARX-shifrov”, Matematicheskie voprosy kriptografii, 11:4 (2020), 97–105 | MR

[6] Pogorelov B. A., Pudovkina M. A., “On the distance from permutations to imprimitive groups for a fixed system of imprimitivity”, Discrete Math. Appl., 24:2 (2014), 95–108 | DOI | MR | Zbl

[7] Pogorelov B. A., Pudovkina M. A., “Overgroups of order $2^n$ additive regular groups of a residue ring and of a vector space”, Discrete Math. Appl., 26:4 (2016), 239–254 | DOI | MR | Zbl

[8] Shemyakina O.V., “On the mixing properties of operations in a finite field”, Discrete Math. Appl., 21:3 (2011), 317–327 | DOI | MR | Zbl

[9] Alquie D., Approximating addition by XOR: how to go all the way, IACR Cryptology Archive, Report 2010/071, 2010 | Zbl

[10] Aumasson J.-P., Meier W., Phan R. C.-W., Henzen L., The hash function Blake, Springer, 2014, 228 pp. | MR | Zbl

[11] Beaulie R., Douglas S., Smith J., Treatman-Clark S., Weeks B., Wingers L., The Simon and Speck families of lightweight block ciphers, IACR Cryptology Archive, Report 2013/404, 2013

[12] Bernstein D.J., “The Salsa20 family of stream ciphers”, Lect. Notes Comput. Sci., 4986, 2008, 84–97 | DOI

[13] Braeken A., Semaev I., “The ANF of composition of addition and multiplication mod with a boolean function”, FSE'05, Lect. Notes Comput. Sci., 2887, 2005, 290–306 | DOI | MR

[14] Dehnavi S.M., Rishakani A.M., Shamsabad M.R.M., A more explicit formula for linear probabilities of modular addition modulo a power of two, IACR Cryptology Archive, Report 2015/26, 2015

[15] Dehnavi S.M., Rishakani A.M., Shamsabad M.R.M., Maimani H., Pasha E., Cryptographic properties of addition modulo $2^n$, IACR Cryptology Archive, Report 2016/181, 2016

[16] Ferguson N., Lucks S., Schneier B., Whiting D., Bellare M., Kohno T., Callas J., Walker J., The Skein hash function family, Submission to NIST (Round 3), 2010

[17] Hong D., Lee J.K., Kim D.C., Kwon D., Ryu K.H., Lee D.G., “LEA: a 128-bit block cipher for fast encryption on common processors”, FSE'05, Lect. Notes Comput. Sci., 2887, 2005, 290–306

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

[19] Lipmaa H., Moriai S., “Efficient algorithms for computing differential properties of addition”, FSE'01, Lect. Notes Comput. Sci., 2355, 2002, 336–350 | DOI | Zbl

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

[21] Maximov A., “On linear approximation of modulo sum”, FSE'04, Lect. Notes Comput. Sci., 3017, 2004, 483–484 | DOI | Zbl

[22] McKay K.A., Vora P.L., Pseudo-linear approximations for ARX ciphers: with application to Threefish, IACR Cryptology Archive, Report 2010/282, 2010

[23] Miyano H., “Addend dependency of differential/linear probability of addition”, IEICE Trans. Fundam. Electronics, Communic. Comput. Sci., 81:1 (1998), 106–109

[24] Mouha N., Kolomeec N, Akhtiamov D., Sutormin I., Panferov M., Titova K., Bonich T., Ishchukova E., Tokareva N., Zhantulikov B., “Maxima of the additive differential probability of exclusive-or”, IACR Trans. Symm. Cryptology, 2021:2 (2021), 292–313 | DOI

[25] Paul S., Preneel B., “Solving systems of differential equations of addition (extended abstract)”, ACISP 2005, Lect. Notes Comput. Sci., 3574, 2005, 75–88 | DOI | Zbl

[26] Sarkar P., On approximating addition by exclusive OR, IACR Cryptology Archive, Report 2009/047, 2009

[27] Schulte-Geers E., “On CCZ-equivalence of addition $\mod{2^n}$”, Designs, codes, and cryptology, 66 (2013), 111–127 | DOI | MR | Zbl

[28] Staffelbach O., Meier W., “Cryptographic significance of the carry for ciphers based on integer addition”, CRYPTO 1990, Lect. Notes Comput. Sci., 537, 1990, 602–614 | DOI

[29] Wallen J., “Linear approximations of addition modulo $\mod{2^n}$”, FSE'03, Lect. Notes Comput. Sci., 2887, 2003, 261–273 | DOI | Zbl

[30] Wang X., Yu H., “How to break MD5 and other hash functions”, EUROCRYPT'05, Lect. Notes Comput. Sci., 3494, 2005, 19–35 | DOI | MR | Zbl

[31] Xue S., Qi W.-F., Yang X.-Y., “On the best linear approximation of addition modulo $\mod{2^n}$”, Cryptogr. Communic., 9 (2017), 563–580 | DOI | MR | Zbl