Since 2008, three different classes of Boolean functions with optimal algebraic immunity have been proposed by Carlet and Feng [2], Wang et al.[8] and Chen et al.[3]. We call them C-F functions, W-P-K-X functions and C-T-Q functions for short. In this paper, we propose three affine equivalent classes of Boolean functions containing C-F functions, W-P-K-X functions and C-T-Q functions as a subclass, respectively. Based on the affine equivalence relation, we construct more classes of Boolean functions with optimal algebraic immunity. Moreover, we deduce a new lower bound on the nonlinearity of C-F functions, which is better than all the known ones.

Based on Tu-Deng's conjecture and the Tu-Deng function, in 2010, X. Tang et al. proposed a class of Boolean functions in even variables with optimal algebraic degree, very high nonlinearity and optimal algebraic immunity. In this corresponding, we consider the concatenation of Tang's function and another Boolean function, and study its cryptographic properties. With this idea, we propose a class of 1-resilient Boolean functions in odd variables with optimal algebraic degree, good nonlinearity and suboptimal algebraic immunity based on Tu-Deng's conjecture.

In this note, we go further on the “basis exchange” idea presented in [2] by using Mobious inversion. We show that the matrix S1(f)S0(f)-1 has a nice form when f is chosen to be the majority function, where S1(f) is the matrix with row vectors υk(α) for all α ∈ 1f and S0(f)=S1(f ⊕ 1). And an exact counting for Boolean functions with maximum algebraic immunity by exchanging one point in on-set with one point in off-set of the majority function is given. Furthermore, we present a necessary condition according to weight distribution for Boolean functions to achieve algebraic immunity not less than a given number.

In this paper, we explicitly construct a large class of symmetric Boolean functions on 2k variables with algebraic immunity not less than d, where integer k is given arbitrarily and d is a given suffix of k in binary representation. If let d = k, our constructed functions achieve the maximum algebraic immunity. Remarkably, 2⌊ log2k ⌋ + 2 symmetric Boolean functions on 2k variables with maximum algebraic immunity are constructed, which are much more than the previous constructions. Based on our construction, a lower bound of symmetric Boolean functions with algebraic immunity not less than d is derived, which is 2⌊ log2d ⌋ + 2(k-d+1). As far as we know, this is the first lower bound of this kind.

We clarify a relation between the XL algorithm and known Grobner basis algorithms. The XL algorithm was proposed to be a more efficient algorithm to solve a system of algebraic equations under a special condition, without calculating a whole Grobner basis. But in our result, it is shown that to solve a system of algebraic equations with a special condition under which the XL algorithm works is equivalent to calculate the reduced Grobner basis of the ideal associated with the system. Moreover we show that the XL algorithm is a Grobner basis algorithm which can be represented as a redundant variant of a known Grobner basis algorithm F4.