Upper Bounds on Algebraic Immunity of Boolean Power Functions (Extended Abstract)

Algebraic attacks have received a lot of attention in studying security of symmetric ciphers. The function used in a symmetric cipher should have high algebraic immunity (AI) to resist algebraic attacks. In this paper we are interested in finding AI of Boolean power functions. We give an upper bound on the AI of any Boolean power function and a formula to find its corresponding low degree multiples. We prove that the upper bound on the AI for Boolean power functions with Inverse, Kasami and Niho exponents are ⌊ √ n ⌋ + ⌈ n ⌊ √ n ⌋ ⌉ − 2, ⌊ √ n ⌋ + ⌈ n ⌊ √ n ⌋ ⌉ and ⌊ √ n ⌋ + ⌈ n ⌊ √ n⌋ ⌉ respectively. We also generalize this idea to Boolean polynomial functions. All existing algorithms to determine AI and corresponding low degree multiples become too complex if the function has more than 25 variables. In our approach no algorithm is required. The AI and low degree multiples can be obtained directly from the given formula.