Improving the high order nonlinearity lower bound for Boolean functions with given algebraic immunity

Algebraic immunity is a recently introduced cryptographic parameter for Boolean functions used in stream ciphers. If pAI(f)pAI(f) and pAI(f⊕1)pAI(f⊕1) are the minimum degree of all annihilators of ff and f⊕1f⊕1 respectively, the algebraic immunity AI(f)AI(f) is defined as the minimum of the two values. Several relations between the new parameter and old ones, like the degree, the rr-th order nonlinearity and the weight of the Boolean function, have been proposed over the last few years.In this paper, we improve the existing lower bounds of the rr-th order nonlinearity of a Boolean function ff with given algebraic immunity. More precisely, we introduce the notion of complementary algebraic immunity  AI¯(f) defined as the maximum of pAI(f)pAI(f) and pAI(f⊕1)pAI(f⊕1). The value of AI¯(f) can be computed as part of the calculation of AI(f)AI(f), with no extra computational cost. We show that by taking advantage of all the available information from the computation of AI(f)AI(f), that is both AI(f)AI(f) and AI¯(f), the bound is tighter than all known lower bounds, where only the algebraic immunity AI(f)AI(f) is used.