Research On Some Mathematical Problems Of Boolean Functions

Boolean functions are the key components of cryptographic systems. The cryptographic properties of Boolean functions used in cryptography are crucial to the security of the cryptographic algorithms. To resist all kinds of earlier attacks, the Boolean functions should be balanced, correlation immune, high algebraic degree, highier nonlinearity, and high algebraic immunity. How to design Boolean functions with good cryptographic properties is an important problem. On the other hand, Boolean functions are related to coding theory, combinatoric design and the designs of signals with good properties. In this thesis, some mathematical problems of Boolean functions are studied:construction of a class of maximal linear orthomorphic permutations is proposed, and the results are applied to the construction of Boolean functions with optimal algebraic immunity; The relationships between resiliency order and algebraic immunity are given; Some orthogonal arrays are obtained by using the link between orthogonal arrays and resilient functions; Constructions and count of1-resilient rotation symmetric Boolean functions(RSBFs) are proposed based on the properties of support tables of1-resilient RSBFs. Lastly, constructions and count of1-resilient rotation symmetric functions with prime number of variables over GF(p) are also studied. The main contributions are introduced as follows:1. At current, construction of orthomorphic permutation is a hot problem in cryptography. The orthomorphic permutations can be seen as resilient functions of order0. Construction and enumeration of the maximal linear orthomorphic permutations are studied firstly in this thesis. The results indicate that this class of orthomorphic permutations can be generated by linear feedback registers, and so maximal linear orthomorphic permutations can be implemented quickly. Constructions of the Boolean functions with optimal algebraic immunity are proposed by using these orthomorphic permutations.2. For the Boolean functions with maximum algebraic immunity, it’s well known that there esist a lower bound of nonlinearity, a lower bound of algebraic degree, and the bounds of its Hamming weight. The relationship between the algebraic immunity and the resilient order is given in thesis. The upper bound of resilient order for Boolean functions with maximal algebraic immunity is presented. The tightness of the upper bound is also demonstrated. The results indicate that there does not exist1-resilient3-variable Boolean function with maximal algebraic immunity. A1-resilient5-variable Boolean function with maximal algebraic immunity is given. It has been experimentally proven that the upper bound is also tight for6>7and8-variable Boolean functions.3. The methods to construct resilient functions proposed by Zheng et al. are analyzed, and the technique of recursion proposed by Wen et al is studied. The technique of recursion is extended to GF(p). A general recursion construction of orthogonal arrays over GF(p) is presented. A large class of symmetric orthogonal arrays are proposed which can be used in experiments of design(DOE) and authentication codes. By using latin squares, many orthogonal arrays of strength t with the same parameter are constructed, these orthogonal arrays are good choices for the designer of experiment and authentication codes.4. It has been experimentally demonstrated that RSBFs are extremely rich in terms of cryptographically significant Boolean functions, and RSBFs can possess the properties such as balancedness, correlation immunity, high nonlinearity, high algebraic degree, and high algebraic immunity. By using the method of matrix analysis, construction and count of p,pq-variable1-resilient RSBFs are proposed, and the constructions of1-resilient2-RSBFs on2p variables are also studied.5. Based on the1-resilient RSBFs constructed before, the properties of the support tables of RSBFs are further studied. A general technique to construct1and2-resilient RSBFs on given number of variables are obtained respectively. Construction of resilient RSBFs on given number of variables is also equivalent to solving an equation system, and the number of resilient RSBFs is equal to the nmber of the solutions of the corresponding equation system.6. Based on the results of construction and count of balanced rotation symmetric functions, the properties of l-value characteristic matrices of the rotation symmetric functions with n variables over GF(p) are proposed. Construction and count of1-resilient RSFs are also presented. It is indicated that the construction and enumeration of the rotation symmetric functions with n variables are equivalent to solving an equation system, and the count of1-resilient RSFs can be represented by the solutions of the equation system, where p and n are both primes. If the number of the variables is not too large, it is effective to construct all the rotation symmetric functions with n variables.