Almost perfect algebraic immune functions with good nonlinearity

In this paper, it is proven that a family of 2k-variable Boolean functions, including the function recently constructed by Tang et al. [IEEE TIT 59(1): 653-664, 2013], are almost perfect algebraic immune for any integer k ≥ 3. More exactly, they achieve optimal algebraic immunity and almost perfect immunity to fast algebraic attacks. The functions of such family are balanced and have optimal algebraic degree. A lower bound on their nonlinearity is obtained based on the work of Tang et al., which is better than that of Carlet-Feng function. It is also checked for 3 ≤ k ≤ 9 that the exact nonlinearity of such functions is very good, which is slightly smaller than that of Carlet-Feng function, and some functions of this family even have a slightly larger nonlinearity than Tang et al.'s function. To sum up, among the known functions with provable good immunity against fast algebraic attacks, the functions of this family make a trade-off between the exact value and the lower bound of nonlinearity.