On some properties of the curvature and nondegeneracy of Boolean functions

R. A. de la Cruz Jiménez

Matematičeskie voprosy kriptografii, Tome 13 (2022) no. 2, pp. 65-98

Résumé

The paper is concerned with the problem of obtaining exact formulas and bounds for the curvature (i.e., the sum of modules of Walsh coefficients) and nondegeneracy (parameter related to the resistance of a Boolean function against some method of analysis) of some classes of cryptographic Boolean functions. Moreover, for these classes we determine other relevant cryptographic parameters as nonlinearity, algebraic degree and distance to linear structures. Also, we extend the notion of curvature to S-Boxes. For several nonlinear transforms used in actual symmetric cryptographic algorithms we investigate the properties of some parameters and matrices connected with the curvature of Boolean functions.

Bibliographie

[1] Alekseev E. K., “Filtering generator attacks with function close to algebraically degenerate”, Sbornik Statei molodyh uchenyh fakult. VMK MSU, 8, Izd. otdel f-ta VMK MSU, 2011, 19–32 (In Russian) https://cs.msu.ru/science/smu/activity/proceedings

[2] Barreto P., Rijmen V., “The Khazad legacy-Level block cipher”, First open NESSIE Workshop (Leuven, 2000)

[3] 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 | MR | Zbl

[4] Beierle C. et al., “The SKINNY Family of Block Ciphers and Its Low-Latency Variant MANTIS”, CRYPTO 2016, Lect. Notes Comput. Sci., 9815, 2016, 123–153 | DOI | MR | Zbl

[5] Carlet C., Boolean Functions for Cryptography and Coding Theory, Cambridge Univ. Press, Cambridge, 2021, xiv+562 pp.

[6] De la Cruz Jiménez R. A., Kamlovskiy O. V., “The sum of modules of Walsh coefficients of Boolean functions”, Diskretnaya Matematika, 26:5 (2016), 259–272 | MR | Zbl

[7] De la Cruz Jiménez R. A., “Constructing $8$-bit permutations, $8$-bit involutions and $8$-bit orthomorphisms with almost optimal cryptographic parameters”, Matematicheskie Voprosy Kriptografii, 12:3 (2021), 89–124 | DOI | MR | Zbl

[8] Dobbertin H., “Construction of Bent functions and balanced Boolean functions with high nonlinearity”, FSE 1994, Lect. Notes Comput. Sci., 1008, 1994, 61–74 | DOI

[9] Dygin D. M., Lavrikov I. V., Marshalko G. B., Rudskoy V. I., Trifonov D. I., Shishkin V. A., “On a new Russian Encryption Standard”, Matematicheskie Voprosy Kriptografii, 6:2 (2015), 29–34 | DOI | MR | Zbl

[10] Evertse J. H., “Linear structures in block ciphers”, EUROCRYPT 1987, Lect. Notes Comput. Sci., 304, 1988, 249–266 | DOI | MR | Zbl

[11] Andreeva E., Lallemand V., Purnal A., Reyhanitabar R., Roy A., Vizár D., Forkcipher: a new primtive for authenticated encryption of very short messages, Cryptology ePrint Archive, Report 2019/1004, https://eprint.iacr.org/2019/1004

[12] Fedorov S. N., “On a new classification of Boolean functions”, Matematicheskie Voprosy Kriptografii, 10:2 (2019), 159–168 | DOI | MR | Zbl

[13] Golić J.D., “On the security of nonlinear filter generators”, FSE 1996, Lect. Notes Comput. Sci., 1039, 1996, 173–188 | DOI | Zbl

[14] Kamlovskiy O. V., “The number of occurrences of elements in the output sequences of filter generators”, Prikladnaya diskretnaya matematika, 3:21 (2013), 11–25 (in Russian) | DOI

[15] Kamlovskiy O. V., “Estimating the number of solutions of systems of nonlinear equations with linear recurring arguments by the spectral method”, Discrete Math. Appl., 27:4 (2017), 199–211 | DOI | MR | Zbl

[16] Kamlovskiy O. V., “The sum of modules of Walsh coefficients of some balanced Boolean functions”, Matematicheskie Voprosy Kriptografii, 8:4 (2017), 75–98 | DOI | MR

[17] Logachev O. A., Smyshlyaev S. V., Yashenko V. V., “New methods of investigation of perfectly balanced Boolean functions”, Discrete Math. Appl., 19:3 (2009), 237–262 | DOI | MR | Zbl

[18] Logachev O. A., Sal'nikov A. A., Smyshlyaev S. V., Yashenko V. V., Boolean Functions in Coding Theory and Cryptology, URSS, M., 2015, 576 pp. (In Russian)

[19] Logachev O. A., Fedorov S. N., Yashenko V. V., “Boolean functions as points on the hypersphere in the Euclidean space”, Discrete Math. Appl., 29:2 (2019), 89–101 | DOI | MR | Zbl

[20] Logachev O. A., Fedorov S. N., Yashenko V. V., “On $\Delta$-equivalence of Boolean functions”, Discrete Math. Appl., 30:2 (2020), 93–101 | DOI | MR | Zbl

[21] Advanced Encryption Standard. Federal Information Processing Standard, (FIPS) 197, NIST, November 2001

[22] 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

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

[24] Smyshlyaev S. V., “Constructing classes of perfectly balanced Boolean functions without barriers”, Prikladnaya discretnaya matematika, 2010, 41–50 (in Russian) | DOI | MR | Zbl

[25] Smyshlyaev S. V., “Barriers of perfectly balanced Boolean functions”, Discrete Math. Appl., 20:3 (2010), 321–336 | DOI | MR | Zbl

[26] Smyshlyaev S. V., “Boolean functions without prediction”, Discrete Math. Appl., 21:2 (2011), 209–227 | DOI | MR | Zbl

[27] Smyshlyaev S. V., “Locally Invertible Boolean Functions”, Prikladnaya discretnaya matematika, 4(14) (2011), 11–21 (in Russian) | DOI | Zbl

[28] Smyshlyaev S. V., “Perfectly balanced $k$-valued functions and the Golić condition”, Discrete Math. Appl., 23:1 (2013), 75–89 | DOI | MR | Zbl

[29] Rueppel R.A., Analysis and design of stream ciphers, Springer-Verlag, Berlin–Heidelberg, 1986, 244 pp. | MR | Zbl

[30] Udovenko A., Design and Cryptanalysis of symmetric-key algorithms in black and white-box models, phd thesis, 2019 http://hdl.handle.net/10993/39350