Construction Of Several Classes Of Cryptographically Significant Boolean Functions

To resist the known attacks on each cryptosystem, the Boolean functions used in stream ciphers should simultaneously satisfy various cryptographic criteria as:balancedness, high (fast) algebraic immunity, large nonlinearity, high algebraic degree, good correlation proper-ties, and so on. In this thesis, we concentrate on the construction of Boolean functions with good cryptographic properties.Firstly, the linear relationships of the column vectors in the generator matrix G(k, n) of the kth order Reed-Muller code RM(k, n) are explored, where k=[n/2]- 1, n is an integer. It is known that the study of the algebraic immunity of a Boolean function over F2n can be completed by the study of the ranks of the submatrices of generator matrix G(k, n). As an application of the linear relationships, we construct two classes of Boolean functions with optimal algebraic immunity, and provide simpler and direct proofs for three known construc-tions.Secondly, based on the linear relationships of the column vectors in the generator matrix G(k, n) of RM(k, n), we construct two classes of balanced n-variable Boolean functions with optimal algebraic immunity by modifying the outputs of majority function, whose nonlinear-ities are also explored. Further, the resistance of these functions to fast algebraic attacks are checked for small values of n.Next, by the use of a result about integer compositions in number theory, two classes of rotation symmetric Boolean functions with optimal algebraic immunity are constructed, which have higher nonlinearity than those of the known rotation symmetric Boolean functions with optimal algebraic immunity. Further, almost all of these functions have optimal algebraic degree.Fourthly, after the study of Krawtchouk polynomials, we put forward an efficient method to construct correlation immune symmetric Boolean functions based on the modification of two classes symmetric Boolean functions with high order correlation immunity. At the same time, we propose several classes of second order or third order correlation immune symmetric Boolean functions by finding roots of quadratic or cubic equations.Finally, for n= 2m?2, we construct a large class of n-variable rotation symmetric bent functions by modifying the outputs of a quadratic rotation symmetric bent function. Then, the algebraic normal forms of these rotation symmetric bent functions are explored. As a result, we give a method of constructing n-variable rotation symmetric bent functions with any possible algebraic degree i,2?i?m, (i=2ifm=1), in a very simple way.