Algebraic attacks are efficient if one can express the cipher as a system of multivariate algebraic equations whose solution gives the secret key. The complexity of the attack depends on the degree of these equations. For any n-variable Boolean function, it is always possible to find a Boolean function g ≠ 0 with degree at most such that f*g has degree at most . For being resistant against algebraic attack, the function f used in a stream cipher should not have low degree multiples g ≠ 0, for which the degree of f*g falls much below .

Recently a new theorem has been introduced which gives a theoretical upper bound on the degree of the product of two monomial trace functions. This bound is much lower than the general bound on algebraic immunity. The impact of the theorem is that a bound on the algebraic immunity of any Boolean power function can be obtained directly from the formula regardless of the value of n and it also provides the low degree multiple of the function.

We present here the investigation of the trace representation of the annihilators of the functions with Kasami and Niho exponents. Our goal is to determine an abstract formula - if it is possible - for the annihilators from which one can immediately gain the algebraic immunity of the Boolean power functions.