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 manyvalued 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.
Cryptographic methods are the basis for building modern information security systems, which determines the relevance of the task of their further improvement [1, 2]. However, the improvement of cryptographic methods implies not only the search for the optimal structures of ciphers that provide the best implementation of the concepts of diffusion and confusion but also the synthesis of sets of high-quality cryptographic primitives that constitute their basis [3–5].
The task of synthesizing such cryptographic
primitives directly depends on chosen
methods for estimating the level of their
cryptographic quality. Today, to estimate the
level of quality of cryptographic primitives, a
set of cryptographic quality criteria is used,
which is applied to the component Boolean
functions of a cryptographic primitive [
Note, that despite the well-known methods for estimating the compliance of Boolean functions and functions of many-valued logic with cryptographic quality criteria, the problem of synthesizing cryptographic primitives of practically valuable lengths that would correspond in the best possible way to these criteria remains unsolved in the general case.
The relationship between the cryptographic quality of component Boolean functions and many-valued logic functions of cryptographic primitive remains understood insufficiently, although both Boolean functions and manyvalued logic functions can be considered as different ways of describing the same construction.
In particular, the relationship between the algebraic nonlinearity of a 4-function and the cryptographic quality of its component Boolean functions remains unexplored. This circumstance makes it difficult to further develop methods for synthesizing cryptographic primitives that would have a high level of cryptographic quality when they are represented in all possible ways using manyvalued logic functions.
The purpose of this paper is to research the
relationship between the algebraic nonlinearity
of a 4-function and the cryptographic properties
of its component Boolean functions.
2. Algebraic Normal Form
The basis of the modern approach for
estimating algebraic nonlinearity is the
mathematical apparatus of the Algebraic
Normal Form (ANF) [
A = fLN , f = ALN , where the direct and inverse Reed-Muller matrices are equal to each other and are determined in accordance with the following recursive relation
L1 = 1, 1 1 LN LN , L2N = 0 1 LN = 0 LN (1) (2)
where the symbol determine the Kronecker product.
In the case of 4-functions, the coefficients of
ANF terms can also be found using the
ReedMuller-Fourier transform, which is described
in [
A = L4F, F = L−41A
where the matrices L4 and L−41 can be found
using the recurrent constructions proposed in
[
L4k−1
L4k−1 L4k−1 L4k−1 0 L−41k−1 3L−41k−1 2L−41k−1 0 3L4k−1 2L4k−1 L4k−1 0 L−41k−1 , L−41k−1 L−41k−1 0 2L4k−1 . 3L4k−1 L4k−1
Note that in the case of 4-functions, the direct and inverse matrices of the Reed-Muller transform do not coincide, while all arithmetic operations are performed in accordance with the arithmetic of the extended Galois field GF(4) . 3. Interconnection Between Cryptographic Properties of Boolean Functions and Algebraic Nonlinearity of 4Functions Each 4-function f4 can be represented as its two component Boolean functions f20 and f21 , which completely determine its properties, as shown by the following example
In this section, we consider the relationship between the cryptographic properties of the component Boolean functions f20 and f21 , which are parts of the 4-function f4 , and its algebraic degree of nonlinearity.
In case of the necessity to process large sets of Boolean functions, experimental data on the algebraic nonlinearity of 4-functions are obtained in this paper by synthesizing them based on a sample of 106 Boolean functions with a given level of cryptographic quality. 3.1. Algebraic Nonlinearity Component Boolean Functions The algebraic degree of nonlinearity of a Boolean function is defined as the largest degree of the term of its ANF. For one of the most practically valuable lengths of Boolean functions N =16 , we represent in the Table 1 the possible terms of the ANF, as well as their algebraic degrees of nonlinearity. In turn, the algebraic degree of nonlinearity of a 4-function is defined as the largest degree of its ANF term, while the possible terms of the ANF, as well as their algebraic degrees of nonlinearity for the 4-function of two variables, are given in Table 2. To determine the relationship between the ANF of component Boolean functions f20 , f21 and the constituted by them 4-function f4 , the following experiment was performed. For the selected Boolean functions f20 and f21 having an equal algebraic degree of nonlinearity (as it is common for component Boolean functions of modern cryptographic algorithms), a 4function was constructed, for which the algebraic degree of nonlinearity was 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 f4 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. Analysis of the data presented in Table 3 allows us to conclude that when combining two Boolean functions of length N =16 , which have an equal algebraic degree of nonlinearity into one 4-function, the algebraic degree of nonlinearity of the resulting 4-function, in the general case, is not lower than the algebraic degree of nonlinearity of the component Boolean functions. 3.2. Distance Nonlinearity of Component
Boolean Functions Next, we present the results of researching the relationship between the nonlinearity distance of component Boolean functions f20 , f21 and the 4-function f4 which is constituted by them.
The nonlinearity distance of a Boolean
function is determined as the minimum among
its Hamming distances to codewords of an
affine code Aj [
N f = min(dist( f , Aj )), j = 1,2k+1 . (5)
In Table 4 we present the values of the algebraic degree of nonlinearity of the resulting 4-functions, which are constituted by the Boolean functions f20 and f21 , which have a given level of nonlinearity distance. At the same time, in Table 4, the numbers in curly brackets indicate the probabilities of the formation of 4-function f4 with a given algebraic degree of nonlinearity when using Boolean functions f20 and f21 , which have a given value of the nonlinearity distance. The analysis of the data presented in Table 4 shows that 4-functions with the largest value of the algebraic degree of nonlinearity can be constituted on the basis of Boolean functions, the nonlinearity distance of which has an odd value. 3.3. Avalanche Characteristics Component Boolean Functions of To solve practical problems, quite a lot of modifications of the error propagation criterion have been proposed, among which the strict avalanche criterion is the most common and in demand. The correspondence of a Boolean function to a strict avalanche criterion is determined based on the following definition.
Definition 1 [
p{ f (x) = f (x u)} = 0.5 , u Vn, wt(u) =1. (6)
In Table 5 we present the results of research of the values of the algebraic degree of nonlinearity of 4-functions constituted by the component Boolean functions that correspond and do not correspond to the strict avalanche criterion. At the same time, in Table 5, the numbers in curly brackets indicate the probabilities of the formation of 4-function f4 with a given algebraic degree of nonlinearity when using Boolean functions f20 and f21 , which (do not) correspond to the strict avalanche criterion. 0 {10−9 }, 1 {1.59 10−8 }, 2 { 1.4310−6 }, 3 { 3.86 10−5 }, 4 {0.0142}, 5 {0.2037}, 6 {0.7821} 2 {1.6 10−4 }, 3 {0.0256}, 4{0.1096}, 5{0.8646} Analysis of the data presented in Table 5 allows us to conclude that 4-functions of length N =16 based on Boolean functions that correspond to the strict avalanche criterion generally have an algebraic degree of nonlinearity greater than 2 and most likely equal to 5. 3.4. Correlation Immunity of Component
Boolean Functions The correlation immunity of the order m of Boolean function means that its output is not dependent on any group of size m of its input variables.
Since the correlation immunity of order m 1 of the Boolean function is a very strict requirement and is rarely used in practice, we consider the case of correlation-immune of order m =1 Boolean functions.
The determination of the correspondence of the Boolean function to the criterion of correlation immunity is performed on the basis of the following definition.
Definition 2 [
In Table 6 we present the results of research on the values of the algebraic degree of nonlinearity of 4-functions constructed on the basis of component Boolean functions that correspond and do not correspond to the correlation immunity criterion of order m =1 . In Table 6, the numbers in curly brackets indicate the probabilities of the formation of 4function f4 with a given algebraic degree of nonlinearity when using Boolean functions f20 and f21 , which (do not) correspond to the correlation immunity criterion. correlation and the Analysis of the data presented in Table 6 allows us to conclude that the largest number of 4-functions that are constituted from the correlation-immune Boolean functions has an algebraic degree of nonlinearity equal to 5.
In this paper, research devoted to understanding the relationship between the algebraic degree of nonlinearity of 4-functions of two variables and the cryptographic properties of its component Boolean functions are performed. The obtained results allowing us to form the following conclusions that are significant for the development of cryptographic primitives: 1. A larger algebraic degree of nonlinearity of the component Boolean functions leads to a larger algebraic degree of nonlinearity of a resulting 4-function. 2. Odd values of the nonlinearity distance of the component Boolean functions lead to the formation of a 4-function with the maximum algebraic degree of nonlinearity. 3. 4-functions consisting of component Boolean functions that satisfy the strict avalanche criterion are most likely to have an algebraic degree of nonlinearity equal to 5. 4. 4-functions consisting of component Boolean functions that satisfy the correlation immunity criterion are most likely to have an algebraic degree of nonlinearity equal to 5. 5. there are no 4-functions with algebraic degree of nonlinearity equal to 6 that are constituted from Boolean functions that correspond to strict avalanche criterion or the criterion of correlation immunity.
Of practical interest are further research devoted to identification of more general patterns that reflect the relationship between the criteria for the cryptographic quality of many-valued logic functions of an arbitrary number of variables and their component Boolean functions.