Constructing Boolean functions in odd number of variables with maximum algebraic immunity

The algebraic immunity of cryptographic Boolean functions with odd number of variables is studied in this paper. We prove that minor modifications of functions achieving maximum algebraic immunity yield functions which are bound to have maximum or almost maximum algebraic immunity. Based on this, a new efficient algorithm to produce functions of guaranteed maximum algebraic immunity is developed. Moreover, it is shown that known constructions of functions with maximum algebraic immunity may also be generalized by using the same concepts.