Construction Of Annihilators And Boolean Functions With Maximum Algebraic Immunity

The key of algebraic attacks on stream cipher based on Linear Feedback Shift Register (LFSR)is finding the annihilators with low algebraic degree of Boolean functions.Boolean functions used in cryptography should have good algebraic immunity in order to resist algebraic attack.It becomes very significant to analyze the algebraic immunity of Boolean functions and to construct Boolean functions with maximum algebraic immunity(MAI).We research the algebraic immunity of Boolean functions from these two points.The main results are as follows:A method of finding low degree annihilators of a Boolean function is proposed.By analyzing the relationship between the algebraic degree and characteristic matrix of a Boolean function,the relationship between the algebraic immunity and characteristic matrix of a Boolean function is obtained.That is,if the algebraic immunity of n variables Boolean function f is d, there exists at least one Boolean function with degree d,whose characteristic matrix is the sub-matrix of the characteristic matrix of f or 1+f.From this,two algorithms to find low degree annihilators of a Boolean function are present:complete searching and stochastic searching.The complete one can not only get all the low degree annihilators of a Boolean function,but also get the algebraic immunity of the function.The stochastic one can get one low degree annihilator quickly.The construction of Boolean functions with MAI is introduced.According to a necessary and sufficient condition on Boolean function having MAI,a construction of even number variables Boolean functions with MAI is given.It will get at least 2.2^C_nn/2(n even)n variables Boolean functions with MAI from one n variables Boolean function with MAI,in which at least 2·C_2M^M(M=1/2C_n^n/2are balanced.It is also analyzed how to construct balanced Boolean functions with MAI and higher algebraic degree,a lower bound of the number of these functions is shown.The relationship between the nonlinearities of the constructed function and the given function is obtained.Furthermore,it is also researched how to construct all the Boolean function with MAI.The construction of Boolean functions with MAI is converted to finding the bases of a vector space from a certain set of the space.Forn≥3,both constructions of all the odd and even number variables Boolean functions with MAI are present respectively.