Cryptographic Properties And Construction Of Boolean Functions

The present Ph.D. dissertation is mainly concerned with the cryptographic properties of Boolean functions. We construct Boolean functions with high algebraic immunity and correlation immune Boolean functions. And we also consider other properties, such as balancedness, algebraic degrees and nonlinearities, of the constructed Boolean functions in this thesis.Boolean functions play a very important role in many cryptosystems. The security of such a cryptosystem mainly depends on the cryptographic properties of the Boolean function it uses. We take advantage of some knowledge of algebra and combinatorics to construct Boolean functions with cryptographic significance. Several classes of Boolean functions with maximum algebraic immunity are constructed. In particular, all the sym-metric Boolean functions with maximum algebraic immunity on even number of variables are determined. We also consider the constructions of symmetric nonpalindromic cor-relation immune Boolean functions and study the algebraic immunity of the symmetric correlation immune Boolean functions.More precisely, the contents of this thesis are organized as follows:Chapter 1 is an introductive chapter. It includes not only the history and current research states in this research area as well as our main results, but also some basics on Boolean functions, our methods, and some basic tools we use. We hope this chapter can provide a full view for the readers.Chapter 2 is concerned with the construction of Boolean functions with maximum algebraic immunity. We generalize the method of constructing the majority functions to construct a large class of Boolean functions with maximum algebraic immunity. We also consider the enumeration and the algebraic degrees of those Boolean functions.Chapter 3 deals with the construction of rotation symmetric Boolean functions with maximum algebraic immunity. We convert the problem of the basic construction of odd-variable rotation symmetric functions with maximum algebraic immunity to a problem of determining the parity of a sum of binomial coefficients and another problem of finding nonsingular matrices over the binary field. As a consequence, we obtain several construc-tions of rotation symmetric Boolean functions with maximum algebraic immunity.Chapter 4 constructs all the symmetric Boolean functions with maximum algebraic immunity on even number of variables and studies their degrees and nonlinearities. The main method is to find the low degree annihilators who play a pivotal role, of symmetric Boolean functions, and study their simplified value vectors. Moreover, we study the sym-metric Boolean functions with high algebraic immunity by using of a similar technique, and concentrate on studying those with submaximum algebraic immunity. As a conse-quence, we obtain some important necessary conditions for symmetric functions to achieve high algebraic immunity.Chapter 5 is mainly concerned with the symmetric correlation immune Boolean func-tions. We construct symmetric nonpalindromic correlation immune Boolean functions for n= 6r,6r+1,6r+2 and 6r+3 respectively and prove that the algebraic immunity of the symmetric palindromic Boolean functions is not high.