On the (Fast) Algebraic Immunity of Boolean Power Functions

Abstract The (fast) algebraic immunity, including (standard) algebraic immunity and the resistance against fast algebraic attacks, has been considered as an important cryptographic property for Boolean functions used in stream ciphers. This paper is on the determination of the (fast) algebraic immunity of a special class of Boolean functions, called Boolean power functions. An n-variable Boolean power function f can be represented as a monomial trace function over finite field F2n, f(x) = Trn1 (λxk), where λ ∈ F2n and k is the coset leader of cyclotomic coset Ck modulo 2 n − 1. To determine the (fast) algebraic immunity of Boolean power functions one may need the arithmetic in F2n, which may be not computationally efficient compared with the operations over F2. We prove that if λ = αk and α is a primitive element of F2n, or k is co-prime to 2n − 1, then the (fast) algebraic immunity of Boolean power function Trn1 (λx k) is the same as that of Trn1 (x k). This may help us determine the immunity of some Boolean power functions more efficiently. We show that Niho functions satisfy the co-prime condition, and verify that a number of odd variables Kasami functions also satisfy the co-prime condition