Annihilators and Algebraic Immunity of Symmetric Boolean Functions

摘要

In this paper, we deal with the algebraic immunity of the symmetric Boolean functions. The algebraic immunity is a property which measures the resistance against the algebraic attacks on symmetric ciphers. It is well known that the algebraic immunity of the symmetric Boolean functions is completely determined by a narrow class of annihilators with low degree which is denoted by G(n, n/2). We study and determine the weight support of part of these functions. Basing on this, we obtain some relations between the algebraic immunity of a symmetric Boolean function and its simplified value vector. For applications, we put forward an upper bound on the number of the symmetric Boolean functions with algebraic immunity at least d and prove that the algebraic immunity of the symmetric palindromic functions is not high.