Construction And Analysis Of Boolean Functions With Fine Cryptographic Properties

Boolean functions are often used to design important components in symmetric cryptosystems,and their security properties are closely related to the security performance of the entire cryptosystem.Therefore,the design of Boolean functions with excellent cryptographic properties has always been one of the important research directions of symmetric cryptosystems.This dissertation is concentrated on the study and optimization of the Hill Climbing(HC)algorithm that generates high nonlinearity balanced Boolean functions.On this basis,combining the two ideas of theoretical construction and intelligent search,a new type of algorithm is presented.Its superior performance in the construction of high nonlinearity balanced Boolean functions is verified by program simulation.First of all,this paper researches the traditional HC1 algorithm for constructing Boolean functions and finds that it has two shortcomings that limit the performance of the algorithm.Firstly,the initial search node is not balanced,which makes the Boolean function generated by the algorithm is not absolutely balanced;secondly,the algorithm stops searching after reaching a balanced search node,which makes the Boolean function generated by the algorithm have low nonlinearity.Focusing on the above two shortcomings,this paper proposes to optimize the HC1 algorithm,which starts from the initial node of balance,and continues to search forward after reaching the balance node.The simulation results show that the probability of optimized HC1 algorithm which generates a balanced Boolean function is increased to 100%,and the nonlinearity performance is also better than the traditional algorithm.Secondly,this article studies the traditional HC2 algorithm,which constructs Boolean functions,but this algorithm does not take full advantage of the second-order hill climbing.Compared with the HC1 algorithm,the HC2 algorithm has a translational direction when looking for the ascending direction.Therefore,this article optimizes the flow of the HC2 algorithm.When the current node does not have an ascending direction,it attempts to move from the contour line to look for the possibility of ascending.Through the simulation results,it can be seen that: first,from a partial perspective,the probability of the optimized HC2 algorithm proposed in this paper at some points is increased by more than 50% compared with the traditional HC2 algorithm;second,from a global perspective,the weighted mean value of nonlinearity of the Boolean function generated by the optimized HC2 algorithm is higher than that of the traditional HC2 algorithm,but the improvement is limited.Finally,with the two ideas of theoretical construction of Boolean functions and intelligent search,this dissertation proposes a DSDHC algorithm,which converts the construction of high-variable Boolean functions into two small-variable Boolean functions,one of which is the construction of the Bent function for even-variable,the second is the construction of a balanced Boolean function with high nonlinearity of arbitrary variables.At the same time,with the characteristics of the Boolean function cycle Walsh spectrum,the function is transformed without affecting the nonlinearity of the function,and the performance of the HC2 algorithm is further optimized.The simulation results show that the DSDHC algorithm proposed in this paper has a 90%probability of constructing a balanced Boolean function of odd variables that reaches the upper limit of the theoretical nonlinearity,and the nonlinearity of the constructed Boolean function of even variables is far better than that of the ordinary HC algorithm.