The limited deficit method and the problem of constructing orthomorphisms and almost orthomorphisms of Abelian groups

A. V. Menyachikhin

Diskretnaya Matematika, Tome 31 (2019) no. 3, pp. 58-77.

Résumé

The limited deficit method is described, which allows constructing new orthomorphisms (almost orthomorphisms) of groups with the use of those already known. A class of transformations is described under which the set of all orthomorphisms (almost orthomorphisms) remains invariant. It is conjectured that the set of all orthomorphisms (almost orthomorphisms) is generated by transformations implemented by the limited deficit method. This conjecture is verified for all Abelian groups of order at most 12. The spectral-linear method and the spectral-differential method of design of permutations over the additive group of the field ${\rm{\mathbb F}}_{2^{m}}$ ($m=4,\ldots,8$) are used to construct orthomorphisms with sufficiently high values of the most important cryptographic parameters.

Détail

Keywords: orthomorphism, almost orthomorphism, permutation deficit, orthogonal Latin squares, permutation, $s$-box, spectral-linear method, spectral-differential method.

Bibliographie

[1] Bugrov A.D., “Kusochno-affinnye podstanovki konechnykh polei”, Prikladnaya diskretnaya matematika, 4:30 (2015), 5–23

[2] Glukhov M.M., “O metodakh postroeniya sistem ortogonalnykh kvazigrupp s ispolzovaniem grupp”, Matematicheskie voprosy kriptografii, 2:4 (2011), 5–24 | DOI

[3] Glukhov M.M., “O primeneniyakh kvazigrupp v kriptografii”, Prikladnaya diskretnaya matematika, 2:2 (2008), 28–32

[4] GOST R 34.11-2012, Informatsionnaya tekhnologiya. Kriptograficheskaya zaschita informatsii. Funktsiya kheshirovaniya, Standartinform, M., 2012

[5] GOST R 34.12-2015, Informatsionnaya tekhnologiya. Kriptograficheskaya zaschita informatsii. Blochnye shifry, Standartinform, M., 2015

[6] Zubov A.Yu, Matematika kodov autentifikatsii, Gelios ARV, M., 2007, 480 pp.

[7] Menyachikhin A.V., “Spektralno-lineinyi i spektralno-differentsialnyi metody postroeniya $S$-boksov s blizkimi k optimalnym znacheniyami kriptograficheskikh parametrov”, Matematicheskie voprosy kriptografii, 8:2 (2017), 97–116 | DOI | MR

[8] Menyachikhin A.V., Sposob postroeniya uzlov zameny, ispolzuyuschii znacheniya lineinogo i raznostnykh spektrov, i ustroistvo, ego realizuyuschee, Patent na izobretenie # 2633132 RF, 29, 2017

[9] Menyachikhin A.V., “Ortomorfizmy abelevykh grupp s minimalno vozmozhnymi poparnymi rasstoyaniyami”, Diskretnaya matematika, 30:4 (2018), 55–65 | DOI | MR

[10] Menyachikhin A.V., Ustroistvo dlya postroeniya ortomorfizmov, ispolzuyuschee parnye raznosti, Patent na izobretenie # 2632119 RF, 28, 2017

[11] Sachkov V.N., “Defitsity podstanovok konechnykh grupp”, Trudy po diskretnoi matematike, 7 (2003), 156–175

[12] Sachkov V.N., Kurs kombinatornogo analiza, NITs «Regulyarnaya i khaoticheskaya dinamika», M.-Izhevsk, 2013, 336 pp.

[13] Sachkov V.N., “Raznostnye spetsifikatsii podstanovok i razbieniya v koltse vychetov”, Matematicheskie voprosy kriptografii, 5:1 (2014), 127–150 | DOI

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

[15] Trishin A.E., “O pokazatele nelineinosti kusochno-lineinykh podstanovok additivnoi gruppy polya $\mathbb F_{2^{n}}$”, Prikladnaya diskretnaya matematika, 4:30 (2015), 32–42

[16] Trishin A.E., “Sposob postroeniya ortogonalnykh latinskikh kvadratov na osnove podstanovochnykh dvuchlenov konechnykh polei”, Obozr. prikl. i promysh. matem., 15:4 (2008)

[17] Tuzhilin M.E., “Latinskie kvadraty i ikh primenenie v kriptografii”, Prikladnaya diskretnaya matematika. Prilozhenie, 3:17 (2012), 47–52

[18] Cheremushkin A.V., Kriptograficheskie protokoly. Osnovnye svoistva i uyazvimosti, Izd. Tsentr «Akademiya», M., 2009, 272 pp.

[19] Buchheim C., Cameron P.J., Wu T., “On the subgroup distance problem”, Discrete Mathematics, 309:4 (2009), 962–968 | DOI | MR | Zbl

[20] Daemen J., “Limitations of the Even–Mansour construction”, ASIACRYPT, Lect. Notes Comput. Sci., 739, 1991, 495–498 | DOI

[21] Dai Z., Golomb S., Gong G., “Generating all linear orthomorphisms without repetition”, Discrete Mathematics, 205 (1999), 47–55 | DOI | MR | Zbl

[22] Denes J., Keedwell A. D., Latin squares and their applications, Academiai Kiado, Budapest, 2015, 545 pp. | MR

[23] Dinur I., Dunkelman O., Keller N., Shamir A., Key recovery attacks on 3-round Even-Mansour, 8-step LED-128, and full AES, 2013 http://eprint.iacr.org/2013/391 | MR

[24] Evans A., Orthomorphisms graphs and groups, Springer-Verlag, Berlin, 1992, 114 pp. | MR

[25] Evans A., “Applications of complete mappings and orthomorphisms of finite groups”, Quasigroups and related systems, 23 (2015), 5–30 | MR | Zbl

[26] Even E., Mansour Y., “A construction of a cipher from a single pseudorandom permutation”, ASIACRYPT, Lect. Notes Comput. Sci., 739, 1991, 210–224 | DOI | MR

[27] Gilboa S., Gueron S., “Balanced permutations Even–Mansour ciphers”, Cryptography, 1:1 (2017), 1–17

[28] Gligoroski D., Odegard R.S., Mihova M. et al., “Cryptographic hash function Edon-R”, Proc. 1st Int. Workshop Secur. Commun. Netw., 2009, 1–9, Trondheim

[29] Hall M., “A combinatorial problem on Abelian groups”, Proc. Amer. Math. Soc., 3:4 (1952), 584–587 | DOI | MR | Zbl

[30] Han H., Xiong Y., Zhu S., “The linear orthomorphisms on the ring ${\mathbb Z}_{n} $”, Res. J. Appl. Sci., Engineer. and Technol., 5:5 (2013), 1848–1852 | DOI

[31] Han H. Xu X., “The evolutionary generation of orthomorphisms in the finite field $\mathbb F_{2^{8}}$”, Res. J. Appl. Sci., Engineer. and Technol., 4:21 (2012), 4458–4462

[32] Johnson D.M., Dulmage A.L., Mendelsohn N.S., “Orthomorphisms of groups and orthogonal Latin squares, I”, Canad. J. Math., 13 (1961), 356–372 | DOI | MR | Zbl

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

[34] Lu Z., Lai X., “A new method for construction of orthomorphic permutations with the highest degree”, Proc. Int. Conf. Computer Networks and Commun. Technol., Adv. Comput. Sci. Res., 54, Atlantic Press, 2016, 579–584

[35] Mann H.B., “On orthogonal Latin squares”, Bull. Amer. Math. Soc., 50 (1944), 249–257 | DOI | MR | Zbl

[36] Niederreiter H., Robinson K., “Bol loops of order $pq$”, Math. Proc. Cambridge Philosoph. Soc., 89:2 (1981), 241–256 | DOI | MR | Zbl

[37] Niederreiter H., Robinson K., “Complete mappings of finite fields”, J. Austral. Math. Soc. Ser., 1982, 197–212 | DOI | MR | Zbl

[38] Nikolic I., Wang L., Wu S., “Cryptoanalysis of round-reduce LED”, FSE, Lect. Notes Comput. Sci., 8424, 2013, 112–130 | DOI

[39] Paige L.J., “A note on finite Abelian groups”, Bull. Amer. Math. Soc., 53 (1947), 590–593 | DOI | MR | Zbl

[40] Tong Y., Zhang H., Han H., “Using Evolutionary Computation in construction of orthomorphism”, Proc. Int. Conf. Multimed. Inf. Netw. and Secur., 2009, 478–481

[41] Tu Z., Zeng X., Hu L., “Several classes of complete permutation polynomials”, Finite fields and applications, 25 (2014), 182–193 | DOI | MR | Zbl

[42] Yuan Y., Tong Y., Zhang H., “Complete mapping polynomials over finite field $\mathbb F_{16}$”, Arithmetic of Finite Fields, Lect. Notes Comput. Sci., 4547, 2007, 147–158 | DOI | MR | Zbl