Dependence of the Algebraic Nonlinearity of 4-Functions of Two Variables from the Cryptographic Properties of Their Component Boolean Functions Nadiia Kazakova1, Artem Sokolov2, and Nataliia Balandina3 1 Odesa State Environmental University, 15 Lvivska str., Odesa, 65016, Ukraine 2 Odesa Polytechnic National University, 1 Shevchenko ave., Odesa, 65044, Ukraine 3 National University “Odesa Law Academy”, 23 Fontanska road, Odesa, 65000, Ukraine Abstract Further development and improvement of the efficiency of ciphers largely depend on the success of solving the problem of synthesizing cryptographic primitives that correspond to the quality criteria both when they are represented by Boolean functions and many- valued logic functions. Among these most significant cryptographic quality criteria are algebraic nonlinearity, distance nonlinearity, error propagation criterion, and correlation immunity criterion. To solve the problem of synthesizing high-quality cryptographic structures, it is important to research the relationship between the level of cryptographic quality of the resulting functions of many-valued logic and their component Boolean functions. In this paper, we represent the results of the research on the algebraic nonlinearity of 4-functions of two variables when they are constructed based on two Boolean functions with given cryptographic quality parameters. The results obtained can be considered as a theoretical basis for improving existing and developing new methods for synthesizing cryptographic primitives, which are characterized by the high cryptographic quality of both component Boolean functions and component many-valued logic functions. Keywords 1 Nonlinearity, algebraic normal form, Reed-Muller transform, Reed-Muller-Furrier transform, Boolean function, many-valued logic function. 1. Introduction level of quality of cryptographic primitives, a set of cryptographic quality criteria is used, Cryptographic methods are the basis for which is applied to the component Boolean building modern information security systems, functions of a cryptographic primitive [6] and which determines the relevance of the task of its component many-valued logic functions. their further improvement [1, 2]. However, the The main criteria for cryptographic quality improvement of cryptographic methods used are the following: the criterion for implies not only the search for the optimal maximizing algebraic nonlinearity, the structures of ciphers that provide the best criterion for maximizing distance nonlinearity, implementation of the concepts of diffusion the error propagation criterion, and the and confusion but also the synthesis of sets of correlation immunity criterion. These criteria high-quality cryptographic primitives that are well-known for Boolean functions [7] and constitute their basis [3–5]. have also been generalized for the case of The task of synthesizing such cryptographic many-valued logic functions [8]. Moreover, primitives directly depends on chosen today there is a known integral approach for methods for estimating the level of their assessing the cryptographic properties of cryptographic quality. Today, to estimate the CPITS-2024: Cybersecurity Providing in Information and Telecommunication Systems, February 28, 2024, Kyiv, Ukraine EMAIL: kaz2003@ukr.net (N. Kazakova); radiosquid@gmail.com (A. Sokolov); nataliabalandina2103@gmail.com (N. Balandina) ORCID: 0000-0003-3968-4094 (N. Kazakova); 0000-0003-0283-7229 (A. Sokolov); 0000-0002-3121-4517 (N. Balandina) ©️ 2024 Copyright for this paper by its authors. Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0). CEUR Workshop Proceedings (CEUR-WS.org) CEUR ceur-ws.org Workshop ISSN 1613-0073 Proceedings 479 component many-valued logic functions, where the symbol  determine the which was presented in [9]. Kronecker product. Note, that despite the well-known methods In the case of 4-functions, the coefficients of for estimating the compliance of Boolean ANF terms can also be found using the Reed- functions and functions of many-valued logic Muller-Fourier transform, which is described with cryptographic quality criteria, the problem in [11], the general form of which can be of synthesizing cryptographic primitives of written as practically valuable lengths that would A = L4 F , F = L−41 A (3) correspond in the best possible way to these criteria remains unsolved in the general case. where the matrices L4 and L can be found −1 4 The relationship between the cryptographic using the recurrent constructions proposed in quality of component Boolean functions and [8] many-valued logic functions of cryptographic  L−41k −1 0 0 0  primitive remains understood insufficiently,  L−1 L−41k −1 L−41k −1 L−41k −1  L−41k =  −41 k −1 , although both Boolean functions and many-  L4k −1 2 L−41k −1 3L−41k −1 L−41k −1  valued logic functions can be considered as  L−1k −1 3L−41k −1 2 L−41k −1 L−41k −1   4 (4) different ways of describing the same  L4k −1 0 0 0  construction.  0 L4k −1 3L4k −1 2 L4k −1  3L4k −1  . L4k =  0 L4k −1 2 L4k −1 In particular, the relationship between the   algebraic nonlinearity of a 4-function and the  L4k −1 L4k −1 L4k −1 L4k −1  cryptographic quality of its component Note that in the case of 4-functions, the Boolean functions remains unexplored. This direct and inverse matrices of the Reed-Muller circumstance makes it difficult to further transform do not coincide, while all arithmetic develop methods for synthesizing cryptographic operations are performed in accordance with primitives that would have a high level of the arithmetic of the extended Galois field cryptographic quality when they are GF (4) . represented in all possible ways using many- valued logic functions. The purpose of this paper is to research the 3. Interconnection Between relationship between the algebraic nonlinearity Cryptographic Properties of of a 4-function and the cryptographic properties Boolean Functions and of its component Boolean functions. Algebraic Nonlinearity of 4- Functions 2. Algebraic Normal Form Each 4-function f 4 can be represented as its The basis of the modern approach for two component Boolean functions f20 and f21 , estimating algebraic nonlinearity is the mathematical apparatus of the Algebraic which completely determine its properties, as Normal Form (ANF) [10]. The coefficients of shown by the following example terms of the algebraic normal form of Boolean f4 1 1 0 1 1 0 2 3 2 1 3 0 0 0 3 1 f 20 1 1 0 1 1 0 0 1 0 1 1 0 0 0 1 1 . (4) functions of k variables whose truth table f 21 0 0 0 0 0 0 1 1 1 0 1 0 0 0 1 0 length is equal to N = 2k , is found using the Reed-Muller transform In this section, we consider the relationship (1) between the cryptographic properties of the A = fLN , f = ALN , component Boolean functions f20 and f21 , where the direct and inverse Reed-Muller which are parts of the 4-function f 4 , and its matrices are equal to each other and are algebraic degree of nonlinearity. determined in accordance with the following In case of the necessity to process large sets recursive relation of Boolean functions, experimental data on the L1 = 1 , algebraic nonlinearity of 4-functions are 1 1 L LN  (2) obtained in this paper by synthesizing them L2 N =   LN =  N  LN  , 0 1 0 based on a sample of 106 Boolean functions with a given level of cryptographic quality. 480 3.1. Algebraic Nonlinearity of Table 3 Component Boolean Functions Relationship between algebraic nonlinearity of Boolean functions and 4-functions The algebraic degree of nonlinearity of a deg( f 20 ) = deg( f 21 ) deg( f 4 ) Boolean function is defined as the largest 0 0 {1.0} 1 1 {0.0667}, degree of the term of its ANF. For one of the 2 {0.9333} most practically valuable lengths of Boolean 2 2 { 7.9  10−4 }, functions N = 16 , we represent in the Table 1 3 {0.2497}, 4 {0.7495} 3 4 {0.0664}, 5 {0.9336} the possible terms of the ANF, as well as their 4 6 {1.0} algebraic degrees of nonlinearity. Table 1 Analysis of the data presented in Table 3 Algebraic degrees of ANF terms of Boolean allows us to conclude that when combining functions of length N = 16 two Boolean functions of length N = 16 , which a0 x4 x3 x3 x4 x2 x2 x4 x2 x3 x2 x3 x4 have an equal algebraic degree of nonlinearity 0 1 1 2 1 2 2 3 into one 4-function, the algebraic degree of x1 x1x4 x1x3 x1x3 x4 x1x2 x1x2 x4 x1x2 x3 x1x2 x3 x4 nonlinearity of the resulting 4-function, in the general case, is not lower than the algebraic 1 2 2 3 2 3 3 4 degree of nonlinearity of the component Boolean functions. In turn, the algebraic degree of nonlinearity of a 4-function is defined as the largest degree of 3.2. Distance Nonlinearity of Component its ANF term, while the possible terms of the ANF, as well as their algebraic degrees of Boolean Functions nonlinearity for the 4-function of two variables, are given in Table 2. Next, we present the results of researching the relationship between the nonlinearity distance Table 2 of component Boolean functions f20 , f21 and Algebraic degrees of ANF terms of 4-functions the 4-function f 4 which is constituted by them. of length N = 16 The nonlinearity distance of a Boolean a0 x2 x22 x23 x1 x1x2 x1x22 x1x23 function is determined as the minimum among 0 1 2 3 1 2 3 4 its Hamming distances to codewords of an x2 1 2 x x 1 2 2 2 x x 1 2 2 3 x x 1 2 x3 1 3 x x 1 2 3 2 x x 1 2 3 3 x x 1 2 affine code A j [12], i.e. 2 3 4 5 3 4 5 6 N f = min( dist ( f , Aj )), j = 1, 2 k +1 . (5) In Table 4 we present the values of the To determine the relationship between the algebraic degree of nonlinearity of the ANF of component Boolean functions f20 , f21 resulting 4-functions, which are constituted by and the constituted by them 4-function f 4 , the the Boolean functions f20 and f21 , which have a following experiment was performed. For the given level of nonlinearity distance. At the selected Boolean functions f20 and f21 having same time, in Table 4, the numbers in curly an equal algebraic degree of nonlinearity (as it brackets indicate the probabilities of the is common for component Boolean functions of formation of 4-function f 4 with a given modern cryptographic algorithms), a 4- algebraic degree of nonlinearity when using function was constructed, for which the Boolean functions f20 and f21 , which have a algebraic degree of nonlinearity was given value of the nonlinearity distance. estimated. The results of the experiment are presented in Table 3. At the same time, in Table 3, the numbers in curly brackets indicate the probabilities of the formation of 4-function f 4 with a given algebraic degree of nonlinearity when using Boolean functions f20 and f21 , which have a given value of the algebraic degree of nonlinearity. 481 Table 4 Table 5 Relationship between the nonlinearity Relationship between the strict avalanche distance of Boolean functions and the algebraic criterion for Boolean functions and the nonlinearity of 4-functions algebraic nonlinearity of 4-functions N f 20 = N f 21 deg( f 4 ) Strict avalanche deg( f 4 ) criterion 0 0 {0.0039},1 {0.0586}, Do not 2 {0.9375} 0 { 10−9 }, correspond 1 6 {1.0} 1 { 1.59  10−8 }, 2 4 {0.0664}, 5 {0.9336} 2 { 1.43  10−6 }, 3 6 {1.0} 4 3 { 3.86  10−5 }, 3 { 4.5  10−4 }, 4 {0.0623}, 4 {0.0142}, 5 {0.9372} 5 {0.2037}, 5 6 {1.0} 6 {0.7821} 6 2 {0.0038}, 3 {0.2606}, Correspond 4 {0.7357} 2 { 1.6  10−4 }, 3 {0.0256}, 4{0.1096}, The analysis of the data presented in Table 4 5{0.8646} shows that 4-functions with the largest value of the algebraic degree of nonlinearity can be Analysis of the data presented in Table 5 constituted on the basis of Boolean functions, allows us to conclude that 4-functions of length the nonlinearity distance of which has an odd N = 16 based on Boolean functions that value. correspond to the strict avalanche criterion generally have an algebraic degree of 3.3. Avalanche Characteristics of nonlinearity greater than 2 and most likely Component Boolean Functions equal to 5. To solve practical problems, quite a lot of 3.4. Correlation Immunity of Component modifications of the error propagation Boolean Functions criterion have been proposed, among which the strict avalanche criterion is the most The correlation immunity of the order m of common and in demand. The correspondence Boolean function means that its output is not of a Boolean function to a strict avalanche dependent on any group of size m of its input criterion is determined based on the following variables. definition. Since the correlation immunity of order Definition 1 [13, 14]. The Boolean function m  1 of the Boolean function is a very strict f 2 corresponds to the strict avalanche requirement and is rarely used in practice, we criterion, if its derivatives consider the case of correlation-immune of Du f 2 ( x) = f 2 ( x)  f 2 ( x  u) in the direction of all order m = 1 Boolean functions. vectors u of weight wt (u) = 1 are balanced The determination of the correspondence of functions, i.e. the Boolean function to the criterion of p{ f ( x) = f ( x  u)} = 0.5 , u Vn , wt (u) = 1 . (6) correlation immunity is performed on the basis of the following definition. In Table 5 we present the results of research Definition 2 [15, 16]. A Boolean function of the values of the algebraic degree of f ( x) , x Vk , is called correlation-immune of the nonlinearity of 4-functions constituted by the component Boolean functions that correspond order m , 1  m  k , if weight is equal and do not correspond to the strict avalanche wt ( f ) = wt ( f ) / 2m , for any of its subfunction f  of criterion. At the same time, in Table 5, the k − m variables, while the subfunction of the numbers in curly brackets indicate the Boolean function f ( x) , x Vk , is a function probabilities of the formation of 4-function f 4 obtained by substituting into it constants "0" with a given algebraic degree of nonlinearity or "1" instead of some of the variables. when using Boolean functions f20 and f21 , In Table 6 we present the results of research which (do not) correspond to the strict on the values of the algebraic degree of avalanche criterion. nonlinearity of 4-functions constructed on the basis of component Boolean functions that 482 correspond and do not correspond to the 4. 4-functions consisting of component correlation immunity criterion of order m = 1 . Boolean functions that satisfy the In Table 6, the numbers in curly brackets correlation immunity criterion are most indicate the probabilities of the formation of 4- likely to have an algebraic degree of function f 4 with a given algebraic degree of nonlinearity equal to 5. nonlinearity when using Boolean functions f20 5. there are no 4-functions with algebraic degree of nonlinearity equal to 6 that are and f21 , which (do not) correspond to the constituted from Boolean functions that correlation immunity criterion. correspond to strict avalanche criterion Table 6 or the criterion of correlation immunity. Relationship between the correlation Of practical interest are further research immunity of Boolean functions and the devoted to identification of more general algebraic nonlinearity of 4-functions patterns that reflect the relationship between Correlation the criteria for the cryptographic quality of immunity of deg( f 4 ) many-valued logic functions of an arbitrary order m = 1 number of variables and their component Do not 2 { 1.43  10−6 }, 3 { 1.71  10−4 }, correspond Boolean functions. 4 {0.0149}, 5 {0.2298}, 6 {0.7551} Correspond 0 { 9.53  10−6 }, 1 { 8.57  10−5 }, References 2 {0.0013}, 3 {0.0628}, 4 {0.1920}, 5 {0.7438} [1] H. Hulak, et al., Dynamic Model of Analysis of the data presented in Table 6 Guarantee Capacity and Cyber Security allows us to conclude that the largest number Management in the Critical Automated of 4-functions that are constituted from the System, in: 2nd International Conference correlation-immune Boolean functions has an on Conflict Management in Global algebraic degree of nonlinearity equal to 5. Information Networks, vol. 3530 (2023) 102–111. [2] P. Anakhov, et al., Protecting Objects of 4. Conclusions Critical Information Infrastructure from Wartime Cyber Attacks by Decentralizing In this paper, research devoted to the Telecommunications Network, in: understanding the relationship between the Workshop on Cybersecurity Providing in algebraic degree of nonlinearity of 4-functions Information and Telecommunication of two variables and the cryptographic Systems, vol. 3550 (2023) 240–245. properties of its component Boolean functions [3] A. Bessalov, et al., Multifunctional CRS are performed. The obtained results allowing Encryption Scheme on Isogenies of Non- us to form the following conclusions that are Supersingular Edwards Curves, in: significant for the development of Workshop on Classic, Quantum, and cryptographic primitives: Post-Quantum Cryptography, vol. 3504 1. A larger algebraic degree of nonlinearity (2023) 12–25. of the component Boolean functions [4] A. Bessalov, et al., Computing of Odd leads to a larger algebraic degree of Degree Isogenies on Supersingular nonlinearity of a resulting 4-function. Twisted Edwards Curves, in: Workshop 2. Odd values of the nonlinearity distance on Cybersecurity Providing in of the component Boolean functions lead Information and Telecommunication to the formation of a 4-function with the Systems, vol. 2923 (2021) 1–11. maximum algebraic degree of [5] A. Bessalov, V. Sokolov, P. Skladannyi, nonlinearity. Modeling of 3- and 5-Isogenies of 3. 4-functions consisting of component Supersingular Edwards Curves, in: 2nd Boolean functions that satisfy the strict Int. Workshop on Modern Machine avalanche criterion are most likely to Learning Technologies and Data Science, have an algebraic degree of nonlinearity no. I, vol. 2631 (2020) 30–39. equal to 5. 483 [6] A. Elhosary et al., State of the Art in Boolean Functions Cryptographic Assessment, Int. J. Comput. Netw. Commun. Secur. (2013) 88–94. [7] O. Logachev, A. Sal’nikov, V. Jashhenko, Boolean Functions in Coding Theory and Cryptology, Publishing House MCNMO (2004). [8] A. Sokolov, O. Zhdanov, Cryptographic Constructions Based on Many-Valued Logic Functions, Monograph, Publishing House Scientific Thought (2020). [9] A. Sokolov, et al., Prerequisites for Developing a Methodology for Estimating and Increasing Cryptographic Strength Based on Many- Valued Logic Functions, in: Cybersecurity Providing in Information and Telecommunication Systems Vol. 2923 (2021) 107–116. [10] A. Rostovcev, Cryptography and Data Protection, Publishing House World and Family (2002). [11] R. Stanković, J. Astola, C. Moraga, Representations of Multiple-Valued Logic Functions, Morgan&Claypool Publishers (2012). [12] F. Rodier, On the Nonlinearity of Boolean Functions, WCC2003, Workshop on Coding and Cryptography (2003) 397– 405. [13] R. Forré, The Strict Avalanche Criterion: Spectral Properties of Boolean Functions and an Extended Definition, Advances in Cryptology, LNCS 403 (1990) 450–468. [14] A. Sokolov, Constructive Method for the Synthesis of Nonlinear S-boxes Satisfying the Strict Avalanche Criterion, Radioelectron. Commun. Syst. 56(8) (2013) 415–423. doi: 10.3103/S0735 272713080049. [15] S. Picek et al., Correlation Immunity of Boolean Functions: An Evolutionary Algorithms Perspective, Annual Conference on Genetic and Evolutionary Computation (2015) 1095–1102. doi: 10.1145/2739480.2754764. [16] K. Kim, Construction of DES-like S-boxes Based on Boolean Functions Satisfying the SAC, Advances in Cryptology— ASIACRYPT’91, LNCS 739 (1991) 59–73. 484