On nonlinearity and hamming weight preserving bijective mappings acting on boolean functions

Sertkaya, İsa
Boolean functions are widely studied in cryptography due to their key role and ap- plications in various cryptographic schemes. Particularly in order to make symmetric crypto-systems resistant against cryptanalytic attacks, Boolean functions are associ- ated some cryptographic design criteria. As a result of Shannon’s similarity of secrecy systems theory, cryptographic design criteria should be at least preserved under the action of basic transformations. Among these design criteria, Meier and Staffelbach analyzed behavior of the nonlinearity criteria under the action of bijective mappings defined on input values of the functions. Later, Preneel proved that nonlinearity still remains invariant under the action of affine equivalence mappings. Motivated by the previous studies, in his master thesis, the author showed the existence of new nonlin- earity preserving bijective mappings. In this thesis, we first give definition of the maximal group that can act on Boolean functions. This maximal group is the symmetric group of the vector space that cor- responds to the set comprised of the truth table of the Boolean functions. We give a representation, based on the coordinate functions’ algebraic normal form, for the ele- ments of this symmetric group and then we list its subgroups that we mainly focus on. Regarding these subgroups, our aim is to enumerate or classify these bijective map- pings with respect to preserving a cryptographic design criterion. After the necessary definitions and notions, we mainly investigate the nonlinearity preserving bijective mappings. Then we apply the procedures constructed on nonlinearity preservability to another cryptographic design criterion, namely the Hamming weight. From a the- oretical viewpoint, our basic result is that we show the existence of new families of bijective mappings that leaves nonlinearity (respectively, Hamming weight) invariant. Under the action of linear and affine bijective mappings we give the necessary and sufficient conditions to keep nonlinearity invariant. We explicitly construct an iso- morphism between the affine equivalency mappings subgroup and the automorphism group of the Sylvester Hadamard matrices and give the order of this automorphism group. Next we construct a family of non-affine nonlinearity preserving bijective map- pings explicitly. However, we also show that all of these explicitly constructed non- linearity preserving bijective mappings produce the same orbit structure as the affine equivalency mappings. On the other hand, we give the exact number of nonlinearity preserving bijective mappings for the functions with n ≤ 6 variables. Then, based on these cardinalities, we prove the existence of new non-affine nonlinearity preserving mappings, without constructing explicitly. We demonstrate some examples for these non-affine mappings. Following the results obtained for nonlinearity preserving bijective mappings, we ex- tend our study to the Hamming weight preserving bijective mappings. First we com- pletely solve the enumeration problem of Hamming weight preserving bijective mappings, and give the exact number of the Hamming weight preserving bijective map- pings for all Boolean functions. Afterwards, we study the classification problem and give partial results. Lechner proved that the Hamming weight property is preserved un- der the action of symmetric group of input vector space. We further prove that among the affine bijective mappings only these mappings preserve the Hamming weight. Finally, again based on the enumeration of the Hamming weight preserving bijective mappings we proved the existence of Hamming weight preserving non-affine bijective mappings.
Citation Formats
İ. Sertkaya, “On nonlinearity and hamming weight preserving bijective mappings acting on boolean functions,” Ph.D. - Doctoral Program, Middle East Technical University, 2014.