A class of nonlinear boolean functions with optimal algebraic immunity on even number of variables

In this paper, a class of 2k-variable Boolean functions is proposed, with the support of two disjoint parts described by successive powers of primitive elements. We prove that our functions possess maximum algebraic degree of 2k-1, and optimal algebraic immunity k on the basis of certain combinatorial facts. We also give a proof on the lower bound for Nonlinearity. Numerical experiments suggest that our functions have very satisfying actual value of Nonlinearity, and our functions are almost perfect algebraic immune (PAI) function when k is odd, but very close to almost PAI function when k is even.