Constructing $8$-bit permutations, $8$-bit involutions and $8$-bit orthomorphisms with almost optimal cryptographic parameters

R. A. de la Cruz Jiménez

Matematičeskie voprosy kriptografii, Tome 12 (2021) no. 3, pp. 89-124

Résumé

Nonlinear bijective transformations are crucial components in the design of many symmetric ciphers. To construct permutations having cryptographic properties close to the optimal ones is not a trivial problem. We propose a new construction based on the well-known Lai – Massey structure for generating binary permutations of dimension $n=2k$, $k\geq2$. The main cores of our constructions are: the inversion in $\mathbb{F}_{2^k}$, an arbitrary $k$-bit non-bijective function (which has no preimage for $0$) and any $k$-bit permutation. Combining these components with the finite field multiplication, we provide new $8$-bit permutations with high values of its basic cryptographic parameters. Also, we show that our approach may be used for constructing $8$-bit involutions and $8$-bit orthomorphisms that have strong cryptographic properties.

Bibliographie

[1] Avanzi R.A., A Salad of Block Ciphers. The State of the Art in Block Ciphers and their Analysis, Cryptology ePrint Archive, Report 2017/1171, http://eprint.iacr.org/2017/1171

[2] Bannier A., Bodin N., Filiol E., Partition-based trapdoor ciphers, Cryptology ePrint Archive, Report 2016/493, http://eprint.iacr.org/2016/493

[3] Bracken C., Leander G., “A highly nonlinear differentially 4 uniform power mapping that permutes fields of even degree”, Finite Fields and Their Appl., 16 (2010), 231–242 | DOI | Zbl

[4] Biryukov A., Perrin L., Udovenko A., “Reverse engineering the S-box of Streebog, Kuznyechik and STRIBOBr1”, EUROCRYPT 2016, Lect. Notes Comput. Sci., 9665, 2016, 372–402 | DOI | Zbl

[5] Boura C., Canteaut A., Jean J. et al., “Two notions of differential equivalence on S-boxes”, Designs, Codes and Cryptogr., 87 (2019), 185–202 | DOI | Zbl

[6] Boura C., Canteaut A., Knudsen L.R. et al., “Reflection ciphers”, Designs, Codes and Cryptogr., 82 (2017), 3–25 | DOI | Zbl

[7] Brier E., Clavier C., Olivier F., “Correlation power analysis with a leakage model”, CHES 2004, Lect. Notes Comput. Sci., 3156, 2004, 157–173

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

[9] Carlet C., Goubin L., Prouff E., Quisquater M., Rivain M., “Higher-order masking schemes for S-boxes”, FSE 2012, Lect. Notes Comput. Sci., 7549, 2012, 366–384 | DOI | Zbl

[10] Courtois N. T., Pieprzyk J., Cryptanalysis of block ciphers with overdefined systems of equations, Cryptology ePrint Archive, Report 2002/044, https://eprint.iacr.org/2002/044

[11] De la Cruz Jiménez R.A., “Generation of 8-Bit S-boxes having almost optimal cryptographic properties using smaller 4-bit S-boxes and finite field multiplication”, LATINCRYPT 2017, Lect. Notes Comput. Sci., 11368, 2017, 191–206

[12] Dinur A., Shamir A., Cube attacks on tweakable black box polynomials, Cryptology ePrint Archive, Report 2008/385, https://eprint.iacr.org/2008/385

[13] Evans A., “Applications of complete mappings and orthomorphisms of finite groups”, Quasigroups and Related System, 23 (2015), 5–30 | Zbl

[14] Evans A., Orthomorphism graphs of groups, Springer-Verlag, Berlin–Heidelberg, 1992, 116 pp. | Zbl

[15] Gierlichs B., Batina L., Tuyls P., Preneel B., “Mutual information analysis”, CHES 2008, Lect. Notes Comput. Sci., 5154, 2008, 426-442 | DOI

[16] Glukhov M.M., Elizarov V.P., Nechaev A.A., Algebra, Textbook, 2nd ed., revised and suppl., Lan', Sankt-Peterburg–Moskva–Krasnodar, 2015 (in Russian)

[17] GOST R 34.12-2015 Information technology. Cryptographic protection of information. Block ciphers, Standartinform, M., 2015

[18] Fomin D. B., “New classes of $8$-bit permutations based on a butterfly structure”, Matematicheskie voprosy kriptografii, 10:2 (2019), 169–180 | DOI | Zbl

[19] Gérard B., Grosso V., Naya-Plasencia M., Standaert F.X., Block ciphers that are easier to mask: how far can we go?, CHES 2013, Lect. Notes Comput. Sci., 8086, 2013, 383–399 | DOI | Zbl

[20] Gérard G. Sh., Gueron Sh., Balanced permutations Even–Mansour ciphers, Cryptology ePrint Archive, Report 2014/642, , 2014 https://eprint.iacr.org/2014/642

[21] Gligoroski D., Odegard R.S., Mihova M., et al., “Cryptographic hash function Edon-R”, Proc. 1st Int. Workshop Security Communic. Networks, IWSCN, IEEE, 2009, 1–9

[22] Feng D., Feng X., Zhang W., Fan X., Wu C., “Loiss: a byte oriented stream cipher”, IWCC 2011, Lect. Notes Comput. Sci., 6639, 2011, 109–125 | DOI | Zbl

[23] 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 | Zbl

[24] Kazymyrov O. V., Kazymyrova V. N., Oliynykov R. V., “A method for generation of high-nonlinear S-boxes based on gradient descent”, Matematicheskie Voprosy Kriptografii, 5:2 (2014), 71–78 | DOI | Zbl

[25] Kazymyrov O. V., Kazymyrova V. N., Extended criterion for absence of fixed points, Cryptology ePrint Archive, Report 2013/576, https://eprint.iacr.org/2013/576

[26] Kim H., Hong S., Lim J., “A fast and provably secure higher-order masking of AES S-box”, CHES 2011, Lect. Notes Comput. Sci., 6917, 2011, 95–107 | DOI | Zbl

[27] Kim J., Combined differential, linear and related-key attacks on block ciphers and MAC algorithms, Cryptology ePrint Archive, Report 2006/451, http://eprint.iacr.org/2006/451.pdf

[28] Kocher P., Jaffe J., Jun B., Introduction to Differential Power Analysis and Related Attacks, Techn. Rep., Cryptography Research Inc., 1998 http://www.cryptography.com/resources/whitepapers/DPA-technical.html

[29] Kocher P., “Timing attacks on implementations of Diffie-Hellman, RSA, DSS and other systems”, CRYPTO '96, Lect. Notes Comput. Sci., 1109, 1996, 104–113 | DOI | Zbl

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

[31] Lachaud G., Wolfmann J., “The weights of the orthogonals of the extended quadratic binary Goppa codes”, IEEE Trans. Inf. Theory, 36:3 (1990), 686–692 | DOI | Zbl

[32] Leander G., Abdelraheem M., Alkhzaimi H., Zenner E., “A cryptanalysis of PRINTcipher: The invariant subspace attack”, CRYPTO 2011, Lect. Notes Comput. Sci., 6841, 20110, 206–221 | DOI | Zbl

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

[34] Menyachikhin A. V., “Spectral-linear and spectral-differential methods for generating S-boxes having almost optimal cryptographic parameters”, Matematicheskie Voprosy Kriptografii, 8:2 (2017), 97–116 | DOI | Zbl

[35] Menyachikhin A. V., Method for generating S-boxes using the values of linear and differential spectra and device for its realization, RU Patent No 2633132, Bull. No 29, 2017 (in Russian) https://patentdb.ru/patent/2633132 | Zbl

[36] Menyachikhin A.V., “Orthomorphisms of Abelian groups with minimal pairwise distances”, Discrete Math. Appl., 30:3 (2020), 177–186 | Zbl

[37] Menyachikhin A.V., “The limited deficit's method and the construction problem of orthomorphisms and almost ortomorphisms of Abelian group”, Diskr. Matem., 31:3 (2019), 58–77 (in Russian) | DOI

[38] Menyachikhin A. V., Device for generating orthomorphisms using paired differences, RU Patent No 2632119, Bull. No 28, 2017 (in Russian) https://patentdb.ru/patent/2632119 | Zbl

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

[40] Niederreiter H., Robinson K., “Complete mappings of finite fields”, J. Australian Math. Soc., 33 (1982), 197–212 | DOI | Zbl

[41] Piret G., Roche T., Carlet C., “PICARO – A block cipher allowing efficient higher-order side-channel resistance”, ACNS 2012, Lect. Notes Comput. Sci., 7341, 2012, 311–328 | DOI

[42] 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 | Zbl

[43] Pokrasenko D. P., “On the maximal component algebraic immunity of vectorial Boolean functions”, J. Appl. Industr. Math., 10:2 (2016), 257–263 | DOI | Zbl

[44] Rijmen V., Preneel B., “A family of trapdoor ciphers”, FSE 1997, Lect. Notes Comput. Sci., 1267, 1997, 139–148 | DOI | Zbl

[45] Sage Mathematics Software (Version 8.1), 2018 http://www.sagemath.org

[46] Udovenko A., Design and Cryptanalysis of symmetric-key algorithms in black and white-box models, PhD diss., Univ. Luxembourg, 2019, 268 pp.

[47] Vaudenay S., Junod P., Device and method for encrypting and decrypting a block of data, United States Patent (20040247117), 2004 https://patents.justia.com/patent/20040247117

[48] Lai X., Massey J.L., “A proposal for a new block encryption standard”, EUROCRYPT'90, Lect. Notes Comput. Sci., 473, 1991, 389–404 | DOI | Zbl

[49] Yan T., Huanguo Zh., Haiqing H., “Using evolutionary computation in construction of orthomorphism”, 2009 Int. Conf. Multimed. Inf. Netw. Security (Hubei, China), v. 2, 2009, 478–481 | DOI