The Study Of The Boolean Functions With The Maximum Algebraic Immunity

Boolean Function in cryptography is one of the important functions. Especially in the stream cipher system design andanalysis, it is on more dominant position. One important reason is that the properties of Boolean function decide the security of cryptography to a certain extent.The emergence of algebraic attack requires that Boolean Function should satisfy new condition to be safe. It makes the algebraic immunity of Boolean function become a new problem. This thesis introduces the basic knowledge of Boolean Function firstly. In particular, it describes the relation between algebraic immunity and annihilators, the relation between algebraic immunity and nonlinearity. Then it sums up the several common methods of constructing the Boolean functions with maximum algebraic immunity. On this basis, we analyze the algebraic degree of the Boolean Function with maximum algebraic immunity. Finally, it proposes a new method to construct the (2t+l)-variable Boolean Functions with maximum algebraic immunity.The section 3 .4 of this paper analyzes the algebraic degree of the Boolean Functions with maximum algebraic degree constructed in section 3.3 and gets the relation between the function f and the constructed function g. Compared them, we find that the fewer points are exchanged and the higher algebraic degree is increased under certain condition. In addition, the new method proposed in this paper, is using the properties of W(Fn). We find out some certain linearly independent groups of the vectors which function value are 1 and weight are odd. This will construct some new (2t+1)-variable Boolean functions with maximum algebraic immunity. At the same time, it also gets a sufficient condition of the (2t+1)-variable Boolean function which can't achieve the maximum algebraic immunity.