×

On some properties of the curvature and nondegeneracy of Boolean functions. (English) Zbl 1519.94256

This article focuses on the study of nondegeneracy and curvature of some cryptographic Boolean functions.
Nondegeneracy of a Boolean function \(f:\mathbb{F}_{2^n}\rightarrow \mathbb{F}_2\) is the distance between \(f\) and the set of all algebraically degenerate Boolean functions and it is given by the formula \[ \text{nd}(f)=2^{n-1}-\frac{1}{4} \max_{\mathbf{0} \neq u\in \mathbb{F}_2^n} \Delta_f(u). \] Here, \(\Delta_f\) is the autocorrelation of \(f\) with itself which is \[ \Delta_f(u) = \sum_{x \in \mathbb{F}_2^n} (-1)^{f(x+u)\oplus f(x)}. \] The curvature \(\text{curv}(f)\) of a Boolean function \(f\) is calculated as the sum of the absolute values of its Walsh transform values and we always have \[ 2^n\leq \text{curv}(f) \leq 2^{3n/2}. \] In Section 2, the author considers some special classes of Boolean functions, subclasses of Maiorana-McFarland functions and calculate the exact values and bounds for the nondegeneracy and curvature of these special classes. In Section 3, the curvature results are given for the functions which are obtained through other Boolean functions by changing just one or multiple random values in the value set of the function. In Section 4, curvature definition is extended to vectorial Boolean functions from \(\mathbb{F}_{2^n}\) to \(\mathbb{F}_{2^n}\) and then certain S-boxes are analyzed for the curvature.

MSC:

94D10 Boolean functions
94A60 Cryptography

References:

[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
[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 · Zbl 1385.94016 · doi:10.1007/978-3-662-49890-3_15
[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 · Zbl 1372.94412 · doi:10.1007/978-3-662-53008-5_5
[5] Carlet C., Boolean Functions for Cryptography and Coding Theory, Cambridge Univ. Press, Cambridge, 2021, xiv+562 pp. · Zbl 1209.94036
[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 · Zbl 1360.06009
[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 · Zbl 1486.94095 · doi:10.4213/mvk377
[8] Dobbertin H., “Construction of Bent functions and balanced Boolean functions with high nonlinearity”, FSE 1994, Lect. Notes Comput. Sci., 1008, 1994, 61-74 · Zbl 0939.94563 · doi:10.1007/3-540-60590-8_5
[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 · Zbl 1475.94115 · doi:10.4213/mvk142
[10] Evertse J. H., “Linear structures in block ciphers”, EUROCRYPT 1987, Lect. Notes Comput. Sci., 304, 1988, 249-266 · Zbl 0659.94001 · doi:10.1007/3-540-39118-5_23
[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, · Zbl 1455.94111
[12] Fedorov S. N., “On a new classification of Boolean functions”, Matematicheskie Voprosy Kriptografii, 10:2 (2019), 159-168 · Zbl 1479.94377 · doi:10.4213/mvk293
[13] Golić J.D., “On the security of nonlinear filter generators”, FSE 1996, Lect. Notes Comput. Sci., 1039, 1996, 173-188 · Zbl 1373.94916 · doi:10.1007/3-540-60865-6_52
[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) · Zbl 1478.11149 · doi:10.17223/20710410/21/2
[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 · Zbl 1405.94036 · doi:10.1515/dma-2017-0022
[16] Kamlovskiy O. V., “The sum of modules of Walsh coefficients of some balanced Boolean functions”, Matematicheskie Voprosy Kriptografii, 8:4 (2017), 75-98 · Zbl 1476.94070 · doi:10.4213/mvk240
[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 · Zbl 1243.94029 · doi:10.1515/DMA.2009.014
[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 · Zbl 1446.94217 · doi:10.1515/dma-2019-0009
[20] Logachev O. A., Fedorov S. N., Yashenko V. V., “On \(\Delta \)-equivalence of Boolean functions”, Discrete Math. Appl., 30:2 (2020), 93-101 · Zbl 1465.94160 · doi:10.1515/dma-2020-0009
[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:10.1007/978-3-642-31284-7_19
[23] Sage Mathematics Software, Version 8.1, 2018
[24] Smyshlyaev S. V., “Constructing classes of perfectly balanced Boolean functions without barriers”, Prikladnaya discretnaya matematika, 2010, 41-50 (in Russian) · Zbl 1519.94263 · doi:10.17223/20710410/9/4
[25] Smyshlyaev S. V., “Barriers of perfectly balanced Boolean functions”, Discrete Math. Appl., 20:3 (2010), 321-336 · Zbl 1235.94083 · doi:10.4213/dm1096
[26] Smyshlyaev S. V., “Boolean functions without prediction”, Discrete Math. Appl., 21:2 (2011), 209-227 · Zbl 1223.94022 · doi:10.1515/dma.2011.013
[27] Smyshlyaev S. V., “Locally Invertible Boolean Functions”, Prikladnaya discretnaya matematika, 4(14) (2011), 11-21 (in Russian) · Zbl 07310085 · doi:10.17223/20710410/14/2
[28] Smyshlyaev S. V., “Perfectly balanced \(k\)-valued functions and the Golić condition”, Discrete Math. Appl., 23:1 (2013), 75-89 · Zbl 1283.94164 · doi:10.1515/dma-2013-004
[29] Rueppel R.A., Analysis and design of stream ciphers, Springer-Verlag, Berlin-Heidelberg, 1986, 244 pp. · Zbl 0618.94001
[30] Udovenko A., Design and Cryptanalysis of symmetric-key algorithms in black and white-box models, phd thesis, 2019
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.