Analysis of Extended Algebraic Immunity of Boolean Functions

Algebraic immunity (AI) is a new cryptographic criterion proposed against algebraic attacks. Extended algebraic immunity (EAI) extends the concept of algebraic immunity, whose point is that a Boolean function f may be replaced by another Boolean function fc called the algebraic complement of f In this paper, we investigate EAI of Boolean functions. Firstly, we present a sufficient and necessary condition to judge AI of a Boolean function equals to its EAI. Secondly, we prove that two classes of Boolean functions with maximum AI also have optimal EAI. Finally, we analyze that the structure of the annihilators of Boolean functions with the algebraic complement.