Algebraic Immunity And Nonlinearity Of Boolean Functions

Boolean functions play very important roles in the design and analysis of block ciphers, stream ciphers and Hash functions. Algebraic immunity, nonlinearity and correlational immunity are important cryptographic properties of Boolean functions. This thesis firstly investigates the properties, the constructions and the count of the Boolean functions with maximum algebraic immunity, then shows a method to construct resilient functions with very high nonlinearity, and at last studies the properties of the absolute value distribution of the Walsh spectrum of a Boolean function. The main contents and fruits of this thesis are outlined as follows:(1) A new method to construct the Boolean functions with maximum algebraic immunity is presented. Based on it, a lower bound on the count of such functions is given, which is the first determined result about this count.(2) It is proved that for any odd positive integer n, there are only two n-variable symmetric Boolean functions with maximum algebraic immunity, which solves the open problem presented by A. Braeken, et.al.(3) For an even integer n, constructions and several necessary conditions of the n-variable symmetric Boolean functions with maximum algebraic immunity are given, then the weight supports of such functions are also investigated.(4) Some properties of a 2~m-variable symmetric Boolean function with maximum algebraic immunity are shown, including its value vector, algebraic normal form, algebraic degree, weight, etc.(5) The problem of solving the minimum distance between Bent and resilient functions is studied. It is converted to two problems. One is to construct a matrix satisfying some conditions.The other is the existence of some Bent functions with special form. Further, a lower bound of the minimum distance between Bent and 1-resilient functions is presented.(6) The absolute value distribution of the Walsh spectrum of a Boolean function is studied and is shown that it isn't changed under affine transformations. Then a necessary condition for a set to be the absolute value distribution of the Walsh spectrum of a Boolean function is presented. At last, the absolute value distributions of the Walsh spectrum of some Boolean functions are computed.