Notion of Algebraic Immunity and Its evaluation Related to Fast Algebraic Attacks
It has been noted recently that algebraic (annihilator) immu- nity alone does not provide sucient resistance against algebraic attacks. In this regard, given a Boolean function f, just checking the minimum degree annihilators of f,1 + f is not enough and one should check the relationships of the form fg = h, and a function f, even if it has very good algebraic immunity, is not necessarily good against fast algebraic attack, if degree of g becomes very low when degree of h is equal to or little greater than the algebraic immunity of f. In this paper we theo- retically study the two currently known constructions having maximum possible algebraic immunity from this viewpoint. To the end, we also ex- perimentally study some cryptographically significant functions having good algebraic immunity.