Research On The Method Of Determining Affine Equivalence Of Boolean Function

The affine equivalence determination of Boolean functions has significant applications in encryption function design and circuit optimization.The main problem of the equivalence determination is to judge whether there is an affine transformation composed of an invertible matrix and a Boolean vector for a given two Boolean functions,so that the two functions are affine equivalent.If the function is equivalent,the corresponding affine transformation should be given.A new method to determine the affine equivalence according to matrix algebra is proposed in this thesis,which has big difference between the existing equivalence determination methods.The size of affine transformation space shows explosive growth with the increase of the number of function variables.The core of solving this problem is to find out the affine transformation which may make the function equivalent.The main ideas of the two existing decision algorithms are as follows.First,the Walsh spectrum and autocorrelation function spectrum of the function are calculated.Second,the constraint conditions of transformation are established based on the invariance of the absolute spectral distribution of equivalent functions.At last,the affine transformation search space is constructed.However,it takes a lot of computation in this step.And the size of the search space of the transformation cannot be estimated in advance.This thesis proposes an affine equivalence decision algorithm based on matrix group over finite fields,by studying the support matrix of Boolean function.By transforming the affine equivalence decision problem into a matrix representation,we first propose and prove the congruent standard form of Boolean function.It lays the foundation for the determination of equivalence because affine Boolean functions must have the same standard form.Based on the analysis of matrix congruence standard form,it is concluded that the affine transformation search space can be composed of support matrix row vectors,Boolean orthogonal matrix group,symplectic matrix group and small invertible matrix group.Finally,the generators of Boolean orthogonal matrix group and symplectic matrix group are given,and the construction of affine transformation search space is completed.The advantage of our method is that it can pre-load the generated Boolean matrix group before determination,which can greatly reduce the amount of computation of constructing search space.The searching space of our method is o(m·2r2/2+n(n-r)),where n is the number of bit operations,and r is the rank of the matrix,which is the product of support matrix of the test Boolean function and its transposition.In order to verify the effectiveness of the new method,we select the random generating function,the special Walsh spectral distribution function and the Boolean function with high nonlinearity as the experimental data.The experimental results shows that our method takes less time to determine equivalence for Boolean functions with higher algebraic times and Boolean functions with concentrated Walsh spectrum distribution in the neighborhood,which is better than the two existing methods.